4. 若有一串列如下圖，請描述說明執行下面程式的結果。(15%)
 

(a) 請說明 sparse matrix 是什麼，並舉一例

(b) 請說明甚麼是 B tree、甚麼是 B+ tree，並說明其差異

(c) 什麼是 stable sorting，並舉一例

(a)

(b)

3. L 為一個 linked list，函式 Reverse(L)是把原來 L 的每一個節點的指標，指向串列 L 中的前一個節點。請撰寫一個以 Iterative 方式的程式來執行 Reverse(L)的功能，並以 文字描述程式邏輯構想。程式可用 C、Java、Pseudocode 撰寫。(15%)

5. 紅黑樹(red-black tree)是一種二進制搜索樹，每一個節點(node)非紅即黑。假設從一 棵空的紅黑樹開始，插入順序為 40、20、10、60、80、114、6。請畫出每次插入節 點的所有紅黑樹，並標示節點顏色。(20%)

(B) (13%) Now you a are given a a weighted graph G-(V, E), a specified vertex s in V, an array d ] of size V, and it is claimed that for each v in Y, dty is the length of the shortest path from s to v. The claim may be correct or may be not. Design a linear time algorithm to check whether the claim is correct. Analyses the time complexity of your algorithm and make sure it is linear, that is, the running time of your algorithm must be O(|V|+|E|).

(A)(12%) For a weighted graph G-(V, E) and two vertices x, y in Y, give an efficient algorithn to find a shortest path from x to y. Analyses the time complexity of the algorithm.

(C) (5%) By the above definitions and theorem, show the following staten ement is true or false. You should also show your reasons. If the reasons are incorrect, then you get no point. Statement: If an NPC problem can be solved in polynomial time by a deterministic algorithm, then all NP problems can also be solved in polynomial time by a deterministic algorithm.

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

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

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

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