Sets and hash tables (HL) – IB Computer Science exam questions with mark scheme

1StandardHL only4 marks

Consider the Python program below.

words = "the cat and the dog and the bird".split()
freq = {}
for w in words:
    freq[w] = freq.get(w, 0) + 1
print(freq)
print(max(freq, key=freq.get))

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

(b) Outline the purpose of freq.get(w, 0). [1]

First line of output is the dictionary with the, cat, and, dog, bird in order of first appearance(1)
Counts are correct: the 3, cat 1, and 2, dog 1, bird 1 → {'the': 3, 'cat': 1, 'and': 2, 'dog': 1, 'bird': 1} (ignore quote style and spacing)(1)
Second line of output is the (the key with the highest value)(1)
(b) Returns the current count for w, or 0 if w is not yet a key, so a new word starts at 0 and no KeyError is raised (accept either idea)(1)
Answer: {'the': 3, 'cat': 1, 'and': 2, 'dog': 1, 'bird': 1} then the
Examiner tip: Dictionaries keep insertion order in Python 3.7+, so the printed order follows first appearance.

2CoreHL only4 marks

A school stores club memberships as sets.

chess = {Ali, Bea, Cai, Dan}
robotics = {Bea, Dan, Eve}

(a) State the result of chess ∪ robotics (union). [1]

(b) State the result of chess ∩ robotics (intersection). [1]

(d) Outline why a set, rather than a list, is a suitable ADT for storing the members of a club. [1]

(a) {Ali, Bea, Cai, Dan, Eve} (any order; each name exactly once; reject if Bea or Dan appears twice)(1)
(b) {Bea, Dan} (any order)(1)
(c) {Ali, Cai} (any order; reject {Eve}, which is robotics − chess)(1)
(d) A set cannot contain duplicate elements, so a student cannot be recorded as a member twice / order of members does not matter / fast membership test (accept any one valid reason linked to clubs)(1)
Answer: (a) {Ali, Bea, Cai, Dan, Eve} (b) {Bea, Dan} (c) {Ali, Cai} (d) no duplicates, so no student is stored twice
Examiner tip: Difference is not symmetric: A − B keeps what is in A only, so reversing the sets gives a different answer.

3CoreHL only4 marks

A hash table is used to store student records, using the student ID as the key.

(a) Define the term hash function. [1]

(b) Define the term collision in the context of a hash table. [1]

(d) Explain one effect on performance of allowing the load factor to become high. [1]

(a) A function that maps / converts a key to an index (address) in the table (accept: calculates the storage location from the key; reject 'encrypts the key')(1)
(b) When two (or more) different keys produce the same hash value / index(1)
(c) 15 ÷ 20 = 0.75 (accept 75% or 3/4)(1)
(d) More collisions occur, so more probes / longer chains are needed, so search / insertion becomes slower (tends towards O(n)) (must link collisions to slower access)(1)
Answer: (a) maps a key to a table index (b) different keys hash to the same index (c) 0.75 (d) more collisions, so slower lookups
Examiner tip: Load factor is items ÷ slots, not slots ÷ items; 20/15 = 1.33 earns nothing.

Stuck on Sets and hash tables (HL)?

Get it sorted in a free 30-minute session

We work through your weakest questions on this topic on Zoom. I reply the same day.

Free 30-min session on this topic Send me 5 questions a day

4StandardHL only5 marks

A hash table has 11 slots (indices 0 to 10). The hash function is h(k) = k mod 11 and collisions are resolved by linear probing (try the next index, wrapping from 10 to 0). The diagram shows the table after four keys have been inserted.

(a) Calculate h(58). [1]

(b) State the index at which 58 is stored, and the number of slots examined to store it. [2]

(d) Identify the problem with linear probing that this table illustrates. [1]

(a) 58 mod 11 = 3(1)
(b) Index 7(1)
5 slots examined (indices 3, 4, 5, 6, 7) (accept 4 collisions before an empty slot is found)(1)
(c) Index 8 (allow follow-through from their (b): the next free index after 58)(1)
(d) (Primary) clustering: keys form a long run of occupied consecutive slots, so new keys that hash into the run need many probes (accept description without the term)(1)
Answer: (a) 3 (b) index 7, 5 slots examined (c) 8 (d) primary clustering
Examiner tip: Count the home slot as well as the extra probes: 58 examines indices 3, 4, 5, 6 and 7, which is 5 slots.

5StandardHL only4 marks

A hash table with 7 slots uses the hash function h(k) = k mod 7. Collisions are resolved by separate chaining: each slot holds a linked list of the keys that hash to it. The diagram shows the table after seven keys have been inserted.

(a) State the index of the list to which the key 52 would be added. [1]

(b) Before 52 is added, a search is made for the key 38, which is not in the table. State the number of key comparisons needed to decide that 38 is not present. [1]

(d) Four of the seven slots are empty, yet searches for some keys are slow. Explain why. [1]

(a) 3 (52 mod 7 = 3)(1)
(b) 5 (38 mod 7 = 3, so all five keys in list 3 are compared)(1)
(c) 7 ÷ 7 = 1 (accept 1.0)(1)
(d) The keys are not evenly distributed: most hash to index 3 (they leave remainder 3 when divided by 7), so one long chain must be searched linearly while other slots are empty(1)
Answer: (a) 3 (b) 5 (c) 1.0 (d) uneven distribution: five keys share index 3
Examiner tip: With chaining, load factor is an average; it says nothing about how evenly the keys are spread, which is what really decides search time.

6HardHL only7 marks

The Python program below uses sets to record the subject tags on a revision website.

tags = {"maths", "physics", "chemistry", "biology"}
needed = {"physics", "maths"}
print(needed <= tags)
print(tags >= {"maths", "art"})
tags.add("physics")
print(len(tags))
tags.discard("art")
tags.remove("biology")
print(sorted(tags))
print(sorted(needed - tags))

(a) State the five lines of output. [4]

(b) Construct a function is_subset(a, b) that returns True if every element of set a is also in set b, and False otherwise. You must not use the operators <=, >= or the methods issubset/issuperset. [3]

(a) True then False (both required)(1)
4 (adding an existing element does not change the set)(1)
['chemistry', 'maths', 'physics'] (accept without brackets/quotes; must be in this order since sorted)(1)
[] (accept 'empty list'; allow follow-through if their previous line contains both maths and physics)(1)
(b) Iterates over every element of a (e.g. for item in a:)(1)
Tests membership of each element in b and returns False as soon as one is not found (e.g. if item not in b: return False)(1)
Returns True only after the loop has finished / all elements checked (reject return True inside the loop; accept equivalent pseudocode or Java)(1)
Answer: (a) True / False / 4 / ['chemistry', 'maths', 'physics'] / [] (b) for item in a: if item not in b: return False; after loop return True
Examiner tip: discard silently ignores a missing element but remove raises a KeyError; and a common bug in (b) is putting return True inside the loop.

7HardHL only6 marks

A word game stores valid words in a hash table with 13 slots. The hash function adds the ASCII codes of the characters and takes the result mod 13.

ASCII codes: A = 65, C = 67, D = 68, G = 71, O = 79, T = 84

(a) Calculate the hash value of "CAT", showing your working. [2]

(b) Calculate the hash value of "DOG". [1]

(d) Suggest how the hash function could be improved to reduce collisions of this kind, and explain why it works. [2]

(a) 67 + 65 + 84 = 216(1)
216 mod 13 = 8(1)
(b) 10 (68 + 79 + 71 = 218; 218 mod 13 = 10) (reject 218 with no mod taken)(1)
(c) Addition is commutative / the sum ignores the order of characters, so anagrams (same letters in a different order) always give the same total and so the same index(1)
(d) Weight each character by its position, e.g. multiply the running total by a constant (such as 31 or 37) before adding the next code / use a polynomial hash (accept: multiply each code by its position)(1)
So the same letters in different positions contribute different amounts, giving different hash values for anagrams (accept: e.g. with h = h×31 + code, CAT → 4 and ACT → 3 mod 13)(1)
Answer: (a) 216 mod 13 = 8 (b) 218 mod 13 = 10 (c) the sum ignores order, so anagrams collide (d) weight characters by position, e.g. polynomial hash
Examiner tip: Show the total before taking mod; an answer of 8 with no working can lose the method mark.

8HardHL only6 marks

A hash table has 8 slots and uses h(k) = k mod size with linear probing. The diagram shows the table after the keys 3, 11, 19, 6, 14 and 22 were inserted in that order.

The table is resized to 16 slots whenever an insertion would make the load factor greater than 0.75.

(a) Calculate the current load factor. [1]

(b) The key 30 is to be inserted next. Show that this causes the table to be resized. [1]

(c) The six keys are re-inserted into the new 16-slot table in their original order, using h(k) = k mod 16 and linear probing. State the new index of key 11 and of key 22. [2]

(d) Explain why each key must be re-hashed rather than copied to the same index in the larger table. [2]

(a) 6 ÷ 8 = 0.75(1)
(b) After inserting 30 there would be 7 keys: 7 ÷ 8 = 0.875, which is greater than 0.75(1)
(c) 11 at index 11(1)
22 at index 7 (22 mod 16 = 6, which is occupied by 6, so the next slot)(1)
(d) The index depends on the table size / mod 16 gives different indices from mod 8(1)
A search uses the new hash function, so a key left at its old index (e.g. 11 at index 4) would be looked for in the wrong place and not found / it also lets clustered keys spread out(1)
Answer: (a) 0.75 (b) 7/8 = 0.875 > 0.75 (c) 11 → index 11, 22 → index 7 (d) index depends on the size; old positions would not be found by searches
Examiner tip: In (c) the hash must use the new size; using mod 8 again just rebuilds the old clusters.

9StandardHL only5 marks

A shop's stock system uses the Java code below.

HashMap<String, Integer> stock = new HashMap<>();
stock.put("pen", 12);
stock.put("ink", 5);
stock.put("pen", 7);
HashSet<String> sold = new HashSet<>();
sold.add("ink");
sold.add("pad");
sold.add("ink");
System.out.println(stock.size() + " " + stock.get("pen"));
System.out.println(stock.containsKey("pad") + " " + stock.getOrDefault("pad", 0));
System.out.println(sold.size());

(a) State the three lines of output. [3]

(b) The shop has 50 000 product codes. Compare the efficiency of checking whether a code is present using a HashSet with checking using an ArrayList. [2]

(a) 2 7 (putting an existing key overwrites its value)(1)
false 0(1)
2 (the duplicate "ink" is not added again)(1)
(b) HashSet: the code is hashed to go (almost) directly to its location, so contains is O(1) on average / constant time regardless of size(1)
ArrayList: contains is a linear search comparing elements one by one, so O(n): up to 50 000 comparisons (accept: HashSet much faster for large n; reject answers that only say 'HashSet is faster' with no reason)(1)
Answer: (a) 2 7 / false 0 / 2 (b) HashSet O(1) average via hashing; ArrayList O(n) linear search
Examiner tip: put with an existing key replaces the value rather than adding a second entry, so the size stays 2.

10StretchHL only6 marks

A hash table has 10 slots, uses h(k) = k mod 10 and resolves collisions with linear probing. The diagram shows the table after inserting 12, 22, 32 and 15 in that order.

The key 22 is then deleted by simply setting slot 3 back to empty.

(a) Explain why a subsequent search for 32 would incorrectly report that 32 is not in the table. [3]

(b) Describe how a "tombstone" (deleted marker) can be used to avoid this problem, for both searching and inserting. [2]

(c) Using the tombstone method instead, 22 is deleted and then 42 is inserted. State the index at which 42 is stored. [1]

(a) 32 hashes to index 2 (32 mod 10 = 2), which holds 12, so the search moves on to index 3(1)
Index 3 is now empty(1)
Linear-probing search stops at the first empty slot (assuming the key would have been placed there), so it never reaches index 4 where 32 is actually stored(1)
(b) When deleting, the slot is marked as deleted (tombstone) instead of empty; a search treats a tombstone as occupied and continues probing past it(1)
An insertion may reuse a tombstone slot (after checking the key is not already further along the probe sequence)(1)
(c) Index 3 (42 mod 10 = 2 is occupied by 12; index 3 holds the tombstone and is reused; accept index 6 only if their (b) explicitly states tombstones are never reused)(1)
Answer: (a) search starts at 2, finds 12, moves to 3 which is empty and stops, never reaching 32 at 4 (b) mark the slot as deleted; searches skip over it, inserts may reuse it (c) 3
Examiner tip: Deletion is the weak point of open addressing: an empty slot means 'stop searching', so it cannot be used to mean 'removed'.

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