# DS |GATE-2018| PREVIOUS YEAR QUESTIONS| SET-3 DS |GATE-2018| Data Structure

1. The post order traversal of a binary tree is 8, 9, 6, 7, 4, 5, 2, 3, 1. The inorder traversal of the same tree is 8, 6, 9, 4, 7, 2, 5, 1, 3. The height of a tree is the length of the longest path from the root to any leaf. The height of the binary tree above is _______.  [GATE – 2018]

a. 2
b. 4
c. 6
d. 8

2. A queue is implemented using a non-circular singly linked list. The queue has a head pointer and a tail pointer, as shown in the figure. Let n denote the number of nodes in the queue. Let ‘enqueue’ be implemented by inserting a new node at the head, and ‘dequeue’ be implemented by deletion of a node from the tail. [GATE – 2018]

a. θ(1), θ(1)
b. θ(1), θ(n)
c. θ(n), θ(1)
d. θ(n), θ(n)

DS |GATE-2018|

3. Let G be a simple undirected graph. And Let TD be a depth first search tree of G. Let TB be a breadth first search tree of G. Consider the following statements.[GATE – 2018]

(I) No edge of G is a cross edge with respect to TD.
(A cross edge in G is between two nodes neither of which is an ancestor of the other in TD.)
(II) For every edge (u,v) of G, if u is at depth i and v is at depth j in TB, then ∣i−j∣ = 1.

Which of the statements above must necessarily be true?

a. I Only
b. II Only
c. Both I and II
d. Neither I and II

DS |GATE-2018|

4. The number of possible min-heaps containing each value from {1, 2, 3, 4, 5, 6, 7} exactly once is ___________. [GATE – 2018]

a. 78
b. 79
c. 80
d. 81