16. Consider the graph in the previous problem. Let dist(i, j) be the length of the shortest path from node i to node j. What is dist(A,F)+dist(B,F) +dist(C,F)+dist(D,F)+dist(E,F)?
(A)7
(B)8
(C)9
(D)10
(E) none of the above

12. Consider the Red-Black tree resulting from sequentially inserting the following numbers into an empty Red-Blacktree:40 60 55 15 20 5 25 30What is the sum of the numbers in the red nodes in the Red-Black tree? (A)90 (B) 130 (C) 155 (D) 160 (E) none of the above

13. Consider the B-tree, say T', resulting from sequentially inserting the following numbers into the following B-tree T with order 3:  15 20  5  25 30 What is the sum of the keys in the non-leaf nodes in T'? (A) 95 (B) 100 (C) 110 (D) 120 (E) none of the above

14. Consider the B+-tree, say T', resulting from sequentially inserting the following numbers into the following B+-tree T with order 3:  15 20 5 25 30 What is the sum of the keys in the non-leaf nodes in T'? (A) 95(B) 100 (C) 110(D) 120(E) none of the above

15. Consider the given directed graph. Let dist(i, j) be the length of the shortest path from node i to node j. What is dist(A,C)+dist(A,E)+dist(A,F)?(A) 10 (B) 12 (C) 13 (D) 15 (E) None of the above.

17. Consider the following activity network. What is the length of the critical path?(A)14 (B) 16 (C) 18(D) 20(E) none of the above

18. Consider six nodes with weights 2, 4, 6, 8, 10 and 12, respectively. Give the weighted external path length of the Hufiman tree with the above six nodes as external nodes. (A)95 (B) 100(C) 102 (D)104 (E) none of the above

19. Consider an empty hash table with 10 buckets and each bucket has 2 slots. Suppose that linear probing is used to handle overflow and the following is used as the hash function: h(n) =n % 10.Now we sequentially insert the following numbers into the hash table:5 15 23 44 3 53 6 4 109 What is the summation of the numbers in the full buckets of the hash table? (A) 153 (B) 150 (C) 262 (D) 43 (E) none of the above

20. What is the cost of minimum cost spanning tree of the given graph?(A) 28 (B) 30 (C) 32 (D) 33 (E) none of the above

21. Let f(n) and g(n) be positive functions. Notation: Ign=logn=1og2n. Which one of the following statements is not correct?  (A)f(n) = O(g(n) implies 1g(f(n))=0(1g(g(n), where lg(g(n) ≥ 1 and f(1) ≥1 for all sufficiently large n. (B) f(n)=0(8(n)) implies 2f(n) =O(2g(n) (C) f(n)+o(f(n)=θ(f(n)) (D) [log(logn)]!= O(n) (E) If log f(n)=θ(logn),then f(n) is polynomially bounded.

22. Let f(n) and g(n) be asymptotically positive functions. T(n) is the time an algorithm takes for an input of size n. Which one of the following statement is not correct? (A) For the two functions (n) and g(n), either (n)-O(g(n)) or (n)=Ω(g(n)) (B) 1g(nc)=O(Ign) for constantc＞0 (C) nc=O(an) for constants c＞0 and a＞1 (D) For any uniform cost RAM program T(n) =Ω(S(n), where S(n) is the space an algorithm uses for an input of size n (E) max(f(n),g(n))=θ(f(n)+g(n))