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