Data Structure GATE CS and IT previous year questions with Answer
Ques 31 Gate 2016 Set-2
The number of ways in which the numbers 1, 2, 3, 4, 5, 6, 7 can be inserted in an empty binary search tree, such that the resulting tree has height 6, is _____________.
Note: The height of a tree with a single node is 0.
a is the correct answer.
Ques 32 Gate 2016 Set-2
A complete binary min-heap is made by including each integer in [1, 1023] exactly once. The depth of a node in the heap is the length of the path from the root of the heap to that node. Thus, the root is at depth 0. The maximum depth at which integer 9 can appear is _____________
a is the correct answer.
Ques 33 Gate 2016 Set-2
In an adjacency list representation of an undirected simple graph G = (V, E), each edge (u, v) has two adjacency list entries: [v] in the adjacency list of u, and [u] in the adjacency list of v. These are called twins of each other. A twin pointer is a pointer from an adjacency list entry to its twin. If |E| = m and |V| = n, and the memory size is not a constraint, what is the time complexity of the most efficient algorithm to set the twin pointer in each entry in each adjacency list?
Ques 34 Gate 2016 Set-2
Consider the following New-order strategy for traversing a binary tree:
Visit the root;
Visit the right subtree using New-order
Visit the left subtree using New-order
The New-order traversal of the expression tree corresponding to the reverse polish expression 3 4 * 5 - 2 ˆ 6 7 * 1 + - is given by:
Ques 35 Gate 2016 Set-2
B+ Trees are considered BALANCED because
Ques 36 Gate 2016 Set-1
Let Q denote a queue containing sixteen numbers and S be an empty stack. Head(Q) returns
the element at the head of the queue Q without removing it from Q. Similarly Top(S) returns
the element at the top of S without removing it from S. Consider the algorithm given below.
if S is Empty OR Top(S) ≤ Head(Q) then
x := Dequeue(Q);
Push(S, x);
else
x := Pop(S);
Enqueue(Q, x);
end
end
The maximum possible number of iterations of the while loop in the algorithm is_____
a is the correct answer.
Ques 37 Gate 2016 Set-1
Let G be a complete undirected graph on 4 vertices, having 6 edges with weights being 1, 2, 3, 4, 5, and 6. The maximum possible weight that a minimum weight spanning tree of G can have is_____
a is the correct answer.
Ques 38 Gate 2016 Set-1
G = (V, E) is an undirected simple graph in which each edge has a distinct weight, and e is a particular edge of G. Which of the following statements about the minimum spanning trees (MSTs) of G is/are TRUE
I. If e is the lightest edge of some cycle in G,
then every MST of G includes e
II. If e is the heaviest edge of some cycle in G,
then every MST of G excludes e
Ques 39 Gate 2016 Set-1
An operator delete(i) for a binary heap data structure is to be designed to delete the item in the i-th node. Assume that the heap is implemented in an array and i refers to the i-th index of the array. If the heap tree has depth d (number of edges on the path from the root to the farthest leaf), then what is the time complexity to re-fix the heap efficiently after the removal of the element?
Ques 40 Gate 2016 Set-1
What will be the output of the following C program?
{
static int d = 1;
printf("%d ", n);
printf("%d ", d);
d++;
if(n > 1) count(n-1);
printf("%d ", d);
}
int main()
{
count(3);
}