12. Let f(n) and g(n) be two asymptotically non-negative functions. Which of the following is always true?
(A)
(B)
(C)
(D)

13. Consider a divide-and-conquer algorithm, which solves a problem of size n by dividing it into two subproblems of size n/3 and n/5, respectively. The solutions of the subproblems are then combined in θ(n2) time. Which of the following is correct about the time complexity T(n) of this algorithm? (A) T(n) must be in θ(n2). (B) T(n) must be in O(n2) but not nec ssarily in Ω(n2). (C) T(n) must be in Ω(n2) but not necessarily in O(n2). (D)None of the above. The complexity of T(n) depends on the exact valuc of n. 

14. Consider an array of size n with perfectly inversely sorted order. Which of the following is correct about the running times to sort this array (deterministically)? (A) Quicksort: O(n ign)； Merge Sort: O(n ign)； Insertion Sort: O(n2) (B) Quicksort: 0(n2)； Merge Sort: O(n2)； Insertion Sort: 0(n2) (C) Quicksort: O(n2)； Merge Sort: O(n lgn)； Insertion Sort: O(n lgn) (D) Quicksort: 0(n2)； Merge Sort: O(n lgn)； Insertion Sort: O(n2)

複選題15. Consider the problem of making change for n cents using the fewest number of coins. An algorithm to solve this problem is to give the coin with the highest available denomination without going over, and repeat the process until the amount of remaining change drops to O. Which of the following sets of available coin denominations would cause this algorithm to fail at yielding an optimal solution? (A) {1,3} (B) {1,3,4,5} (C) {1,5,10, 25} (D) {c0,c1,..,..ck) for any set of integers c > 1 and k ≥1

16. Which of the following algorithms can be used to most efficiently determine the presence of a cycle in a given graph? (A) Depth First Search (DFS) (B)Breadth First Search (BFS) (C) Prim's Minimun Spanning Tree (MST) Algorithm (D) Kruskal's Minimum Spanning Tree (MST) Algorithm

17. Consider the following undirected connected graph. What is the total weight of its maximum spanning tree?  (A)23(B)24(C)25(D)26

18. Suppose we run Dijkstra's single-source shortest-path algorithm on the following weighted directed graph with vertex a as the source. In what order do the nodes get included into the set of verticcs for which the shortest path distances are finalized?(A)  a, b, c, d, e,f (B) a, b, c,f, d,e (C) a, b, c, f,e, d (D) a, b, e,  c, f, d

19. Let G be a graph represented using adjacency matrix with n vertices and m cdges. What is the tightest upper bound on the running time of depth-first search (DFS) on this graph? (A) 0(n) (B) 0(m+n) (C) 0(n2) (D) 0(mn)

20. Assume P ≠NP. Which of the following is true? (A)(B)NP-complete = NP (C) NP-hard -NP (D) P=NP-complete

21. Let S be an NP-complete problem and Q and R be two other problems not known to be in NP. Q is polynomial-time reducible to S and S is polynomial-time reducible to R. Which of the following statements is true? (A)R is NP-complete. (B) Ris NP-hard. (C) Ois NP-complete. (D) Q is NP-hard.

22. Suppose you can take any arbitrary portion of cach item. What is the highest total value you can get by filling your knapsack? (A) 184 (B) 100(C)90 (D) 84

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

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

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

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