A hash table of length 10 uses open addressing with the hash function h(k) = k…
201820102026
A hash table of length 10 uses open addressing with the hash function h(k) = k mod 10 and linear probing. After six values are inserted into an empty table, the following table is obtained:
Which of the following could be the insertion order?
Answer: C. 46, 34, 42, 23, 52, 33 — CONCEPT In open addressing, every key first tries its home index h(k). With linear probing, an occupied home slot makes the insertion move one index at a…
- A.
46, 42, 34, 52, 23, 33
- B.
34, 42, 23, 52, 33, 46
- C.
46, 34, 42, 23, 52, 33
- D.
42, 46, 33, 23, 34, 52
Attempted by 408 students.
Show answer & explanation
Correct answer: C
CONCEPT
In open addressing, every key first tries its home index h(k). With linear probing, an occupied home slot makes the insertion move one index at a time, wrapping if necessary, until the first empty slot is found.
The final table therefore depends on insertion order whenever two or more keys compete for the same probe sequence.
APPLICATION
Test the sequence 46, 34, 42, 23, 52, 33 by applying the rule to each key:
Insert 46: h(46) = 6. Index 6 is empty, so place 46 at index 6.
Insert 34: h(34) = 4. Index 4 is empty, so place 34 at index 4.
Insert 42: h(42) = 2. Index 2 is empty, so place 42 at index 2.
Insert 23: h(23) = 3. Index 3 is empty, so place 23 at index 3.
Insert 52: h(52) = 2. Indices 2, 3, and 4 are occupied, so linear probing places 52 at index 5.
Insert 33: h(33) = 3. Indices 3, 4, 5, and 6 are occupied, so linear probing places 33 at index 7.
CROSS-CHECK
The occupied portion of the resulting table is:
Index | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|
Value | 42 | 23 | 34 | 52 | 46 | 33 |
This index-to-value mapping is identical to the displayed table. Hence the possible insertion order is 46, 34, 42, 23, 52, 33.