8.Given a weighted directed graph G = (V,E, w) with no negative-weight edges, we can solve its single source shortest path problem in O(V + E) time.
(A)O
(B)X

9. Given a weighted directed graph G = (V,E,w), we can determine whether a negative-weight cycle exists in G in O(V + E) time.(A)O(B)X

10. Every problem in NP can be solved in exponential time. Please choose the best possible answer in each of the following qucstions. In questions that ask for time complexities, please choose the tightest bound.(A)O(B)X

11.Which of the following is correct? (A) (B) (C)(D)

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

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

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

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

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