1. Home
  2. GATE
  3. Computer Science and Information Technology
  4. 2021 Paper 1
  5. Q47
GATE CSE · 2021 · CS

Question 47: Databases

Give it a try, then reveal the answer to check your work.

Question 47

CSMSQ2 marksNeeds review
Consider a dynamic hashing approach for 4-bit integer keys:
There is a main hash table of size 4.
The 2 least significant bits of a key is used to index into the main hash table.
Initially, the main hash table entries are empty.
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.
First, the 3rd least significant bit is used to divide the keys into left and right subtrees.
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.
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.
Diagram for Computer Science and Information Technology question 47

Which of the following sequences of key insertions can cause the above state of the hash table (assume the keys are in decimal notation)?
Your answerSelect all correct options. You can choose more than one.

Log in to check the answer

You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer

EXPLORE & PRACTISE

Paper and topic context

See where this question comes from and choose what to practise next.

2021CS

GATE CSE 2021 · Paper 1

Computer Science and Information Technology · Original paper archive

Section
Computer Science and Information Technology
Question type
Multiple select (MSQ)
Marks
2 marks
View complete paperPractise this paper

Practise related topics

Explore more previous year questions using this question’s imported topic tags.

computer science

GATE CSE previous year questions

Practise topic

information technology

GATE CSE previous year questions

Practise topic

computing

GATE CSE previous year questions

Practise topic

databases

GATE CSE previous year questions

Practise topic

Comments

Ask a question, share your approach, or help someone understand.

Log in to view the discussion

You’re not logged in. Log in or create an account to see discussions and add comments.