Singapore H2 Computing Wiki

Paper 2 Implementing Algorithms Drills

3 min read

Paper 2 Implementing Algorithms Drills

These are original Paper 2-style practice questions. They use exact function/class names, test calls, file contents, and output evidence.

Detailed answers and model code are in Paper 2 Implementing Algorithms Answers.

Revise the topic hub first:

Questions

Write a function linear_search(values, target) that returns the index of target, or -1 if absent. Test it with the calls below. [5]

print(linear_search([14, 3, 27, 9], 27))
print(linear_search([14, 3, 27, 9], 5))

Question 2: Implement Insertion Sort

Write a function insertion_sort(values) that returns a new sorted list in ascending order. It must not change the original list. Test it with the calls below. [8]

data = [8, 4, 6, 2]
print(insertion_sort(data))
print(data)

Question 3: Implement Fixed Stack

Implement a fixed-capacity class FixedStack with methods push(value) and pop().

  • push should return False if the stack is full and True otherwise.
  • pop should return None if the stack is empty.

Test it with the calls below. [10]

s = FixedStack(2)
print(s.push("A"))
print(s.push("B"))
print(s.push("C"))
print(s.pop())
print(s.pop())
print(s.pop())

Question 4: Implement Circular Queue

Implement a fixed-capacity class CircularQueue with methods enqueue(value), dequeue(), and display_array().

  • enqueue should return False if the queue is full.
  • dequeue should return None if the queue is empty.
  • Use modulo arithmetic for wrap-around.

Test it with the calls below. [12]

q = CircularQueue(3)
print(q.enqueue("A"))
print(q.enqueue("B"))
print(q.enqueue("C"))
print(q.dequeue())
print(q.enqueue("D"))
print(q.display_array())
print(q.dequeue())

Question 5: Implement Linked Insert

Define a Node class and a function insert_head(head, value) that inserts a new node at the head of a linked list and returns the new head. Insert 30, then 20, then 10, and print the list values. [8]

Using the linked list 10 -> 20 -> 30, write a function linked_search(head, target) that returns True if target is found and False otherwise. Test it with 20 and 99. [7]

Question 7: Implement BST Insert

Define a BSTNode class and an insert(root, value) function. Insert [40, 25, 60, 15, 30], then print the root value and the values of its left and right children. [10]

Question 8: Implement BST Traversal

Using the BST from Question 7, write a function inorder(root) that returns the inorder traversal list. [7]

Assume a text file serial_records.txt contains:

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

Write a function serial_search(filename, key) that returns the first matching line without the newline, or "NOT FOUND" if absent. Test it with key C01. [7]

Question 10: Sequential File Early Stop

Assume a text file sequential_records.txt is ordered by key:

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

Write a function sequential_search(filename, key) that:

  • returns the matching line without the newline if found;
  • returns "NOT FOUND STOPPED AT <current key>" if the current key has passed the target;
  • returns "NOT FOUND" if the end of file is reached.

Test it with keys 105 and 107. [8]

Review Checklist

After attempting these questions, check whether you can:

  • implement search and sort functions with clear return values;
  • preserve input lists when asked;
  • implement overflow and underflow handling;
  • update linked-list head pointers safely;
  • implement BST insert/traversal;
  • read serial and sequential files with correct stopping conditions.

Graph View

Backlinks