Final Exam Math 106 Fall 06 Instructor: Jeff Lang MULTIPLE CHOICE. Choose the one alternative that best completes the statement or answers the question. Use the figure below to answer the following question(s). 1) The number of paths from A to D is A) 4. B) 5. C) 3. D) 2. E) None of the above 1) 2) The number of bridges in this graph is A) 2. B) 0. C) 3. D) 1. E) None of the above 2) 3) This graph has A) an Euler circuit that starts at A. B) a Hamilton path that beins at A. C) a Hamilton circuit that starts at A. D) 5an Euler path that starts at A. E) None of the above 3) Use the figure below to answer the following question(s). 4) The graph A) has a single Hamilton circuit (and its mirror-image circuit). B) has several Hamilton circuits, none of which contain the edge BD. C) has several Hamilton circuits, all of which contain the edge AG. D) has no Hamilton circuit. E) None of the above 4) 1 A delivery truck must deliver furniture to 4 different locations (A, B, C, and D). The trip must start and end at A. The graph below shows the distances (in miles) between location. We want to minimize the total distance traveled. 5) The cheapest-link algorithm applied to the graph yields the following solution: A) A, B, D, C, A. B) A, D, C, B, A. C) A, C, B, D, A. D) A, D, B, C, A. E) None of the above 5) A delivery truck must deliver furniture to 4 different locations (A, B, C, and D). The trip must start and end at A. The graph below shows the distances (in miles) between location. We want to minimize the total distance traveled. 6) The nearest-neighbor algorithm applied to the graph yields the following solution: A) A, D, C, B, A. B) A, B, D, C, A. C) A, C, B, D, A. D) A, D, B, C, A. E) None of the above 6) A delivery truck must deliver packages to 5 different store locations (A, B, C, D, and E). The trip must start and end at A. The graph below shows the distances (in miles) between locations. We want to minimize the total distance traveled. 7) How many different Hamilton circuits would we have to check if we use the brute-force algorithm? (Do not count the same circuit traveled backward.) A) 4 B) 30 C) 60 D) 12 E) None of the above 7) 2 Solve the problem. 8) A tree is A) any graph that has no bridges. B) any graph that is connected and has no circuits. C) any graph with one component. D) any graph that has no circuits. E) None of the above 8) 9) How many spanning trees does the following graph have? A) 18 B) 10 C) 17 D) 19 E) None of the above 9) The question(s) that follow refer to the problem of finding the minimum spanning tree for the weighted graph shown below. 10) The total weight of the minimum spanning tree is A) 34. B) 49. C) 39. D) 60. E) None of the above 10) Suppose you have the following project digraph. (The numbers in parenthesis represent hours.) 11) The length of the critical path from E is A) 2 hours. B) 9 hours. C) 8 hours. D) 6 hours. E) None of the above 11) 3 Suppose you have the following project digraph. (The numbers in parenthesis represent hours.) 12) Consider the following schedule using three processors. A) This schedule is an optimal schedule for three processors. B) This schedule is an illegal schedule because task E was started before task C was completed. C) This schedule is not an optimal schedule because the project can be scheduled with a completion time of 11 hours. D) This schedule is an illegal schedule because task F was started before task E was completed. E) None of the above 12) Suppose you have the following project digraph. (The numbers in parenthesis represent hours.) 13) Using the priority list, C, E, G, F, B, A, D and the priority-list model to schedule this project with two processors results in a completion time of A) 21 hours. B) 26 hours. C) 24 hours. D) 22 hours. E) None of the above 13) In the following question(s), F N represents the Nth Fibonacci number. 14) If F 500 = a and F 501 = b, then F 505 = A) 2a + 3b. B) a + b. C) 3a + 5b. D) a + 2b. E) None of the above 14) 4 Solve the problem. 15) Rectangle A is 25 by 50. Rectangle B is a gnomon to rectangle A. The dimensions of rectangle B are A) 50 by 75. B) 25 by 50. C) 50 by 50. D) 50 by 100. E) None of the above 15) 16) If the shaded "rectangular ring" is a gnomon to the white rectangle, then x = A) 3. B) 15. C) 10. D) 20. E) None of the above 16) 17) 5 + 8 + 11 + 14 + . . . = 321 terms A) 155,685 B) 308,800 C) 154,400 D) 311,370 E) None of the above 17) 18) The 100th term in the arithmetic sequence 3, 7, 11, 15, . . . is A) 399. B) 403. C) 103. D) 407. E) None of the above 18) 19) 1 + 4 + 4 2 + 4 3 + . . . + 4 217 = A) 4 218 - 1 3 B) 4 218 C) 4 218 3 - 1 D) 4 216 - 1 3 E) None of the above 19) 5 The figure below is a square ABCD with center O. (M, N, P, and Q are the midpoints of the sides.) 20) A translation sends the point A to the point Q. The image of P under this translation is A) O. B) B. C) N. D) C. E) None of the above 20) Solve the problem. 21) The letter C has the same symmetry type as the letter A) B. B) A. C) X. D) Q. E) None of the above 21) The figure below is a regular hexagon ABCDEF with center O. (P, Q, R, S, T and U are the midpoints of the sides.) 22) A glide reflection sends the point A to the point D and the point B to the point O. The image of C under this glide reflection is A) U. B) F. C) P. D) S. E) None of the above 22) 6 The table below shows the scores of a group of students on a 10 point multiple choice placement test. Exam Score Frequency 3 4 5 6 7 8 9 10 5 3 5 2 7 6 1 1 23) The average score on the test is A) 5. B) 5.5. C) 6.5. D) 6. E) None of the above 23) 24) The first quartile on the test is A) 5.5. B) 4.5. C) 5. D) 4. E) None of the above 24) Use the data set {-1, -3, -5, -7, 0, 0, 7, 9} to answer the following question: 25) The 15th percentile of the eight numbers is A) -5. B) -3. C) -4. D) -2. E) None of the above. 25) 7 Jeffrey Lang Final.tst