Consider a hash table π[0, 1, β¦ , 10] that is initially empty. The hash table is
maintained using open addressing with linear probing. The hash function used is
β(π₯) = (π₯+ 7) mod 11.
Consider the following sequence of insertions performed on π:
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 π[0, 1, β¦ , 10] that is initially empty. The hash table is
maintained using open addressing with linear probing. The hash function used is
β(π₯) = (π₯+ 7) mod 11.
Consider the following sequence of insertions performed on π:
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
- 0
- 10
- 2
- 1
The Correct Option is C
Solution and Explanation
We have a hash table P[0..10] (11 slots) using open addressing with linear probing and hash function \(h(x) = (x+7) \bmod 11\). We insert 1, 13, 22, 15, 11, 24 in order and must find the empty slots afterward.
Step 1: Insert 1.
\(h(1) = (1+7) \bmod 11 = 8\). Slot 8 is empty, so place 1 at index 8.
Step 2: Insert 13.
\(h(13) = (13+7) \bmod 11 = 20 \bmod 11 = 9\). Slot 9 is empty, so place 13 at index 9.
Step 3: Insert 22.
\(h(22) = (22+7) \bmod 11 = 29 \bmod 11 = 7\). Slot 7 is empty, so place 22 at index 7.
Step 4: Insert 15.
\(h(15) = (15+7) \bmod 11 = 22 \bmod 11 = 0\). Slot 0 is empty, so place 15 at index 0.
Step 5: Insert 11.
\(h(11) = (11+7) \bmod 11 = 18 \bmod 11 = 7\). Slot 7 is occupied (22), so probe forward: slot 8 is occupied (1), slot 9 is occupied (13), slot 10 is empty. Place 11 at index 10.
Step 6: Insert 24.
\(h(24) = (24+7) \bmod 11 = 31 \bmod 11 = 9\). Slot 9 is occupied (13), probe slot 10 (occupied by 11), wrap around to slot 0 (occupied by 15), then slot 1 is empty. Place 24 at index 1.
Step 7: List the final table and identify empty slots.
Final table: index 0 = 15, index 1 = 24, index 2 = empty, index 3 = empty, index 4 = empty, index 5 = empty, index 6 = empty, index 7 = 22, index 8 = 1, index 9 = 13, index 10 = 11.
So the empty slots are 2, 3, 4, 5, and 6. Among the given options (0, 10, 2, 1), only index 2 is empty; indices 0, 10, and 1 are all occupied.
\[ \boxed{\text{Option C (index 2)}} \]Top GATE CS Computer Science and IT Engineering Questions
- Suppose a program is running on a non-pipelined single processor computer system. The computer is connected to an external device that can interrupt the processor asynchronously. The processor needs to execute the interrupt service routine (ISR) to serve this interrupt. The following steps (not necessarily in order) are taken by the processor when the interrupt arrives:
(i) The processor saves the content of the program counter.
(ii) The program counter is loaded with the start address of the ISR.
(iii) The processor finishes the present instruction.
Which ONE of the following is the CORRECT sequence of steps? - Which ONE of the following statements is FALSE regarding the symbol table?
- Which ONE of the following techniques used in compiler code optimization uses live variable analysis?
- Consider a demand paging memory management system with 32-bit logical address, 20-bit physical address, and page size of 2048 bytes. Assuming that the memory is byte addressable, what is the maximum number of entries in the page table?
A schedule of three database transactions \(T_1\), \(T_2\), and \(T_3\) is shown. \(R_i(A)\) and \(W_i(A)\) denote read and write of data item A by transaction \(T_i\), \(i = 1, 2, 3\). The transaction \(T_1\) aborts at the end. Which other transaction(s) will be required to be rolled back?
Top GATE CS Hashing 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 ?