Singapore H2 Computing Wiki

Paper 2 Data Structures Drills

3 min read

Paper 2 Data Structures Drills

These are original Paper 2-style practice questions. They use exact class/function names and test calls so your answers can be checked exactly.

Detailed answers and model code are in Paper 2 Data Structures Answers.

Revise the topic hub first:

Questions

Question 1: Stack Class

Implement a class Stack with methods push(value), pop(), and display(). pop() should return None if the stack is empty. Test it with the calls below. [10]

s = Stack()
s.push("red")
s.push("blue")
print(s.pop())
s.push("green")
print(s.display())

Question 2: Queue Class

Implement a class Queue with methods enqueue(value), dequeue(), and display(). dequeue() should return None if the queue is empty. Test it with the calls below. [10]

q = Queue()
q.enqueue("job1")
q.enqueue("job2")
print(q.dequeue())
q.enqueue("job3")
print(q.display())

Question 3: Circular Queue

Implement a fixed-size class CircularQueue with capacity passed to the constructor. It should have enqueue(value) and display_array() methods. enqueue should return False if the queue is full and True otherwise.

Test it with the calls below. [9]

cq = CircularQueue(4)
print(cq.enqueue("A"))
print(cq.enqueue("B"))
print(cq.enqueue("C"))
print(cq.enqueue("D"))
print(cq.enqueue("E"))
print(cq.display_array())

Question 4: Linked Node

Define a class Node with attributes data and next. Create a linked list containing "cat" -> "dog" -> "eel" and print the data values by following the links manually. [6]

Question 5: Linked Traversal

Using the Node class, write a function to_list(head) that traverses a linked list and returns the data values in a Python list. Test it on the linked list 4 -> 9 -> 12. [7]

Question 6: BST Insert

Define a class BSTNode and a function insert(root, value) that inserts values into a binary search tree and returns the root. Insert the values below and print the root value, root’s left value, and root’s right value. [10]

values = [40, 25, 60, 15, 30]

Write a function bst_search(root, target) that returns True if target is found in a BST and False otherwise. Test it using the tree built from [40, 25, 60, 15, 30]. [7]

print(bst_search(root, 30))
print(bst_search(root, 99))

Question 8: Traversal Function

Write a function inorder(root) that returns a list of values from a BST in inorder traversal. Test it using the tree built from [40, 25, 60, 15, 30]. [7]

print(inorder(root))

Question 9: Stack Use Case

Write a function reverse_words(words) that uses a stack to reverse a list of strings. Test it with the call below. [6]

print(reverse_words(["first", "second", "third"]))

Question 10: Queue Simulation

Write a function process_jobs(jobs) that uses a queue to process jobs in first-in-first-out order and returns the processed jobs. Test it with the call below. [6]

print(process_jobs(["print", "scan", "email"]))

Review Checklist

After attempting these questions, check whether you can:

  • implement classes with clear attributes and methods;
  • handle empty stack/queue cases;
  • use wrap-around in circular queues;
  • follow linked-list next pointers;
  • implement BST insert, search, and inorder traversal;
  • show output evidence for each required test.

Graph View

Backlinks