Practice Exam #3, Math 100, Professor Wilson
MULTIPLE CHOICE. Choose the one alternative that best completes the statement or answers the question.
1) A tree is
A) any graph that is connected and every edge is a bridge.
B) any graph that has no circuits.
C) any graph with one component.
D) any graph that has no bridges.
E) None of the above
2) Graph 1 is connected and has no circuits. Graph 2 is such that for any pair of vertices in the graph there is one
and only one path joining them.
A) Graph 1 cannot be a tree; Graph 2 cannot be a tree.
B) Graph 1 must be a tree; Graph 2 may or may not be a tree.
C) Graph 1 must be a tree; Graph 2 must be a tree.
D) Graph 1 must be a tree; Graph 2 cannot be a tree.
E) None of the above
3) Suppose T is a tree with 21 vertices. Then
A) T has one bridge.
B) T has no bridges.
C) T can have any number of bridges.
D) T has 20 bridges.
E) None of the above
4) How many spanning trees does the following graph have?
A) 1
B) 2
C) 3
D) 4
E) None of the above
Figure 7.10
The question(s) that follow refer to the problem of finding the minimum spanning tree for the weighted graph shown
below.
5) In Figure 7.10, using Kruskal's algorithm, which edge should we choose first?
A) AB
B) EG
C) BE
D) AG
E) None of the above
6) In Figure 7.10, using Kruskal's algorithm, which edge should we choose third?
A) EF
B) AG
C) BG
D) EG
E) None of the above
7) In Figure 7.10, using Kruskal's algorithm, which edge should we choose last?
A) None of the above
B) AB
C) AC
D) C D
E) BC
8) In figure 7.10, which of the following edges of the given graph are not part of the minimum spanning tree?
A) AC
B) EF
C) AG
D) BG
E) None of the above
9) In Figure 7.10, the total weight of the minimum spanning tree is
A) 36.
B) 42.
C) 55.
D) 95.
E) None of the above
10) Which of the following statements is true about Kruskal's algorithm.
A) It is an inefficient algorithm, and it never gives the minimum spanning tree.
B) It is an efficient algorithm, and it always gives the minimum spanning tree.
C) It is an efficient algorithm, but it doesn't always give the minimum spanning tree.
D) It is an inefficient algorithm, but it always gives the minimum spanning tree.
E) None of the above
Figure 8.1
For the following question(s), refer to the digraph below.
11) In Figure 8.1, which of the following is not a path from vertex E to vertex B in the digraph?
A) E, B, C, B
B) E, D, B
C) E, A, B
D) E, A, C, B
E) All of the above are paths from A to E.
12) The critical path algorithm is
A) an approximate and inefficient algorithm.
B) an optimal and efficient algorithm.
C) an approximate and efficient algorithm.
D) an optimal and inefficient algorithm.
E) None of the above
Situation 8.3
Suppose you have the following project digraph. (The numbers in parenthesis represent hours.)
13) In Situation 8.3, what is the number of tasks in this project?
A) 7
B) 11
C) 6
D) 9
E) None of the above
14) In Situation 8.3, what is the number of direct precedence relations in this project?
A) 6
B) 7
C) 11
D) 9
E) None of the above
15) In Situation 8.3, the length of the critical path from A is
A) 14 hours.
B) 5 hours.
C) 6 hours.
D) 11 hours.
E) None of the above
16) In Situation 8.3, the length of the critical path of this project digraph is
A) 11 hours.
B) 14 hours.
C) 12 hours.
D) 16 hours.
E) None of the above
17) In Situation 8.3, if we use the priority list F, E, A, D, B, G, C and the priority-list model to schedule this project
with two processors, we should start by assigning
A) task B to one processor, task E to the other one.
B) task A to one processor, task C to the other one.
C) task A to one processor, task B to the other one.
D) task B to one processor, task C to the other one.
E) None of the above
18) In Situation 8.3, if we use the priority list F, E, A, D, B, G, C and the priority-list model to schedule this project
with two processors, the project completion time is
A) 21 hours.
B) 19 hours.
C) 20 hours.
D) 18 hours.
E) None of the above
19) In Situation 8.3, using the critical path algorithm to schedule this project with two processors, the project
completion time is
A) 20 hours.
B) 17 hours.
C) 18 hours.
D) 19 hours.
E) None of the above
20) In Situation 8.3, using the critical path algorithm to schedule this project with three processors, the project
completion time is
A) 11 hours.
B) 12 hours.
C) 13 hours.
D) 14 hours.
E) None of the above
Answer Key, Practice Exam #3
1) Answer: A
2) Answer: C
3) Answer: D
4) Answer: C
5) Answer: C
6) Answer: A
7) Answer: C
8) Answer: D
9) Answer: C
10) Answer: B
11) Answer: A
12) Answer: C
13) Answer: A
14) Answer: A
15) Answer: D
16) Answer: B
17) Answer: C
18) Answer: A
19) Answer: C
20) Answer: D
