GATE CS 2021 Set 1 — Question 57
Go beyond PYQs with Success TrackerAI-powered personalised practice and doubt support. Unlimited practice on eligible plans; AI usage limits apply.MSQ+2 / -0HardStatic & Dynamic HashingIndexing & File OrganizationDatabasesChainingHashingProgramming & Data Structures
Databases → Hashing → Chaining
Last updated
Question
Consider a dynamic hashing approach for 4-bit integer keys:
Which of the following sequences of key insertions can cause the above state of the hash table (assume the keys are in decimal notation)?
1.There is a main hash table of size 4.
2.The 2 least significant bits of a key is used to index into the main hash table.
3.Initially, the main hash table entries are empty.
4.Thereafter, when more keys are hashed into it, to resolve collisions, the set of all keys corresponding to a main hash table entry is organized as a binary tree that grows on demand.
5.First, the least significant bit is used to divide the keys into left and right subtrees.
6.To resolve more collisions, each node of the binary tree is further sub-divided into left and right subtrees based on the least significant bit.
7.A split is done only if it is needed, i.e., only when there is a collision.
Consider the following state of the hash table.Which of the following sequences of key insertions can cause the above state of the hash table (assume the keys are in decimal notation)?
Correct answer
(C) 10, 9, 6, 7, 5, 13
Solution
The hashing scheme uses the 2 least significant bits (LSB) for the main table index. Collisions are resolved by building a tree using the LSB, and then the LSB if needed.Analyzing the given state:
Let's convert keys to 4-bit binary:
- Index 00: Empty. No keys end in
00. - Index 01: Points to a tree. The root (split on bit) has a left child (0) and a right child (1). The right child is further split (on bit) into left (0) and right (1).
- This implies: One key with bit 0. Two keys with bit 1 (one with bit 0, one with bit 1).
- Index 10: Points to a tree. The root (split on bit) has a left child (0) and a right child (1). Both are leaves.
- This implies: One key with bit 0. One key with bit 1.
- Index 11: Points to a single leaf node.
- This implies: One key ending in
11.
Let's convert keys to 4-bit binary:
- 10 (): Ends in
10. bit is 0. Goes to Index 10, Left branch. - 9 (): Ends in
01. bit is 0. Goes to Index 01, Left branch. - 6 (): Ends in
10. bit is 1. Goes to Index 10, Right branch. - 7 (): Ends in
11. Goes to Index 11. - 5 (): Ends in
01. bit is 1. Goes to Index 01, Right branch. ( bit is 0). - 13 (): Ends in
01. bit is 1. Goes to Index 01, Right branch. ( bit is 1).
- Index 00: Empty. (Matches)
- Index 01: Contains 9 (), 5 (), 13 (). The collision between 5 and 13 on the bit forces a split on the bit. (Matches diagram)
- Index 10: Contains 10 () and 6 (). Split on bit. (Matches diagram)
- Index 11: Contains 7. (Matches diagram)
- (A) Contains 4 (), which would go to Index 00. The diagram shows Index 00 is empty.
- (B) Contains 1 () and 9 (). Both end in
01and have bit 0. This would cause a collision and split in the left branch of Index 01. The diagram shows no split there. - (D) Contains 6 () and 14 (). Both end in
10and have bit 1. This would cause a collision and split in the right branch of Index 10. The diagram shows no split there.
Continue learning with Success Tracker
A step still unclear? Work through it with support
Use Success Tracker to ask about the reasoning, then try another GATE CS question to check your understanding.
AI-powered practice· Unlimited practice on eligible plans
- PYQs with solutions
- Attempt available previous-year questions, then compare your reasoning with the worked solution. Coverage varies by stream.
- Practice that adapts
- Choose a topic, work on weaker areas and bookmark questions to revisit. Your attempts feed your progress tracking.
- AI doubt support
- Ask follow-up questions about a step or concept while practising, instead of stopping at the final answer.
Unlimited practice is available on eligible plans. Free practice and AI usage have limits; check the current plan allowances before choosing.
This page stays readable without an account. AI responses can be wrong; check them against the solution and source material.
More questions on Hashing
2026 Set 2 Q12The set T represents various traversals over binary tree. The set S represents the order of…2026 Set 2 Q15In the context of DBMS, consider the two sets T and S given below. | T | S | |---|---| | I:…2026 Set 2 Q19Consider the following three ANSI-C programs, P1, P2, and P3. P1 [code] P2 [code] **P3**…2026 Set 2 Q20Consider concurrent execution of two transactions and in a DBMS, both of which access a…2026 Set 1 Q23Let be an odd number greater than 100. Consider a binary minheap with elements stored in an…