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

各章配分

表中數字是各題的卷面配分，依主題加總。有子題的照子題分，沒有子題的整題算在主要考點，敘述判斷題算在多數選項所屬的主題。章與細項依十年合計排序，顏色越深，占當年總分的比例越高。Bloom filter 算在 Hashing，Patricia trie、digital search tree 這類 trie 算在 Other Search Trees，leftist、binomial、Fibonacci、min-max heap 算在 Advanced Heaps。

章／細項	106	107	108	109	110	111	112	113	114	115	合計	占比	年數
Complexity Analysis	28	20	10	30	25	10	10	10	10	12	165	16%	10
Recurrences	10	10	10	20	15	10	10	10	10	10	115	12%	10
Asymptotic Notation	18			10	10					2	40	4%	4
Amortized Analysis		10									10	1%	1
Trees	10	10			10	18	30	25	24	22	149	15%	8
Tree Basics & Traversal	10					4	5	5	8	3	35	4%	6
Other Search Trees						5	10	5		7	27	3%	4
Binary Search Tree		10			10			5			25	2%	3
Red-Black Tree						5	5	5	4	6	25	2%	5
B-Tree / B+ Tree						2	5	5	5	4	21	2%	5
AVL Tree							5		4	2	11	1%	3
Disjoint Set						2			3		5	<1%	2
Algorithm Design	10		6	10	20	10	20	20	30	16	142	14%	9
Dynamic Programming	10		4	10	10	10	20	20	20	10	114	11%	9
Greedy			2		10				10	6	28	3%	4
Graph Traversal	22	10	46	18		12		2	4	6	120	12%	8
Representation & BFS / DFS	12	10	26	12		12		2	4		78	8%	7
Topological Sort & DAG			20	6							26	3%	2
Connectivity	10									6	16	2%	2
Shortest Paths & MST		10	4	16	20	10	5	13	15	20	113	11%	9
Minimum Spanning Tree		10	4	16	10		5	3	5	6	59	6%	8
All-pairs Shortest Paths					10				10	10	30	3%	3
Single-source Shortest Paths						10		10		4	24	2%	3
Heaps	10	10			3	14	10	15	8	6	76	8%	8
Binary Heap	10	10			3	6	5	2		2	38	4%	7
Advanced Heaps						8	5	13	8	4	38	4%	5
Sorting & Searching	10	10	20	10		4	10	10			74	7%	7
Merge Sort & k-way Merge	10		20								30	3%	2
Sort Comparison & Lower Bound		10						10			20	2%	2
Quicksort				10		4					14	1%	2
Heapsort							10				10	1%	1
Hashing	10		4	16	10	8	5	5	3	12	73	7%	9
Bloom Filter				10		4		5		12	31	3%	4
Collision Resolution			4	6		4	5		3		22	2%	5
Hash Functions	10				10						20	2%	2
NP-Completeness		20	10		12	10				6	58	6%	5
P / NP & Reductions		10	10		9					6	35	4%	4
Approximation Algorithms		10			3	10					23	2%	3
Network Flow		10					10				20	2%	2
Max Flow / Min Cut		10					10				20	2%	2
Linear Structures						4			6		10	1%	2
Infix / Postfix						4					4	<1%	1
Stack & Queue									3		3	<1%	1
Array & Linked List									3		3	<1%	1

八校各章配分比較 →

重複出題

同一題隔幾年重複出現的清單如下。

題目	出現年度	備註
O(V) 時間判斷 undirected graph 有無環	106 第 7 題、108 第 5 題	同一題，108 年多寫一句與 \|E\| 無關
T(n) = 27T(n/3) + Θ(n³/lg n)	109 Part II 第 5 題、112 第 11 題	recurrence 完全相同，109 年寫 if possible、112 年要求緊界
Optimal BST	106 第 5 題、111 第 14 題、112 第 14 題	真實鍵數依序為 6、5、7
comparison sort 的下界 Ω(n log n)	107 第 7 題、113 第 14 題	完全相同
Floyd-Warshall 遞推式填空	110 第 9(2) 題、114 第 18 題	完全相同
system of difference constraints 求可行解	111 第 16 題、113 第 15 題	八條不等式的變數配對相同，只換常數；111 求一組可行解，113 求可行解集合
MST 上的路徑是否為 shortest path（是非）	108 第 1(2) 題、109 第 1(3) 題	完全相同
DFS 用 adjacency matrix／list 的複雜度（是非）	108 第 1(1) 題、109 第 1(4) 題	只換表示法
高度 h 的 heap 最多元素數	106 第 3 題、107 第 5 題、110 第 7(5) 題	三次，106 年另問最少
red-black tree 插入 62	111 第 3 題、113 第 8 題	插入值相同，起始的樹不同
max flow（給圖求 max flow 值）	107 第 8 題、112 第 15 題	只換圖
Bloom filter	109 第 2 題、111 第 4 題、113 第 5 題、115 題組 A	四次，115 年的 C 程式沒有寫出這個名稱
approximation ratio 計算	107 第 10 題（vertex cover）、111 第 17 題（set cover）	成對

表中 111–115 年的重複題，多數是 106–110 年的手寫題換了題型或換了數字。

冷門資料結構

下面這些結構在 108–115 年的卷子裡出現過：

結構	出現年度
Leftist tree（HBLT）	113、114、115
Binomial heap	114
Fibonacci heap（DecreaseKey／cascading cut）	111、113、115
Min-Max heap／Symmetric min-max heap	112、113、115
Patricia trie	111、112、113
Compressed trie／Digital search tree	112、114、115
Winner tree／Loser tree	108
2-3-4 tree／B\*-tree	111、112、113
Bloom filter（115 年的 C 程式沒有寫出名稱）	109、111、113、115

優先準備的五個主題

Recurrence 與 Master theorem。上表 Complexity Analysis 一章 165 分，recurrence 十年每年都有。109 Part II 第 5 題寫 if possible，110 第 6 題寫「若不適用要指出並說明」，112 第 11 題的 recurrence 與 109 年相同。
Optimal BST。考過三次（106、111、112），要填大型 DP 表。
冷門資料結構。見上表，是 111–115 年 Part I 的主要內容。上表 Trees 一章 111 年起每年 18–30 分。
Bloom filter。109 推導錯誤率，111 判斷查詢結果，113 問最佳 hash function 個數，115 以 C 程式出題。
Approximation ratio 與 NP reduction：107 第 10 題（vertex cover）、111 第 17 題（set cover）、115 第 16 題（是非，問 reduction 方向）。

題型演變

年度	結構	題數	頁數	倒扣
106	全手寫	9	2	未寫
107	全手寫（十題各 10 分）	10	3	未寫
108	全手寫	8	2	未寫
109	全手寫	8	2	未寫
110	全手寫	9	3	未寫
111	資結 12 題組＋演算法 5 題	17	16	未寫
112	資結 10 題選擇（多為複選）＋演算法 5 題	15	7	未寫
113	資結 10 大題選擇（每題一個正確答案，含 None of the above）＋演算法 5 題	15	10	未寫
114	單選 4＋複選 7＋問答 2＋演算法 5	18	11	未寫
115	問答 4＋單選 8＋複選 3＋是非 5＋問答 4	24	11	單選與是非答錯 −1，其餘未寫

111 年起卷子由 2–3 頁變成 7–16 頁，題型加入複選與填空。

給 116 年考生的準備方向

重複題表中的題目多數是 106–110 年的手寫題，這五年的手寫題值得先寫過一遍。
Part I 的答案要整理在答案卷第一頁的表格：111 年寫要用一頁做一張整合的表，112、113 年另寫「否則，不予計分」；114、115 年改成劃記答案卡。進場先看作答規定。
115 年明寫單選、是非答錯倒扣 1 分；106–114 年卷面沒有寫倒扣規則。
113–115 年有題目以情境包裝（neural network、排課、防火牆、MRI、微影機、影像去背），練習時要先找出底下是哪個經典問題。

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

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