A-LevelComputer ScienceProgramming9618/32 · Oct/Nov 2021 · Q1013 Marks
State three essential features of recursion.
- (a)State three essential features of recursion.[3]
- (b)Explain the reasons why a stack is a suitable Abstract Data Type (ADT) to implement recursion.[3]
- (c)Identify two ADTs other than a stack.[2]
- (d)The function StackFull () checks whether a stack is full. The function uses the variable TopOfStack to represent the pointer to the most recent position used on the stack, and the variable Max to represent the maximum size of the stack. Assume TopOfStack and Max are global variables. FUNCTION StackFull() RETURNS BOOLEAN IF TopOfStack = Max THEN RETURN TRUE ELSE RETURN FALSE ENDIF ENDFUNCTION An algorithm AddInteger is required to add a new integer data element to a stack. The stack is implemented as an array ArrayStack. The function AddInteger() calls StackFull() and returns an appropriate message. Complete the pseudocode for the function AddInteger(). FUNCTION AddInteger(NewInteger : INTEGER) RETURNS STRING[5]
Mark scheme
Marking points from the official mark scheme (Oct/Nov 2021). The mark or mark type is shown in brackets.
- [1] Must have a base case/stopping condition
- [1] Must have a general case
- [1] ... which calls itself (recursively) // Defined in terms of itself
- [1] ... which changes its state and moves towards the base case
- [1] Unwinding can occur once the base case is reached.
- [1] A stack is a LIFO data structure
- [1] Each recursive call is pushed onto the stack
- [1] ... and is then popped as the function ends
- [1] Enables backtracking/unwinding
- [1] to maintain the required order.
- [1] Linked List
- [1] Queue
- [1] Binary Tree
- [1] Checking if stack is full / empty using IF ... THEN ... (ELSE) ... ENDIF
- [1] correctly using StackFull() function
- [1] RETURN suitable message if stack is full
- [1] RETURN message if space available on stack
- [1] Incrementing TopOfStack pointer if space available
- [1] Assigning new data using correct NewInteger variable
- [1] to correct the array element in ArrayStack [] array.
Write your answer and get it marked
On Oracle Prep you can write or photograph your own answer and have it marked by AI against this mark scheme, with feedback on what you missed.
Sign up free →