104年 - 104 國立交通大學_碩士班考試入學試題_資訊聯招：資料結構與演算法#113199

1. The transitive closure matrix of the given directed graph have k elements that are 1's. What is true about k?
(A)k≤6 (B)7≤k≤10(C)11≤k≤14(D)15≤k≤18(E)k≥19

3. Below is the C++ implementation of ADTX, an unknown abstract data type. For clarity, exception handling codes are omitted. Which of the following is the most likely abstract data type implemented here?
(A) stack(B) first-in-first-out queue (C) priority queue (D) linked list (E) none of the above

4. For the ADTX implementation in the previous question, after the following C++ code is executed, what is the value in adtx. x[1]?
(A)6(B)9(C)3(D)7 (E)5 

5. For the postorder traversal sequence of the binary tree below, which of these statements is true?
(A) Node B appears at the second position. (B) Node M appears after node D. (C) Node H appears immediately before node J. (D) The first four nodes in the sequence are all leaf nodes in the tree. (E) Node A appears between node B and node D.

9. A max-heap is given below； the numbers at the nodes are their keys. Now after one insertion operation (the number inserted is 14) and then one deletion operation, which of the following statements is false regarding the resulting heap? Here node (n) represents the node with key n.
(A) The parent of node (4) is node (11). (B) node (13) has two children. (C) The position of node (10) in the tree does not change. (D) node (17) is the root. (E) The number of leaf nodes does not change.

10. For a doubly-linked list class, each of its nodes has two links left and right to its two neighboring nodes. Assume that we want to implement a member function ShiftRight, which takes an input x, a pointer to a node, and swaps that node with the node to its right. Let us further assume that neither xx nor the node to its right is the first or the last node of the list. There are six pointers to be set, and the statements, labeled s1 to s6, are listed in the box below. Which of the following ordering of these statements will produce the correct behavior?
(A)s5→s2→s6→s1→s4→s3 (B)s2→s5→s4→s3→s1→s6 (C)s4→s3→s6→s1→s2→s5 (D)s1→s2→s3→s6→s5→s4 (E)s4→s5→s3→s6→s1→s2

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

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 2^f(n) =O(2^g(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(n^c)=O(Ign) for constantc＞0 (C) n^c=O(aⁿ) 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))

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

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/log²n, 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) θ(n²logn) (D) θ(nlogn) (E) θ(logn)²)

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

35. Complete the pseudo code below for the counting sort algorithm. We assume 

Input: A[1. . n],where A[j] {0, 1, , k} forj = 1, 2,..., n. Array A and values n and k are given as parameters.
Output: B[1 . . n], sorted. B is assumed to be already allocated and is given as a parameter.
Auxiliary storage: C[O . . k]
COUNTING-SORT(A, B, n, k)
   (A) (B)(C) (D)(E)

36. For a chain of matrix A₁A₂A₃A₄ with their dimensions in the following table, parenthesize the product A₁A₂A₃A₄ to minimize the number of scalar multiplications. What is the minimum number of scalar multiplications?
(A)82 (B)72 (C)112 (D)99(E)70

38. Professor Chen uses the following algorithm for merging k sorted lists, each having n/k elements. He takes the first list and merges it with the second list using a linear-time algorithm for merging two sorted lists, such as the merging algorithm used in merge sort. Then, he merges the resulting list of 2n/k elements with the third list, merges the list of 3n/k elements that results with the fourth list, and so forth, until she ends up with a single sorted list of all elements. What is the worst-case running time of the professor Chen's algorithm in terms of n and k. (A)θ(log(nk))(B)θ(nk) (C)θ(nlogk) (D)θ(lognlogk) (E)θ(n)

39. A hiker faces the Knapsack problem. There are 7 items to be packed into the knapsack, each with value viand weight w_i as shown in the following table.

The knapsack, which is initially empty, can hold a maximum weight of 16, so some item(s) must be left

behind. The optimality criterion is to maximize the total value of the items that are placed in the knapsack.The hiker fills the knapsack one item at a time. Now consider the following two cases: (a) fractions of items cannot be packed, and (2) fractions of items can be packed. What are the optimal values of the items that are packed in these two cases respectively?

Give the answer in the form of (no-fractions-allowed, fractions-allowed).

(A)(28,30.5) (B)(37,40)(C)(30,34) (D)(38,40) (E)(34,38.5)

40. Determine the expected search cost of an optimal binary search tree for a set of n = 5 keys with the following probabilities. We assume that all searches are successful. (A) 2.15 (B)1.15 (C)2.10 (D) 1.10 (E) 2.0