Register

GATE Overflow Test Series | Algorithms | Test 1 | Question: 15

190 views
3 votes
3 votes

You are given an empty hash table of size $6$ that uses open addressing. The following sequence of keys is to be inserted:
$$32\; 7\; 14\; 22\; 29\; 3$$If linear probing with $h(x) = x \% 6;$ is used, which all elements will cause a collision? (Mark all choices which are CORRECT)

  1. $3$
  2. $14$
  3. $29$
  4. $22$
User Avatar

1 Answer

Best answer
4 votes
4 votes
  • $32 \mod 6 = 2$ -occupies slot $2$
  • $7 \mod 6 = 1$ - occupies slot $1$
  • $14 \mod 6 = 2$ - collide. Occupies next slot which is  slot $3$
  • $22 \mod 6 = 4$ - occupies slot $4$
  • $29 \mod 6 = 5$ - occupies slot $5$
  • $3 \mod 6 = 3$ - collide on slot $3.$ Occupied next free slot which is slot $0.$ 
• selected by
User Avatar
Voting & Accepting an answer helps improve the community
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

4 votes
4 votes
1 answer
1
gatecse asked Aug 18, 2020
402 views
GATE Overflow Test Series | Algorithms | Test 1 | Question: 23
You are given an empty hash table of size $7$ that uses open addressing. The following sequence of keys is to be inserted: $13\;18\;25\;11\;20\;29$If hash function $h_1(x) = x \% 7;$ ... $25$ $11$ $20$ $29$
You are given an empty hash table of size $7$ that uses open addressing. The followingsequence of keys is to be inserted:$$13\;18\;25\;11\;20\;29$$If hash function $h_1(x...
User Avatar
4 votes
4 votes
1 answer
3
gatecse asked Aug 18, 2020
638 views
GATE Overflow Test Series | Algorithms | Test 1 | Question: 9
In a hashtable with $20$ slots $30$ records are inserted with collisions being resolved by chaining. What is the expected number of key comparisons in an unsuccessful search assuming uniform hashing?
In a hashtable with $20$ slots $30$ records are inserted with collisions being resolved by chaining. What is the expected number of key comparisons in an unsuccessful sea...
User Avatar
Link Copied!