106 台大資工所軟體考點分析
全卷只有 5 大題、2 頁，卻有 50 分是「設計演算法並證明最佳性」的純論述題，且證明答錯倒扣 10 分。台大十年來倒扣最重的一年。
題型與配分
科目「資料結構與演算法」（題號 413、節次 1），全卷 2 頁、5 大題、100 分，全部手寫、沒有任何選擇題。
| 題號 | 主題 | 配分 |
|---|---|---|
| 1 | 遞迴式求解（4 小題） | 20 |
| 2 | BST 搜尋序列判斷（3 小題） | 15 |
| 3 | LCS pseudo-code 填空 | 15 |
| 4 | DAG 上的最短路徑設計＋證明 | 25 |
| 5 | 二分圖匹配化約成 max flow＋證明 | 25 |
第 4、5 題的特殊作答規定
這是整份考卷最需要先知道的事。卷面明訂了三條規定，違者該題不計分：
- 不要書寫任何程式碼或代碼，請以文字、圖表、數學符號陳述概念
- 一個子題的回答以一頁為限，並按順序寫在完整的一頁。字太小、太潦草或英文文法問題導致閱卷者無法理解，該題不計分
- 每題的 (a) 是觀念陳述佔 10 分，(b) 是觀念的證明佔 15 分。證明部分有倒扣：答對得 15 分，答錯倒扣 10 分，不答得 0 分
卷面甚至直接寫著「知之為知之，不知為不知，是知也。瞎掰不能解決問題，珍惜分數，遠離倒扣。」
這代表第 4(b)、5(b) 兩小題合計 30 分的證明，沒把握時留白的期望值優於硬寫。 這是台大近十年唯一一次對申論題設倒扣。
逐題考點
- 第 1 題（20%）｜遞迴式求 big-O 上界，且要求 as tight as possible 並說明理由。四小題分別是 T(n)=T(n/3)+1、T(n)=3T(n/3)+1、T(n)=T(n/10)+T(9n/10)+n、T(n)=2T(√n)+lg n。前三題是 Master theorem 與遞迴樹的標準題，第 (d) 題要換元（令 m = lg n）才解得出來
- 第 2 題（15%）｜BST 中存放 1 到 1000 的數字、要搜尋 400，判斷給定的三個序列能不能是被檢查過的節點序列，並說明理由。考的是搜尋路徑上的區間會不斷收縮這個性質
- 第 3 題（15%）｜給定
LCS_LENGTH與LCS_OUTPUT兩支 pseudo-code，填 3A、3B、3C 三個空格。3A 是字元相等時的遞迴式、3B、3C 在輸出函式裡。要同時看懂len與prev兩個表格怎麼配合 - 第 4 題（25%）｜給一張 DAG，節點有參觀天數 c(v)、邊有交通天數 r(u,v)，求從首都到每個城市的最少天數 M(v)。(a) 10% 設計最佳演算法 (b) 15% 分析時間複雜度並證明它是最佳的。核心是拓撲排序後一次掃描的 O(V+E) 解，難點在 (b) 要論證 Ω(V+E) 的下界
- 第 5 題（25%）｜C 個班級、R 間教室，給定可分配的 (c,r) 配對集合 M，求最多能分配幾個班級。(a) 10% 說明如何轉成網路流問題 (b) 15% 證明 Ford–Fulkerson 用你的轉換能正確求解 —— 題目特別追問「是否任何一個 maximum flow 都會給出正確答案」，要論證整數流的存在性（integrality theorem）
這份考卷的難點
- 倒扣是最大變因。 第 4(b)、5(b) 答錯各扣 10 分，兩題全錯就是 −20。全卷只有 5 題，這個比重極高。
- 「證明最佳性」不是「分析複雜度」。 第 4(b) 真正要的是下界論證，只寫「拓撲排序是 O(V+E)」拿不到分。
- 不能寫程式碼。 很多人習慣用 pseudo-code 交代演算法，這一年明文禁止，必須用文字與圖表把想法講清楚，而且一頁寫完。
- 第 5(b) 的 integrality 論證是研究所等級的內容，能完整寫出來的人不多。
準備建議
- 遞迴式必須練到換元（T(n)=2T(√n)+lg n 這類），Master theorem 之外的解法要熟
- LCS 的 DP 表與回溯輸出要能默寫，台大 106 這題只是填空，但同一組觀念在後續年度反覆出現
- Max flow 與二分圖匹配的轉換（加超級源點、匯點、容量設 1）是台大高頻考點，106 的第 5 題、110 的第 16 題、114 的第 7 題都是同一套工具
- 證明題要練「先講結論、再分點論證」的寫法，這一年限定一頁，寫得散就講不完