111 台大資工所考古題詳解｜軟體考點分析

題型與配分

全卷 4 頁、22 題、100 分，全部單選，作答於答案卡（2B 鉛筆）。

卷面只寫「請用 2B 鉛筆作答於答案卡，並先詳閱答案卡上之『畫記說明』」，沒有扣分規定。

逐題考點

複雜度對照（第 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 第一趟分割後 array 變成 [7, 11, 16, 10, 17, 1, 18, 30]，問有幾個元素可能是 pivot

loop invariant 與字串（第 10–11 題）

• 第 10 題｜給一段 binary search 變形 COMPUTE-P，問 while 迴圈維持的 loop invariant 是哪一個區間關係
• 第 11 題｜在字串前面補最少字元使其成為回文，問答案的計算式

理論與 hash（第 12–13 題）

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

Red-black tree（第 14–15 題）

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

DP（第 16–17 題）

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

圖論（第 18–21 題）

• 第 18 題｜Dijkstra 哪一個敘述錯誤
• 第 19 題｜給一張 undirected graph 與其 MST T，哪一個敘述錯誤，包含某條邊是否在 T 中、以及降低某條邊的權重後 T 是否仍為 MST
• 第 20 題｜Floyd–Warshall 的 space complexity
• 第 21 題｜Edmonds-Karp 求 max flow，哪一個敘述正確

greedy（第 22 題）

• 第 22 題｜6 件物品的 fractional knapsack，W = 20，問取用物品的順序

作答時要注意的地方

1. 第 14、15 題相連，第 15 題接續第 14 題的條件。
2. 第 9 題問的是有幾個元素可能是 pivot，要逐一檢查每個位置。
3. 第 18、19、21 題問「哪一個錯誤」或「哪一個正確」，每個選項都要檢查。
4. 第 20 題問的是空間複雜度。

準備方向

• 複雜度對照表，111 第 1–5 題與 107 第 1–7 題幾乎相同。
• CLRS 的 matrix-chain 範例，111 第 16 題直接取自課本。
• Floyd–Warshall 的時間與空間複雜度。
• red-black tree 的性質推論（黑高、節點數上下界、紅節點分布），111、113、115 都出現。