1
GATE CSE 2021 Set 1
MCQ (Single Correct Answer)
+2
-0.67

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 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.

GATE CSE 2021 Set 1 Data Structures - Hashing Question 3 English Which of the following sequence of key insertions can cause the above state of the hash table (assume the keys are in decimal notation)?

A
10, 9, 6, 7, 5, 13
B
5, 9, 4, 13, 10, 7
C
9, 5, 13, 6, 10, 14
D
9, 5, 10, 6, 7, 1
2
GATE CSE 2015 Set 2
MCQ (Single Correct Answer)
+2
-0.6
Which one of the following hash functions on integers will distribute keys most uniformly over $$10$$ buckets numbered $$0$$ to $$9$$ for $$𝑖$$ ranging from $$0$$ to $$2020$$?
A
$$h\left( i \right) = {i^2}\,mod\,\,10$$
B
$$h\left( i \right) = {i^3}\,mod\,\,10$$
C
$$h\left( i \right) = \left( {11 * {i^2}} \right)\,\bmod \,10$$
D
$$h\left( i \right) = \left( {12 * i} \right)\,\bmod \,10$$
3
GATE CSE 2014 Set 3
MCQ (Single Correct Answer)
+2
-0.6
Consider a hash table with 100 slots. Collisions are resolved using chaining. Assuming simple uniform hashing, what is the probability that the first 3 slots are unfilled after the first 3 insertions?
A
97 × 97 × 97)/1003
B
(99 × 98 × 97)/1003
C
(97 × 96 × 95)/1003
D
(97 × 96 × 95)/(3! × 1003)
4
GATE CSE 2014 Set 1
MCQ (Single Correct Answer)
+2
-0.6
Consider a hash table with 9 slots. The hash function is h(k) = k mod 9. The collisions are resolved by chaining. The following 9 keys are inserted in the order: 5, 28, 19, 15, 20, 33, 12, 17, 10. The maximum, minimum, and average chain lengths in the hash table, respectively, are
A
3, 0, and 1
B
3, 3, and 3
C
4, 0, and 1
D
3, 0, and 2
GATE CSE Subjects
Software Engineering
Web Technologies
EXAM MAP
Medical
NEET
Graduate Aptitude Test in Engineering
GATE CSEGATE ECEGATE EEGATE MEGATE CEGATE PIGATE IN
Civil Services
UPSC Civil Service
CBSE
Class 12