GATE CS 2021 (Forenoon) — Question 57

AlgorithmsSearching, Sorting, Hashing MechanismsMSQ2 marksHard

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 \(3^{\text{rd}}\) 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 \(4^{\text{th}}\) 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.
Question image
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. A
    5, 9, 4, 13, 10, 7
  2. B
    9, 5, 10, 6, 7, 1
  3. C
    10, 9, 6, 7, 5, 13
  4. D
    9, 5, 13, 6, 10, 14
Practise the full 2021-FN paper
Challenge a friend: WhatsApp Telegram
Recommended book · affiliate linkIntroduction to Algorithms (CLRS)The standard reference behind most GATE algorithm questions.
Practise more on Searching, Sorting, Hashing MechanismsTimed, in the real exam interface · free to start

A GATE question every morning

One real past-paper question every morning for your branch, answer hidden until you tap. Free on Telegram.

Join
Stuck? Ask in the student group