1
GATE CSE 2021 Set 1
+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.

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 2021 Set 1
+2
-0.67
Let P be an array containing n integers. Let t be the lowest upper bound on the number of comparisons of the array elements, required to find the minimum and maximum values in an arbitrary of n elements. Which one of the following choices is correct?
A
t > 2n - 2
B
$$t > 3\left\lceil {\frac{n}{2}} \right\rceil$$ and t ≤ 2n - 2
C
t > n and $$t \le 3\left\lceil {\frac{n}{2}} \right\rceil$$
D
$$t > \left\lceil {{{\log }_2}(n)} \right\rceil$$ and t ≤ n
3
GATE CSE 2021 Set 1
+2
-0.67
A binary search tree T contains n distinct elements. What is the time complexity of picking an element in T that is smaller than the maximum element in T?
A
Θ(1)
B
Θ(n log n)
C
Θ(log n)
D
Θ(n)
4
GATE CSE 2021 Set 1
+2
-0.67

Consider the following statements.

S1 : The sequence of procedure calls corresponds to a preorder traversal of the activation tree.

S2 : The sequence of procedure returns corresponds to a postorder traversal of the activation tree.

Which one of the following options is correct?

A
S1 is true and S2 is true
B
S1 is false and S2 is true
C
S1 is false and S2 is false
D
S1 is true and S2 is false
GATE CSE Papers
2023
2022
2020
2019
2018
2013
2012
2011
2010
2009
2008
2007
2006
2005
2004
2003
2002
2001
2000
1999
1998
1997
1996
1995
1994
1993
1992
1991
1990
1989
1988
1987
EXAM MAP
Medical
NEET