| Date | May 2021 | Marks available | 2 | Reference code | 21M.1.HL.TZ0.16 |
| Level | HL | Paper | 1 | Time zone | no time zone |
| Command term | Outline | Question number | 16 | Adapted from | N/A |
Question
A network is set up with shared printers so that when a user wishes to print, print jobs are sent to a queue until the printer is available.
The factorial of the positive integer n, which is written n!, is the product of all the positive integers less than or equal to n. A stack may be used to perform a factorial calculation as shown by the algorithm:
//stack for factorial(NUM)
//creates a stack of (NUM - 1) elements
//when NUM = 6
NUM = 6
loop while NUM > 1
stack.push(NUM)
NUM = NUM – 1
end loop
PRODUCT = 1
loop while not stack.isEmpty()
NUM = stack.pop()
PRODUCT = PRODUCT * NUM
end loop
output PRODUCT
Outline why a queue is the appropriate data structure to manage print jobs.
Draw a diagram to show how a print queue may be implemented using a linked list.
Explain why a stack would not be appropriate as a data structure for managing print jobs.
Copy and complete the trace table for the algorithm shown for NUM = 6.
Explain how a stack may be used in the implementation of a recursive function.
Markscheme
Award [2 max]
Print jobs are to be completed in the order received;
Queue is appropriate because print jobs are added/enqueued at the back/rear and dequeued/removed from the front / because queue is a FIFO data structure;
Award [3 max]
Correct use of pointers and null pointer in the last node;
External pointer to the beginning of the list (head);
External pointer to the end of the list (tail);
Each node consists of at least 2 parts/fields: data (print jobs) and pointer;
Award [3 max]
Print jobs would not be managed in an orderly manner;
Because stack is LIFO data structure / elements are added/pushed and removed/popped at only one end;
And each time another one is added it takes precedence over those that are already in the data structure;
Award [3 max]
NUM column correct;
PRODUCT column correct;
OUTPUT column correct;
Note: The trace table may be differently presented.
Award [4 max]
A recursive function calls itself during its execution;
First call (all local variables, data, return addresses, etc.) is pushed onto stack;
Second/subsequent recursive calls are pushed on to the stack (added above previous call(s));
When the terminating condition is met/ execution of recursive function ends;
The function calls pop from the stack;
In the reverse order to which they were pushed/LIFO;
Examiners report
Part (a) and (b) were well answered questions, although most marks could be obtained from general knowledge.
Part (a) and (b) were well answered questions, although most marks could be obtained from general knowledge.
To gain credit for the diagram, the students had to clearly show the components of a node in the list, and the internal and external pointers.
Candidates were generally able to produce a trace table (with appropriate column headings given in the question paper) and sufficient trace detail to score good marks for this question.
Some candidates failed to achieve full marks as result of incomplete and vague explanations. A number of candidates wrote too much on a data structure stack and on recursive functions, rather than writing answers to explain how a stack may be used in the implementation of a recursive function, as required in the question.
