Data Structure GATE Question Answers with Explanation.
Q1 – Consider the problem of reversing a singly linked list. To take an example, given the linked list below,
the reversed linked list should look like
Which one of the following statements is TRUE about the time complexity of
algorithms that solve the above problem in O(1) space? (GATE 2022)
The best algorithm for the problem takes Ɵ(n) time in the worst case.
The best algorithm for the problem takes Ɵ(nlogn) time in the worst case.
The best algorithm for the problem takes Ɵ(n2) time in the worst case.
It is not possible to reverse a singly linked list in O(1) space.
Ans – (1)
Explanation –
Q2 – Suppose we are given n keys, m hash table slots, and two simple uniform hash functions h1 and h2. Further suppose our hashing scheme uses h1 for the odd keys and h2 for the even keys. What is the expected number of keys in a slot? (GATE 2022)
m/n
n/m
2n/m
n/2m
Ans – (2)
Explanation –
Q3 – Suppose a binary search tree with 1000 distinct elements is also a complete binary tree. The tree is stored using the array representation of binary heap trees. Assuming that the array indices start with 0, the 3rd largest element of the tree is stored at index_____________. (GATE 2022)
Ans – (509)
Explanation –
Q4 – Consider a simple undirected graph of 10 vertices. If the graph is disconnected, then the maximum number of edges it can have is ____________. (GATE 2022)
Ans – (36)
Explanation –
Q5 – Consider a simple undirected unweighted graph with at least three vertices. If A is the adjacency matrix of the graph, then the number of 3-cycles in the graph is given by the trace of (GATE 2022)
A3
A3 divided by 2
A3 divided by 3
A3 divided by 6
Ans – (4)
Explanation –
Q6 – Consider the queues Q1 containing four elements and Q2 containing none (shown as the Initial State in the figure). The only operations allowed on these two queues are Enqueue (Q, element) and Dequeue (Q). The minimum number of Enqueue operations on Q1 required to place the elements of Q1 in Q2 in reverse order (shown as the Final State in the figure) without using any additional storage is___________. (GATE 2022)
Ans – (0)
Explanation –