資工所考古題詳解師大資工所考古題詳解軟體十年大統整（106–115）
各章配分
表中數字是各題的卷面配分，依主題加總。有子題的照子題分，沒有子題的整題算在主要考點。章與細項依十年合計排序，顏色越深，占當年總分的比例越高。C／C++ 的程式填空題依內容算在對應的資料結構（stack、linked list、binary search 等），只考語言本身的題目（113 年 gets()、字串常數、函式指標、巨集）才算在 Programming。
| 章／細項 | 106 | 107 | 108 | 109 | 110 | 111 | 112 | 113 | 114 | 115 | 合計 | 占比 | 年數 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Data Structures & Algorithms | 100 | 100 | 95 | 100 | 100 | 100 | 100 | 75 | 100 | 100 | 970 | 97% | 10 |
| Shortest Paths & MST | 26 | 25 | 20 | 30 | 15 | 9 | 6 | 15 | 10 | 156 | 16% | 9 | |
| All-pairs Shortest Paths | 20 | 10 | 20 | 15 | 10 | 75 | 8% | 5 | |||||
| Minimum Spanning Tree | 20 | 5 | 9 | 7 | 41 | 4% | 4 | ||||||
| Single-source Shortest Paths | 6 | 15 | 5 | 6 | 8 | 40 | 4% | 5 | |||||
| Algorithm Design | 15 | 25 | 25 | 20 | 40 | 5 | 4 | 20 | 154 | 15% | 8 | ||
| Dynamic Programming | 15 | 7 | 25 | 17 | 20 | 10 | 94 | 9% | 6 | ||||
| Greedy | 3 | 20 | 4 | 10 | 37 | 4% | 4 | ||||||
| Divide and Conquer | 18 | 18 | 2% | 1 | |||||||||
| Recursion | 5 | 5 | <1% | 1 | |||||||||
| Graph Traversal | 4 | 14 | 30 | 7 | 11 | 10 | 10 | 32 | 13 | 10 | 141 | 14% | 10 |
| Representation & BFS / DFS | 4 | 15 | 3 | 6 | 10 | 29 | 6 | 10 | 83 | 8% | 8 | ||
| Connectivity | 4 | 5 | 5 | 10 | 3 | 7 | 34 | 3% | 6 | ||||
| Topological Sort & DAG | 10 | 10 | 4 | 24 | 2% | 3 | |||||||
| Sorting & Searching | 25 | 12 | 12 | 21 | 26 | 15 | 16 | 11 | 138 | 14% | 8 | ||
| Quicksort | 10 | 3 | 3 | 13 | 5 | 34 | 3% | 5 | |||||
| Selection & Binary Search | 15 | 6 | 5 | 7 | 33 | 3% | 4 | ||||||
| Merge Sort & k-way Merge | 15 | 10 | 5 | 30 | 3% | 3 | |||||||
| Elementary Sorts | 6 | 15 | 21 | 2% | 2 | ||||||||
| Heapsort | 4 | 3 | 6 | 13 | 1% | 3 | |||||||
| Sort Comparison & Lower Bound | 3 | 4 | 7 | <1% | 2 | ||||||||
| Linear Structures | 22 | 4 | 10 | 13 | 5 | 10 | 25 | 5 | 20 | 114 | 11% | 9 | |
| Array & Linked List | 10 | 4 | 8 | 8 | 5 | 19 | 10 | 64 | 6% | 7 | |||
| Stack & Queue | 12 | 10 | 5 | 10 | 37 | 4% | 4 | ||||||
| Infix / Postfix | 2 | 5 | 6 | 13 | 1% | 3 | |||||||
| Trees | 4 | 8 | 12 | 8 | 5 | 12 | 6 | 10 | 65 | 6% | 8 | ||
| Tree Basics & Traversal | 4 | 5 | 3 | 5 | 7 | 3 | 27 | 3% | 6 | ||||
| Binary Search Tree | 3 | 3 | 3 | 10 | 19 | 2% | 4 | ||||||
| AVL Tree | 3 | 6 | 5 | 14 | 1% | 3 | |||||||
| Other Search Trees | 5 | 5 | <1% | 1 | |||||||||
| Heaps | 8 | 6 | 6 | 10 | 10 | 3 | 10 | 53 | 5% | 7 | |||
| Binary Heap | 8 | 6 | 3 | 10 | 10 | 3 | 10 | 50 | 5% | 7 | |||
| Advanced Heaps | 3 | 3 | <1% | 1 | |||||||||
| Complexity Analysis | 3 | 5 | 15 | 30 | 53 | 5% | 4 | ||||||
| Asymptotic Notation | 3 | 5 | 20 | 28 | 3% | 3 | |||||||
| Recurrences | 15 | 15 | 2% | 1 | |||||||||
| Randomized Analysis | 10 | 10 | 1% | 1 | |||||||||
| NP-Completeness | 10 | 10 | 20 | 40 | 4% | 3 | |||||||
| P / NP & Reductions | 10 | 10 | 20 | 2% | 2 | ||||||||
| Approximation Algorithms | 20 | 20 | 2% | 1 | |||||||||
| Network Flow | 15 | 15 | 30 | 3% | 2 | ||||||||
| Max Flow / Min Cut | 15 | 10 | 25 | 2% | 2 | ||||||||
| Bipartite Matching | 5 | 5 | <1% | 1 | |||||||||
| String Matching | 10 | 10 | 1% | 1 | |||||||||
| Automaton & Other Methods | 10 | 10 | 1% | 1 | |||||||||
| Hashing | 3 | 5 | 8 | <1% | 2 | ||||||||
| Collision Resolution | 3 | 5 | 8 | <1% | 2 | ||||||||
| Other | 8 | 8 | <1% | 1 | |||||||||
| Programming | 5 | 25 | 30 | 3% | 2 | ||||||||
| C / C++ Basics | 5 | 25 | 30 | 3% | 2 | ||||||||
| Arrays & Strings | 10 | 10 | 1% | 1 | |||||||||
| Control Flow & Loops | 5 | 5 | <1% | 1 | |||||||||
| Pointers | 5 | 5 | <1% | 1 | |||||||||
| I/O & Formatting | 5 | 5 | <1% | 1 | |||||||||
| Structs & Dynamic Memory | 5 | 5 | <1% | 1 |
分數最多的是 Shortest Paths & MST（156 分）與 Algorithm Design（154 分），Graph Traversal 141 分、十年每年都有。
重複出題清單
| 題目 | 出現年度 |
|---|---|
| adjacency matrix 表示的圖，traversal 終止於某頂點的所有邊 | 109 第一(3)題、110 第 3-1 題（題目相同）、114 第三(一)題 |
| array 5 3 8 9 1 7 0 2 6 4 以 5 為 pivot 做 partition | 109 第一(4)題、110 第 3-3 題 |
| hash k % 9、linear probing，插入 5、29、20、0、27、18 | 109 第一(5)題、110 第 4 題 |
| heap 10 8 6 2 1 4 5 做兩次 deleteMax | 109 第一(6)題、110 第 5 題 |
| Floyd-Warshall 的 d_ij(k) 意義、填 D(1)、negative weight | 106 第 8 題、111 第 7 題（兩年 (a) 相同）、115 第 9 題（填整張表） |
| LCS 的暴力解、DP recurrence、填表 | 108 第 4 題、112 第 8 題 |
| merge sort 比暴力排序省略了哪些計算 | 109 第六(b)題、112 第 7(a) 題（112 另問 quicksort） |
| AOE 網路的 critical activity | 107 第 5 題、109 第五題 |
| P、NP、NP-complete 的關係 | 107 第 8 題（Venn 圖）、108 第 6 題（reduction 方向） |
| greedy 演算法的理由 | 107 第 6(b) 題（Dijkstra）、109 第七(c)題（Prim）、112 第 9(a) 題（Huffman） |
| negative weight 對演算法的影響 | 106 第 8(c) 題、107 第 6(c) 題、109 第七(d)題、110 第 11 題、111 第 7(c) 題、114 第七題 |
| binary search 的程式填空 | 107 第 1(c) 題（遞迴）、108 第 2(c) 題（迭代） |
| infix 轉 postfix 用 stack | 106 第 2(2) 題、108 第 1.2 題、109 第三題 |
| AVL tree | 108 第 1.10 題、109 第二題、113 第 10 題 |
| binary tree 的高度、葉節點與節點數 | 108 第 1.8 題、113 第 8(a)(b) 題、114 第三(二)題 |
反覆出現的兩種題型
1. 一個主題連問三到五問
同一個經典問題連續問好幾小題，106 到 114 年每年都有一到三題，115 年沒有：
| 年度 | 主題 | 問法 |
|---|---|---|
| 106 第 6 題（15 分） | Randomized select | 第 4 行的 k 是什麼 → 最壞執行時間 → 造成最壞情況的 partition 序列 |
| 106 第 7 題（15 分） | Rod cutting | 第 8 行存什麼 → 實際算 → 修改成回傳切法 |
| 106 第 8 題（20 分） | Floyd-Warshall | d_ij(k) 的意義 → D(1) → 偵測負環 → 省空間的版本是否正確 |
| 107 第 6 題（15 分） | Dijkstra | 算的是什麼 → 為何是 greedy → 不適用的條件與例子 |
| 107 第 7 題（25 分） | maximum subarray | 暴力解 → 跨中點的線性時間做法 → recurrence → 線性時間 DP |
| 108 第 4 題（25 分） | LCS | 暴力解加複雜度 → DP recurrence 加複雜度 → 填表 |
| 109 第七題（20 分） | Prim | 用途 → 實際執行 → greedy 選擇為何最佳 → negative weight |
| 109 第八題（15 分） | max flow | residual network → 是否最大並以 cut 證明 → 多源多匯 |
| 110 第 11 題（20 分） | Johnson 演算法 | 設計理由 → reweighting → 計算 → 簡單的 reweighting 方法有什麼問題 |
| 111 第 6 題（20 分） | 0-1 Knapsack | 暴力解加複雜度 → DP recurrence → 填表 → 哪些 greedy 可行 |
| 112 第 8 題（20 分） | LCS | 暴力解加複雜度 → DP recurrence → 填表 → 為何這個最長路徑實例是多項式 |
| 112 第 9 題（15 分） | Huffman | 為何是 greedy → 實際建碼 → 最大碼長 |
| 113 第 13 題（30 分） | bipartite graph、最大匹配 | DFS → 是否 bipartite graph → 判斷演算法 → max flow／min cut → 如何解最大匹配 |
| 114 第八題（20 分） | TSP 2-approximation | 分三步證明 approximation ratio |
2. 給程式碼或結構，問它做什麼
| 年度 | 題目 |
|---|---|
| 106 第 2(1) 題 | 六個變數名稱沒有語意的 C++ 函式，找出哪個是 stack、queue、circular queue 的 Add 或 Delete |
| 110 第 7 題 | 一段 while 迴圈，畫出執行後的 linked list 與 Head、middle、trail 的指向 |
| 111 第 3 題（20 分） | 兩個用 array 實作的資料結構 X、Y，辨認它們是什麼、搭配的搜尋程序叫什麼 |
| 113 第 1 題 | 遞迴函式 f1(12345) 的輸出 |
| 113 第 2 題 | function pointer array 加 enum，執行 10 個輸入後印出的狀態 |
| 113 第 3 題 | 描述函式 f3 的功能 |
| 113 第 6 題 | 描述巨集 TEST 的用途 |
優先準備的五個主題
- Graph traversal。十年每年都有，包括 DFS／BFS 的拜訪順序（107、108）、DFS／BFS spanning tree（113）、strongly connected component（110）、dfn／low 與 articulation point（108、112、114）、biconnected component（106、113、114）、DFS 的邊分類（115），109 年考 adjacency matrix 表示法。
- Shortest path 與 negative weight。Floyd-Warshall（106 20 分、111、115）、all-pairs shortest paths 的 pseudo-code 與計算（107）、Johnson 演算法（110，20 分）、Dijkstra（106 程式追蹤、107 三問、110、113）、邊權加常數的影響（114）；negative weight 會讓哪些演算法出問題，六年問過。
- Dynamic programming。rod cutting（106）、maximum subarray（107）、LCS（108 25 分、112 20 分）、knapsack（111 20 分）、matrix-chain（115）。暴力解、recurrence、填表這個問法反覆出現。
- Heap、sorting 與 binary tree 的基本操作。108、109 年的選擇題與 110 年的選擇題大多是這類，109 與 110 年有四小題相同。
- C 程式填空與追蹤：stack 與 queue 的函式辨認、quicksort 與 shortestpath（106）、binary search（107、108）、sparse matrix 轉置與 circular linked list（112）、linked list 與 threaded tree（110）、用 linked list 實作 queue 與 Dijkstra（113）、stack 與 linked list 合併（114）。
考試形式
- 全卷 4–7 頁、6–13 題
- 作答於答案卷
- 卷面固定註明「請依序在答案卷上作答，並標明題號，不必抄題」「答案必須寫在指定作答區內，否則依規定扣分」
- 卷面十年都沒寫倒扣
- 108、109 年有選擇題，卷面另外提醒選擇題要寫在「作答區」、不要寫在「評分欄」
- 115 年是 10 題、每題 10 分
題型演變
| 年度 | 題數 | 頁數 | C／C++ 程式碼題 | 最大單題 |
|---|---|---|---|---|
| 106 | 8 | 7 | 31 分（第 2、3、4(2)、5(1) 題） | Floyd-Warshall 四問（20 分） |
| 107 | 8 | 5 | 6 分（第 1(c)(d) 題） | maximum subarray 四問（25 分） |
| 108 | 6 大題 | 6 | 15 分（第 2 題，其中 (c) 是 Java 寫法） | 選擇題 12 小題（28 分）、LCS 三問（25 分） |
| 109 | 8 大題 | 7 | 0 分 | 選擇題 9 小題（27 分）、Prim 四問（20 分） |
| 110 | 11 | 6 | 10 分（第 7、8 題） | Johnson 演算法（20 分）、merge sort 與 quick sort（20 分） |
| 111 | 7 | 4 | 0 分 | Knapsack 四問（20 分）、兩個 array 實作的資料結構（20 分） |
| 112 | 10 | 6 | 29 分（第 1、2、6 題） | LCS 四問（20 分） |
| 113 | 13 | 7 | 49 分（第 1–4、6、7、8(c)、11、12 題） | bipartite graph 與最大匹配（30 分） |
| 114 | 8 大題 | 5 | 20 分（第一題） | 第一題填空（20 分）、TSP 2-approximation 證明（20 分） |
| 115 | 10 | 6 | 0 分 | 每題都是 10 分 |
C／C++ 程式碼題指題目給 C 或 C++ 程式碼，要填空、追蹤輸出或自己寫的題目，pseudo-code 不計。113 年最多，題目有 gets()、字串常數、function pointer array、巨集與圍棋氣數函式。109、111、115 年沒有 C 或 C++ 程式碼題，題目都是 pseudo-code 與演算法分析。
成組的選擇題出現在 108 年（第 1 題 12 小題，單選加複選）、109 年（第一題 9 小題）、110 年（第 3 題 5 小題）、114 年（第三題 4 小題）與 115 年（第 6 題），其他年度只有零星的可複選小題（111 第 6(d) 題、112 第 4(b) 題）。
給 116 年考生的準備方向
- 卷面十年都沒寫倒扣，每一題都要寫。115 年第 6 題是選擇題，卷面寫明答案要完全正確才得分；108 年的複選題卷面沒寫給分方式。
- 答案要標明題號、寫在指定作答區內，不必抄題；108、109 年的選擇題另外提醒要寫在作答區。
- 106 第 8(d) 題、107 第 6(b) 題、108 第 6 題、109 第七(c)題、110 第 11(a)(i)、(d) 題、112 第 8(d) 題、112 第 9(a) 題這類題目問的是設計理由，要練習把每一步的理由寫出來。
- 110 第 11(d) 題考邊權減去常數對 shortest path 的影響，114 第七題考邊權加上常數對 MST 與 shortest path 的影響。
- 115 年是 10 題、每題 10 分，沒有 C 或 C++ 程式碼題。
本頁的題型、配分都取自各年度試卷上的標示，各章配分是逐題分類後加總的。如果發現有誤，歡迎來信指正。
最後更新：2026-10-22