Data structures (stacks, queues, graphs, trees, hash tables, dictionaries, vectors) – A-level Computer Science exam questions with mark scheme

1Core4 marks

(a) Explain the difference between a static data structure and a dynamic data structure. [2]

(b) A stack is described as a LIFO data structure and a queue as a FIFO data structure. Explain what is meant by each of these terms. [2]

(a) A static data structure has a fixed size/maximum number of items set when it is created (memory allocated at compile time / in advance)(1)
(a) A dynamic data structure can grow and shrink in size during execution (memory allocated/freed at run time from the heap)(1)
(b) LIFO (Last In First Out): the most recently added item in a stack is the first one removed(1)
(b) FIFO (First In First Out): the item that has been in the queue longest/was added first is the first one removed(1)
Answer: (a) Static: fixed size decided in advance; dynamic: size changes at run time. (b) LIFO: last item added is first removed; FIFO: first item added is first removed.
Examiner tip: Expanding the acronym alone earns nothing – you must say which item is removed next.

2Standard5 marks

A circular queue is implemented using an array Q with six elements, indexed 0 to 5, and the variables front, rear and size. Initially the queue is empty with front = 0, rear = -1 and size = 0.

When an item is added, rear is updated using rear ← (rear + 1) MOD 6; when an item is removed, front ← (front + 1) MOD 6.

The following operations are carried out in order:

Enqueue(A), Enqueue(B), Enqueue(C), Enqueue(D), Dequeue, Dequeue, Enqueue(E), Enqueue(F), Enqueue(G)

(a) State the values of front, rear and size after these operations. [3]

(b) State the item stored at index 0 of the array. [1]

(c) Explain why a circular queue is a more efficient use of memory than a linear queue implemented in a fixed-size array. [1]

(a) front = 2(1)
(a) rear = 0(1)
(a) size = 5(1)
(b) G(1)
(c) In a linear queue the spaces freed at the front by dequeuing cannot be reused (without shuffling every item forward), whereas the circular queue wraps round to reuse them(1)
Answer: (a) front = 2, rear = 0, size = 5 (b) G (c) Freed positions at the start of the array are reused by wrapping round, with no need to shuffle items.
Examiner tip: The MOD wrap-around is the whole point: after index 5 the next rear is 0, not 6.

3Standard5 marks

A stack is implemented using an array and a top pointer. The array has indices 0 to 4. Initially the stack is empty and the top pointer is −1.

The following operations are carried out in order. Each value removed by POP is output.

PUSH(7), PUSH(3), POP, PUSH(9), PUSH(4), POP, POP, PUSH(2), PUSH(8)

(a) State the values that are output, in order. [2]

(b) State the contents of the stack, from bottom to top, and the value of the top pointer after all of the operations. [2]

(c) Describe the check that the PUSH operation should make before adding an item, and what should happen if the check fails. [1]

(a) 3, 4 (first two outputs correct and in order)(1)
(a) 9 as the third output (all of 3, 4, 9 in order)(1)
(b) Stack (bottom to top) 7, 2, 8(1)
(b) top pointer = 2(1)
(c) Check whether the stack is full (top pointer = 4 / maximum index); if so, do not add the item and report an error/stack overflow(1)
Answer: (a) 3, 4, 9 (b) 7, 2, 8 (bottom to top), top pointer = 2 (c) Check if top = 4 (full); if so report overflow instead of pushing.
Examiner tip: Popped items are not 'deleted' in an array implementation – only the pointer moves – so don't list them as still in the stack.

4Standard5 marks

The diagram shows a weighted, undirected graph.

(a) The graph is to be stored as an adjacency matrix. Complete rows C, D and E of the matrix, using 0 where there is no edge. [2]

	A	B	C	D	E
A	0	4	2	0	0
B	4	0	5	10	0
C
D
E

(b) Explain why an adjacency list might be more suitable than an adjacency matrix for storing a graph with many vertices but few edges. [2]

(a) Row C correct: 2, 5, 0, 0, 3(1)
(a) Rows D and E correct: D = 0, 10, 0, 0, 4; E = 0, 0, 3, 4, 0(1)
(b) A matrix stores an entry for every possible pair of vertices (n² entries), most of which would be empty/0 for a sparse graph, wasting memory(1)
(b) An adjacency list only stores the edges that exist, so it uses less memory (the time to check a specific edge being slower is acceptable)(1)
(c) It contains a cycle (e.g. A–B–C–A); a tree is a connected graph with no cycles(1)
Answer: (a) C: 2 5 0 0 3; D: 0 10 0 0 4; E: 0 0 3 4 0 (b) Sparse graph – matrix wastes memory on n² mostly empty entries; list stores only existing edges. (c) It has a cycle, e.g. A–B–C–A.
Examiner tip: An undirected graph's matrix is symmetric – use that to check your rows.

5Hard6 marks

A hash table has 11 locations, indexed 0 to 10. The hashing function is h(key) = key MOD 11. Collisions are handled by rehashing using linear probing (the next free location is used, wrapping round from 10 to 0).

Index	0	1	2	3	4	5	6	7	8	9	10
Key

(a) Show the contents of the hash table after the keys 23, 45, 70, 13, 81 are inserted in that order. [3]

(b) Explain the steps taken to search the table for the key 92 and state how many occupied locations are examined before the search ends. [2]

(a) 23 at index 1 and 70 at index 4(1)
(a) 45 at index 2 and 13 at index 3(1)
(a) 81 at index 5 (and no other locations used)(1)
(b) Hash 92 to give 4; compare with key at 4 (70), then move on to 5 (81), then reach empty location 6 so the search stops – key not present (allow: search ends at the first empty location)(1)
(b) 2 occupied locations examined(1)
(c) Two (or more) different keys produce the same hash value / are mapped to the same location in the table(1)
Answer: (a) 1: 23, 2: 45, 3: 13, 4: 70, 5: 81 (b) 92 MOD 11 = 4; check 4, then 5, then empty location 6 means not found – 2 occupied locations examined. (c) Two different keys hash to the same location.
Examiner tip: When searching with linear probing, reaching an empty location is what proves the key isn't there – you don't search the whole table.

6Hard5 marks

A binary search tree is stored in an array of records. Each record has a Left pointer, a Data field and a Right pointer. A pointer value of −1 means there is no child. Items are inserted using alphabetical order: an item that comes before a node's data goes to the left of that node and an item that comes after it goes to the right. The items are inserted in the following order, with Mango as the root at index 0 and each later item stored at the next index:

Mango, Cherry, Peach, Apple, Fig, Plum, Banana, Kiwi

(a) Complete the Left and Right pointers in the table. [3]

Index	Left	Data	Right
0		Mango
1		Cherry
2		Peach
3		Apple
4		Fig
5		Plum
6		Banana
7		Kiwi

(b) Describe how the tree would be searched to determine whether Grape is stored in it, stating the items compared. [2]

(a) Index 0 (Mango): Left 1, Right 2(1)
(a) Index 1 (Cherry): Left 3, Right 4; index 2 (Peach): Left −1, Right 5(1)
(a) Index 3 (Apple): Right 6; index 4 (Fig): Right 7; all other pointers −1(1)
(b) Start at root and compare: Grape < Mango so go left; Grape > Cherry so go right; Grape > Fig so go right(1)
(b) Items compared are Mango, Cherry, Fig, Kiwi; Grape < Kiwi and Kiwi's left pointer is −1 so Grape is not in the tree(1)
Answer: (a) 0: L1 R2; 1: L3 R4; 2: L−1 R5; 3: L−1 R6; 4: L−1 R7; 5, 6, 7: L−1 R−1 (b) Compare Mango (left), Cherry (right), Fig (right), Kiwi (left = −1) – not found.
Examiner tip: Every insertion starts again from the root – Banana goes Mango → Cherry → Apple → right of Apple.

7Standard4 marks

The Python program below uses a dictionary.

words = "the cat sat on the mat the end".split()
counts = {}
for w in words:
    counts[w] = counts.get(w, 0) + 1
print(counts["the"], len(counts))

(a) State the output of the program. [2]

(b) Explain why a dictionary is a suitable data structure for counting how many times each word occurs in a very long document, rather than a list of [word, count] pairs. [2]

(a) 3(1)
(a) 6 (output 3 6)(1)
(b) A dictionary stores key–value pairs where the word is the key, so the count for a word can be accessed directly by its key(1)
(b) Dictionaries are implemented using hashing so lookup/update takes (approximately) constant time O(1), whereas a list would need a linear search O(n) for every word(1)
Answer: (a) 3 6 (b) Word is the key, giving direct access to its count; hashing gives O(1) lookup instead of an O(n) linear search per word.
Examiner tip: len() of a dictionary counts distinct keys, not total words – 'the' only counts once.

8Standard5 marks

The vectors u = [3, −1, 2] and v = [1, 4, −2] are defined over ℝ.

(a) Calculate u + v. [1]

(b) Calculate 2u − v. [1]

(d) The vector w = 0.25u + 0.75v. Explain why w is a convex combination of u and v. [1]

(a) [4, 3, 0](1)
(b) [5, −6, 6](1)
(c) u · v = 3×1 + (−1)×4 + 2×(−2) = −5(1)
(c) Negative dot product so the angle between them is obtuse / greater than 90° (FT their dot product)(1)
(d) Both coefficients (0.25 and 0.75) are ≥ 0 and they sum to 1(1)
Answer: (a) [4, 3, 0] (b) [5, −6, 6] (c) −5; angle is obtuse (> 90°) (d) 0.25, 0.75 ≥ 0 and 0.25 + 0.75 = 1.
Examiner tip: For a convex combination you need BOTH conditions: non-negative coefficients and a sum of 1.

Still losing marks on this topic?

Book a free introductory session and we'll find exactly which step is costing you.

Book a free intro