112 中興資工所考古題解答｜數學考點分析

全卷 12 大題，寫在答案卷上，卷面沒有倒扣標示。線代 1–6 題與離散 7–12 題各 50 分，離散考遞迴與 generating function、Master Theorem、郵票湊錢、grammar。

題型與配分

全卷 3 頁、12 大題、100 分，不得使用計算機。卷首註明請於答案卷上作答，否則不予計分。第 1、12 題是是非小題，第 8 題是選出正確的敘述，其餘是申論或計算，卷面沒有倒扣標示。

區段	題號	主題	配分
線性代數	1–6	是非題、eigenvalue、linear transformation、Gaussian elimination、Gram-Schmidt、projection	50%
離散數學	7–12	遞迴與 generating function、Master Theorem、郵票湊錢、無理數證明、grammar、是非題	50%

第 1 題（10%）｜十個是非小題，標 O 或 X：
1(a)｜trace(A) = a 時，trace(A⁻¹) 是否為 1/a
1(b)｜A² = A 時，A 是否只能是 I 或 0
1(c)｜k 維 subspace 的任何 spanning set 是否恰有 k 個向量
1(d)｜A、B 為 symmetric 且可逆時，AB 是否 symmetric
1(e)｜AB = I 時，B 的 inverse 是否為 A
1(f)｜把某一列的倍數加到另一列，determinant 是否不變
1(g)｜Ax = b 不相容時，rank[A | b] 是否大於 rank A
1(h)｜A^TA 是否 symmetric，A + A^T 是否 skew-symmetric
1(i)｜A diagonalizable 時，是否必有 n 個相異 eigenvalue
1(j)｜n×n 的 RREF 且 rank 為 n 時，是否等於 I_n
第 2 題（8%）｜求給定矩陣 A 的 eigenvalue 與 eigenvector
第 3 題（8%）｜已知 linear transformation T : R² → R² 在兩個向量上的像：
3(a)（4%）｜求 T 的 standard matrix
3(b)（4%）｜求 T 的值域的一組 spanning set
第 4 題（8%）｜含參數 k 的三元線性方程組：寫成 Ax = b，用 Gaussian elimination 把 augmented matrix 化成 row echelon form，再求 x 有唯一解時 k 的值
第 5 題（8%）｜W 由 S = {v₁, v₂, v₃} 生成，用 Gram-Schmidt 把 S 轉成 orthonormal set S′
第 6 題（8%）｜v ∈ R³，求 v 在 subspace W 上的 projection 向量

第 7 題（8%）｜數列 2, 3, 7, 15, 31, 63, …：
7(a)（3%）｜寫出 recurrence relation
7(b)（5%）｜求 generating function
第 8 題（5%）｜Master Theorem，判斷四個 recurrence 與漸近界的配對哪些正確：
8(a)｜T(n) = 3T(n/4) + Θ(n²)，T ∈ Θ(n²)
8(b)｜T(n) = 5T(n/2) + Θ(n²)，T ∈ Θ(n²)
8(c)｜T(n) = 2T(n/4) + Θ(n)，T ∈ Θ(n)
8(d)｜T(n) = 2T(n/4) + Θ(n² log n)，T ∈ Θ(n² log n)
第 9 題（10%）｜如何用 10 分與 16 分的郵票湊出 12.74 美元，最少與最多各要用幾張郵票
第 10 題（5%）｜證明 √13 是無理數
第 11 題（10%）｜grammar G = (V, T, S, P)，V = {0, 1, A, S}，T = {0, 1}，產生規則為 S → 1S、S → 10A、A → 0A、A → 0：
11(a)（5%）｜證明 1111000 屬於 G 產生的語言
11(b)（5%）｜描述 G 產生的語言
第 12 題（12%）｜六個是非小題，每題 2 分：
12(a)｜52 張牌分成 13 堆各 4 張，是否一定能從每堆各取一張，湊齊 13 種點數
12(b)｜圖有 Euler circuit 是否若且唯若每個頂點的 degree 都是偶數
12(c)｜每棵樹是否都是 bipartite graph
12(d)｜degree sequence (4, 4, 3, 3, 3, 2, 1) 的圖是否有 20 條邊
12(e)｜符號 {A, B, C} 且 P(A) = 0.5 的訊源，編碼所需的最少位元數
12(f)｜(P ∨ Q) → R 與 (P → R) ∨ (Q → R) 是否邏輯等價

subspace 的 Gram-Schmidt 與 orthogonal basis：112 第 5 題，109 第 2 題、114 計算題第 2 題也有。
orthogonal projection：112 第 6 題，113 第 15 題、114 第 12 題與計算題也有；114 計算題第 2 題的 v 與 W 和 112 第 6 題相同。
由兩個像求 linear transformation 的 standard matrix：112 第 3 題，114 第 8、11 題也有；114 第 11 題給的兩個像與 112 第 3 題相同。
recurrence relation 與 generating function：112 第 7 題。
Master Theorem：112 第 8 題，113 第 10 題有巢狀迴圈的複雜度。
郵票問題與模運算：112 第 9 題，109 第 7 題、111 第 9 題也有模運算。
grammar 與 formal language：112 第 11 題，113 第 2 題考 Kleene's theorem。
Euler circuit 的條件與樹的二分性：112 第 12(b)(c) 題。