Skip to content
GATEiit

GATE CSE 2021 Set 1 Q57: Insertion order producing a given dynamic hashing state

Question

Consider a dynamic hashing approach for 4-bit integer keys:

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 3rd 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 4th 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)?

Main hash table with entries 00, 01, 10, 11. Entry 00 is empty. Entry 01 points to a node split on the 3rd bit: its 0-child is a key, its 1-child is split again on the 4th bit into two keys. Entry 10 points to a node split on the 3rd bit with one key on each side. Entry 11 holds a single key
Tap the figure to enlarge

Try it: multiple select: one or more correct options

Select one or more options
Select all correct options. No negative marking, no partial marks.
Show answer and explanation

Answer: C (official GATE 2021 final answer key)

Concept used: Index by the two low bits, then split on bit 3 and then bit 4; the final shape depends only on the set of keys.

First step: The state needs no key ending in 00, three keys ending in 01 (one with bit 3 = 0, two with bit 3 = 1 differing in bit 4), two ending in 10 with different bit 3, and one ending in 11. Write each option's keys in binary.

Full step-by-step solution

Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.

Share this question

WhatsAppDownload image

Source: official GATE 2021 Set 1 CS question paper and final answer key, organised by IIT Bombay. Question paper · Answer key

More Programming and Data Structures PYQs

PracticePractise Programming and Data Structures questions →Full paperAll GATE CSE 2021 Set 1 questions →