A hash table of length 10 uses open addressing with hash function h(k) = k mod…
2010
A hash table of length 10 uses open addressing with hash function h(k) = k mod 10 and linear probing.
After inserting six values into an empty hash table, the final table is:
0: empty
1: empty
2: 42
3: 23
4: 34
5: 52
6: 46
7: 33
8: empty
9: empty
How many different insertion sequences of these key values can produce the table shown above?
Answer: C. 30 — Correct answer: 30 Home positions are: 42→2, 23→3, 34→4, 52→2, 46→6, 33→3. For 52 to finish at slot 5, slots 2, 3, and 4 must already be occupied. Hence 42,…
- A.
10
- B.
20
- C.
30
- D.
40
Attempted by 163 students.
Show answer & explanation
Correct answer: C
Correct answer: 30
Home positions are: 42→2, 23→3, 34→4, 52→2, 46→6, 33→3.
For 52 to finish at slot 5, slots 2, 3, and 4 must already be occupied. Hence 42, 23, and 34 must be inserted before 52.
For 33 to finish at slot 7, slots 3, 4, 5, and 6 must already be occupied. Hence 23, 34, 52, and 46 must be inserted before 33. This also makes 33 the last insertion.
Among the first five keys, 46 can be placed freely, but 52 must come after 42, 23, and 34.
So the count is 5! / 4 = 120 / 4 = 30.