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

各章配分

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

章／細項	106	107	108	109	110	111	112	113	114	115	合計	占比	年數
Trees	21	30	12	15	20	22.5	15	13	19	25	192.5	19%	10
Red-Black Tree	6	10			6.5	2.5	3		13	8	49	5%	7
Binary Search Tree				5	7.5	10	3	5		17	47.5	5%	6
Tree Basics & Traversal	5	20					6	3			34	3%	4
B-Tree / B+ Tree	6		6	6	3.5			5	6		32.5	3%	6
AVL Tree	4		6			10	3				23	2%	4
Disjoint Set				4	2.5						6.5	<1%	2
Shortest Paths & MST	20	20	15	15	7	12.5	12	19	9	16	145.5	15%	10
Minimum Spanning Tree	15	5	5	7	3.5	5	8	6	6	7	67.5	7%	10
Single-source Shortest Paths	5		10	8	3.5	7.5	4	13	3	9	63	6%	9
All-pairs Shortest Paths		15									15	2%	1
Algorithm Design	10	10	14	15	13.5	5	15	14	27		123.5	12%	9
Dynamic Programming		10	14	9	4	5	7	14	16		79	8%	8
Greedy	10				9.5		2		11		32.5	3%	4
Divide and Conquer				6			6				12	1%	2
Linear Structures	10	10	15	5	4	12.5	7	7		10	80.5	8%	9
Array & Linked List	5	10	10	5	4	5				10	49	5%	7
Stack & Queue			5			5	7	7			24	2%	4
Infix / Postfix	5					2.5					7.5	<1%	2
Network Flow	5	10	14	10	9.5	2.5	8	5	10		74	7%	9
Max Flow / Min Cut	5	10	14	10	9.5	2.5	4	5	10		70	7%	9
Bipartite Matching							4				4	<1%	1
Sorting & Searching	10		6	5	13	7.5	22	5		5	73.5	7%	8
Quicksort	10		6			2.5		5			23.5	2%	4
Selection & Binary Search					2.5		15			5	22.5	2%	3
Sort Comparison & Lower Bound					7	2.5					9.5	<1%	2
Elementary Sorts				2.5		2.5	4				9	<1%	3
Linear-time Sorts					3.5						3.5	<1%	1
Merge Sort & k-way Merge							3				3	<1%	1
Heapsort				2.5							2.5	<1%	1
NP-Completeness	3	15	8	19	8	10				5	68	7%	7
P / NP & Reductions	3	15	8	19	8	10				5	68	7%	7
Complexity Analysis	2	5			16	7.5	9	10	15		64.5	6%	7
Recurrences	2	5			3.5	5	3	10	15		43.5	4%	7
Asymptotic Notation					9.5	2.5	2				14	1%	3
Amortized Analysis					3		4				7	<1%	2
Heaps	9		10	5	3	5	6		9	14	61	6%	8
Binary Heap	5		10	5	3	5	6		9	14	57	6%	8
Advanced Heaps	4										4	<1%	1
Graph Traversal			6	6	3	5	3		3	25	51	5%	7
Topological Sort & DAG					3					19	22	2%	2
Representation & BFS / DFS			6			5	3		3		17	2%	4
Connectivity				6						6	12	1%	2
Other						2.5		21	8		31.5	3%	3
Other						2.5		15	8		25.5	3%	3
Computational Geometry								6			6	<1%	1
Hashing	5			5	3	7.5	3	6			29.5	3%	6
Collision Resolution	5			5	3	7.5	3	6			29.5	3%	6
String Matching	5										5	<1%	1
KMP / Failure Function	5										5	<1%	1

八校各章配分比較 →

交大軟體的三個特點

1. 題組全對制

108、109、113、114 四年都採題組全對制，108 年卷面原文是：

「For each problemset, if your answer is correct for all the questions in the problemset, you receive the full points; or otherwise ... you receive 0 point.」

一個題組動輒 6–13 分，錯一小題整組歸零。108 年第 9 題組（Dijkstra 程式追蹤）10 分、109 年第 3 題組（Hamiltonian reduction）13 分，都要三、四個小題全對才給分。所以不用每題都猜一點，把會的題組做到完全正確比較划算。

2. 給程式碼，問它在做什麼

十年裡有九年（只有 110 年沒有），而且愈來愈進階：

年度	題目
106 第 3 題	對 linked list 做條件式交換
107 第 5、6 題	兩支遞迴函式、三支 linked list 函式
108 第 9 題組	8×8 矩陣與雙層迴圈
111 第 5 題	一段 pseudo-code，問功能與複雜度
112 第 9 題	兩個指標掃描的 pseudo-code，要填空
113 第 2 題組	遞迴的排序函式
113 第 6 題組	兩支數字處理函式，問它在解什麼問題
114 第 14 題	`foo1`／`foo2`／`foo3`，判斷各自能解什麼
115 第 12–14 題	三支有 bug 的程式，找出 bug 並修正

這類題只記得演算法名字沒用，要能逐行讀懂程式。

3. Hamiltonian reduction 連考三年

107、108、109 連續三年考同一系列：給 HamP(G) 或 HamC(G) 當黑盒子，要在指定的複雜度內拿它解一個變形問題。

107 第 10 題（15%）：由 HamP 建構 HamEx（路徑端點不能是 x），並證明正確性
108 第 16 題組（8%）：補完 HamC3（x、y、z 三點連續）的三個空格
109 第 3 題組（13%）：補完 HamP2x3（從 a₁/a₂ 出發、停在 x₁/x₂/x₃）的四個空格

三題建議一起練。

優先準備的五個主題

依上表十年合計：

Trees，192.5 分，十年每年都有。Red-black tree 考了七年，BST、B-tree 各六年，AVL 四年。旋轉、著色與節點數界、B-tree 的分裂與 minimum degree 都出現過，108、109、113、114 年又是題組全對制。
Shortest Paths & MST，145.5 分，十年每年都有。MST 十年都考，shortest path 也是十年都有（107 年是給一段 pseudo-code 問它在算什麼）。要能從程式碼認出是 Dijkstra、Bellman-Ford 還是 Floyd-Warshall（114 第 14 題），也要能手動追蹤（108 第 9 題組、115 第 1–3 題）。
Algorithm Design，123.5 分，十年考九年。DP 一項 79 分、考了八年：107 年 maximum subarray、108 年加括號與 knapsack、109 年 prefix-sum 條件的子序列、113 年回文雙峰子序列、114 年 DAG 上的最大權重路徑與最長回文子序列。
Linear Structures，80.5 分，十年考九年。多半是 linked list、stack、queue 的程式追蹤或填空（106 第 3 題、107 第 6 題、113 第 1 題組、115 第 13 題）。要實際寫過程式才有感覺，只看講義不夠。
Network Flow，74 分，十年考九年。Bipartite matching（112 第 21 題）、雙處理器排程（109）、edge-disjoint 與 node-disjoint paths（114）用的是同一套工具。

另外，median of medians 的分組大小在 110 第 30 題、112 第 18 題考了兩次，分組大小的選擇和理由都要能說明。

題型演變

年度	結構	選擇題	手寫	頁數
106	手寫 17 題	0%	100%	3
107	手寫 10 題	0%	100%	5
108	16 題組、38 小題	100%	0%	9
109	15 題組、36 小題	100%	0%	7
110	30 題多選	100%	0%	8
111	40 題多選	100%	0%	12
112	選擇 16＋手寫 10	50%	50%	9
113	選擇 8 題組＋手寫 4	50%	50%	9
114	選擇 14 題組＋手寫 7	51%	49%	7
115	單選 8＋簡答 3＋除錯 3＋手寫 3	24%	76%	9

115 年是十年來結構變動最大的一年：新增 25 分的程式碼除錯題，手寫比重拉到 76%。

計分規則逐年對照

年度	計分方式	該不該猜
106	全手寫，不涉及倒扣	—
107	全手寫，第 10 題漸進較慢不給部分分數	—
108	題組全對才給分，錯一小題整組 0 分	全填，重點是會的題組不能錯
109	同上	同上
110	多選，全對才給分，卷面明寫答錯不倒扣	全填
111	同上（40 題每題 2.5 分，卷面明寫答錯不倒扣）	全填
112	多選須全選到，卷面未提倒扣	全填
113	題組全對才計分，卷面未提倒扣	全填
114	同上	全填
115	單選答錯倒扣 1 分；第四部分（非選擇題，第 15–17 題）可答 PASS 得 1 分	單選要有把握；第 15–17 題不會就寫 PASS

十年裡卷面寫明倒扣的只有 115 年。「全對才給分」從 108 年起連續七年（108–114），115 年改成單選倒扣。與其多做幾題，不如把會的題目做到零失誤。PASS 只限 115 年第四部分的第 15–17 題，簡答題與除錯題沒有這個選項。

給 116 年考生的準備方向

優先練 112–115。112 到 114 年選擇、手寫各約一半，115 年手寫佔 76%。108–111 的全選擇題可以拿來練判斷的精確度。
題組全對制下，寧可少答也不要半猜。時間花在確認每個選項，比多掃幾題有用。
115 年新增的程式碼除錯題很可能會延續，建議在紙上練習找 bug。
115 年第四部分的 PASS 規則如果延續，不會的題寫 PASS 拿 1 分，不要硬掰。簡答題與除錯題沒有 PASS。
交大有重複前一年題目的習慣：111 第 6 題和 110 第 7 題一字不差，113 和 112 的 residual network 圖相同。練考古題時相鄰兩年建議一起看。

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

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