中央資工所軟體考古題十年大統整（106–115）
題型演變
| 年度 | 結構 | 選擇題 | 手寫 |
|---|---|---|---|
| 106 | 問答題 8 題 | 0% | 100% |
| 107 | 單選 14 題＋多選 8 題 | 100% | 0% |
| 108 | 單選 25＋複選 35＋問答 40 | 60% | 40% |
| 109 | 複選 30＋是非 5＋申論 65 | 35% | 65% |
| 110 | 複選 50＋問答 50 | 50% | 50% |
| 111 | 複選 50＋多選 10＋問答 40 | 60% | 40% |
| 112 | 複選 50＋問答 50 | 50% | 50% |
| 113 | 複選 20 題 | 100% | 0% |
| 114 | 複選 20 題 | 100% | 0% |
| 115 | 多選 10＋複選 10 | 100% | 0% |
115 年雖然也是 20 題全選擇，但把前 10 題改成逐選項計分的多選題、後 10 題維持全對才給分的複選題。這是 113 年以來的第一次微調，值得注意。
倒扣規則逐年對照
倒扣強度差異很大，直接影響「該不該猜」的策略：
| 年度 | 倒扣方式 | 嚴苛度 |
|---|---|---|
| 107 | 答錯倒扣 1 分／題 | 中 |
| 108 | 答錯倒扣 1 分／題，扣到該大題 0 分為止 | 中 |
| 109 | 全對才給分，答錯倒扣 1.25 分 | 高 |
| 110 | 全對才給分，答錯一個選項扣 1.5 分 | 最高 |
| 111 | 複選 1 分／題；多選逐選項 ±1 分 | 中 |
| 112 | 答錯倒扣 1 分／題 | 中 |
| 113 | 全對才給分，答錯倒扣 1 分 | 高 |
| 114 | 全對才給分，答錯倒扣 1 分 | 高 |
| 115 | 前 10 題逐選項扣 1 分；後 10 題全對才給分、錯一題扣 1 分 | 高 |
結論：近三年在「全對才給分」的規則下，沒有九成把握的題目留白的期望值優於硬猜。
兩組幾乎重複的年份
這是整份統整最實用的發現 —— 中央有成對出題的習慣，隔年會把前一年的題目換數字再考一次：
110 ↔ 111（複選題八題以上同型）
| 主題 | 110 | 111 | 差異 |
|---|---|---|---|
| Infix／postfix 與 stack token 數 | 第 1 題 | 第 1 題 | 選項幾乎完全相同 |
| AVL tree 性質 | 第 2 題 | 第 3 題 | Fibonacci 不等式方向相反 |
| Leftist tree | 第 3 題（WBLT） | 第 4 題（HBLT） | 換成另一種 |
| 遞迴函式 F1／F2／F3 | 第 4 題 | 第 5 題 | F1 由 3x+1 改成 3x+2 |
| 二維陣列指標 | 第 5 題 arr[3][2] | 第 6 題 arr[2][3] | 只換索引 |
| stack／queue 判斷 | 第 6 題 | 第 7 題 | 包裝成「黑盒子傳訊息」 |
| hash 刪除後搬移 | 第 7 題 | 第 8 題 | 集合中一個數字不同 |
| linked list reverse 填空 | 第 9 題 | 第 9 題 | 多挖一個空格 |
| AOE network critical path | 第 10 題 | 第 10 題 | dur 值微調 |
114 ↔ 115（七題以上同型）
| 主題 | 114 | 115 |
|---|---|---|
| hash 反推插入順序 | 第 1 題 | 第 12 題 |
| 運算式互轉 | 第 2 題 | 第 16 題 |
| LSD Radix sort 各 pass | 第 3 題 | 第 14 題 |
| inorder＋postorder 重建二元樹 | 第 4 題 | 第 18 題 |
| 同段程式碼在四種容器的行為 | 第 5 題 | 第 17 題 |
| Red-black tree 插入 | 第 6 題 | 第 15 題 |
| LeetCode 型貪婪＋heap | 第 8–10 題 | 第 19 題 |
練考古題時務必成對練：只練 110 會錯過 111 的變化點，只練 115 會漏掉 114 才有的最大流。
主題出現年度一覽
| 主題 | 出現年度 |
|---|---|
| Hash table（探測法、刪除搬移、反推順序） | 107、108、109、110、111、112、113、114、115 |
| 排序演算法（quick／merge／heap／radix） | 107、108、109、110、111、112、113、114、115 |
| NP 理論（NP／NP-hard／NPC、歸約方向） | 106、107、109、110、111、112、114、115 |
| 動態規劃（LCS、matrix chain、knapsack） | 106、107、108、111、113、114、115 |
| Heap（建堆、插入刪除、heapsort） | 106、107、108、109、112、114、115 |
| 運算式轉換（infix／postfix／prefix） | 109、110、111、112、113、114、115 |
| MST（Prim／Kruskal／次佳生成樹） | 107、109、111、113、114、115 |
| Floyd–Warshall／全點對最短路徑 | 107、108、112、114、115 |
| 樹的走訪與重建 | 106、109、113、114、115 |
| Linked list 操作（反轉、雙向） | 110、111、112、113 |
| 遞迴式求解 | 107、110、113、115 |
| 圖走訪／拓撲排序／可達性 | 109、112、115 |
| Leftist tree（HBLT／WBLT） | 110、111、112 |
| AOE network／critical path | 110、111、115 |
| 漸進符號 | 113、114、115 |
| Red-black tree | 114、115 |
| AVL tree | 110、111 |
| 最大流（Max Flow） | 114 |
必守的五個主題
按「出現年度 × 計算量」排序，這五個投報率最高：
- Hash table —— 十年考了九年，而且考法一直在變：linear／quadratic／pseudo-random probing、一個 bucket 多個 slot、刪除後哪些 key 要搬、給最終表格反推插入順序。必須練到能穩定手動模擬
- 排序演算法 —— 九年。除了複雜度表要背熟，quick sort 第一趟 partition 的結果、LSD radix 每一趟的中間狀態都要能手算
- NP 理論 —— 八年。選項通常只差歸約箭頭的方向，建議自己畫一張圖釐清 NP、NP-hard、NPC 的包含關係與歸約方向
- 動態規劃 —— 七年。LCS 與 matrix-chain multiplication 是最常出現的兩題，遞迴式要能默寫
- 運算式轉換 —— 七年。這是純技術題，練熟就是穩分
給 116 年考生的策略
- 優先練 113、114、115，題型與現在一致；再回頭用 110–112 補觀念
- 113 年起沒有手寫題，代表「會寫演算法」不再直接得分，但手動模擬（trace）的重要性反而上升
- 倒扣下留白是合理策略，特別是「全對才給分」的題組
- 近年出現 LeetCode 風格的貪婪＋heap 題（114 的加油站、115 的課程排程），這類題在傳統課本裡找不到，值得另外準備
- 科目全名是「資料結構與演算法」，不含作業系統與計算機組織 —— 那些在「硬體」考科
本頁的題型、配分、倒扣規則均直接取自各年度試卷標示；主題出現年度為逐題比對後的整理。若發現有誤，歡迎來信指正。