Consider a hash table of size 7 with starting index 0 and hash function (6x + 3) mod 4. Assuming the table is initially empty, which of the following is the content of the table when the sequence 1, 3, 8, 10, 5 is inserted using closed hashing (linear probing)? Here '_' denotes an empty location.
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: D. _, 1, 3, 8, 10, 5, _
Explanation
h(1) = 9 mod 4 = 1 → slot 1. h(3) = 21 mod 4 = 1 → collides, goes to 2. h(8) = 51 mod 4 = 3 → slot 3. h(10) = 63 mod 4 = 3 → goes to 4. h(5) = 33 mod 4 = 1 → probes 2, 3, 4 → slot 5. Table: _, 1, 3, 8, 10, 5, _.More Data Structures and Algorithms questions
- Match List I with List IIList I List II A. Running time of a straightforward recursive method to compute the nth Fibonacci number Fₙ I. O(n…
- Statement I: If f and g are two functions and f = O(g) but g ≠ o(f), we say that the growth rate of g is smaller than that of f. Statement…
- Given below are two statements: one is labelled as Assertion A and the other is labelled as Reason R. Assertion A: It is possible to create…
- For each function below, let n be the least integer such that f(x) is O(xⁿ). Arrange the functions in increasing order of n: A. f(x) = 3x³…
- f(n) = a·f(n/b) + g(n) is a divide-and-conquer recurrence. Match the algorithms in List I with their recurrences in List II.List I List II…
- The height of a binary search tree built by inserting the words banana, peach, apple, pear, coconut, mango and papaya (in this order, alpha…