Paper 2 Data Structures Answers

These answers correspond to Paper 2 Data Structures Drills.

Verification note: the model snippets in this file were executed locally as a combined Python script on 2026-07-08.

Answer 1: Stack Class

class Stack:
    def __init__(self):
        self.items = []
 
    def push(self, value):
        self.items.append(value)
 
    def pop(self):
        if len(self.items) == 0:
            return None
        return self.items.pop()
 
    def display(self):
        return self.items[:]
 
 
s = Stack()
s.push("red")
s.push("blue")
print(s.pop())
s.push("green")
print(s.display())

Expected output:

blue
['red', 'green']

Mark points:

• defines a Stack class;
• initialises internal storage;
• implements push;
• implements last-in-first-out pop;
• handles empty pop with None;
• returns a displayable stack state;
• produces the required output.

Common weak answer:

• using pop(0), which removes the oldest item and behaves like a queue.

Answer 2: Queue Class

class Queue:
    def __init__(self):
        self.items = []
 
    def enqueue(self, value):
        self.items.append(value)
 
    def dequeue(self):
        if len(self.items) == 0:
            return None
        return self.items.pop(0)
 
    def display(self):
        return self.items[:]
 
 
q = Queue()
q.enqueue("job1")
q.enqueue("job2")
print(q.dequeue())
q.enqueue("job3")
print(q.display())

Expected output:

job1
['job2', 'job3']

Mark points:

• defines a Queue class;
• initialises internal storage;
• implements enqueue at the rear;
• implements first-in-first-out dequeue;
• handles empty dequeue with None;
• returns a displayable queue state;
• produces the required output.

Common weak answer:

• using normal pop() for dequeue, which removes the most recent item instead of the earliest item.

Answer 3: Circular Queue

class CircularQueue:
    def __init__(self, capacity):
        self.items = [None] * capacity
        self.front = 0
        self.rear = -1
        self.size = 0
        self.capacity = capacity
 
    def enqueue(self, value):
        if self.size == self.capacity:
            return False
        self.rear = (self.rear + 1) % self.capacity
        self.items[self.rear] = value
        self.size = self.size + 1
        return True
 
    def display_array(self):
        return self.items[:]
 
 
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())

Expected output:

True
True
True
True
False
['A', 'B', 'C', 'D']

Mark points:

• stores fixed capacity;
• keeps front, rear, and size;
• checks full condition before inserting;
• updates rear using modulo arithmetic;
• inserts at the wrapped rear position;
• returns False for a full queue;
• produces the required output.

Common weak answer:

• incrementing rear without modulo, which fails when wrap-around is needed.

Answer 4: Linked Node

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
 
 
first = Node("cat")
second = Node("dog")
third = Node("eel")
first.next = second
second.next = third
 
print(first.data)
print(first.next.data)
print(first.next.next.data)

Expected output:

cat
dog
eel

Mark points:

• defines a Node class;
• stores data;
• stores next;
• creates three nodes;
• links first to second and second to third;
• follows links to print values in order.

Common weak answer:

• storing the values in a Python list only, without node objects and next links.

Answer 5: Linked Traversal

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
 
 
def to_list(head):
    values = []
    current = head
    while current is not None:
        values.append(current.data)
        current = current.next
    return values
 
 
head = Node(4)
head.next = Node(9)
head.next.next = Node(12)
print(to_list(head))

Expected output:

[4, 9, 12]

Mark points:

• starts from head;
• uses a loop that continues until None;
• appends each node’s data;
• moves to current.next;
• returns the collected values;
• produces the required output.

Common weak answer:

• forgetting current = current.next, causing an infinite loop.

Answer 6: BST Insert

class BSTNode:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
 
 
def insert(root, value):
    if root is None:
        return BSTNode(value)
    if value < root.data:
        root.left = insert(root.left, value)
    elif value > root.data:
        root.right = insert(root.right, value)
    return root
 
 
values = [40, 25, 60, 15, 30]
root = None
for value in values:
    root = insert(root, value)
 
print(root.data)
print(root.left.data)
print(root.right.data)

Expected output:

40
25
60

Mark points:

• defines a BST node with data, left, and right;
• creates a new node when the current root is None;
• inserts smaller values to the left;
• inserts larger values to the right;
• preserves existing child links by assigning recursive return values;
• returns the root;
• produces the required output.

Common weak answer:

• creating a new root for every inserted value, losing the existing tree.

Answer 7: BST Search

class BSTNode:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
 
 
def insert(root, value):
    if root is None:
        return BSTNode(value)
    if value < root.data:
        root.left = insert(root.left, value)
    elif value > root.data:
        root.right = insert(root.right, value)
    return root
 
 
def bst_search(root, target):
    current = root
    while current is not None:
        if current.data == target:
            return True
        if target < current.data:
            current = current.left
        else:
            current = current.right
    return False
 
 
root = None
for value in [40, 25, 60, 15, 30]:
    root = insert(root, value)
 
print(bst_search(root, 30))
print(bst_search(root, 99))

Expected output:

True
False

Mark points:

• starts at the root;
• compares target with current node;
• moves left for smaller target;
• moves right for larger target;
• returns True when found;
• returns False after reaching None;
• produces both required outputs.

Common weak answer:

• searching both subtrees every time, which ignores the BST ordering advantage.

Answer 8: Traversal Function

class BSTNode:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
 
 
def insert(root, value):
    if root is None:
        return BSTNode(value)
    if value < root.data:
        root.left = insert(root.left, value)
    elif value > root.data:
        root.right = insert(root.right, value)
    return root
 
 
def inorder(root):
    if root is None:
        return []
    return inorder(root.left) + [root.data] + inorder(root.right)
 
 
root = None
for value in [40, 25, 60, 15, 30]:
    root = insert(root, value)
 
print(inorder(root))

Expected output:

[15, 25, 30, 40, 60]

Mark points:

• handles an empty subtree;
• visits left subtree first;
• visits current node after the left subtree;
• visits right subtree last;
• returns a list of values;
• produces the sorted inorder output for this BST.

Common weak answer:

• using preorder or postorder while calling it inorder.

Answer 9: Stack Use Case

def reverse_words(words):
    stack = []
    for word in words:
        stack.append(word)
 
    reversed_words = []
    while len(stack) > 0:
        reversed_words.append(stack.pop())
 
    return reversed_words
 
 
print(reverse_words(["first", "second", "third"]))

Expected output:

['third', 'second', 'first']

Mark points:

• pushes all words onto a stack;
• pops words from the stack;
• uses last-in-first-out behaviour;
• appends popped words to a result list;
• returns the reversed list;
• produces the required output.

Common weak answer:

• using queue behaviour, which would keep the words in the original order.

Answer 10: Queue Simulation

def process_jobs(jobs):
    queue = []
    for job in jobs:
        queue.append(job)
 
    processed = []
    while len(queue) > 0:
        processed.append(queue.pop(0))
 
    return processed
 
 
print(process_jobs(["print", "scan", "email"]))

Expected output:

['print', 'scan', 'email']

Mark points:

• enqueues all jobs in arrival order;
• removes jobs from the front;
• uses first-in-first-out behaviour;
• records each processed job;
• returns the processed jobs;
• produces the required output.

Common weak answer:

• using stack pop(), which would process "email" before "print".