複選題
(49) Let N=10, then which is correct about the corresponding abc?
(A)a=4
(B) a+b=6
(C) b+c=2
(D) b=2
(E) atb+c=7.

複選題(50) Let N=18, then what is correct about the corresponding abc? (A)a+b+c=12(B) a+b=10 (C)b+c=7 (D) a=6 (E) b=4.

(51) Which of the followings is wrong about this representation of N? (A) There can be more than one digit for a. (B) The representation can be found by a greedy algorithm. (C) We can use it as a number system to represent positive integers. (D) This representation can be generalized as N= Bino(a, 4) + Bino(b, 3) + Bino(c, 2)+ Bino(d, 1), where a ＞ b＞ c＞ d ＞=0. (E) The representation may not be unique for some positive N.

(52) What can the procedure mystery() find ? (A) shortest path tree (B) all pairs of shortest paths (C) minimum cut (D) minimum spanning tree (E) a maximum matching.

(53) If we change the statement (*) into "if (distance[w] ＞ (distance[v]+weight))}" and the statement (**) into "distance[w]=distance[v]+ weight；", then what can the procedure mystery() find ? (A) shortest path tree (B) all pairs of shortest paths (C) minimum cut (D) minimum spanning tree (E) none of the above.

(54) What is the most accurate time complexity of the procedure mystery/, if there are n vertices and m edges? (A) O(mlog n) (B)O(m) (C)O(mn2) (D)O(n log n) (E)O(n2 +(m+n)).

(55) Which of the following statements is wrong? (A) A problem is NP-complete, if it belongs to the class NP and all the other members in NP can be reduced to it in polynomial time. (B) Problem I belongs to NP. (C) Problem III belongs to NP. (D) Problem III is NP-complete. (E) If we change the graph in Problem IlI to directed graph, then it belongs to P.

複選題(56) Which of the followings is wrong? (A) If a spanning tree has the maximum degree as 2, then it is a Hamiltonian path. (B)If Problem III can be solved in polynomial time, then we can find a Hamiltonian path in polynomial time. (C) Problem I can be solved with the Prim's algorithm.. (D) A graph can have more than one spanning tree. (E) If P=NP, then Problem II can be solved in polynomial time.

複選題(57) Continuing the previous question, which of the following is wrong? (A) Problem II can be solved with the Floyd-Warshall algorithm. (B) An algorithm for Problem III can be used to find the longest path of a graph. (C) If there is an algorithm that can find the longest path in a graph in polynomial time, then Problem III can be solved in polynomial time. (D) Problem III can be reduced to Problem II by making each weight negative and thus can be solved with the Bellman-Ford algorithm. (E) If Problem IIlI can be solved in polynomial time, then P=NP.

(58) Which of the following statements is wrong? (A) By the Ford-Fulkerson algorithm we can find the maximum flow. (B) Given a flow network G=(V, E), Edmonds-Karp algorithm has time complexity O(|V||E|2). (C) The time complexity of Ford-Fulkerson algorithm depends on the capacity. (D) If each edge has a different capacity, then there exists a unique minimum cut. (E) The maximum flow is equal to the capacity of a minimum cut.

(59) Which statement is wrong for a flow network G=(V, E)? (A) If f is a maximum flow in G, then the corresponding residual network contains no augmenting path. (B) For any cut (S, T), the capacity of the cut is not smaller than the value of the flow crossing this cut. (C) The value of any flow f in G is bounded above by the capacity of any cut of G (D) If all edges of G have different capacities, then there exists a unique flow f that gives the maximum flow. (E) The capacity of each edge of G can be any non-negative number.

110年 - 110 國立臺灣科技大學_碩士班招生試題_電子工程系：資料結構#112844

110年 - 110 國立高雄科技大學_碩士班招生考試_電腦與通訊工程系：資料結構(乙組)#110488

110年 - 110 國立高雄科技大學_碩士班招生考試_資訊工程系：資料結構#110422

110年 - 110 國立中山大學_碩士暨碩士專班招生考試_資管系/乙組:資料結構#105545

110年 - 110台灣聯合大學系統_碩士班招生考試_電機類:資料結構#104954

110年 - 110 國立中央大學_碩士班招生考試_資訊管理暨大數據分析類:資料結構#103860

110年 - 110 國立政治大學_碩士班招生考試_資訊管理學系/科技組:資料結構#102881

110年 - 110 國立臺灣大學_碩士班招生考試_生物機電工程學研究所丙組:資料結構(C)#100901

110年 - 110 國立臺灣大學_碩士班招生考試_ 工程科學及海洋工程學研究所丁組:資料結構(A)#100759

109年 - 109 國立高雄大學_碩士班招生考試_資訊工程學系：資料結構#103082