Paper 1 Data Structures Answers

These answers correspond to Paper 1 Data Structures Drills.

Answer 1: Stack Operations

Trace:

Operation	stack from bottom to top	top
start	empty	-1
PUSH 18	18	0
PUSH 7	18, 7	1
PUSH 25	18, 7, 25	2
POP	18, 7	1
PUSH 12	18, 7, 12	2

Final stack:

index: 0   1   2   3   4
data:  18  7   12  -   -
top = 2

Mark points:

• pushes place items in last-in position;
• pop removes 25;
• 12 is pushed after 7;
• final top is 2;
• final stack contents are 18, 7, 12.

Common weak answer:

• removing 18 on the pop operation. A stack is last-in-first-out, so 25 is removed.

Answer 2: Linear Queue Operations

Trace:

Operation	array contents	front	rear	size
start	[-, -, -, -, -]	0	-1	0
ENQUEUE "A"	[A, -, -, -, -]	0	0	1
ENQUEUE "B"	[A, B, -, -, -]	0	1	2
DEQUEUE	[-, B, -, -, -]	1	1	1
ENQUEUE "C"	[-, B, C, -, -]	1	2	2
ENQUEUE "D"	[-, B, C, D, -]	1	3	3

Final state:

array = [-, B, C, D, -]
front = 1
rear = 3
size = 3

Mark points:

• enqueues add at the rear;
• dequeue removes A from the front;
• front moves to index 1;
• rear ends at index 3;
• remaining queue contents are B, C, D.

Common weak answer:

• shifting all items left after dequeue. This question uses front/rear pointers, so shifting is not needed.

Answer 3: Circular Queue

1. The next enqueue uses index 2.
2. The rear moves from index 1 to (1 + 1) MOD 5 = 2. A circular queue treats the array as wrapping around, so earlier array positions can be reused after front has moved past them.

Mark points:

• correct next index 2;
• explains modulo or wrap-around movement;
• explains that freed positions can be reused.

Common weak answer:

• saying the queue is full because index 4 is occupied. The queue has size 4 and capacity 5, so one slot remains.

Answer 4: Linked List Diagram

One valid description:

head -> [14 | next] -> [22 | next] -> [31 | NULL]

Mark points:

• head points to the first node;
• nodes contain values 14, 22, and 31 in order;
• each node has a next pointer to the following node;
• the final next pointer is NULL.

Common weak answer:

• drawing the values in order but omitting pointer direction or the final NULL.

Answer 5: Free Space List

1. The free space list keeps track of unused node positions in the array so that new linked-list nodes can be allocated efficiently.
2. When a new node is allocated, the first free node is removed from the free space list and used for the new data.

Mark points:

• identifies that unused/free nodes are tracked;
• states that allocation removes a node from the free list.

Common weak answer:

• saying the free space list stores deleted data values. It stores available node positions, not useful list data.

Answer 6: BST Insertion

Final tree:

        40
      /    \
    25      60
   /  \    /  \
 15   30  50   70

Reasoning:

• 40 becomes the root.
• 25 is less than 40, so it goes left.
• 60 is greater than 40, so it goes right.
• 15 is less than 40 and less than 25, so it is left child of 25.
• 30 is less than 40 but greater than 25, so it is right child of 25.
• 50 is greater than 40 but less than 60, so it is left child of 60.
• 70 is greater than 40 and greater than 60, so it is right child of 60.

Mark points:

• correct root 40;
• correct left subtree under 25;
• correct right subtree under 60;
• correct placement of 15 and 30;
• correct placement of 50 and 70.

Common weak answer:

• sorting the values into a list rather than preserving the BST insertion structure.

Answer 7: Tree Traversal

Preorder, root-left-right:

A, B, D, E, C, F

Inorder, left-root-right:

D, B, E, A, C, F

Postorder, left-right-root:

D, E, B, F, C, A

Mark points:

• 2 marks for correct preorder;
• 2 marks for correct inorder;
• 2 marks for correct postorder.

Common weak answer:

• using BST sorted-order assumptions. This is a binary tree, not necessarily a binary search tree.

Answer 8: BST Search

Search for 50 in the BST from Question 6:

40 -> 60 -> 50

Reasoning:

• 50 > 40, so move right to 60.
• 50 < 60, so move left to 50.
• 50 is found.

Mark points:

• starts at root 40;
• moves right to 60;
• moves left to 50;
• states that the target is found.

Common weak answer:

• visiting every node in the tree. BST search follows comparisons and does not need to scan all nodes.

Answer 9: Static vs Dynamic Allocation

Two paired comparison points:

• Static allocation reserves space for 1000 records before use, even when fewer than 100 are stored; dynamic allocation can allocate records only as they are needed.
• Static allocation is simpler because positions are fixed, but it may waste memory; dynamic allocation is more flexible, but it needs pointer/free-space management.

Mark points:

• compares both static and dynamic allocation in each point;
• links the comparison to the scenario’s uncertain record count;
• mentions wasted reserved space for static allocation;
• mentions flexibility and management overhead for dynamic allocation.

Common weak answer:

• describing only dynamic allocation without making a paired comparison with static allocation.

Answer 10: Structure Choice

1. Undoing the most recent editing command: stack, because the most recent command should be undone first.
2. Serving print jobs in arrival order: queue, because the first job to arrive should be processed first.
3. Searching a changing set of unique numeric IDs with smaller values left and larger values right: binary search tree, because it stores values according to ordering comparisons.

Mark points:

• stack linked to last-in-first-out;
• queue linked to first-in-first-out;
• BST linked to ordered left/right placement.

Common weak answer:

• choosing a stack for print jobs. That would process the most recent job first, not the earliest job.