Data Structure GATE CS and IT previous year questions with Answer

Ques 51 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

See Answer Video Solution

Ques 52 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

See Answer Video Solution

Ques 53 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

See Answer Video Solution

Ques 54 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(n^a Logn^b). Then the value of a + 10b is ________

See Answer Video Solution

Ques 55 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

θ(n²)

D

θ(m²)

See Answer Video Solution

Ques 56 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

G₁ = (V,E₁) where E₁={(u,v)∣(u,v)∉E}

B

G₂ = (V,E₂) where E₂={(u,v)∣(v,u)∈E}

C

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

D

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

See Answer Video Solution