115 中央資工所考古題詳解｜數學考點分析

題型與配分

全卷 7 頁、20 題、100 分，禁用計算器。

線性代數考點

多選 1–5（理論）

• 第 1 題（5%）｜determinant：det(A) ≠ 0 與 A 的列是否構成 Rⁿ 的 basis、det(cA) 與 c det(A)、rank r < n 時的 determinant、triangular matrix 的 determinant、AB = BA 時 det(A+B)
• 第 2 題（5%）｜vector space V：linearly independent 子集能否擴充成 basis、有限維時 spanning set 是否為 basis、有限維空間任兩組 basis 的向量個數、basis 是否唯一、生成 V 的集合是否 linearly independent
• 第 3 題（5%）｜linear transformation T : V → W：injection 與 ker(T) = {0}、surjection 與 dim V = dim Image(T)、V 的 basis 的像是否為 W 的 basis、dim V = dim W 且 injection 時是否 surjection、表示矩陣與 basis 的選取
• 第 4 題（5%）｜inner product space 中的 orthogonality：u ⊥ v 且 u ⊥ w 時 u ⊥ (v + w)、非零 orthogonal set 的 linear independence、orthonormal set 是否為 basis、Pythagorean theorem、‖u+v‖ = ‖u‖ + ‖v‖ 與 u、v orthogonal
• 第 5 題（5%）｜n×n Hermitian matrix：eigenvalue 是否為實數、相異 eigenvalue 的 eigenvector 是否 orthogonal、兩個 Hermitian matrix 的和與乘積、是否可用 unitary matrix diagonalize

單選 6–10（計算，答案取絕對值或四捨五入後 mod 5）

• 第 6 題（5%）｜A = [[3,2],[−1,0]]，B = A²⁰ = [[M,N],[P,Q]]，求 mod(|P|, 5)
• 第 7 題（5%）｜對 A = [[1,1,1,1],[−1,1,1,1],[0,0,2,3],[0,0,0,7]] 做 QR 分解，K 為 R 中所有非零元素的乘積，求 mod(round(|K|), 5)
• 第 8 題（5%）｜5×5 矩陣的 determinant 為 K，求 mod(|K|, 5)
• 第 9 題（5%）｜把 b = [1 2 3 4]^T projection 到 4×4 矩陣 A 的 column space 得到 c，K 為 c 所有元素的乘積，求 mod(round(|K × 4|), 5)
• 第 10 題（5%）｜S、T 是 R³ 的兩組 ordered basis（各三個向量），V 相對於 T 的座標為 [2 3 1]^T，相對於 S 的座標為 [M N P]^T，求 mod(round(|M+N+P|), 5)

離散數學考點（11–20）

• 第 11 題（5%）｜演算法 A：n ≤ 4 時結束，否則把輸入切成 4 個大小約相等的子集，取其中 2 個當樣本遞迴呼叫 A 兩次，兩個結果各有 n/4 個項目，再用程序 I（輸入為兩個大小 m 的集合時花 Θ(√(m/4))）整合。判斷 A 是不是 linear recursive、divide-and-conquer，以及複雜度 Θ(n²)、Θ(n)、Θ(√n log n) 哪個成立
• 第 12 題（5%）｜predicate D(x,y)：y 是 x 的倍數，C₃(x,y)：x 與 y 模 3 congruence，C₆(x,y)：x 與 y 模 6 congruence。給一個含否定與 implication 的邏輯式，問哪些中英文敘述是正確的解讀
• 第 13 題（5%）｜a_n = −a_n−1 + 6a_n−2（n ≥ 2，a₀ = 0、a₁ = 5），判斷 G(x) 的等式、partial fraction 與 closed-form solution
• 第 14 題（5%）｜數學史與基礎：集合是否先於微積分被正式定義、所有無窮集是否同基數、Hilbert's program 是否成功、經驗主義是否主張知識完全由邏輯證成、以上皆非
• 第 15 題（5%）｜f : C → D、g : A → B，f∘g 是 surjection，比較 |A|、|B|、|C|、|D| 之間可能的大小關係
• 第 16 題（5%）｜n 個人排成一列，任兩位男性不相鄰，a_n 為排法數（例如 a₃ = 5），判斷 recurrence、初始值與 Fibonacci 數的關係
• 第 17 題（5%）｜n ≥ 3 個頂點的 connected simple graph G：有 Hamilton cycle 與沒有 cut vertex 的關係、是否 2-connected、是否存在不是 3-connected 的 Hamiltonian graph、最小 degree 至少 2 是否蘊含 Hamilton
• 第 18 題（5%）｜C₆、W₆、K₅、K₄,₄、Q₄ 哪些有 Euler circuit
• 第 19 題（5%）｜bipartite graph：是否不含 odd cycle、是否必為 planar graph、K₃,₃ 是否為 bipartite graph、樹是否為 bipartite graph、有 Hamilton cycle 時兩部分頂點數的關係
• 第 20 題（5%）｜n ≥ 3 個頂點、m 條邊的簡單 planar graph：m ≤ 3n − 6、每個面的 degree 至少 4 時 m ≤ 2n − 4、是否可含 K₅ 或 K₃,₃ 的 subdivision、是否都有 Hamilton cycle、是否都可用至多四種顏色 coloring

作答時要注意的地方

1. 三個大題各自獨立扣到 0 分為止。
2. 第 1–5 題與第 11–20 題是逐選項倒扣，第 6–10 題答錯倒扣 2 分。
3. 第 14 題有「以上皆非」的選項。
4. 第 15 題問的是 f∘g 為 surjection 時四個集合大小的可能關係。

準備方向

• determinant、vector space、linear transformation、orthogonality、Hermitian matrix 的定理判斷（115 第 1–5 題），106、107、108、109、110、111 的線代也以性質判斷為主。
• 矩陣高次冪（115 第 6 題），112 第 18 題、114 第 3 題也有。
• QR 分解（115 第 7 題）與 projection（115 第 9 題），106、111、112、113 也有。
• basis 座標轉換（115 第 10 題），112 第 16 題、113 第 2 題、114 第 1 題也有。
• pseudo-code 的複雜度（115 第 11 題），106、107、108、109、110、111、112、114 都有。
• predicate logic 翻成自然語言（115 第 12 題），106 第 7 題也用 D(x,y) 為 y 是 x 的倍數。
• generating function 解遞迴（115 第 13 題）與計數遞迴（115 第 16 題）。
• 數學史與基礎（115 第 14 題），109 第 46 題考 Gödel 不完備定理。
• 合成函數與基數（115 第 15 題），106、107、109、110 也有基數。
• Hamilton、Euler、bipartite graph、planar graph（115 第 17–20 題），113、114 也有，Euler circuit 在 114 第 16 題。