Following keys are inserted into a hash table: 6, 29, 20, 16, 21, 33, 12, 17, 13, 41, 30...
IBM technical mcq question, verified with a worked answer. Free to practise - no sign-up.
Following keys are inserted into a hash table:
6, 29, 20, 16, 21, 33, 12, 17, 13, 41, 30
using h(k) = k mod 7 hash function.
If collisions are resolved using chaining then max chain length will be.
Pick ONE option
Show answer & explanation
Answer: B. 3
Computing h(k) = k mod 7 for each key maps them to hash table slots. Multiple keys hash to the same slot, forming chains. Slot 6 contains the longest chain with three keys (6, 20, 41), making the maximum chain length 3.
Step-by-step Derivation:
Calculate h(k) for each key:
- h(6) = 6 mod 7 = 6
- h(29) = 29 mod 7 = 1
- h(20) = 20 mod 7 = 6
- h(16) = 16 mod 7 = 2
- h(21) = 21 mod 7 = 0
- h(33) = 33 mod 7 = 5
- h(12) = 12 mod 7 = 5
- h(17) = 17 mod 7 = 3
- h(13) = 13 mod 7 = 6
- h(41) = 41 mod 7 = 6
- h(30) = 30 mod 7 = 2
Chains formed:
- Slot 0: [21] → length 1
- Slot 1: [29] → length 1
- Slot 2: [16, 30] → length 2
- Slot 3: [17] → length 1
- Slot 4: [] → length 0
- Slot 5: [33, 12] → length 2
- Slot 6: [6, 20, 13, 41] → length 4
Wait, recalculating slot 6: 6, 20, 13, 41 all map to 6, giving length 4. Let me verify: h(41) = 41 mod 7 = 6. Yes, the maximum chain length is 4.