PRACTICE TEST
Chapter 12: Trees and Networks
INSTRUCTIONS: Answer each question below. Once you finish taking the test, check
the answers provided in the Answer Key at the end of this test.
1. If a tree has more than one vertex, it must have at least how many vertices of
degree 1?
A: 0
B: 1
C: 2
D: none of the above
2. How many edges will a tree with 50 vertices have?
A: 49
B: 50
C: 51
D: none of the above
3. Given a graph G with n vertices, which of the following statements characterize a
tree?
A: If u and v ate two vertices in G, then there exists only one path from u to v.
B: G is a connected graph and has exactly n-1 edges.
C: G has no cycles and exactly n-1 edges.
D: all of the above
4. What is the number of non-isomorphic trees with four vertices?
A: 1
B: 2
C: 3
D: none of the above
5. What is the number of non-isomorphic trees with six vertices?
A: 4
B: 5
©2010 Cengage Learning Asia Pte Ltd
C: 6
D: none of the above
6. Suppose a tree has 99 edges, how many vertices does it have?
A: 98
B: 99
C: 100
D: none of the above
7. Suppose a tree has 75 vertices, what is the sum of the degrees in the tree?
A: 148
B: 149
C: 150
D: none of the above
8. Suppose T is a tree with a vertex of degree 7, then T must have at least how many
vertices of degree one?
A: 6
B: 7
C: 8
D: none of the above
For exercises 9 through 12,
9. How many leaves does T have?
A: 2
B: 6
C: 10
D: none of the above
10. What is the height of the tree?
A: 2
©2010 Cengage Learning Asia Pte Ltd
B: 3
C: 4
D: none of the above
11. What labeled vertex (vertices) is a descendant of the vertex c?
A: a
B: e
C: a and e
D: none of the above
12. The vertex labeled d is on what level of T?
A: 1
B: 2
C: 3
D: none of the above
13. Suppose T is a full binary tree with 25 internal vertices, how many vertices does
T have?
A: 26
B: 50
C: 51
D: none of the above
14. Suppose T is a binary tree with 64 terminal vertices then what is the least height
that T may have?
A: 7
B: 8
C: 9
D: none of the above
For exercises 15 through 17,
©2010 Cengage Learning Asia Pte Ltd
15. The inorder sequence for T is:
A: 1, 2, 3, 7, 5, 3, 6
B: 4, 7, 2, 5, 1, 6, 3
C: 7, 4, 5, 2, 6, 3, 1
D: none of the above
16. The preorder sequence for T is:
A: 1, 2, 3, 7, 5, 3, 6
B: 4, 7, 2, 5, 1, 6, 3
C: 7, 4, 5, 2, 6, 3, 1
D: none of the above
17. The postorder sequence for T is:
A: 1, 2, 3, 7, 5, 3, 6
B: 4, 7, 2, 5, 1, 6, 3
C: 7, 4, 5, 2, 6, 3, 1
D: none of the above
18. What is the average number of vertices visited in a search of a binary search tree
with n vertices?
A: (n2)
B: (n)
C: (lg n)
D: none of the above
19. Evaluate the post fix expression 2 5 7 3 + x
A: 30
B: 2
C: -30
D: none of the above
20. Evaluate the prefix expression × - 2 5 + 7 3
A: 210
B: 31
©2010 Cengage Learning Asia Pte Ltd
C: -30
D: none of the above
21. Convert infix expression (x + y)z – a(b+c) to postfix.
A: x y + z – a b c + × -
B: x y + z × a b c × + -
C: x y + z × a b c - × +
D: none of the above
22. What is Prim's algorithm in the worst case?
A: O(n lg n)
B: O(n2)
C: O(n3)
D: none of the above
23. When does a graph G have a spanning tree?
A: always
B: whenever G is connected
C: cannot be determined
D: none of the above
24. If a graph G with n vertices has two spanning trees which are edge disjoint then
G must have at least how many edges?
A: 2n -2
B: 2n
C: 3n-3
D: none of the above
25. If a binary tree has 72 vertices what is the maximum height of the tree?
A: 6
B: 7
C: 71
D: none of the above
26. If a binary tree has 72 vertices what is the minimum height of the tree?
©2010 Cengage Learning Asia Pte Ltd
A: 6
B: 7
C: 71
D: none of the above
27. If a binary search tree is built from the input list 2 4 6 8 10 12 14, what is the
height of the tree?
A: 2
B: 5
C: 6
D: none of the above
28. If a binary search tree is built from the input list 8 4 12 2 14 6 10, what is the
height of the tree?
A: 2
B: 5
C: 6
D: none of the above
29. For the transport network below find a maximal flow.
A: 10
B: 11
C: 12
D: none of the above
30. What is the weight of a minimal spanning tree for the graph below?
©2010 Cengage Learning Asia Pte Ltd
A: 16
B: 18
C: 20
D: none of the above
©2010 Cengage Learning Asia Pte Ltd
Answers:
1. C 2. A 3. D 4. B 5. B 6. C 7. A 8. B 9. B 10. C
11. B 12. B 13. C 14. A 15. B 16. D 17. C 18. C 19. C 20. C
21. B 22. C 23. B 24. A 25. C 26. A 27. D 28. B 29. B 30. B
©2010 Cengage Learning Asia Pte Ltd
