4.2.6.1 Hash tables, hashing and collisions Quiz: AQA Computer Science, Unit 2

The 20 questions

1. What is a hash table?

   • A list of values stored in sorted order only, with each value placed by comparing it to the rest
   • A data structure that maps keys to values using a hash function
   • A tree with a single root, where each node holds one key and a value and links to its children
   • A file that stores binary records, with each record's position found by searching the file

2. What is a hash function?

   • A function that always returns a random number, so that each key is placed in a random slot
   • A function that converts a key into a storage index or address
   • A function that deletes a table, removing all of its keys and values from memory when it is called
   • A function that sorts a list into order, using comparisons between neighbouring values in the list

3. What is a collision in a hash table?

   • A key that is deleted from the table
   • A value that is larger than the table
   • Two different keys produce the same hash value
   • A table that has no keys at all

4. What is rehashing in the context of collisions?

   • Converting values to strings, so that each value is stored as text in its slot in the table
   • Deleting all keys from the table, which clears the slots so that the table can start again from empty
   • Sorting the keys into alphabetical order, so that each key is placed beside its neighbours in the table
   • Computing a new location for the key using a different method when the first is occupied

5. A hash function is key MOD 7 and the table has 7 slots (0 to 6). Where is the key 23 stored?

   • Slot 3
   • Slot 5
   • Slot 2
   • Slot 0

6. Using key MOD 7 with 7 slots, the keys 10 and 17 are inserted. Which slot does each go to, and is there a collision?

   • Neither key is stored
   • Both go to slot 3, so there is a collision
   • Both go to slot 0, so there is a collision
   • 10 goes to slot 3 and 17 goes to slot 4, so no collision

7. A hash table of 10 slots uses key MOD 10. Which slot does the key 47 use?

   • 47
   • 0
   • 4
   • 7

8. A hash table has 11 slots and uses key MOD 11. Which key below would hash to slot 0?

   • 13
   • 9
   • 23
   • 22

9. Why do good hash functions aim to spread keys evenly across the table?

   • To store values in a binary file, so the table can be saved to disk without any conversion step
   • To remove the need for keys, since an even spread means that the values can be found without them
   • To make the table a tree, so that each key has a parent and a set of children in the structure
   • To reduce collisions and keep lookups fast

10. Which operation is typically fastest in a hash table with few collisions?

    • Finding the middle value of the table
    • Traversing values in a tree
    • Looking up a value by its key
    • Sorting all values into order

11. What is one common approach to resolve collisions with rehashing?

    • Storing the key in a stack
    • Converting the key to a Boolean
    • Deleting the table whenever a collision happens
    • Probing to the next free slot using a fixed step

12. A hash table uses linear probing with step 1. Key A hashes to slot 4, which is occupied, and slot 5 is free. Where is A stored?

    • Slot 3
    • Slot 4
    • Slot 6, since probing skips the next slot
    • Slot 5

13. A hash table is built to store customer records keyed by customer ID. Which property is most desirable for the hash function?

    • It always sends every ID to slot 0
    • It converts IDs into strings of unequal length
    • It distributes IDs evenly so few records share a slot
    • It sorts the IDs in ascending order

14. What is the relationship between a hash table and a dictionary?

    • They have no relationship at all
    • A dictionary is a stack implemented in an array
    • A hash table is one common way to implement a dictionary
    • A dictionary is always a binary tree

15. A hash table has 8 slots and uses key MOD 8. The keys 5, 13 and 21 are inserted in that order. What happens?

    • Only 5 is stored and the others are lost, since the table can hold only one key in each slot
    • The table cannot store keys divisible by 8, so the insertion of 13 and 21 is refused by the table
    • They all go to slot 0 without collision, because every key is divisible by 8 in this example
    • All three collide at slot 5, so the second and third need rehashing

16. Why is a hash table's key normally not used directly as the storage address?

    • Keys may be large or not numbers, so a hash function maps them into the table's range
    • Storing keys directly is illegal in all languages, so a hash function is always required by the rules
    • Keys are always too small to be stored, so each key must be enlarged before it is used as an address
    • Keys must always be stored as strings, so the table cannot use a number as an address for a key

17. A hash table with 5 slots uses key MOD 5, and the keys 12 and 27 are added. Which statement is correct?

    • Both hash to slot 2, so a collision occurs
    • Both hash to slot 4
    • 12 hashes to slot 2 and 27 hashes to slot 0
    • Neither can be stored

18. What is the main disadvantage of a hash table compared with a sorted array?

    • It always uses more slots than values, so memory is wasted in every table of this kind
    • It cannot be searched at all, since the keys are stored in an order that cannot be read
    • It does not keep keys in order, so ordered traversal needs extra work
    • It cannot store integers, so keys must always be text values that are stored as characters

19. A hash table is nearly full with many collisions. Which action is most sensible?

    • Remove the hash function altogether, so that every key is stored in the next free slot in order
    • Stop adding any new values, so the table stays at its current size and no collisions can occur
    • Increase the table size and rehash the keys into the larger table
    • Store all keys in a single slot, which means that every lookup checks the same position each time

20. Which statement describes a simple hashing algorithm?

    • It stores each key in a random slot with no calculation, so the table is filled in no fixed order
    • It sorts the keys before storing them, so that the slots are filled from the smallest key upwards
    • It takes the key, performs a simple calculation such as a remainder, and uses the result as an index
    • It stores the keys in a binary file, which is read back to find each key when it is needed

Related quizzes

• Data structures and abstract data types Quiz · 4.2.1.1 · 20 questions
• Single- and multi-dimensional arrays Quiz · 4.2.1.2 · 20 questions
• Reading and writing text and binary files Quiz · 4.2.1.3 · 20 questions
• Linear, circular and priority queues Quiz · 4.2.2.1 · 20 questions
• Stack operations Quiz · 4.2.3.1 · 20 questions
• Graphs: weighted, directed and adjacency representations Quiz · 4.2.4.1 · 20 questions
• Trees and binary trees Quiz · 4.2.5.1 · 20 questions
• Dictionaries and key-value pairs Quiz · 4.2.7.1 · 20 questions
• Vectors and vector operations Quiz · 4.2.8.1 · 20 questions
• Data types Quiz · 4.1.1.1 · 20 questions