Singapore H2 Computing Wiki

Paper 1 Implementing Algorithms Drills

3 min read

Paper 1 Implementing Algorithms Drills

These are original Paper 1-style practice questions. They use concrete implementation states and code fragments so the answers can be checked exactly.

Detailed answers are in Paper 1 Implementing Algorithms Answers.

Revise the topic hub first:

Questions

Question 1: Implementation Preconditions

State one precondition for each search implementation.

  1. Binary search on an array. [1]
  2. Search in a binary search tree. [1]

Question 2: Array Stack Trace

A stack is stored in items[0..3]. It is initially empty and top = -1.

Trace these operations:

PUSH 11
PUSH 6
POP
PUSH 9
PUSH 14

Show the final array contents and final top. [5]

Question 3: Circular Queue Full and Empty Checks

A circular queue has capacity 5, with variables front, rear, and count.

  1. State the condition for the queue to be empty. [1]
  2. State the condition for the queue to be full. [1]
  3. If front = 3, rear = 1, and count = 4, state the next rear index after one enqueue. [1]
  4. Explain why modulo arithmetic is used. [1]

Question 4: Linked Insert at Head

The current linked list is:

head -> [20 | next] -> [35 | NULL]

A new node containing 12 must be inserted at the head.

State the creation/use of the new node and the two pointer updates required, in the correct order. [3]

Question 5: BST Insert Trace

The current BST is:

        45
      /    \
    20      70
   /  \    /
 10   30  60

Insert the value 25. State the comparisons made and where the new node is placed. [5]

A serial file contains these records in this order:

C03,Asha
C01,Ben
C04,Chen
C02,Divya

The program searches for key C02.

State the records inspected and explain when the search stops. [2]

A sequential file is ordered by key:

101,Asha
105,Ben
109,Chen
114,Divya

The program searches for key 107.

State the records inspected and explain why the search can stop early. [3]

Question 8: Implementation Choice

Choose the most suitable implementation for each task and give a reason.

  1. Find a target in a sorted Python list of 1000 IDs. [1]
  2. Store browser pages for a Back button. [1]
  3. Process print jobs in arrival order. [1]

Question 9: Pseudocode Completion

Complete the missing lines in the stack POP pseudocode, and explain why item must be saved before top is decremented. [4]

FUNCTION Pop()
    IF top = -1 THEN
        RETURN "UNDERFLOW"
    ENDIF
    item <- _________
    top <- _________
    RETURN _________
ENDFUNCTION

Question 10: Error Identification

The pseudocode below is intended to insert a new node at the head of a linked list.

newNode.data <- 12
head <- newNode
newNode.next <- head
  1. Identify the pointer error. [2]
  2. State the corrected order of pointer updates. [2]

Review Checklist

After attempting these questions, check whether you can:

  • trace array indexes and pointer variables exactly;
  • use stack, queue, linked-list, and BST invariants;
  • explain serial versus sequential file search;
  • complete pseudocode with correct state updates;
  • recognise empty/full/absent cases before updating implementation state;
  • identify pointer-update order errors.

Graph View

Backlinks