111 台大資工所軟體考點分析

題型與配分

科目「資料結構與演算法（A）」（題號 361、節次 1），全卷 4 頁、22 題、100 分，全部單選、作答於答案卡（2B 鉛筆）。

這一年沒有倒扣。 卷面只寫「請用 2B 鉛筆作答於答案卡，並先詳閱答案卡上之『畫記說明』」，沒有任何扣分規定。沒把握的題目也應該全部填滿 —— 這和 110 年（倒扣 2.5 分）的策略完全相反。

逐題考點

複雜度對照（1–5，各 3 分）

共用 O(1)/O(lg n)/O(n)/O(n lg n)/O(n²) 五個選項：selection sort 期望、merge sort 期望、MAX_HEAPIFY 期望、quick sort 最壞、Θ(n) 個 bucket 的 bucket sort 期望。與 107 年第 1–7 題幾乎同一組題目，純記憶分。

排序與 heap（6–9）

• 第 6 題｜哪一個不是 in-place 排序（標準實作）
• 第 7 題｜依序插入 5, 4, 2, 6, 1, 3 到 max-heap，問索引 2 的值
• 第 8 題｜承上，值為 3 的節點其左子節點
• 第 9 題｜quicksort 第一趟分割後陣列變成 [7, 11, 16, 10, 17, 1, 18, 30]，問有幾個元素可能是 pivot —— 反推題，要找出「左邊都比它小、右邊都比它大」的位置

迴圈不變量與字串（10–11）

• 第 10 題｜給一段二分搜尋變形 COMPUTE-P，問 while 迴圈維持的 loop invariant 是哪一個區間關係
• 第 11 題｜在字串前面補最少字元使其成為回文：把原字串與反轉字串用 # 串接後跑 KMP 的 failure function，問答案的計算式

理論與雜湊（12–13）

• 第 12 題｜哪一個敘述已被證明為真 —— NP 問題間歸約關係的四個選項
• 第 13 題｜f(n) 個 entry 的 hash table，什麼條件能保證成功搜尋為 O(1) —— 考 load factor 與 Ω 的關係

Red-black tree（14–15）

• 第 14 題｜n 個內部節點（n 為偶數）的紅黑樹，最多有幾個「黑節點恰有一個紅子節點」
• 第 15 題｜承上，在達到該上界的 26 節點紅黑樹中，最大樹高是多少（單一節點的樹高算 1）

這兩題連動，第 14 題想錯第 15 題必錯，是全卷最需要推理的一組。

動態規劃（16–17）

• 第 16 題｜matrix-chain multiplication，給 A₁..A₆ 的維度 30×35, 35×15, 15×5, 5×10, 10×20, 20×25，求 m[2,5]。這是 CLRS 課本的原始範例，答案是 7125
• 第 17 題｜求 A₁A₂…A_n 最少純量乘法次數的 DP 時間複雜度

圖論（18–21）

• 第 18 題｜Dijkstra 哪一個敘述錯誤 —— 選項涵蓋 BFS 式的搜尋原則、貪婪性質、陣列實作的 O(V²)、以及稠密圖用 binary min-heap 能否達到 O(V²)
• 第 19 題｜給一張無向圖與其 MST T，哪一個敘述錯誤 —— 包含某條邊是否在 T 中、以及降低某條邊的權重後 T 是否仍為 MST
• 第 20 題｜Floyd–Warshall 的 space complexity（注意問的是空間不是時間，答案 Θ(n²)）
• 第 21 題｜Edmonds-Karp 求最大流，哪一個敘述正確 —— 考複雜度 O(VE²) 與「用 BFS 而非 DFS」

貪婪（22）

• 第 22 題｜6 件物品的 fractional knapsack，W = 20，問取用物品的順序。依單位價值 v_i/w_i 由大到小排序即可

這份考卷的難點

1. 難點其實不多。 這是台大近十年最貼近課本的一份考卷，第 1–5、16、17、20、22 題幾乎都是 CLRS 的標準內容或原始範例。
2. 第 14、15 題的紅黑樹計數是唯一需要自行推理的地方，也是區分度所在。
3. 第 9 題的 pivot 反推容易漏算 —— 要逐一檢查每個位置，不是只看最左最右。
4. 第 18、19、21 題都在問「哪一個錯誤／正確」，要逐項檢查，不能看到熟悉的敘述就選。

準備建議

• 這一年沒有倒扣，務必每題都填。 台大的倒扣規則逐年在變（110 扣 2.5、112 扣 1、113 扣 1、111 與 114、115 不扣），進考場第一件事是讀卷首規定
• CLRS 的 matrix-chain 原始範例（30×35×15×5×10×20×25）建議直接記住整張 m 表，台大 111 與多校都考過
• Floyd–Warshall 要分清楚時間 Θ(n³)、空間 Θ(n²)，這題很多人答錯
• 紅黑樹的性質推論（黑高、節點數上下界、紅節點分布）值得花時間推一次，111、113、115 都出現