Introduction to Abstract Data Types (ADT) — Paper 3 · A Level Computer Science 9618

4 (a) (i) Explain why Reverse Polish Notation (RPN) is used to carry out the evaluation of expressions. … … … … [2] (ii) Identify, with reasons, a data structure that could be used to evaluate an expression in RPN. … … … … [2] (b) Write the infix expression in RPN. (a – b) * (a + c) / 7 … … [1] (c) Write the RPN expression as an infix expression. a b / 4 * a b + - … … [1] (d) Evaluate the RPN expression: a b + c d / / where a = 17, b = 3, c = 48 and d = 12. Show your working. … … … … [2]

8 marks

Mark scheme: 4(a)(i) One mark for each correct marking point (Max 2) 2 • Reverse Polish Notation provides an unambiguous method of representing an expression • … reading from left to right • …without the need to use brackets • …with no need for rules of precedence / BODMAS 4(a)(ii) One mark for identification of the data structure, 2 One mark for a sensible reason Either: Structure: stack The operands are popped from the stack in the reverse order to how they were pushed Or: Structure: Binary tree A (binary) tree allows both infix and postfix to be evaluated (tree traversal) 4(b) a b - a c + * 7 / 1 4(c) a / b * 4 – (a + b) 1 4(d) 1 mark for correct structure 2 1 mark for correct substitution (a + b) / (c / d) (17 + 3) / (48 / 12)

This question in 9618/31 May/June 2021

4 (a) (i) Explain why Reverse Polish Notation (RPN) is used to carry out the evaluation of expressions. … … … … [2] (ii) Identify, with reasons, a data structure that could be used to evaluate an expression in RPN. … … … … [2] (b) Write the infix expression in RPN. (a – b) * (a + c) / 7 … … [1] (c) Write the RPN expression as an infix expression. a b / 4 * a b + - … … [1] (d) Evaluate the RPN expression: a b + c d / / where a = 17, b = 3, c = 48 and d = 12. Show your working. … … … … [2]

8 marks

Mark scheme: 4(a)(i) One mark for each correct marking point (Max 2) 2 • Reverse Polish Notation provides an unambiguous method of representing an expression • … reading from left to right • …without the need to use brackets • …with no need for rules of precedence / BODMAS 4(a)(ii) One mark for identification of the data structure, 2 One mark for a sensible reason Either: Structure: stack The operands are popped from the stack in the reverse order to how they were pushed Or: Structure: Binary tree A (binary) tree allows both infix and postfix to be evaluated (tree traversal) 4(b) a b - a c + * 7 / 1 4(c) a / b * 4 – (a + b) 1 4(d) 1 mark for correct structure 2 1 mark for correct substitution (a + b) / (c / d) (17 + 3) / (48 / 12)

This question in 9618/32 May/June 2021

4 (a) (i) Explain why Reverse Polish Notation (RPN) is used to carry out the evaluation of expressions. … … … … [2] (ii) Identify, with reasons, a data structure that could be used to evaluate an expression in RPN. … … … … [2] (b) Write the infix expression in RPN. (a – b) * (a + c) / 7 … … [1] (c) Write the RPN expression as an infix expression. a b / 4 * a b + - … … [1] (d) Evaluate the RPN expression: a b + c d / / where a = 17, b = 3, c = 48 and d = 12. Show your working. … … … … [2]

8 marks

Mark scheme: 4(a)(i) One mark for each correct marking point (Max 2) 2 • Reverse Polish Notation provides an unambiguous method of representing an expression • … reading from left to right • …without the need to use brackets • …with no need for rules of precedence / BODMAS 4(a)(ii) One mark for identification of the data structure, 2 One mark for a sensible reason Either: Structure: stack The operands are popped from the stack in the reverse order to how they were pushed Or: Structure: Binary tree A (binary) tree allows both infix and postfix to be evaluated (tree traversal) 4(b) a b - a c + * 7 / 1 4(c) a / b * 4 – (a + b) 1 4(d) 1 mark for correct structure 2 1 mark for correct substitution (a + b) / (c / d) (17 + 3) / (48 / 12)

This question in 9618/33 May/June 2021

10 (a) State three essential features of recursion. 1 … … 2 … … 3 … … [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. 1 … 2 … [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 … … … … … … … … … … … … ENDFUNCTION [5]

13 marks

Mark scheme: 10(a) One mark for each correct marking point (Max 3) 3 • Must have a base case/stopping condition • Must have a general case • … which calls itself (recursively) // Defined in terms of itself • … which changes its state and moves towards the base case Unwinding can occur once the base case is reached. 10(b) One mark for each correct marking point (Max 3) 3 • A stack is a LIFO data structure • Each recursive call is pushed onto the stack • …. and is then popped as the function ends • Enables backtracking/unwinding … to maintain the required order. 10(c) One mark for each marking point (Max 2) 2 • Linked List • Queue Binary Tree 10(d) One mark for each marking point (Max 5) 5 • Checking if stack is full / empty using IF … THEN … (ELSE) … ENDIF • … correctly using StackFull() function • RETURN suitable message if stack is full • RETURN message if space available on stack • Incrementing TopOfStack pointer if space available • Assigning new data using correct NewInteger variable • … to correct the array element in ArrayStack[] array. Example algorithm FUNCTION AddInteger(NewInteger : INTEGER) RETURNS STRING IF StackFull() THEN RETURN "The stack is full" ELSE TopOfStack ← TopOfStack + 1 ArrayStack[TopOfStack] ← NewInteger RETURN "Item added" ENDIF ENDFUNCTION

This question in 9618/31 Oct/Nov 2021

10 (a) State three essential features of recursion. 1 … … 2 … … 3 … … [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. 1 … 2 … [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 … … … … … … … … … … … … ENDFUNCTION [5]

13 marks

Mark scheme: 10(a) One mark for each correct marking point (Max 3) 3 • Must have a base case/stopping condition • Must have a general case • … which calls itself (recursively) // Defined in terms of itself • … which changes its state and moves towards the base case Unwinding can occur once the base case is reached. 10(b) One mark for each correct marking point (Max 3) 3 • A stack is a LIFO data structure • Each recursive call is pushed onto the stack • …. and is then popped as the function ends • Enables backtracking/unwinding … to maintain the required order. 10(c) One mark for each marking point (Max 2) 2 • Linked List • Queue Binary Tree 10(d) One mark for each marking point (Max 5) 5 • Checking if stack is full / empty using IF … THEN … (ELSE) … ENDIF • … correctly using StackFull() function • RETURN suitable message if stack is full • RETURN message if space available on stack • Incrementing TopOfStack pointer if space available • Assigning new data using correct NewInteger variable • … to correct the array element in ArrayStack[] array. Example algorithm FUNCTION AddInteger(NewInteger : INTEGER) RETURNS STRING IF StackFull() THEN RETURN "The stack is full" ELSE TopOfStack ← TopOfStack + 1 ArrayStack[TopOfStack] ← NewInteger RETURN "Item added" ENDIF ENDFUNCTION

This question in 9618/32 Oct/Nov 2021

5 Part of a program’s calculations uses the integer variables j, k, m, n and p. j = 3 k = 2 m = 10 n = (j + k)/(j - k) p = m * (m - j * k) (a) Write the Reverse Polish Notation (RPN) for the expression: (j + k)/(j - k) … [2] (b) (i) Show the changing contents of the stack as the value for p is calculated from its RPN expression: m m j k * - * [4] (ii) Describe the main steps in the evaluation of this RPN expression using a stack. … … … … … … … … [4] (c) State two other uses of a stack. 1 … … 2 … … [2]

12 marks

Mark scheme: 5(a) One mark for each in order jk+jk-/ jk+ jk-/ 5(b)(i) 1 mark per ring Do not allow operators in stacks 2 3 3 6 10 10 10 10 4 10 10 10 10 10 10 40 4 5(b)(ii) Any four from Max 4 Max 3 generic answer only  Working from left to right in the expression  PUSH 10/m onto the stack  PUSH the following numbers (10/m, 3/j, 2/k) onto the stack  When the first operator ,*, is reached  … POP the top two numbers, 2/k and 3/j  … apply the operation  PUSH result back onto stack  Continue to the end of the expression 4 5(c) Any two from  recursion  implementation of ADTs e.g. linked lists  procedure calls  interrupt handling (storing contents of registers etc) 2

This question in 9618/31 May/June 2022

5 Part of a program’s calculations uses the integer variables j, k, m, n and p. j = 3 k = 2 m = 10 n = (j + k)/(j - k) p = m * (m - j * k) (a) Write the Reverse Polish Notation (RPN) for the expression: (j + k)/(j - k) … [2] (b) (i) Show the changing contents of the stack as the value for p is calculated from its RPN expression: m m j k * - * [4] (ii) Describe the main steps in the evaluation of this RPN expression using a stack. … … … … … … … … [4] (c) State two other uses of a stack. 1 … … 2 … … [2]

12 marks

Mark scheme: 5(a) One mark for each in order jk+jk-/ jk+ jk-/ 5(b)(i) 1 mark per ring Do not allow operators in stacks 2 3 3 6 10 10 10 10 4 10 10 10 10 10 10 40 4 5(b)(ii) Any four from Max 4 Max 3 generic answer only  Working from left to right in the expression  PUSH 10/m onto the stack  PUSH the following numbers (10/m, 3/j, 2/k) onto the stack  When the first operator ,*, is reached  … POP the top two numbers, 2/k and 3/j  … apply the operation  PUSH result back onto stack  Continue to the end of the expression 4 5(c) Any two from  recursion  implementation of ADTs e.g. linked lists  procedure calls  interrupt handling (storing contents of registers etc) 2

This question in 9618/33 May/June 2022

5 (a) Write the infix expression in Reverse Polish Notation (RPN). a * b + b - d + 15 … … [1] (b) (i) Write the RPN expression in infix form. a b - c d + * a / … … [1] (ii) Evaluate your infix expression from part (b)(i) when a = 5, b = 10, c = 27 and d = 12. … … [1]

3 marks

Mark scheme: 5(a) a b * b + d - 15 + 1 5(b)(i) (a - b) * (c + d) / a 1 5(b)(ii) –39 1

This question in 9618/31 Oct/Nov 2022

11 A simplified linked list is used to store the names of flowers in alphabetical order. It is implemented using two 1D arrays: • Flower stores the names of the flowers. • NextPointer stores the pointer to the next flower name in the list. HeadPointer indicates the index of the first flower name in the linked list. HeadPointer 6 When the end of the linked list is reached, the next pointer has the value of 0. The following table shows the initial content of the arrays. Index Flower NextPointer 1 Rose 7 2 Marigold 1 3 Foxglove 10 4 Iris 9 5 Daisy 3 6 Dahlia 5 7 Saxifrage 0 8 Lupin 2 9 Lily 8 10 Hydrangea 4 (a) Several flower names have been deleted from the linked list. These are crossed out in the following table. Complete the table to show the new values of HeadPointer and NextPointer to keep the remaining flower names in alphabetical order. HeadPointer Index Flower NextPointer 1 Rose 2 Marigold 3 Foxglove 4 Iris 5 Daisy 6 Dahlia 7 Saxifrage 8 Lupin 9 Lily 10 Hydrangea [3] (b) Complete the pseudocode algorithm so that it achieves the following when applied to the arrays: • The flower name is input. • The linked list is searched, in order, for the flower name. • If the flower name is found, an appropriate message is output to indicate it has been found. • If the flower name is not found, an appropriate message is output to indicate it has not been found. • The algorithm terminates when the next pointer value is 0. Pointer HeadPointer Found 0 OUTPUT "Enter a flower name " IF Flower[Pointer] = FlowerName THEN Found Pointer Pointer 0 ELSE ENDWHILE ELSE [5] (c) Explain how you could improve the simplified linked list structure. … … … … [2]

10 marks

Mark scheme: 11(a) One mark for each point 3 • Correct HeadPointer • Any three correct NextPointer • All six NextPointer correct HeadPointer 5 Index Flower NextPointer 1 Rose 0 2 Marigold 3 Foxglove 4 4 Iris 9 5 Daisy 3 6 Dahlia 7 Saxifrage 8 Lupin 1 9 Lily 8 10 Hydrangea 11(b) One mark for each correct line 5 Pointer  HeadPointer Found  0 OUTPUT "Enter a flower name " INPUT FlowerName WHILE Pointer <> 0 IF Flower[Pointer] = FlowerName THEN Found  Pointer Pointer  0 ELSE Pointer  NextPointer[Pointer] ENDIF ENDWHILE IF Pointer = 0 THEN // IF Found <> 0 THEN OUTPUT Flower[Found], " is found" ELSE OUTPUT "The flower you wanted is not in the list" ENDIF 11(c) One mark for each point (Max 2) 2 • Include a free list pointer • …to reuse the unused space • …as a linked list of free space.

This question in 9618/32 Oct/Nov 2022

5 (a) Write the infix expression in Reverse Polish Notation (RPN). a * b + b - d + 15 … … [1] (b) (i) Write the RPN expression in infix form. a b - c d + * a / … … [1] (ii) Evaluate your infix expression from part (b)(i) when a = 5, b = 10, c = 27 and d = 12. … … [1]

3 marks

Mark scheme: 5(a) a b * b + d - 15 + 1 5(b)(i) (a - b) * (c + d) / a 1 5(b)(ii) –39 1

This question in 9618/33 Oct/Nov 2022

11 Pseudocode is to be written to implement a queue Abstract Data Type (ADT) with items of the string data type. This will be implemented using the information in the table. Identifier Data type Description FrontPointer INTEGER points to the start of the queue RearPointer INTEGER points to the end of the queue Length INTEGER the current size of the queue Queue STRING 1D array to implement the queue A constant, with identifier MaxSize, limits the size of the queue to 60 items. (a) Write the pseudocode to declare MaxSize, FrontPointer, RearPointer, Length and Queue. … … … … … … [3] (b) Complete the following pseudocode for the function Dequeue to remove the front item from the queue. FUNCTION Dequeue RETURNS STRING DECLARE Item : STRING … > 0 THEN Item ← … … IF Length = 0 THEN CALL Initialise // reset the pointers ELSE IF FrontPointer > MaxSize THEN … ← 1 ENDIF ENDIF ELSE OUTPUT "The print queue was empty – error!" Item ← "" ENDIF RETURN Item ENDFUNCTION [4] (c) Explain how a new element can be added to the queue if it is implemented using two stacks. … … … … … … [4]

11 marks

Mark scheme: 11(a) One mark per mark point (Max 3) 3  correctly defined constant  correctly defined array  three correctly defined integers CONSTANT MaxSize = 60 DECLARE Queue : ARRAY[1:60] OF STRING // DECLARE Queue : ARRAY[0:59] OF STRING // DECLARE Queue : ARRAY[1:MaxSize] OF STRING // DECLARE Queue : ARRAY[0:MaxSize - 1] OF STRING DECLARE FrontPointer : INTEGER DECLARE RearPointer : INTEGER DECLARE Length : INTEGER 11(b) One mark for each correctly completed line (Max 4) 4 FUNCTION Dequeue RETURNS STRING DECLARE Item : STRING IF Length > 0 THEN Item  Queue[FrontPointer] FrontPointer  FrontPointer + 1 Length  Length – 1 IF Length = 0 THEN CALL Initialise // procedure to reset the pointers ELSE IF FrontPointer > MaxSize THEN FrontPointer  1 ENDIF ENDIF ELSE OUTPUT "The print queue was empty – error" Item  "" ENDIF RETURN Item ENDFUNCTION 11(c) One mark per mark point (Max 4) 4 MP1 (Two stacks are required) so that the second stack can reverse the order of the first stack. MP2 Stack 1 operates as the queue with the newest elements at the bottom. Stack 2 is empty. MP3 To add an element, pop all the elements from stack 1 and push onto stack 2. MP4 Push the new element onto either stack. MP5 Pop all the elements of stack 2 back onto stack 1.

This question in 9618/31 May/June 2023