110 交大資工所軟體考點分析｜國立陽明交通大學

改名陽明交大後的第一份考卷。30 題全複選、全對才給分但不倒扣，配分分四個級距。題目廣度是十年之最，幾乎每個課本章節都出現。

題型與配分

科目「資料結構與演算法（1101）」，國立陽明交通大學（110 年合校後第一年），系所班別資訊聯招，考試日期 110 年 2 月 3 日第 1 節，全卷 8 頁、30 題、100 分，不可使用計算機，用答案卡作答。

計分規則：全卷 30 題多選題，每題有一個（含）以上的正確選項。各題填答必須完全符合正確選項，答錯沒有倒扣，若有任一選項不符則該題 0 分。

配分分四個級距：

沒有倒扣，所以每題都該作答；但「全對才給分」代表部分把握等於沒把握，要逐一確認每個選項。

理論與 NP（1–2，各 4 分）

第 1 題｜L₁ 可多項式時間歸約到 L₂，四個推論何者正確 —— 考歸約方向（L₁ NP-hard ⇒ L₂ NP-hard、L₂ ∈ P ⇒ L₁ ∈ P）
第 2 題｜假設 NP ≠ P，哪些問題是 NP-hard：最長簡單路徑、最小環、最大環、負權環偵測、有負環時的最短簡單路徑

樹與編碼（3–4）

第 3 題（4 分）｜給五棵二元編碼樹，選出不可能是 Huffman code 的那些。關鍵是 Huffman 樹必為 full binary tree（每個內部節點都有兩個子節點）
第 4 題（4 分）｜紅黑樹性質：外部節點是否必為黑、根到外部節點的路徑能否有兩個連續黑節點（可以）、每條路徑的紅節點數是否相同（不是）、插入是否 O(1)

資料結構與複雜度（5–8）

第 5 題（4 分）｜各種結構的操作複雜度：有序 linked list 的插入是否 O(1)（不是，要先找位置）、queue 逐一移除 n 個元素、deque 的加入與尋找、雙向串列給定節點的刪除
第 6 題（4 分）｜自訂的 O(f) > O(g) 關係下比較五組函數，包含 3^(log₄n) 與 n³、⌊n/2⌋^⌊n/2⌋ 與 n!
第 7 題（4 分）｜哪些圖演算法使用動態規劃：Kruskal、Dijkstra、LCS、Floyd-Warshall
第 8 題（4 分）｜BST 的 preorder 為 6, 2, 4, 3, 5, 9, 7, 8，判斷祖先關係、兄弟節點、postorder 的先後、兩棵子樹高度是否相同。要先重建整棵樹

排序（9–10、18）

第 9 題（3.5 分）｜LSD radix sort 逐趟追蹤：312, 256, 19, 713, 44, 608, 210, 909 在第一趟、第二趟後的位置
第 10 題（3.5 分）｜哪些排序用分治法（Quick／Heap／Selection／Insertion／Merge）
第 18 題（3.5 分）｜分治排序的四種變體各自的複雜度，其中 (D) 把 n 個數切成 n/lg n 組、每組 lg n 個、各自 heap-sort 再合併，問是否為 O(n log log n)

Max flow（11、17、28）

第 11 題（3.5 分）｜最大割是否有多項式演算法（沒有，是 NP-hard）、最小割是否有、是否可能有多個不同的最大流、不同的最小割是否可能有不同容量（不可能）
第 17 題（3.5 分）｜給一張標了 x/y（流/容量）的流網路，判斷四組 a、b、c、d 的值哪些是合法的流（要同時滿足容量限制與流量守恆）
第 28 題（2.5 分）｜給流網路與其殘餘網路，反推 a、b、c、d 的關係式

遞迴式與漸進（12、22、29）

第 12 題（3.5 分）｜五條遞迴式的解，包含 T(n)=2T(n/2)+n/log n 與 T(n)=2T(n/2)+n/log²n（這兩條 Master theorem 用不了，要用遞迴樹）
第 22 題（3 分）｜f=O(g) 能否推出 log f = O(log g)、反向是否成立、能否推出 2^f = O(2^g)、⌈log n⌉! 與 n 的關係
第 29 題（2.5 分）｜**迭代對數 lg\*n**：f⁽ⁱ⁾ 的定義、lg\*16 的值（答案 3）

圖論（13、15、23）

第 13 題（3.5 分）｜最短路徑距離 δ(v) 的性質：是否對每個 v 都存在邊使 δ(v)=δ(u)+l(e)、這些邊的集合是否構成生成樹、是否構成 MST（不是）、三角不等式的方向
第 15 題（3.5 分）｜給一張帶權圖，x 為 MST 總權重、y 為次佳生成樹總權重，判斷 x、y 的關係式
第 23 題（3 分）｜有向帶權圖的拓撲排序與 Dijkstra：加一條權重 0 的邊後拓撲排序是否仍合法、Dijkstra 找到的路徑是否改變

樹結構（14、16、19、25）

第 14 題（3.5 分）｜minimum degree 3 的 B-tree，依序插入 5, 6, 4, 2, 1, 7, 8, 10 後，再分別插入 9 或 3 時樹高是否改變、哪些 key 在同一節點
第 16 題（3.5 分）｜BST 的節點關係推論（四個都是要小心判讀的敘述）
第 19 題（3 分）｜Max-Heap 的陣列表示：線性時間建堆的結果、刪除最大值後的陣列、插入 10 後的陣列、兩個 max-heap 能否線性時間合併
第 25 題（2.5 分）｜空紅黑樹依序插入 5, 3, 8, 2 後的性質（外部節點數、紅節點數、旋轉次數）

其他（20、21、24、26、27、30）

第 20 題（3 分）｜C++ STL 的 vector：是否連續記憶體、push_back 的擴張策略（每次只加 1 是否合理）、攤銷成本能否達 Θ(n)、單次 push_back 是否可能 Θ(n)
第 21 題（3 分）｜把 Huffman 推廣到三元編碼（符號 0、1、2），選出不可能的編碼樹。與第 3 題成對出現
第 24 題（3 分）｜h(key)=key mod 5，插入 1, 2, 4, 6, 8：chaining 與 linear probing 下 key 8 的位置、以及「load factor < 0.5 是否就不碰撞」（錯）
第 26 題（2.5 分）｜一串 Make-Set 與 Union 操作後，有幾個集合、哪些 Find-Set 回傳同一節點
第 27 題（2.5 分）｜活動選擇問題的五種貪婪策略，哪些能得到最佳解（答案：最早結束、最晚開始兩種都可以）
第 30 題（2.5 分）｜median of medians：改成分 3 組或分 7 組是否仍線性、heap sort 解法的複雜度、以及「因為 heap sort 下界是 Ω(n log n) 所以此問題下界也是」這個錯誤推論

廣度是十年之最。 30 題涵蓋 NP、Huffman（二元與三元）、紅黑樹、B-tree、max flow、radix sort、disjoint set、活動選擇、median of medians、迭代對數、C++ vector 攤銷 —— 幾乎沒有死角。
全對才給分。 每題都是複選且要完全命中，第 1–8 題每題 4 分，錯一個選項就掉 4 分。
第 12 題的兩條遞迴式（n/log n 與 n/log²n）Master theorem 都不適用，必須用遞迴樹算 —— 而且兩條的答案不同。
第 27 題的「最晚開始」策略很多人會漏掉，只記得「最早結束」是對的。