資工所考古題詳解中央資工所考古題詳解軟體十年大統整（106–115）
各章配分
表中數字是各題的卷面配分，依主題加總。有子題的照子題分，沒有子題的整題算在主要考點，敘述判斷題算在多數選項所屬的主題。章與細項依十年合計排序，顏色越深，占當年總分的比例越高。
| 章／細項 | 106 | 107 | 108 | 109 | 110 | 111 | 112 | 113 | 114 | 115 | 合計 | 占比 | 年數 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Shortest Paths & MST | 10 | 32 | 32 | 25 | 25 | 15 | 5 | 25 | 15 | 10 | 194 | 19% | 10 |
| Single-source Shortest Paths | 10 | 5 | 15 | 25 | 5 | 10 | 5 | 5 | 80 | 8% | 8 | ||
| Minimum Spanning Tree | 4 | 25 | 15 | 15 | 5 | 5 | 69 | 7% | 6 | ||||
| All-pairs Shortest Paths | 23 | 17 | 5 | 45 | 4% | 3 | |||||||
| Algorithm Design | 33 | 18 | 18 | 15 | 5 | 23 | 20 | 30 | 25 | 187 | 19% | 9 | |
| Dynamic Programming | 10 | 14 | 8 | 10 | 18 | 15 | 10 | 10 | 95 | 10% | 8 | ||
| Recursion | 5 | 4 | 10 | 5 | 5 | 5 | 34 | 3% | 6 | ||||
| Greedy | 5 | 15 | 10 | 30 | 3% | 3 | |||||||
| Backtracking & Search Strategies | 18 | 5 | 5 | 28 | 3% | 3 | |||||||
| Sorting & Searching | 10 | 27 | 30 | 5 | 5 | 5 | 10 | 10 | 5 | 20 | 127 | 13% | 10 |
| Quicksort | 15 | 5 | 5 | 5 | 5 | 10 | 45 | 4% | 6 | ||||
| Heapsort | 12 | 8 | 20 | 2% | 2 | ||||||||
| Sort Comparison & Lower Bound | 5 | 10 | 5 | 20 | 2% | 3 | |||||||
| Merge Sort & k-way Merge | 17 | 17 | 2% | 1 | |||||||||
| Elementary Sorts | 10 | 10 | 1% | 1 | |||||||||
| Linear-time Sorts | 5 | 5 | 10 | 1% | 2 | ||||||||
| Selection & Binary Search | 5 | 5 | <1% | 1 | |||||||||
| Linear Structures | 11 | 20 | 20 | 15 | 15 | 10 | 10 | 101 | 10% | 7 | |||
| Stack & Queue | 10 | 5 | 5 | 5 | 5 | 5 | 35 | 4% | 6 | ||||
| Array & Linked List | 10 | 10 | 5 | 10 | 35 | 4% | 4 | ||||||
| Infix / Postfix | 1 | 5 | 5 | 5 | 5 | 5 | 5 | 31 | 3% | 7 | |||
| NP-Completeness | 12 | 10 | 5 | 25 | 5 | 25 | 10 | 5 | 97 | 10% | 8 | ||
| P / NP & Reductions | 12 | 10 | 5 | 25 | 5 | 25 | 10 | 5 | 97 | 10% | 8 | ||
| Trees | 20 | 5 | 6 | 5 | 17 | 15 | 10 | 10 | 88 | 9% | 8 | ||
| Tree Basics & Traversal | 15 | 1 | 10 | 5 | 5 | 36 | 4% | 5 | |||||
| Binary Search Tree | 5 | 5 | 5 | 15 | 2% | 3 | |||||||
| Disjoint Set | 12 | 12 | 1% | 1 | |||||||||
| AVL Tree | 5 | 5 | 10 | 1% | 2 | ||||||||
| Red-Black Tree | 5 | 5 | 10 | 1% | 2 | ||||||||
| Other Search Trees | 5 | 5 | <1% | 1 | |||||||||
| Graph Traversal | 13 | 5 | 5 | 30 | 5 | 58 | 6% | 5 | |||||
| Topological Sort & DAG | 5 | 5 | 5 | 8 | 5 | 28 | 3% | 5 | |||||
| Representation & BFS / DFS | 7 | 13 | 20 | 2% | 2 | ||||||||
| Connectivity | 1 | 9 | 10 | 1% | 2 | ||||||||
| Hashing | 5 | 10 | 5 | 5 | 5 | 5 | 5 | 10 | 5 | 55 | 6% | 9 | |
| Collision Resolution | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 40 | 4% | 8 | ||
| Hash Functions | 5 | 5 | 5 | 15 | 2% | 3 | |||||||
| Heaps | 15 | 5 | 5 | 5 | 5 | 10 | 45 | 4% | 6 | ||||
| Binary Heap | 15 | 5 | 5 | 5 | 30 | 3% | 4 | ||||||
| Advanced Heaps | 5 | 5 | 5 | 15 | 2% | 3 | |||||||
| Complexity Analysis | 8 | 10 | 5 | 10 | 33 | 3% | 4 | ||||||
| Asymptotic Notation | 4 | 5 | 5 | 5 | 19 | 2% | 4 | ||||||
| Recurrences | 4 | 5 | 9 | <1% | 2 | ||||||||
| Amortized Analysis | 5 | 5 | <1% | 1 | |||||||||
| Other | 10 | 10 | 1% | 1 | |||||||||
| Network Flow | 5 | 5 | <1% | 1 | |||||||||
| Max Flow / Min Cut | 5 | 5 | <1% | 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 |
| 2D array 指標 | 第 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 題 |
| infix／postfix／prefix 互轉 | 第 2 題 | 第 16 題 |
| LSD radix sort 各 pass | 第 3 題 | 第 14 題 |
| inorder＋postorder 重建 binary tree | 第 4 題 | 第 18 題 |
| 同段程式碼在四種容器的行為 | 第 5 題 | 第 17 題 |
| Red-black tree 插入 | 第 6 題 | 第 15 題 |
| LeetCode 型 greedy＋heap | 第 8–10 題 | 第 19 題 |
這兩組要成對練。只練 110 會錯過 111 的變化點，只練 115 會漏掉 114 才有的 max flow。
其他重複出現的題目
| 題目 | 出現年度 |
|---|---|
| Floyd–Warshall 與 AllPairCost 填空 | 107 第 4、5、20、21 題、108 第 8、9 題與問答第 3 題 |
Max heap 的 adjust、heapsort 填空（同一支程式） | 107 第 8–10 題、108 問答第 4 題 |
| Quicksort 第一趟 partition 反推 pivot | 108 第 1 題、109 第 5 題 |
| 每個 bucket 兩個 slot 的 hash 滿 bucket 總和 | 108 第 6 題、109 第 6 題 |
perm 排列程式填空（同一支程式） | 108 第 4、5 題、109 申論第 2 題 |
| MST 性質判斷（不假設邊權相異） | 107 第 3 題、113 第 15 題 |
| LSD radix sort（同一組 12 個數字，個別數字不同） | 112 第 4 題、114 第 3 題 |
| infix／postfix／prefix 互轉（b+a*c/d 三年都有，其餘式子略有不同） | 112 第 10 題、114 第 2 題、115 第 16 題 |
優先準備的五個主題
依上表十年合計：
- Shortest Paths & MST，194 分，十年每年都有。Single-source shortest path 考了八年，Floyd–Warshall 與 AllPairCost 在 107、108 年各有 23、17 分，MST 考了六年。
- Algorithm Design，187 分，十年考九年（112 年沒有）。DP 一項 95 分、考了八年，LCS 和 matrix-chain multiplication 最常出，recurrence 要能默寫。Recursion（
perm排列、河內塔變形、F1／F2／F3）在 106–111 年每年都有。 - Sorting & Searching，127 分，十年都有。Quicksort 考了六年，第一趟 partition 的結果、LSD radix sort 每一趟的中間狀態都要能手算。
- Linear Structures，101 分，109 年起每年都有。infix／postfix／prefix 互轉七年（109–115），stack 與 queue 六年，linked list 反轉與 2D array 指標四年。純技術題，練熟就能穩拿。
- NP-Completeness，97 分，十年考八年。選項通常只差 reduction 箭頭的方向，建議自己畫一張圖，把 NP、NP-hard、NPC 的包含關係和 reduction 方向弄清楚。
Hashing 十年合計 55 分，但十年考了九年，考法一直在變：linear／quadratic／pseudo-random probing、一個 bucket 多個 slot、刪除後哪些 key 要搬、給最終表格反推插入順序。要練到能穩定手動模擬。
題型演變
| 年度 | 結構 | 選擇題 | 手寫 |
|---|---|---|---|
| 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 分；多選每個小題答錯倒扣 1 分，扣到該題 0 分為止 | 中 |
| 108 | 答錯倒扣 1 分／題，扣到該大題 0 分為止 | 中 |
| 109 | 複選全對才給分，答錯倒扣 1.25 分；是非題答錯倒扣 0.5 分 | 高 |
| 110 | 全對才給分，答錯一個選項扣 1.5 分 | 最高 |
| 111 | 複選全對才給分、答錯倒扣 1 分；多選逐選項 ±1 分 | 中 |
| 112 | 答錯倒扣 1 分／題 | 中 |
| 113 | 全對才給分，答錯倒扣 1 分 | 高 |
| 114 | 全對才給分，答錯倒扣 1 分 | 高 |
| 115 | 前 10 題逐選項扣 1 分；後 10 題全對才給分、錯一題扣 1 分 | 高 |
113、114 年全卷是全對才給分加倒扣，115 年後 10 題也是：每題答對 5 分、答錯扣 1 分，答對機率超過六分之一，作答的期望值就是正的。
給 116 年考生的準備方向
- 優先練 113、114、115，題型跟現在一致，再用 110–112 補觀念。
- 113 年起沒有手寫題。會寫演算法不再直接得分，手動模擬（trace）反而更重要。
- 作答前先算期望值。全對才給分的題答對 5 分、答錯只扣 1 分；115 年前 10 題逐選項計分，每個選項答對 +1、答錯 −1。
- 近年出現 LeetCode 風格的 greedy 加 heap 題（114 的加油站、115 的課程排程），傳統課本裡找不到，值得另外準備。
本頁的題型、配分、倒扣規則都取自各年度試卷上的標示，各章配分是逐題分類後加總的。如果發現有誤，歡迎來信指正。
最後更新：2026-10-23