Hash tables, dictionaries and vectors – A-level Computer Science exam questions with mark scheme

1Hard6 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.

2Standard4 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.

3Standard5 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.

Stuck on this topic?

Book a free 30-minute session on WhatsApp and we'll find exactly which step is costing you the marks. Or build a timed paper on it.

Free 30-minute session