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?
Correct Answer :
2
Solution :
The correct option is 2 (which corresponds to position/index 2 in the hash table).
Let us understand why this is correct by walking through the step-by-step insertion of the keys into the hash table of size 11 (indices 0 to 10), using open addressing with linear probing.
The given hash function is:
Under linear probing, if a collision occurs at a slot i, we check subsequent slots sequentially in the order:
,
, and so on, until an empty slot is found.
Initially, the hash table is completely empty:
P = [empty, empty, empty, empty, empty, empty, empty, empty, empty, empty, empty]
Step 1: Insert key 1
Compute the hash value:
Slot 8 is empty, so we place 1 at index 8.
P[8] = 1
Step 2: Insert key 13
Compute the hash value:
Slot 9 is empty, so we place 13 at index 9.
P[9] = 13
Step 3: Insert key 22
Compute the hash value:
Slot 7 is empty, so we place 22 at index 7.
P[7] = 22
Step 4: Insert key 15
Compute the hash value:
Slot 0 is empty, so we place 15 at index 0.
P[0] = 15
Step 5: Insert key 11
Compute the hash value:
Let's resolve the collision for key 11 using linear probing:
- Attempt 1: Slot 7 is occupied (contains 22). We check the next slot (7 + 1 = 8).
- Attempt 2: Slot 8 is occupied (contains 1). We check the next slot (8 + 1 = 9).
- Attempt 3: Slot 9 is occupied (contains 13). We check the next slot (9 + 1 = 10).
- Attempt 4: Slot 10 is empty, so we place 11 at index 10.
P[10] = 11
Step 6: Insert key 24
Compute the hash value:
Let's resolve the collision for key 24 using linear probing:
- Attempt 1: Slot 9 is occupied (contains 13). We check the next slot (9 + 1 = 10).
- Attempt 2: Slot 10 is occupied (contains 11). We check the next slot (10 + 1 = 11 mod 11 = 0).
- Attempt 3: Slot 0 is occupied (contains 15). We check the next slot (0 + 1 = 1).
- Attempt 4: Slot 1 is empty, so we place 24 at index 1.
P[1] = 24
Final State of the Hash Table:
- P[0] = 15
- P[1] = 24
- P[2] = empty
- P[3] = empty
- P[4] = empty
- P[5] = empty
- P[6] = empty
- P[7] = 22
- P[8] = 1
- P[9] = 13
- P[10] = 11
Comparing the state of the hash table with the given options (0, 10, 2, 1), we see that position 2 remains empty, whereas slots 0, 1, and 10 are occupied.
Access expert-curated educational resources and study materials—completely free.
Create, conduct, and manage professional online assessments with Mindyard. Perfect for teachers and institutes.
Copyright © 2026 Mindyard. All Rights Reserved.
