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 i^th 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).

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))

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.

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.

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

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