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

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.

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

110年 - [非官方正解]110 國立臺灣大學_碩士班招生考試_電信工程研究所丙組:資料結構與演算法(B)#113108

110年 - [非官方正解]110 國立中央大學_碩士班招生考試_資工類：資料結構與演算法#105890

109年 - 109 東吳大學_轉學生招生考試_資訊管理學系三年級︰資料結構#105850

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