Singapore H2 Computing Wiki

Paper 1 Data Structures Drills

3 min read

Paper 1 Data Structures Drills

These are original Paper 1-style practice questions. They use concrete operation sequences and diagrams described in text so the answers can be checked exactly.

Detailed answers are in Paper 1 Data Structures Answers.

Revise the topic hub first:

Questions

Question 1: Stack Operations

A stack is stored in an array with indexes 0 to 4. The stack is initially empty and top = -1.

Perform these operations in order:

PUSH 18
PUSH 7
PUSH 25
POP
PUSH 12

Show the final stack contents and final value of top. [5]

Question 2: Linear Queue Operations

A linear queue is stored in an array with indexes 0 to 4. It is initially empty, with front = 0, rear = -1, and size = 0.

Perform these operations in order:

ENQUEUE "A"
ENQUEUE "B"
DEQUEUE
ENQUEUE "C"
ENQUEUE "D"

Show the final array contents, front, rear, and size. [5]

Question 3: Circular Queue

The circular queue below has capacity 5.

index:   0   1   2   3   4
data:    P   Q   -   M   N
front = 3, rear = 1, size = 4
  1. State which index will be used by the next enqueue operation. [1]
  2. Explain why a circular queue can use this index even though it is before front in the array. [2]

Question 4: Linked List Diagram

A linked list stores the values 14, 22, and 31 in that order.

Draw or describe the linked list using:

  • a head pointer;
  • one data field and one next pointer in each node;
  • a NULL pointer at the end. [4]

Question 5: Free Space List

An array-based linked-list implementation stores unused nodes in a free space list.

  1. State the purpose of the free space list. [1]
  2. State what happens to the free space list when a new node is allocated. [1]

Question 6: BST Insertion

Insert these values into an empty binary search tree in the order shown:

40, 25, 60, 15, 30, 50, 70

Draw or describe the final tree. [5]

Question 7: Tree Traversal

Use the binary tree below.

        A
      /   \
     B     C
    / \     \
   D   E     F

Give the preorder, inorder, and postorder traversal sequences. [6]

Use the BST from Question 6. Trace a search for 50.

State the nodes visited in order and whether the target is found. [4]

Question 9: Static vs Dynamic Allocation

A program may store up to 1000 customer records, but most runs use fewer than 100 records.

Compare static and dynamic allocation for this situation. Give two paired comparison points. [4]

Question 10: Structure Choice

Choose the most suitable data structure for each task and justify your choice.

  1. Undoing the most recent editing command. [1]
  2. Serving print jobs in arrival order. [1]
  3. Searching a changing set of unique numeric IDs where smaller IDs should be kept to the left of larger IDs. [1]

Review Checklist

After attempting these questions, check whether you can:

  • trace top, front, rear, and size accurately;
  • explain circular wrap-around;
  • draw linked-list pointers and tree structure clearly;
  • apply BST ordering during insertion and search;
  • choose data structures from their access pattern.

Graph View

Backlinks