## Discrete Mathematics Questions and Answers – Tree

This section focuses on "Tree" in Discrete Mathematics. These Multiple Choice Questions (MCQ) should be practiced to improve the Discrete Mathematics skills required for various interviews (campus interviews, walk-in interviews, company interviews), placements, entrance exams and other competitive examinations.

1. A Tree is a connected?

A. cyclic undirected graph

B. acyclic undirected graph

C. acyclic directed graph

D. cyclic directed graph

View Answer

Ans : B

Explanation: A Tree is a connected acyclic undirected graph.

2. A tree with N number of vertices contains?

A. (N-1) Edges

B. (N^2)-1 Edges

C. N Edges

D. (N+1) Edges

View Answer

Ans : A

Explanation: A tree with N number of vertices contains (N−1) number of edges.

3. The vertex which is of 0 degree is called?

A. Leaf

B. Root

C. Internal node

D. None of the above

View Answer

Ans : B

Explanation: The vertex which is of 0 degree is called root of the tree. The vertex which is of 1 degree is called leaf node of the tree and the degree of an internal node is at least 2.

4. A ___________ tree is a tree the vertices of which are assigned unique numbers from 1 to n.

A. Bi-Centers

B. Centers

C. Unlabeled

D. labeled

View Answer

Ans : D

Explanation: A labeled tree is a tree the vertices of which are assigned unique numbers from 1 to n.

5. number of edges incident with the vertex V is called?

A. O(n)

B. O(log n)

C. O(n^2)

D. O(nlog n)

View Answer

Ans : A

Explanation: Insertion Complexity : Average complexity O(log n) and worst case O(n).

6. What is Space Complexity for Binary search tree?

A. O(n)

B. O(log n)

C. O(n^2)

D. O(nlog n)

View Answer

Ans : A

Explanation: Space Complexity : Average complexity O(n) and worst case O(n).

7. The number of labeled trees of k number of vertices is?

A. k^(n-1)

B. k^(n-2)

C. k^(2)

D. k^(n)

View Answer

Ans : B

Explanation: The number of labeled trees of k number of vertices is k^(n-2).

8. A linear graph consists of vertices arranged in a line.

A. TRUE

B. FLASE

C. either true or false

D. cannot determined

View Answer

Ans : B

Explanation: A linear graph also known as a path graph is a graph which consists of k vertices arranged in a line, so that vertices from i and i+1 are connected by an edge for i=0,…, k-1.

9. What is true about star tree?

A. A tree having n vertices arranged in a line

B. A tree which contains n vertices and n-1 cycles

C. A tree having a single internal vertex and n-1 leaves

D. A tree which has 0 or more connected subtrees

View Answer

Ans : C

Explanation: A star tree of order n is a tree with as many leaves as possible or in other words a star tree is a tree that consists of a single internal vertex and n-1 leaves. However, an internal vertex is a vertex of degree at least 2.

10. If a tree has only one eccentricity, it is called

A. Bi-Centers

B. Labeled Trees

C. Rooted Tree

D. Central Tree

View Answer

Ans : D

Explanation: If a tree has only more than one centers, it is called Bi-central Tree.

Discussion