# Data Structure MCQ Questions and Answers

## 21. What is the average case time complexity for finding the height of the binary tree?

1. h = O(loglogn)
2. h = O(n)
3. h = O(nlogn)
4. h = O(log n)

Explanation: The nodes can be either a part of left sub tree or the right sub tree, so we don’t have to traverse all the nodes, this means the complexity is lesser than n, in the average case, assuming the nodes are spread evenly, the time complexity becomes O(logn). So, option D is correct.

## 22. Which of the following statement about binary tree is correct?

1. Every binary tree is either complete or full
2. Every full binary tree is also a complete binary tree
3. Every complete binary tree is also a full binary tree
4. A binary tree cannot be both complete and full

Explanation: Every full binary tree is also a complete binary tree. So, option B is correct.

## 23. In a full binary tree if number of internal nodes is I, then number of leaves L are?

1. L = 2I
2. L = I + 1
3. L = I – 1
4. L = 2I – 1

Explanation: In a full binary tree if number of internal nodes is I, then number of leaves L are L = I + 1.

## 24. What is the number of edges present in a complete graph having n vertices?

1. (n*(n+1))/2
2. (n*(n-1))/2
3. n
4. Given information is insufficient

Explanation: Number of ways in which every vertex can be connected to each other is nC2. The number of edges present in a complete graph having n vertices is (n*(n-1))/2. So, option B is correct.

## 25. Suppose a binary tree is constructed with n nodes, such that each node has exactly either zero or two children. The maximum height of the tree will be?

1. (n-1)/2
2. (n+1)/2
3. n/2 -1
4. (n+1)/2 -1

Explanation: (n-1)/2

## 26. Which of the following statements for a simple graph is correct?

1. Every trail is a path
2. Every path is a trail
3. Every trail is a path as well as every path is a trail
4. None of the above mentioned

Explanation: In data structures, in a walk, if the vertices are distinct it is called a path, whereas if the edges are distinct it is called a trail. So, option B is correct.

## 27. Which of the following ways can be used to represent a graph?

1. Incidence Matrix
4. No way to represent

Explanation: A graph can be represented through some ways including: Adjacency List, Adjacency Matrix as well as Incidence Matrix.

## 28. If all c( i , j )’s and r( i, j )’s are calculated, then OBST algorithm in worst case takes one of the following time:

1. O(log n)
2. O(n^2)
3. O(n log n)
4. O(n^3)

Explanation: O(n^3)

## 29. The postfix form of the expression (A+ B)*(C*D- E)*F / G is?

1. AB+ CD*E – FG /**
2. AB + CD* E – F **G /
3. AB + CD* E – *F *G /
4. AB + CDE * – * F *G /