Data Structure Questions Answers GATE 2021

Data Structure GATE Question Answers with Explanation.

Q1 – In an undirected connected planar graph G, there are eight vertices and five faces. The number of edges in G is _________. (GATE 2021 Set 1)

Answer

Ans – (11)

Explanation –

Q2 – Consider the following undirected graph with edge weights as shown:

The number of minimum-weight spanning trees of the graph is ___________. (GATE 2021 Set 1)

Answer

Ans – (3)

Explanation –

Q3 – Consider the following sequence of operations on an empty stack.

push(54); push(52); pop(); push(55); push(62); s=pop();

Consider the following sequence of operations on an empty queue.

enqueue(21); enqueue(24); dequeue(); enqueue(28); enqueue(32); q=dequeue();

The value of s+q is ___________. (GATE 2021 Set 1)

Answer

Ans – (86)

Explanation –

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

(A) There is a main hash table of size 4.

(B) The 2 least significant bits of a key is used to index into the main hash table.

(C) Initially, the main hash table entries are empty.

(D) 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.

(E) First, the 3rd least significant bit is used to divide the keys into left and right subtrees.

(F) 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.

(G) 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)? (GATE 2021 Set 1)

5, 9, 4, 13, 10, 7
9, 5, 10, 6, 7, 1
10, 9, 6, 7, 5, 13
9, 5, 13, 6, 10, 14

Answer

Ans – (3)

Explanation –

Data Structure Questions Answers GATE 2021

Data Structure GATE Question Answers with Explanation.

Q1 – In an undirected connected planar graph G, there are eight vertices and five faces. The number of edges in G is _________. (GATE 2021 Set 1)

Q2 – Consider the following undirected graph with edge weights as shown:

The number of minimum-weight spanning trees of the graph is ___________. (GATE 2021 Set 1)

Q3 – Consider the following sequence of operations on an empty stack.

push(54); push(52); pop(); push(55); push(62); s=pop();

Consider the following sequence of operations on an empty queue.

enqueue(21); enqueue(24); dequeue(); enqueue(28); enqueue(32); q=dequeue();

The value of s+q is ___________. (GATE 2021 Set 1)

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

(A) There is a main hash table of size 4.

(B) The 2 least significant bits of a key is used to index into the main hash table.

(C) Initially, the main hash table entries are empty.

(D) 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.

(E) First, the 3rd least significant bit is used to divide the keys into left and right subtrees.

(F) 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.

(G) 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)? (GATE 2021 Set 1)

5, 9, 4, 13, 10, 7

9, 5, 10, 6, 7, 1

10, 9, 6, 7, 5, 13

9, 5, 13, 6, 10, 14