User interface language: English | Español

Date November 2020 Marks available 2 Reference code 20N.1.HL.TZ0.12
Level HL Paper 1 Time zone no time zone
Command term Outline Question number 12 Adapted from N/A

Question

Describe one difference between stack and queue data structures.

[2]
a.

State the purpose of the following queue method:

enqueue()

[1]
b.i.

State the purpose of the following queue method:

dequeue()

[1]
b.ii.

State the purpose of the following queue method:

isEmpty()

[1]
b.iii.

Assume that the queue Q holds the following data:

The reversed queue Q would be:

Construct an algorithm in pseudocode for reversing the queue using a stack data structure.

You may assume that the data in the queue is input and a new empty stack is created.
Only the standard queue and stack operations are allowed.

[5]
c.

Consider the following recursive method:

mystery(N)
if N>0 then
return 3 + mystery(N-3)
else
return 3
end if
end mystery

where N is an integer.

Determine the value of mystery(7). Show all your working.

[3]
d.

Outline one disadvantage of solving problems recursively.

[2]
e.

Markscheme

Award [2 max] 
In a stack, the same end is used to insert and delete the elements;
whilst two different ends are used in the queue to insert and delete the elements;

Stack has only one open end so only one pointer is used to refer to the top of the stack;
but queue has two open ends and two pointers should be used (to refer front and the rear end of the queue);

Queue is a first-in-first-out (FIFO) data structure;
and stack is last-in-first-out (LIFO) data structure;

a.

Award [1 max] 
(enqueue) adds an item to rear/tail of the queue;

b.i.

Award [1 max] 
(dequeue) removes an item from front/head of the queue;

b.ii.

Award [1 max] 
(isEmpty)
checks if the queue is empty or not;
returns TRUE if the queue is empty, FALSE otherwise;

b.iii.

Award [5 max] 
Award [1] for a while loop (through queue);
Award [1] for placing each item removed from the beginning of the queue to the top of the stack;
Award [1] for a while loop (through stack);
Award [1] for adding each element popped from the stack to the end of the queue;
Award [1] for the correct use of stack and queue methods;

Example:

//S is a new/created empty stack
// push all of the elements of Q to stack
while not Q.isEmpty()
X=Q.dequeue()
S.push(X) // OR S.push(Q.dequeue())
end while

//then, pop each element from the stack and add it to Q

while not S.isEmpty()
X=S.pop()
Q.enqueue(X); //OR Q.enqueue(S.pop())
end while
c.

Award [3 max] 

mystery(7)= 3 + mystery(4);
= 3 +3 + mystery(1) ;
= 3 +3 + 3 +mystery(-2)=3+3+3+3=12  ;

NOTE: Award only [1] if the working is not shown and only the final result is given.

d.

Award [2 max]  
More difficult/complicated to code;
if the data structure being processed is not recursive;

It is difficult to find bugs;
particularly while using global variables;

Can use more memory (than iterative solution) when executed;
because every recursive call increases the call stack;

Recursion to a deeper level will be difficult/impossible to implement;
if the call stack space on the system is limited;

Slower execution / using a recursive function takes more time to execute;
as compared to its non- recursive/ iterative counterpart;

e.

Examiners report

Well answered question.

a.

Candidates mostly gave good responses for this question.

b.i.

Candidates mostly gave good responses for this question.

b.ii.

Candidates mostly gave good responses for this question.

b.iii.

A few candidates did not attempt this question. However, those who did generally answered well. A few candidates incorrectly used 'enqueue' operations also for the stack. 

c.

A simple enough recursive algorithm, leading to a high number of correct answers.

d.
[N/A]
e.

Syllabus sections

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

View options