台大資工所考古題解答軟體十年大統整（106–115）

各章配分

表中數字是各題的卷面配分，依主題加總。有子題的照子題分，沒有子題的整題算在主要考點。章與細項依十年合計排序，顏色越深，占當年總分的比例越高。

章／細項	106	107	108	109	110	111	112	113	114	115	合計	占比	年數
Algorithm Design	15	15	20	20	25	15	15	30	15	16	186	19%	10
Dynamic Programming	15	10	20	15	20	10	5	20	15	4	134	13%	10
Greedy		5		5		5	5			4	24	2%	5
Divide and Conquer					5			10		8	23	2%	3
Backtracking & Search Strategies							5				5	<1%	1
Trees	15	12		41	10	10	20	20	5	16	149	15%	9
Tree Basics & Traversal				20	10		10	10			50	5%	4
Binary Search Tree	15	4		3				10	5	4	41	4%	6
Red-Black Tree		2		3		10				4	19	2%	4
Disjoint Set				15						4	19	2%	2
AVL Tree		6					5				11	1%	2
B-Tree / B+ Tree							5			4	9	<1%	2
Sorting & Searching		6	20	14	5	27	31	5		12	120	12%	8
Quicksort		4	20	3	5	8				4	44	4%	6
Merge Sort & k-way Merge				6		3	26				35	4%	3
Selection & Binary Search				5		5		5		4	19	2%	4
Sort Comparison & Lower Bound						5	5				10	1%	2
Linear-time Sorts		2				3				4	9	<1%	3
Elementary Sorts						3					3	<1%	1
Shortest Paths & MST	25	20	6		10	15	10		10	4	100	10%	8
Single-source Shortest Paths	25	20	6			5	5		5		66	7%	6
Minimum Spanning Tree					10	5	5		5	4	29	3%	5
All-pairs Shortest Paths						5					5	<1%	1
Complexity Analysis	20	14		6				5	25	16	86	9%	6
Amortized Analysis		14						5	5	8	32	3%	4
Recurrences	20								10		30	3%	2
Asymptotic Notation				3					5	4	12	1%	3
Randomized Analysis				3					5	4	12	1%	3
NP-Completeness				10	10	5		30	20	8	83	8%	6
P / NP & Reductions				10	10	5			10	8	43	4%	5
Approximation Algorithms								20	5		25	2%	2
Linear / Integer Programming								10	5		15	2%	2
Heaps		10	18	6		13	5	5		4	61	6%	7
Binary Heap		10	18	6		13	5			4	56	6%	6
Advanced Heaps								5			5	<1%	1
Hashing		10	13		10	5	5		5	8	56	6%	7
Collision Resolution		8	13		10	5	5			8	49	5%	6
Hash Functions		2							5		7	<1%	2
Linear Structures		8	15	3	15		5			4	50	5%	6
Stack & Queue		8	10	3	10					4	35	4%	5
Infix / Postfix			5				5				10	1%	2
Array & Linked List					5						5	<1%	1
Network Flow	25				5	5			10	4	49	5%	5
Bipartite Matching	25									4	29	3%	2
Max Flow / Min Cut					5	5			10		20	2%	3
String Matching					10	5	9			4	28	3%	4
KMP / Failure Function					5	5	9			4	23	2%	4
Automaton & Other Methods					5						5	<1%	1
Graph Traversal		5	8					5		4	22	2%	4
Representation & BFS / DFS		5	8							4	17	2%	3
Topological Sort & DAG								5			5	<1%	1
Other									10		10	1%	1

八校各章配分比較 →

台大軟體的三個特點

1. 情境包裝題

台大常把經典問題包進一個應用情境：

年度	題目長相
106 第 5 題	班級分配教室
108 第 9 題	14 艘船過河、航線交叉要等 15 分鐘
108 第 10 題	圖形替換求最小成本
109 第 15 題	SNP 基因標記選擇，並要證明 NP-complete
110 第 2–5 題	Snake sequence
114 第 3 題	DNA 序列分群
114 第 4 題	蛋白質序列比對
114 第 7 題	球隊是否已被淘汰

遇到陌生的情境，先想這是哪個經典問題換了皮。

2. 超出課本的進階內容

近三年（113–115）每年都有幾題超出一般資料結構課本的內容：

114 第 2 題：Akra-Bazzi theorem
114 第 11 題：universal hashing 的最壞期望碰撞數
114 第 16 題：integrality gap
114 第 19(b) 題：subset sum 的 FPTAS
113 第 13 題：vertex cover 兩種 approximation algorithm 的 ratio bound 比較
115 第 3 題：AlphaTensor 的 4×4 matrix multiplication
115 第 9 題：FFT 靠 roots of unity 的哪個性質加速

選擇題部分每題 4–5 分，113 年第 13 題的證明或反證是 10 分。不用為了它們放掉基本題。選擇題考的多是哪個敘述成立，結論與適用條件要知道。

3. 「哪個敘述正確／錯誤」的選項

近三年很多，錯的選項常常只差一個前提條件：

112 第 12 題：邊權加上同一個常數對 shortest path 的影響
115 第 25 題：cut property 的前提條件有沒有寫完整
115 第 15 題：hash table 擴張的真正理由，和幾個干擾選項
113 第 3 題、115 第 19 題：dynamic array 縮小門檻的設計

這種題光背複雜度沒用，要能說出為什麼。

優先準備的六個主題

依上表十年合計，前六章是：

Algorithm Design，186 分，十年每年都有。Dynamic programming 一項就 134 分：LCS、matrix chain（111 年直接考 CLRS 的原始範例，113 年考遞迴式裡各項的相依次數）、knapsack、格子 DP、區間切段 DP 都考過。Divide and conquer 有 113 年的 majority hash value（10 分）與 115 年的 AlphaTensor、FFT。
Trees，149 分，十年考九年。BST 考了六年，red-black tree 考了四年（111 年兩題共 10 分，115 年考擴充 size 欄位）。109 年第 14 題樹的直徑與中心一題 20 分，113 年有 re-rooting。
Sorting & Searching，120 分，十年考八年。Quicksort 六年有題，108 年第 5 題 20 分，(c) 小題考三路分割。112 年第 15 題合併 k 條已排序 linked list 的三種做法一題 21 分。
Shortest Paths & MST，100 分，十年考八年。106、107 是 25、20 分的設計題（106 DAG 上的最少天數、107 地震後最早修通的路徑），110–112、114、115 年各有一到三題選擇題（113 年沒有），問 Kruskal 與 Prim 的加入順序、Dijkstra 的前提、cut property、邊權加常數的影響。
Complexity Analysis，86 分，十年考六年。需要變數代換的 recurrence 在 106、114 都出現過。Amortized analysis 在 107、113、114、115 都有，114 年要自己設計 potential function。
NP-Completeness，83 分，十年考六年。A ≤_p B 代表誰比較難，畫張圖弄清楚。Set Cover、Vertex Cover、Subset Sum 三個 reduction 要能默寫。113 年 vertex cover 的 approximation algorithm 與 ILP 一題 30 分。

接下來是 Heaps（61 分）、Hashing（56 分）、Linear Structures（50 分）、Network Flow（49 分）。Hash 十年考七年，手動跑 probing、double hashing 的探測條件（108、115 各考一次）、chaining 的期望比較次數，都要能算。Network flow 要會把二分圖匹配、球隊淘汰、min cut 轉成 flow network。KMP 的 failure function 在 110、111、112、115 都出現，每次 4–9 分。

題型演變

年度	結構	選擇題	手寫	頁數
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 頁。113 年起不少題目要先讀完半頁以上的演算法描述。

倒扣規則逐年對照

台大軟體沒有固定的倒扣政策，每年進場都要先看卷首。

年度	倒扣方式	該不該猜
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 年卷面明寫答錯得 0 分，115 年卷首沒有寫計分方式。110 年扣 2.5 分、107 年扣滿該題分數，116 年還是不能預設不扣。

給 116 年考生的準備方向

進場先讀卷首的計分規定。106、107、110、112、113 年有倒扣，方式各不相同；114 年明寫答錯不扣分，115 年卷首沒寫計分方式。
優先練 112–115，這四年都是選擇題為主。106–109 的手寫題也值得寫，因為同樣的觀念會換成選擇題再出現，例如 106 的班級分配教室和 114 的球隊淘汰，都是 max flow 建模。
時間要抓。115 年 25 題、每題 4 分，題數是十年最多。113 年題目敘述長到半頁，光讀題就很花時間。
手寫題多半是設計演算法加證明或分析（106、107、109、113、114），108 年是補程式與填空。106 年第 4、5 題明文禁止寫程式碼，要練用文字和圖把演算法講清楚。

本頁的題型、配分、倒扣規則都取自各年度試卷上的標示，各章配分是逐題分類後加總的。如果發現有誤，歡迎來信指正。

台大資工所考古題詳解軟體十年大統整（106–115）