CS/IT Gate Subject



Data Structure GATE previous year questions with answer

Ques 66 Gate 2015 Set-1

The height of a tree is the length of the longest root-to-leaf path in it. The maximum and minimum number of nodes in a binary tree of height 5 are

A

63 and 6, respectively

B

64 and 5, respectively

C

32 and 6, respectively

D

31 and 5, respectively


(Tree ) is the correct answer.

Ques 67 Gate 2015 Set-1

What are the worst-case complexities of insertion and deletion of a key in a binary search tree?

A

Θ(logn) for both insertion and deletion

B

Θ(n) for both insertion and deletion

C

Θ(n) for insertion and Θ(logn) for deletion

D

Θ(logn) for insertion and Θ(n) for deletion


(Binary Search Tree) is the correct answer.

Ques 68 Gate 2015 Set-1

Which of the following is/are correct inorder traversal sequence(s) of binary search tree(s)?

I. 3, 5, 7, 8, 15, 19, 25
II. 5, 8, 9, 12, 10, 15, 25
III. 2, 7, 10, 8, 14, 16, 20
IV. 4, 6, 7, 9, 18, 20, 25

A

I and IV only

B

II and III only

C

II and IV only

D

II only


(Tree Traversal) is the correct answer.

Ques 69 Gate 2014 Set-1

Consider a rooted Binary tree represented using pointers. The best upper bound on the time required to determine the number of subtrees having having exactly 4 nodes O(na Lognb). Then the value of a + 10b is ________


(a) is the correct answer.

Ques 70 Gate 2014 Set-1

Let G be a graph with n vertices and m edges. What is the tightest upper bound on the running time on Depth First Search of G?
Assume that the graph is represented using adjacency matrix.

A

θ (n)

B

θ (n+m)

C

θ(n2)

D

θ(m2)


(Graph Theory) is the correct answer.

Ques 71 Gate 2014 Set-1

Let G=(V,E) be a directed graph where V is the set of vertices and E the set of edges. Then which one of the following graphs has the same strongly connected components as G ?

A

G1 = (V,E1) where E1={(u,v)∣(u,v)∉E}

B

G2 = (V,E2) where E2={(u,v)∣(v,u)∈E}

C

G3 = (V,E3) where E3={(u,v)∣ there is a path of length ≤2 from u to v in E}

D

G4= (V4,E) where V4 is the set of vertices in G which are not isolated


(Graph Theory) is the correct answer.

Unique Visitor Count

Total Unique Visitors

Loading......

Question Options

Contributed by: