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

各章配分

表中數字是各題的卷面配分，依主題加總。有子題的照子題分，沒有子題的整題算在主要考點，是非題各小題分開算。離散與線代分開列，各自依十年合計排序，顏色越深，占當年總分的比例越高。106、109 年由 tridiagonal matrix 的 determinant 導出遞迴式那題算在離散的 Recurrences，108 年的 max flow 算在離散的 Graph Theory。

章／細項	106	107	108	109	110	111	112	113	114	115	合計	占比	年數
Linear Algebra	50	50	50	50	50	50	50	50	50	50	500	50%	10
Eigenvalues & Diagonalization	30	10	30	15	10		16	12	10		133	13%	8
Eigenvalues & Eigenvectors	15		15		10		13	10	10		73	7%	6
Matrix Powers & Functions	15			15							30	3%	2
Diagonalization & Similarity			15				3	2			20	2%	3
Jordan Form		7									7	<1%	1
Cayley-Hamilton & Minimal Polynomial		3									3	<1%	1
Vector Spaces	20	20		5			22	12	20		99	10%	6
Rank & Nullity		20		5			13	2	20		60	6%	5
Subspaces & Direct Sums	10							10			20	2%	2
Basis, Dimension & Coordinates	10						9				19	2%	2
Symmetric & Normal Matrices		15	10		15	40		2	4	10	96	10%	7
Positive Definite & Quadratic Forms		10	10			20		2	4	10	56	6%	6
SVD & Pseudo-inverse		5			15						20	2%	2
Spectral Theorem & Orthogonal Diagonalization						20					20	2%	1
Inner Product Spaces		5		20	25	10	9	2	6	10	87	9%	8
Least Squares				5	10					10	25	2%	3
Gram-Schmidt & QR				10	15						25	2%	2
Inner Products & Norms						10	9				19	2%	2
Orthogonal Projection & Complement		5		5				2	6		18	2%	4
Matrices & Linear Systems			10							30	40	4%	2
Linear Systems & Row Reduction			10							30	40	4%	2
Determinants							3	12	10		25	2%	3
Linear Transformations				10							10	1%	1
Matrix Representation & Change of Basis				5							5	<1%	1
Linearity, Kernel & Range				5							5	<1%	1
Other								10			10	1%	1
Discrete Mathematics	50	50	50	50	50	50	50	50	50	50	500	50%	10
Recurrences & Generating Functions	25	10	15	20	10		20	32	10	10	152	15%	9
Linear Recurrence Relations	25	10	15	20			10	7	10	10	107	11%	8
Generating Functions							10	25			35	4%	2
Other Recurrences					10						10	1%	1
Graph Theory			20	20	5	20		5		20	90	9%	6
Graph Algorithms			20			10					30	3%	2
Planar Graphs				20						10	30	3%	2
Trees					5			5			10	1%	2
Coloring & Independent Sets						10					10	1%	1
Graph Basics & Isomorphism										10	10	1%	1
Counting	10			10	5	20	10		10	10	75	8%	7
Permutations & Combinations						20	10				30	3%	2
Pigeonhole Principle				10	5					10	25	2%	3
Integer Solutions & Distributions	10								10		20	2%	2
Sets, Relations & Functions			15		5	10	10		10		50	5%	5
Sets						10			10		20	2%	2
Partial Orders & Lattices			15								15	2%	1
Functions					5		10				15	2%	2
Automata & Languages								13	20	10	43	4%	3
Finite State Machines								13	20	10	43	4%	3
Probability		30									30	3%	1
Number Theory		10					10				20	2%	2
Modular Arithmetic		10					10				20	2%	2
Logic & Proofs					20						20	2%	1
Proof Techniques & Induction					20						20	2%	1
Algebraic Structures	15										15	2%	1
Rings & Fields	15										15	2%	1
Other					5						5	<1%	1

八校各章配分比較 →

離散這邊 Recurrences & Generating Functions 合計 152 分、十年考九年，是全卷分數最多的一章。線代這邊是 Eigenvalues & Diagonalization（133 分，十年考八年）。

重複出題清單

題目	出現年度
circulant matrix 的 eigenvalue	108 第 1 題、110 第 6 題
tridiagonal matrix 的 determinant 遞迴	106 第 6 題、109 第 5 題
Gram-Schmidt QR decomposition	109 第 2 題、110 第 5(a) 題（110 年接著解 least squares 問題）
matrix exponential e^A、e^At	109 第 3 題（計算）、111 第 8 題（證明性質）
「UU^T = I」是否成立	109 第 1(e) 題、114 第 9(c) 題
row equivalent 矩陣的 determinant 是否相等	112 第 10(c) 題、114 第 7(D) 題
nonhomogeneous recurrence	112、113、114、115
planar graph 的 Euler 公式與邊界	109 第 6 題、115 第 2 題
pigeonhole principle	109 第 4 題、110 第 2(b) 題、115 第 3 題
finite state machine	113 第 4 題、114 第 1 題、115 第 5 題

常考的四個題型

1. Recurrence（十年中九年有，111 年沒有）

112、113、114、115 年是右式為常數或指數的 nonhomogeneous recurrence，107 到 110 年為齊次、耦合或由演算法導出的遞迴，106 年右式寫成 sin(nπ)：

年度	Recurrence	類型
106	6a_n−5a_n−1+a_n−2 = sin(nπ)	右式是三角函數
107	3a_n−6a_n−1−3a_n−2+6a_n−3 = 0	三階
108	A(n)、B(n) 耦合遞迴	兩個數列互相依賴
109	tridiagonal matrix 的 determinant D_n 的遞迴	由矩陣導出 recurrence
110	divide-and-conquer 演算法的比較次數 T(N)	由演算法導出 recurrence
112	a_n+2−5a_n+1+6a_n = 2	常數右式
113	a_n+2−4a_n+1+3a_n = −200	常數右式
114	a_n−3a_n−1 = 5·3ⁿ	指數右式
115	E_n−4E_n−1+4E_n−2 = 2ⁿ+3ⁿ	右式有兩項指數

2. 矩陣分解（107、108、109、110、115 年）

LU（108、115）、QR／Gram-Schmidt（109、110）、SVD 與 Jordan form（107）、pseudo-inverse（110）。

3. Graph theory 的計數與 planarity（108、109、110、111、113、115 年）

spanning tree 計數（110）、tree 的計數（113）、simple graph 與 connected component 計數（115）、chromatic number（111）、planar graph 判定（109、115）、minimum spanning tree 的性質（111）、max flow min cut（108）。

4. 證明題

證明題集中在 110、111 年，113 第 8 題與 115 第 7(a) 題也有：

110 離散第 2 題與第 3(a)(b) 題：整數根的存在、格子染色、proof by contrapositive、整數表示（第 3(c) 題是求比較次數，不是證明）
111 離散第 2 題與線代第 6–9 題：minimum spanning tree 的性質、Rayleigh quotient、Frobenius norm、e^A positive definite、A^TA positive semidefinite

優先準備的五個主題

Recurrence，含 nonhomogeneous 與耦合遞迴，十年中九年有。
矩陣分解：LU、QR、SVD。
Graph theory 的 Euler 公式和它的推論：邊數上界、girth 的推廣、complement graph 與 planarity。
證明題的書寫：proof by contrapositive、induction、pigeonhole principle。
Finite state machine，113、114、115 連續三年出現，上表 Automata & Languages 三年合計 43 分。

題型演變

年度	題數	頁數	順序	特色
106	8	2	線代 → 離散	自訂 field 運算、tridiagonal determinant
107	8	2	線代 → 離散	SVD 佔 25 分、兩題機率 30 分
108	6	2	線代 → 離散	circulant matrix、max flow 20 分
109	6	2	線代 → 離散	25 分是非題、complement graph 非平面
110	6	3	離散 → 線代	離散第 2、3 題多為證明題
111	9	2	離散 → 線代	線代全是證明題
112	10	2	離散 → 線代	離散五題各 10 分
113	10	2	離散 → 線代	generating function 25 分、finite state machine 13 分
114	9	3	離散 → 線代	第 1–8 題為選擇題
115	7	4	離散 → 線代	第 2、3、5 題以情境敘述，LU 分塊 30 分

110 年起離散數學排在線性代數之前，一直到現在。

給 116 年考生的準備方向

106、107 年全卷，以及 108、109、110、115 年的離散部分，明訂只有答案不給分，練習時要完整寫出過程。
114 年第 1–8 題為選擇題，115 年回到申論，兩種形式都要準備。
115 年第 2、3、5 題改用情境敘述（資料中心路由器、衛星、電子鎖），要練習把情境剝掉，找出底下的經典問題。
110 年起離散排在線代之前。

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

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