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]
a.

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

[3]
b.

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]
c.

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]
d.

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()).

a.

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);

b.

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.

c.

Award [3].

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

d.

Examiners report

[N/A]
a.
[N/A]
b.
[N/A]
c.
[N/A]
d.

Syllabus sections

Topic 5: Abstract data structures » 5.1 Abstract data structures
Show 80 related questions
Topic 5: Abstract data structures

View options