A-LevelComputer ScienceData types and structures9618/23 · May/June 2025 · Q211 Marks
A programmer uses a number of Abstract Data Types (ADT) in the programs that she is developing. (a) A stack using memory locations 400 to 409 is used in one program. The diagram represents the current state of the stack. A variable TopOfStack pointer indicates the last value added to the stack. [Figure showing a stack with memory locations 400-409, values 'B', 'D', 'X', 'P' at 400-403, and TopOfStack pointing to 403 ('P')].
- (a)(i)Complete the answer column in the following table: Answer the memory location of the value that has been on the stack for the longest time the number of consecutive push operations that will result in the TopOfStack variable containing 409[2]
- (a)(ii)The diagram shows the current state of the stack. [Figure showing a stack with memory locations 400-409, values 'D', 'R', 'S', 'B', 'K', 'F', 'C', 'A' at 400-407, and TopOfStack pointing to 407 ('A')]. The following sequence of operations are performed: PUSH 'T' POP POP PUSH 'Z' PUSH 'X' POP PUSH 'Y' Complete the following diagram to show the state of the stack after the operations have been performed. [Figure showing a blank stack with memory locations 400-409].[3]
- (b)(i)In a different program, the programmer decides to implement a linked list using an array of records. The array is represented in the diagram. A pointer value of -1 indicates the end of the linked list. Complete the pointer field to produce a linked list that is in alphabetical order. Index Data Pointer 0 "Neptune" 1 "Jupiter" 2 "Saturn" 3 "Earth" 4 "Mercury" 5 "Uranus"[3]
- (b)(ii)The variable StartPointer contains the index of the first item in the linked list. State the value of the variable StartPointer[1]
- (c)A third program is also being created to manage a queue. Describe two features of a queue. Feature one .............................................................................................................................................................................................. Feature two ..............................................................................................................................................................................................[2]
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 (May/June 2025). The mark or mark type is shown in brackets.
- [2] MP1 400
- MP2 6
- [3] Stack Memory location Value 409 408 'Y' <-- TopOfStack 407 'Z' 406 'C' 405 'F' 404 'K' 403 'B' 402 'S' 401 'R' 400 'D'
- MP1 TopOfStack pointing to 'Y' and value 'Y' in location 408
- MP2 Values 'C' and 'Z' in 406 and 407
- MP3 Values 'D' to 'F' unchanged in 400 to 405 and 409 is empty
- [3] Index Data Pointer 0 "Neptune" 2 MP3 1 "Jupiter" 4 2 "Saturn" 5 3 "Earth" 1 MP1 4 "Mercury" 0 5 "Uranus" -1 MP2
- MP1 Earth pointer 1
- MP2 Uranus pointer -1
- MP3 Other four correct pointers
- [1] 3
- [2] MP1 First value added to queue is the first value removed // FIFO // LILO
- MP2 Two pointers needed to indicate the start and end of the queue
- MP3 May behave as a circular queue
- MP4 Manipulated using enqueue()/dequeue() operations // by description
- Max 2
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 →