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

各章配分

表中數字是各題的卷面配分，依主題加總。有子題的照子題分，沒有子題的整題算在主要考點，敘述判斷題算在多數選項所屬的主題。Programming 與資料結構演算法分開列，各自依十年合計排序，顏色越深，占當年總分的比例越高。C/C++ 那一半全部算在 Programming，手寫程式與除錯另成一章；106 年第 13 題排在資料結構那一段，但要用 C 寫出整支 BST 程式，也算在 Program Writing。

章／細項	106	107	108	109	110	111	112	113	114	115	合計	占比	年數
Programming	65	50	50	50	50	48	50	50	50	50	513	51%	10
C / C++ Basics	35	34	37	5	15	18	29	50	25	29	277	28%	10
Arrays & Strings	5	18	8		5	12	4	5		8	65	6%	8
Pointers	5	8			10	2	10	10	10		55	6%	7
Functions & Parameter Passing	15	8	7	5		2		10			47	5%	6
I/O & Formatting			8				10	12	5	3	38	4%	5
Expressions & Operators	5		2			2		6	10	9	34	3%	6
Control Flow & Loops	5		3				5	7			20	2%	4
Structs & Dynamic Memory			9							9	18	2%	2
Object-oriented Programming	15	16	6	5	15	15	15		25	12	124	12%	9
Inheritance & Polymorphism	15	15	2	1	15				25		73	7%	6
Classes & Objects		1	4	4		14	15			8	46	5%	6
Templates & STL						1				4	5	<1%	2
Program Writing & Debugging	15		7	40	20	15				9	106	11%	6
Program Writing	15			20	10	15				9	69	7%	5
Debugging			7	20	10						37	4%	3
Other							6				6	<1%	1
Data Structures & Algorithms	35	50	50	50	50	52	50	50	50	50	487	49%	10
Trees	2	11	13	12	3	9	13	12	15	3	93	9%	10
Tree Basics & Traversal			5	4	3	6	7	3		3	31	3%	7
AVL Tree				4		3	3	9	5		24	2%	5
Binary Search Tree		11	8								19	2%	2
Red-Black Tree				4			3		5		12	1%	3
B-Tree / B+ Tree	2								5		7	<1%	2
Shortest Paths & MST	2	11	7		13	19	7	12	5	3	79	8%	9
All-pairs Shortest Paths		4	5		5	15	5		5		39	4%	6
Single-source Shortest Paths	2	4	2		8	4	2	10		3	35	4%	8
Minimum Spanning Tree		3						2			5	<1%	2
Sorting & Searching	11		16	11	3	9	10	4	10	2	76	8%	9
Sort Comparison & Lower Bound	5		13		3	4	4		5		34	3%	6
Quicksort	2			5			2		5	2	16	2%	5
Heapsort	2		3	3		3					11	1%	4
Linear-time Sorts				3			2				5	<1%	2
Elementary Sorts	2						2				4	<1%	2
Selection & Binary Search						2		2			4	<1%	2
Merge Sort & k-way Merge								2			2	<1%	1
Graph Traversal	2	16	5	3	9	6	9	2		19	71	7%	9
Connectivity					9	4	2			16	31	3%	4
Representation & BFS / DFS		10	5	3			5				23	2%	4
Topological Sort & DAG	2	6				2	2	2		3	17	2%	6
Complexity Analysis	12	2			8		2	6	5	10	45	4%	7
Recurrences	12	2			8			6	5		33	3%	5
Amortized Analysis										10	10	1%	1
Asymptotic Notation							2				2	<1%	1
Network Flow				10			6	5	5	5	31	3%	5
Max Flow / Min Cut				10			6	5		5	26	3%	4
Bipartite Matching									5		5	<1%	1
Algorithm Design	4	3		3	9	4			5		28	3%	6
Dynamic Programming		3		3	6				5		17	2%	4
Greedy	4				3	4					11	1%	3
Linear Structures	2	2		4		3		6		3	20	2%	6
Infix / Postfix		2		4		3		6		3	18	2%	5
Array & Linked List	2										2	<1%	1
String Matching				4	5			3		3	15	2%	4
KMP / Failure Function				4	5			3		3	15	2%	4
Heaps		3	3				3		5		14	1%	4
Binary Heap		3	3				3		5		14	1%	4
NP-Completeness		2	4	3							9	<1%	3
P / NP & Reductions		2	4	3							9	<1%	3
Hashing			2			2				2	6	<1%	3
Collision Resolution			2			2				2	6	<1%	3

八校各章配分比較 →

Programming 十年合計 513 分，106 年連同手寫 BST 有 65 分，111 年 48 分，其餘八年都是 50 分。資料結構演算法這邊 Trees 93 分最多、十年每年都有，接著是 Shortest Paths & MST 79 分、Sorting & Searching 76 分、Graph Traversal 71 分。

重複出題清單

題目	出現年度	備註
articulation point（dfn／low）	110 第 3 題、111 第 16 題、115 第 17–19 題	三次
KMP failure function	109 第 11 題、110 第 6 題、113 第 6 題、115 第 22 題	四次
由 inorder 加 postorder 重建 binary tree	110 第 4 題、113 第 7 題、115 第 23 題	用同一組序列：A,B,G,E,D,I,J,F,H,C ／ G,E,J,I,H,F,D,C,B,A
red-black tree 插入 50, 10, 80, 90, 70, 60, 65, 62	109 第 10 題、112 第 9(5) 題	同一組數字
AOE network 的 critical path	111 第 17.1 題、115 第 21 題	同一張圖
constructor 的回傳型別、`this` pointer	112 第 6 甲、7 乙題、115 第 7、8 題	115 第 7 題與 112 第 7 乙選項相同；115 第 8 題的前三個選項與 112 第 6 甲相同，但改問哪個不正確
排序演算法是否 asymptotically optimal	108 第 9 題、111 第 18 題、112 第 10(a) 題、114 第 7(d) 題	四次
negative-weight edge 上的 Dijkstra、reweighting	107 第 12 題、110 第 5、11 題、111 第 19 題、112 第 11 題	110–112 連三年，108 第 10、11 題考 Johnson
Dijkstra 頂點選取順序	107 第 6(a) 題、108 第 4(a) 題、110 第 5.1 題、111 第 17.2 題、113 第 8 題、115 第 24 題	六次
swap 函式	106 第 6 題（C 與 C++ 各寫一次）、107 第 16 題（連呼叫的引數一起填）、109 第 6 題
運算式轉 postfix	107 第 8 題、109 第 8 題	111、113 考 prefix，113、115 考運算式樹
binary tree 形狀的計數	109 第 9 題、112 第 9(4) 題
max flow	109 第 14 題、112 第 12 題、113 第 22 題、114 第 6、10 題、115 第 13 題	五個年度
2-3-4 tree 與 B-tree 的關係	114 第 2 題	四個敘述裡有三個與成大 112 第 6 題相同

C/C++ 考點細目

表上的 Programming 只分到章與細項，下面列出各年考過的具體語法點。

主題	出現年度
const pointer、pointer to const	110、112、114
virtual function、abstract class 與 dynamic binding	107、108（pure virtual）、110、114
inheritance 與存取權限（含 multiple inheritance）	106、107
name hiding 與 object slicing	114
constructor、destructor、copy constructor	106、107、108、109、110、111、112、115
`this` pointer	112、115
reference 與 pointer	106、107、108、110、112、114
pointer arithmetic 與 pointer to array	106、107、108、111、112、113、115
compile error 與 undefined behavior 的判斷	107、115
bitwise operation	111、114、115
printf 格式指定符	112、113、114
字串函式與字串操作（strcmp／strdup／strcpy／strcat／fgets）	106、107、108、109、110、111、113
template	111、115
operator overloading	115
debugging	108、109、110、115
手寫或填空程式	106、107、109、110、111、113、115
名詞配對	111、113、114

優先準備的五個主題

C/C++ 語法與程式題。每年 48 分以上，表上 C / C++ Basics 合計 277 分最多，其中 Arrays & Strings 65 分、Pointers 55 分。OOP 部分 Inheritance & Polymorphism 73 分，106、107、110 年各 15 分，114 年 25 分。手寫與除錯六年有，109 年兩者合計 40 分。
Trees。十年每年都有，AVL tree 五年、red-black tree 三年，BST 的建立與刪除在 107、108 年，由 inorder 加 postorder 重建 binary tree 考了三次。
Shortest path。Dijkstra 頂點選取順序考了六次；negative-weight edge 與 reweighting 在 107、110、111、112 年都有，111 年第 19 題連 Floyd-Warshall 共 17 分，108 年考 Johnson。
排序。十年九年有（107 年沒有），問法有 stability、是否 asymptotically optimal、quicksort 逐趟追蹤、比較排序的下界。
Graph traversal 與 connectivity。articulation point 的 dfn／low 在 110、111、115 年考三次，115 年另有 10 分的 biconnected component；topological sort 與 AOE critical path 合計六年有。

KMP failure function 合計 15 分，但 109、110、113、115 年考了四次；max flow 五個年度出現。

題型演變

年度	C/C++ 題配分	題數	頁數	計分規定
106	65	13	5	卷面沒有特別的計分規定
107	50	16	5	第 10 題是非題答錯要改正錯誤的部分，單純否定不給分
108	50	14	6	第 8 題答錯每個選項倒扣 1 分，最多扣到 5 分；第 7 題答錯要改正錯誤的部分
109	50	14	4	第 13 題是非題答錯要改正錯誤的部分，單純否定不給分
110	50	15	6	第 10、11 題明訂只答 yes 或 no 不給分
111	48	20	6	卷面沒有特別的計分規定
112	50	12	5	第 5、6、7 題（21 分）複選沒有部分給分；第 11 題只答 yes 或 no 不給分
113	50	23	7	第 1–9 題要寫在第一頁的選擇題作答區，否則不計分
114	50	15	5	第 1、2、6–10 題為複選題，卷面沒有寫計分方式
115	50	25	8	第 1–24 題（91 分）為複選題，沒有部分給分

C/C++ 題配分包含語法、程式輸出、debugging、手寫程式與名詞配對。十年之中有八年是 50 分，111 年是 48 分；106 年第 1–8 題是 50 分，再加上第 13 題用 C 手寫 BST 的 15 分，共 65 分。

給 116 年考生的準備方向

C/C++ 每年都有 48 分以上，106 年連同手寫 BST 是 65 分。106、107、108、109、110、111、113、115 年有手寫、填空或 debugging 題，112 年第 1 題要寫單行 C 敘述式，114 年的 C/C++ 只有程式輸出與名詞配對。
複選題沒有部分給分的規定出現在 112 年（第 5、6、7 題，21 分）與 115 年（第 1–24 題，91 分）。114 年的複選題卷面沒有寫計分方式。
重複題有 articulation point、KMP failure function、inorder 加 postorder 重建、Dijkstra 頂點順序、AOE critical path。
115 年出現 amortized analysis（第 11 題 dynamic array、第 12 題 stack 的 potential function），106–114 年都沒有。
110 第 10、11 題與 112 第 11 題明訂只答 yes 或 no 不給分，111 第 18、19 題也要寫理由。107 第 10 題、108 第 7 題、109 第 13 題的是非題答錯要改正錯誤的部分，單純否定不給分。
115 年卷面的系所組別只寫「資訊工程學系」，沒有標甲組。

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

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