27. 1og(n!) is asymptotically equal to
(A) θ(n)
(B) θ(nlog(logn)
(C) θ(n²logn)
(D) θ(nlogn)
(E) θ(logn)²)

23. Which of the following algorithms can sort n data in O(n log n) worst-case time? (A) bubble sort (B) quick sort (C) merge sort (D) both quick sort and merge sort (E) both heap sort and bubble sort.

24. Let G=(V, E) be an undirected graph with n vertices, where n ＞1, and M be the adjacency matrix of G. Which of the following statements is not correct? (A) M is a 2-dimension nxn array. (B) M is symmetric. (C) The degree of any vertex i is equal to the ith row sum. (D) The graph has an even number of vertices of odd degree. (E) The number of edges of G is equal to M(i, j).

25. Assume that T(n) is constant for sufficiently small n. Which one of the following statements is correct? (A) T(n)=2 T(n2) + nlogn,then T(n)=θ(nlogn). (B) T(n)=2 T(n2)+n/logn,then T(n)=θ(n). (C) T(n)=2T(n2) +n/log2n, then T(n)=θ(n). (D) T(m)=T(n-1)+, then T(n)=θ(nlogn). (E) T(n)= T(n-1) + nlogn, then T(n)=θ(nlogn).

26. Let G =(V, E) be an undirected connected graph, where each edge e has a given length I(e)＞ 0. Let s be a fixed vertex of this graph and let δ(v) be the length of a shortest path from s tov. Which one of the following statements is not correct? (A) For each vertex v ≠s, there is an incident edge e=(u,v) such that  δ(V)=δ(น)+l(e). (B) For each vertex v≠s, choose one incident edge e=(u,v) such that δ(V)=δ(น)+l(e),the collection of these edges forms a spanning tree of G. (C) For each vertex v≠s, choose one incident edge e=(u,y) such that δ(V)=δ(น)+l(e),the collection of these edges forms a minimum weight spanning tree of G. (D) Bellman-Ford algorithm can find a shortest path from s to v in this case. (E) Dijkstra's algorithm can find a shortest path from s to v in this case.

28. Which one of the following statements is not correct? (A) If an edge is contained in some minimum spanning tree, then it is a light edge crossing some cut of the graph. (Definition: An edge is a light edge crossing a cut if its weight is the minimum of any edge crossing the cut.) (B) If a graph has a unique minimum spanning tree then, for every cut of the graph, there is a unique light edge crossing the cut. (C) A graph has a unique minimum spanning tree if, for every cut of the graph, there is a unique light edge crossing the cut. (D) Let e be a maximum-weight edge on some cycle of the graph G = (V, E), then there is a minimum spanning tree of G' = (V, E-{e}) that is also a minimum spanning tree of G = (V, E). (E) Let (u, ) be a minimum-weight edge in a graph G. Then (u, v) belongs to some minimum spanning tree of G.

29. The digraph shown below is a flow network from source s to sink t, where the number on each edge represents the edge capacity. What is the minimum cut capacity between s and t? (A)20(B)21 (C)22 (D)23 (E)24

30. The digraph shown below is a flow network from source s to sink t, where the number on each edge represents the edge capacity. What is the value of the maximum flow from s to t?(A)19(B)20 (C)21 (D)22 (E)23

31. Which of the following algorithm employs dynamic programming? (A)Prim's algorithm for finding a minimum spanning tree (B) Dijksta algorithm for solving the single source shortest paths problem (C) Floyd-Warshall for solving the all pair shortest paths problem (D)Hufiman algorithm for constructing a Hufiman code (E) Kruskal's algorithm for finding a minimum spanning tree

32. Which of the following are false? i. The worst-case running time and expected running time are equal to within constant factors for any randomized algorithm. ii. Sorting 6 elements with a comparison sort requires at least 10 comparisons in the worst case. iii. In Blum, Floyd, Pratt, Rivest, and Tarjan [1973] worst-case linear-time order statistics algorithm, instead of dividing the n elements into groups of 5, dividing them into groups of 3 gives the same linear time complexity. iv. If a dynamic programming problem satisfies the optimal substructure property, then a locally optimal solution is a globally optimal. (A)i (B)i,iii,iv (C)i,ii；,iv (D)ii,iv (E)iii,iv

33. Which of the following are true? i. The maximum flow problem is in P ii. If a problem is in P, it must also be in NP iii. If a problem is in NP, it must also be in P iv. If a problem is NP-complete, it must also be in NP (A) i,ii (B)i,ii,ii；,iv (C)i,ii,iv (D)i,ii,iv (E)i,iv