A2 · Practice questions · Stacks, queues, linked lists and binary trees

Pointers, moved.

Six original Cambridge-style questions on implementing ADTs with arrays, records and pointers.

Original questions All questions on this page are original work, written in the Cambridge AS & A Level style. They are not from past papers. They test the same concepts and skills the syllabus rewards.

Keep these straight

Check, then move.

Insert: check for full (free pointer null / count = size), then take a node and set the pointers.
Delete: check for empty, then reconnect around the item and return the node to the free list.
Circular queue: move pointers with (Pointer + 1) MOD Size and keep a count.
Binary tree: from the root, smaller goes left, otherwise right, until a null pointer.

Write

[6 marks]

Using the record type TreeNode and the global variables in this lesson, write pseudocode for a function FindNode(SearchItem : INTEGER) RETURNS INTEGER that returns the index of the node holding SearchItem, or −1 if it is not in the tree.

Function header and ENDFUNCTION; local Current initialised to RootPointer. ✓
Loop while Current is not the null pointer (−1). ✓
If Tree[Current].Data = SearchItem, return Current (or set a flag and exit the loop). ✓
If SearchItem is less than Tree[Current].Data, Current ← Tree[Current].LeftPointer. ✓
Otherwise Current ← Tree[Current].RightPointer. ✓
Return −1 after the loop when the item is not found. ✓

Trace

[4 marks]

An empty binary search tree uses nodes 0 to 9 in order from the free list. The values 40, 25, 60, 10, 30, 55, 75 are inserted in that order. Draw the tree and give the LeftPointer and RightPointer of nodes 0 and 1.

40 is the root (node 0); 25 (node 1) left of 40; 60 (node 2) right of 40. ✓
10 (node 3) left of 25; 30 (node 4) right of 25; 55 (node 5) left of 60; 75 (node 6) right of 60. ✓
Node 0: LeftPointer 1, RightPointer 2. ✓
Node 1: LeftPointer 3, RightPointer 4. ✓

Write

[5 marks]

A circular queue uses Queue : ARRAY[0:9] OF STRING, FrontPointer, RearPointer and NumberInQueue. Write pseudocode for a procedure Enqueue(NewItem : STRING) that adds an item, or outputs an error message if the queue is full.

Procedure header with STRING parameter and ENDPROCEDURE. ✓
Check NumberInQueue = 10; output an error message if full. ✓
Otherwise RearPointer ← (RearPointer + 1) MOD 10. ✓
Queue[RearPointer] ← NewItem. ✓
NumberInQueue ← NumberInQueue + 1. ✓

Trace

[4 marks]

Using the linked list table in this lesson (StartPointer = 1, FreeListPointer = 2), state every value that changes when (a) DeleteItem("Ava") is run on the original table (b) DeleteItem("Eli") is run on the original table.

(a) Ava is the first node, so StartPointer ← List[1].Pointer = 4. ✓
(a) List[1].Pointer ← 2 and FreeListPointer ← 1. ✓
(b) Previous is Dan (node 6), so List[6].Pointer ← List[3].Pointer = −1. ✓
(b) List[3].Pointer ← 2 and FreeListPointer ← 3. ✓

Explain

[4 marks]

A delivery company wants to store the towns it serves and the roads between them, with the driving time for each road. Identify a suitable ADT, describe its key features and justify the choice.

A graph. ✓
Towns are vertices (nodes); roads are edges (arcs) joining pairs of vertices. ✓
Edges are weighted with the driving time (and may be directed for one-way roads). ✓
Justification: towns can be connected in any pattern, including cycles, which a tree or list cannot represent; algorithms can then find the quickest route. ✓

Explain

[3 marks]

Explain how a queue can be implemented using two stacks.

Enqueue pushes the new item onto the first (input) stack. ✓
Dequeue pops from the second (output) stack. ✓
If the output stack is empty, first pop every item from the input stack and push it onto the output stack, which reverses the order so the oldest item is on top (first in, first out). ✓

Mark this once you have attempted all six and checked your working. It records a Practiced badge on the topic and adds a one-time bonus. Revealing the solutions alone does not count.