IB Questionbank

User interface language: English | Español

Date	May 2018	Marks available	5	Reference code	18M.1.HL.TZ0.13
Level	HL	Paper	1	Time zone	no time zone
Command term	Construct	Question number	13	Adapted from	N/A

Question

The names of students attending a science fair were recorded in a stack data structure as each one arrived.

The first item stored in the stack was “Sophie”.

Note that “Troy” is currently in position 0 in the stack.

Construct the pseudocode that will search the stack for a specific name, and output its position in the stack. You may assume that all names in the stack are unique.

[5]

Explain the benefits of using a binary search tree, compared to a stack, when searching for a specific item.

[3]

If the tree is populated with the data from the stack, the first item popped off will become the root. For each subsequent item popped from the stack, a recursive procedure is followed until the item is correctly placed in the tree.

Without writing code, describe this recursive procedure.

[4]

By considering only the data visible in the stack shown above, sketch the binary search tree that has been created from the items removed from the stack.

[3]

Markscheme

Award [5 max] as follows:

Example answer 1:

searchName(NAME, STACK)
  DEPTH = 0
  NAMEDEPTH = -1
  while not STACK.isEmpty() do
    X = STACK.pop()
    if X == NAME
      then NAMEDEPTH=DEPTH
    DEPTH = DEPTH + 1
  end while
  if NAMEDEPTH == -1
    then output(NAME + ’not found’)
    else output(NAMEDEPTH)
  endif
end searchName

Award [1] for initialization.
Award [1] for a correct while/until loop.
Award [1] for correct comparison and assignment.
Award [1] for updating and outputting correct position of NAME on the stack(NAMEDEPTH)
Award [1] for use of stack methods (pop() and isEmpty())

Example answer 2:

NAME=input()
CSTK = STACK.copy() // must make a real copy,
//any attempt to make a copy of stack is acceptable
DEPTH = 0
SEARCHING = true
while SEARCHING and not CSTK.isEmpty() do
  if NAME == CSTK.pop()
  then
    SEARCHING = false
  else
    DEPTH = DEPTH + 1
  end if
endwhile
if not SEARCHING
  then output(DEPTH)
  else output NAME + " not found"
end if

Award [1] for initialization.
Award [1] for a correct while/until loop (even if flag is missing).
Award [1] for correct comparison and assignment.
Award [1] for incrementing and outputting correct position of NAME (DEPTH).
Award [1] for use of stack methods pop() and isEmpty()).

Award [3 max].

Example answer 1 (time efficiency):
The data in the binary search tree(BST) is ordered;
Such that as each node is checked for the item, half of the remaining nodes are ignored;
But each element in the stack has to be checked;
Which, for large data sets, may be inefficient compared to the BST;

Example answer 2 (memory efficiency):
Each element on the stack has to be popped off/removed from the stack to be checked for the searched item;
When the item is found the stack will be empty/stack contents will be changed;
When an element in the BST is checked for the item it is not removed from the BST;
So there is no need to create an additional copy of the BST (but a real copy of the stack must be created which for large data sets may be inefficient);

Award [4 max].

Example answer:
The (next) stack item is (placed into a new node and) compared (alphabetically) to the root;
If the root is empty it would be placed here (and this recursive procedure terminates);
Else, depending upon the comparison, it would look to the node to the left or right and the (recursive) procedure calls itself again (with the new root);
If it is lower than the root, then the left child of the root becomes the new root;
If it is higher than the root, then the right child of the root becomes the new root;

Note: Marks should also be awarded for an algorithm constructed in pseudocode.

Award [3].

Award marks as follows:
Clearly a binary tree;
Correct root;
All values correct;

Examiners report

[N/A]

Syllabus sections

Topic 5: Abstract data structures » 5.1 Abstract data structures

Show 80 related questions

17N.1.HL.TZ0.13c:

Show the output produced by the following algorithm.

loop while (NOT FRUITS.isEmpty()) AND (NOT FLOWERS.isEmpty())
  X = FRUITS.pop()
  Y = FLOWERS.pop()
  if X < Y then
    output X
  else
    output Y
  end if
end loop

Hide related questions

Topic 5: Abstract data structures

Question

Markscheme

Examiners report

Syllabus sections

View options