Discussion
Consider a hash table P[0, 1, ... , 10] that is initially empty. The hash table is maintained using open addressing with linear probing. The hash function used is h(x) = (x + 7) mod 11.
Consider the following sequence of insertions performed on P:
1, 13, 22, 15, 11, 24
Which of the following positions in the hash table is/are empty after these insertions are performed?
Answer: C
Of the positions listed, only 2 is empty.
Insert each key with h(x) = (x + 7) mod 11, probing forward on a collision:
- 1: h = 8, placed at 8.
- 13: h = 20 mod 11 = 9, placed at 9.
- 22: h = 29 mod 11 = 7, placed at 7.
- 15: h = 22 mod 11 = 0, placed at 0.
- 11: h = 18 mod 11 = 7; 7, 8 and 9 are full, placed at 10.
- 24: h = 31 mod 11 = 9; 9, 10 and 0 are full, placed at 1.
The occupied slots are 0, 1, 7, 8, 9 and 10, so slots 2 to 6 are empty. Positions 0, 10 and 1 are all filled, 10 and 1 only after probing past earlier keys.
No comment is present. Be the first to comment.
Loading…
Post your comment
Please log in or register to post a comment.
Examination Categories
- SSC Exams
- Banking Exams
- Teaching Exams
- Civil Services Exams
- Railways Exams
- Engineering Recruitment Exams
- Defence Exams
- State Government Exams
- Police Exams
- Insurance Exams
- Nursing Exams
- Other Government Exams
- NRA CET
- PG Entrance Exams
- Campus Placement
- MBA Entrance Exams
- CUET and UG Entrance
- Judiciary Exams
- Regulatory Body Exams
- Software Development