台大資工所軟體考古題十年大統整（106–115）
題型演變
| 年度 | 結構 | 選擇題 | 手寫 | 頁數 |
|---|---|---|---|---|
| 106 | 手寫 5 大題 | 0% | 100% | 2 |
| 107 | 選擇 16 題＋手寫 2 大題 | 40% | 60% | 2 |
| 108 | 手寫／填答 10 題 | 0% | 100% | 4 |
| 109 | 複選 10 題＋手寫 5 題 | 30% | 70% | 6 |
| 110 | 選擇 20 題 | 100% | 0% | 4 |
| 111 | 單選 22 題 | 100% | 0% | 4 |
| 112 | 選擇 14 題＋手寫 2 題 | 70% | 30% | 7 |
| 113 | 選擇 12 題＋手寫 1 題 | 70% | 30% | 6 |
| 114 | 選擇 17 題＋手寫 2 題 | 85% | 15% | 7 |
| 115 | 單選 25 題 | 100% | 0% | 7 |
卷長在變厚。 106、107 只有 2 頁，112 年以後穩定在 6–7 頁。題目敘述越來越長，閱讀速度本身就是一種能力。
倒扣規則逐年對照
這是整份統整最該先看的一張表。台大沒有固定的倒扣政策，每年進考場都必須先讀卷首。
| 年度 | 倒扣方式 | 該不該猜 |
|---|---|---|
| 106 | 申論的證明子題答對 +15、答錯 −10、不答 0 | 不會就留白 |
| 107 | 選擇題不答 0 分，答錯倒扣當題分數 | 最嚴苛，沒把握就留白 |
| 108 | 無倒扣，但「部分正確不給分」 | 全填 |
| 109 | 無倒扣（複選，正確答案可能 0–5 個） | 全填 |
| 110 | 每題 5 分，答錯倒扣 2.5 分 | 排除到剩兩個選項才值得猜 |
| 111 | 無倒扣 | 全填 |
| 112 | 單選答錯 −1；複選每選項 +1／−0.5 | 選項有把握就填 |
| 113 | 單選答錯 −1；複選每選項 +1／−0.5（10 分題 +2／−1） | 選項有把握就填 |
| 114 | 完全無倒扣（答錯得 0 分） | 全填，每個選項都填 |
| 115 | 卷首無任何計分說明＝無倒扣 | 全填 |
結論：近兩年（114、115）沒有倒扣，答案卡應該填滿。但 110 年扣 2.5 分、107 年扣滿分的先例還在，116 年不能預設不扣。
主題出現年度一覽
| 主題 | 出現年度 |
|---|---|
| 複雜度與遞迴式求解（Master theorem、換元、遞迴樹） | 106、107、109、110、111、113、114、115 |
| 排序演算法（quick／merge／heap／bucket／radix） | 107、108、109、110、111、112、113、115 |
| Hash table（probing、chaining、互質條件、universal hashing） | 107、108、110、111、112、113、114、115 |
| NP 理論與歸約方向 | 106、109、110、111、113、114、115 |
| Max flow／二分圖匹配／最小割 | 106、110、111、112、114、115 |
| 樹與 BST／AVL／紅黑樹 | 107、109、111、112、113、115 |
| 動態規劃（LCS、matrix chain、knapsack、格子 DP） | 106、107、108、110、111、113、114、115 |
| Heap 操作與建堆 | 107、108、109、111、112、115 |
| MST（Prim／Kruskal／cut property） | 110、111、112、114、115 |
| 字串比對（KMP failure function、自動機） | 110、111、112、115 |
| 攤銷分析（accounting／potential／動態陣列） | 107、113、114、115 |
| 最短路徑（Dijkstra／Bellman-Ford／Floyd-Warshall） | 108、111、112、114 |
| Stack／queue／deque 實作 | 107、108、109、110、115 |
| 近似演算法與 ILP | 113、114 |
| Disjoint set | 109、115 |
| Huffman coding | 112、115 |
| B-tree／B+ tree | 112、115 |
| FFT | 115 |
台大最鮮明的三個特色
1. 情境包裝題
台大很愛把經典問題換一層皮，題面完全不提演算法名稱：
| 年度 | 題目長相 | 其實是 |
|---|---|---|
| 106 第 5 題 | 班級分配教室 | 二分圖匹配／max flow |
| 108 第 9 題 | 14 艘船過河、航線交叉要等 15 分鐘 | 非交叉匹配 |
| 108 第 10 題 | 圖形替換求最小成本 | 區間 DP |
| 109 第 15 題 | SNP 基因標記選擇 | Set Cover，並要證明 NP-complete |
| 110 第 2–5 題 | Snake sequence | 格子 DP |
| 114 第 3 題 | DNA 序列分群 | k-means 性質判斷 |
| 114 第 4 題 | 蛋白質序列比對 | Needleman-Wunsch DP |
| 114 第 7 題 | 球隊是否已被淘汰 | Max flow 建模 |
練台大考古題時，看到陌生的情境不要慌，先問「這是哪個經典問題換皮」。
2. 超出課本的進階內容
台大幾乎每年都會放一兩題研究所等級的題目：
- 114 第 2 題｜Akra-Bazzi theorem
- 114 第 11 題｜universal hashing 的最壞期望碰撞數
- 114 第 16 題｜integrality gap
- 114 第 19(b) 題｜subset sum 的 FPTAS
- 113 第 13 題｜vertex cover 兩種近似演算法的 ratio bound 比較
- 115 第 3 題｜AlphaTensor 的 4×4 矩陣乘法
- 115 第 9 題｜FFT 靠單位根的哪個性質加速
這些題目通常只佔 4–5 分，策略上不該為了它們放棄基本盤，但讀懂結論與適用條件就能拿分。
3. 「哪個敘述正確／錯誤」的選項陷阱
近三年大量出現這種題型，錯誤選項往往只差一個前提條件：
- 112 第 12(E)｜所有邊加同一個常數，最短路徑會不會變？（會變）
- 115 第 25 題｜cut property 少寫了「respects A」這個前提
- 115 第 15 題｜hash 擴張是為了「避免鏈長線性成長」，不是「避免載入因子達 1」
- 113 第 3 題／115 第 19 題｜動態陣列縮小門檻設 1/4 可以、設 1/2 攤銷就壞掉
這類題目背複雜度沒有用，要能說出「為什麼」。
必守的六個主題
按「出現年度 × 配分」排序，這六個投報率最高：
- 複雜度與遞迴式求解 —— 十年考八年。除了 Master theorem，換元法（T(n)=2T(√n)+lg n、T(n)=log n+T(√n)）在 106、114 都出現，必須會
- Hash table —— 十年考八年。手動跑 probing、
gcd(h₂(k), m)=1的互質條件（108、115 各考一次）、chaining 的期望比較次數，都要能算 - NP 理論與歸約方向 —— 十年考七年。A ≤p B 代表誰比較難，畫一張圖釐清；Set Cover、Vertex Cover、Subset Sum 三個歸約要能默寫
- 動態規劃 —— 十年考八年。LCS、matrix chain（111 直接考 CLRS 原始範例）、knapsack、格子 DP、區間切段 DP 都出現過
- Max flow 的建模 —— 十年考六年。二分圖匹配、球隊淘汰、最小割對偶，都是「把問題轉成流網路」的能力
- KMP 的 failure function —— 110、111、112、115 連四次。純技術題，練熟就是穩分
給 116 年考生的策略
- 進場第一件事是讀卷首的計分規定。 台大十年換過六種倒扣方式，114、115 無倒扣但 110 扣 2.5 分，策略完全相反
- 優先練 112–115，題型與現在接近；106–109 的手寫題仍值得寫，因為同樣的觀念會以選擇題形式重現（例如 106 的班級分配教室 → 114 的球隊淘汰，都是 max flow 建模）
- 時間分配是近年的主要壓力。 115 年 25 題 4 分制，平均每題約 4 分鐘，其中十題以上要動手算；113 年題目敘述長達半頁，光讀題就很花時間
- 手寫題若再出現，八成是「設計演算法＋證明／分析」，而不是寫程式碼。106 年甚至明文禁止寫 code，要練用文字與圖表講清楚演算法
- 科目全名是「資料結構與演算法」，不含作業系統與計算機組織 —— 那些在「計算機系統」（計系）考科
本頁的題型、配分、倒扣規則均直接取自各年度試卷標示；主題出現年度為逐題比對後的整理。若發現有誤，歡迎來信指正。