A-LevelComputer ScienceData types and structures9618/22 · Oct/Nov 2022 · Q313 Marks

3 A stack is used in a program to store string data which needs to be accessed in several modules.

(a)A stack is an example of an Abstract Data Type (ADT). Identify one other example of an ADT and describe its main features. Example Features[3]
(b)Explain how the stack can be implemented using an array.[5]
(c)A second stack is used in the program. The diagram below shows the initial state of this stack. Value X is at the top of the stack and was the last item added. Upper-case letters are used to represent different data values. Stack operations are performed in three groups as follows: Group 1: PUSH D PUSH E Group 2: POP POP POP Group 3: PUSH A PUSH B POP PUSH C Complete the diagram to show the state of the stack after each group of operations has been performed. Include the current stack pointer (SP) after each group. Memory Initial After After After location state Group 1 Group 2 Group 3 957 956 955 954 953 X ←SP 952 Y 951 Z 950 P[5]

This question uses a diagram from the original paper, which isn't shown here. Open the full paper from the past papers archive to see it.

Mark scheme

Marking points from the official mark scheme (Oct/Nov 2022). The mark or mark type is shown in brackets.

[3] (a) One mark for name, Max two for features (Max 3 in total) Name: Queue Features: 1 Each queue element contains one data item 2 A Pointer to the front / start of the queue 3 A Pointer to the back / end of the queue 4 Data is added at back / end and removed from front / start // works on a FIFO basis 5 May be circular ALTERNATIVE: Name: Linked List Features: 1 Each node contains data and a pointer to the next node 2 A Pointer to the start of the list 3 Last node in the list has a null pointer 4 Data may be added / removed by manipulating pointers (not moving data) 5 Nodes are traversed in a specific sequence 6 Unused nodes are stored on a free list // a free-list pointer to the Free List
[5] (b) One mark per point (Max 5): 1 Declare a (1D) array of data type STRING 2 The number of elements in that array corresponds to the size of the required stack 3 Declare an integer / variable for StackPointer 4. Declare an integer / variable for the size of the stack // for the max value of StackPointer 5 Use the StackPointer as an index to the array 6 Pointers and variables initialised to indicate empty stack 7 Store each item on the stack as one array element / Each stack item maps to one array element 8 Attempt to describe Push and Pop operations 9 Push and Pop routines need to check for full or empty conditions
[5] (c) One mark for each: 1 Data 'After Group 1' (as shown, including blank cells) 2 Data 'After Group 2' (as shown, including blank cells) 3 Data 'After Group 3' (as shown, including blank cells) 4 SP 'After Group 1' pointing to location 955 5 Final two SPs pointing to locations 952 and 954