IB Questionbank

User interface language: English | Español

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

Question

Describe one difference between stack and queue data structures.

[2]

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]

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]

Outline one disadvantage of solving problems recursively.

[2]

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;

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

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.

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;

Examiners report

Well answered question.

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.

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

[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