Question:
Consider a hash table \( P[0,1,\ldots,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) \bmod 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?
Consider a hash table \( P[0,1,\ldots,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) \bmod 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?
Show Hint
Simulate each insertion in order, computing h(x) = (x+7) mod 11, and moving to the next slot (wrapping past index 10 back to 0) whenever there is a collision.
Updated On: Jul 22, 2026
- 0
- 10
- 2
- 1
Show Solution
Verified By Collegedunia
The Correct Option is C
Solution and Explanation
Step 1: Recall how linear probing resolves collisions.
To insert key x, compute its home slot \( h(x) = (x+7) \bmod 11 \). If that slot is empty, place x there; if occupied, probe the next slot \( (h(x)+1) \bmod 11 \), then the next, wrapping from index 10 back to index 0, until an empty slot is found.
To insert key x, compute its home slot \( h(x) = (x+7) \bmod 11 \). If that slot is empty, place x there; if occupied, probe the next slot \( (h(x)+1) \bmod 11 \), then the next, wrapping from index 10 back to index 0, until an empty slot is found.
Step 2: Insert 1.
\( h(1) = 8 \bmod 11 = 8 \). Slot 8 empty, place 1 at index 8.
\( h(1) = 8 \bmod 11 = 8 \). Slot 8 empty, place 1 at index 8.
Step 3: Insert 13.
\( h(13) = 20 \bmod 11 = 9 \). Slot 9 empty, place 13 at index 9.
\( h(13) = 20 \bmod 11 = 9 \). Slot 9 empty, place 13 at index 9.
Step 4: Insert 22.
\( h(22) = 29 \bmod 11 = 7 \). Slot 7 empty, place 22 at index 7.
\( h(22) = 29 \bmod 11 = 7 \). Slot 7 empty, place 22 at index 7.
Step 5: Insert 15.
\( h(15) = 22 \bmod 11 = 0 \). Slot 0 empty, place 15 at index 0.
\( h(15) = 22 \bmod 11 = 0 \). Slot 0 empty, place 15 at index 0.
Step 6: Insert 11.
\( h(11) = 18 \bmod 11 = 7 \). Slot 7 occupied (22); probe 8, occupied (1); probe 9, occupied (13); probe 10, empty, place 11 at index 10.
\( h(11) = 18 \bmod 11 = 7 \). Slot 7 occupied (22); probe 8, occupied (1); probe 9, occupied (13); probe 10, empty, place 11 at index 10.
Step 7: Insert 24.
\( h(24) = 31 \bmod 11 = 9 \). Slot 9 occupied (13); probe 10, occupied (11); probe 0 (wrap-around), occupied (15); probe 1, empty, place 24 at index 1.
\( h(24) = 31 \bmod 11 = 9 \). Slot 9 occupied (13); probe 10, occupied (11); probe 0 (wrap-around), occupied (15); probe 1, empty, place 24 at index 1.
Step 8: Final table state and check the given options.
Occupied indices: 0(15), 1(24), 7(22), 8(1), 9(13), 10(11). Empty indices: 2, 3, 4, 5, 6.
(A) Index 0 holds 15: occupied.
(B) Index 10 holds 11: occupied.
(C) Index 2: never touched, empty.
(D) Index 1 holds 24: occupied.
Occupied indices: 0(15), 1(24), 7(22), 8(1), 9(13), 10(11). Empty indices: 2, 3, 4, 5, 6.
(A) Index 0 holds 15: occupied.
(B) Index 10 holds 11: occupied.
(C) Index 2: never touched, empty.
(D) Index 1 holds 24: occupied.
Step 9: Conclusion.
Among the listed positions, only index 2, option (C), is empty after the insertions.
\[ \boxed{\text{Option (C)}} \]Among the listed positions, only index 2, option (C), is empty after the insertions.
Was this answer helpful?
0
0
Top GATE CS Programming and Data Structures Questions
- Which of the following sequences when stored in an array at locations A[1],..., A[10] forms a max-heap?
- Given N distinct elements in an array, determine the number of comparisons required to find the element which is not the largest:
Consider the following code:
main() { int x = 126, y = 105; { if (x > y) x = x - y; else y = y - x; } while (x != y) printf("%d", x); }- In a binary search tree with the following elements: \( 10, -4, 15, 13, 20, 5, 16, 19 \), the number of edges from node 19 to the root is?
Consider the following code:
int a; int arr[] = {30, 50, 10}; int *ptr = arr[10] + 1; a = *ptr; (*ptr)++; ptr = ptr + 1; printf("%d", a + arr[1] + *ptr);
View More Questions
Top GATE CS Questions
- Which of the following sequences when stored in an array at locations A[1],..., A[10] forms a max-heap?
- The Lucas sequence Ln is defined by the recurrence relation: Ln = Ln−1 + Ln−2, for n ≥ 3, with L1 = 1 and L2 = 3. Which one of the options given is TRUE?
- Which of the following fields of IP header is/are always modified by any router before it forwards to IP Packet ?
- Which one of the following CIDR profix exactly represent the range of IP addresses 10.12.2.0 to 10.12.3.255?
- Consider an ethernet segment whose transmission is \(10^8\) bits per second. Maximum segment length \(500\ m\), speed of the provocation media velocity is \(2 × 10^8\) meter per second. What is the minimum frame size in bits ?
View More Questions