112 中興資工所數學考點分析

題型與配分

系所「資訊科學與工程學系 甲組」，科目：離散數學與線性代數（從 112 年起甲組的數學考科由「基礎數學 A」改名），本科目試題共 3 頁、12 大題、100 分，不得使用計算機。

「請於答案卷上作答，否則不予計分」——112 年全部題目都寫在答案卷，沒有答案卡、沒有倒扣。這與 110、111 年的選擇題形式完全相反。

線性代數考點（1–6，50%）

• 第 1 題（10%）｜十個是非小題（(a)–(j)），每個 1 分，是整份卷子的線代觀念總複習：
• (a) trace(A) = a ⇒ trace(A⁻¹) = 1/a（假）
• (b) A² = A ⇒ A = I 或 A = 0（假，任何投影矩陣都是反例）
• (c) 「k 維子空間的任何生成集恰有 k 個向量」（假）
• (d) A、B 對稱且可逆 ⇒ AB 對稱（假）
• (e) AB = I ⇒ B⁻¹ = A（真）
• (f) 某列加上另一列的倍數不改變行列式（真）
• (g) Ax = b 不相容 ⇒ rank[A|b] > rank A（真）
• (h) A^TA 對稱、(A + A^T) 是斜對稱（後半為假，A + A^T 是對稱）
• (i) 可對角化 ⇒ 有 n 個相異特徵值（假）
• (j) n×n 的 RREF 且 rank n ⇒ R = I_n（真）
• 第 2 題（8%）｜求給定矩陣的特徵值與特徵向量
• 第 3 題（8%）｜由兩個像決定線性變換：T : R² → R²
• (a) 4%：求 標準矩陣
• (b) 4%：求 range(T) 的生成集
• 第 4 題（8%）｜含參數的線性方程組：把方程組寫成 Ax = b，做高斯消去化成列梯形，再求使解唯一的 k 值
• 第 5 題（8%）｜Gram-Schmidt：把生成集 S = {v₁,v₂,v₃} 轉成單位正交集 S′
• 第 6 題（8%）｜正交投影：求 v = (3,6,…)^T 在子空間 W 上的投影向量

離散數學考點（7–12，50%）

• 第 7 題（8%）｜由數列反推遞迴與生成函數：數列 2, 3, 7, 15, 31, 63, …
• (a) 3%：寫出遞迴關係（觀察 a_n = 2a_n−1 + 1）
• (b) 5%：求生成函數
• 第 8 題（5%）｜Master Theorem 四選一：判斷下列哪些成立
• T(n) = 3T(n/4) + Θ(n²) → Θ(n²)（適用 case 3）
• T(n) = 5T(n/2) + Θ(n²) → n^log₂5 ≈ n^2.32 勝過 n²，所以不是 Θ(n²)
• T(n) = 2T(n/4) + Θ(n) → Θ(n)（適用 case 3）
• T(n) = 2T(n/4) + Θ(n²log n) → Θ(n²log n)
• 第 9 題（10%）｜錢幣／郵票問題：如何用 10 分與 16 分的郵票湊出 $12.74？並求最少與最多能用幾張郵票。關鍵是 10a + 16b = 1274，但 10a + 16b 必為偶數而 1274 是偶數 → 化簡成 5a + 8b = 637，再解丟番圖方程並找出 a、b ≥ 0 的範圍
• 第 10 題（5%）｜證明 √13 是無理數（標準反證法，用「13 | p² ⇒ 13 | p」）
• 第 11 題（10%）｜文法與形式語言：G 的產生規則為 S → 1S、S → 10A、A → 0A、A → 0
• (a) 5%：證明 1111000 屬於 G 產生的語言（寫出推導過程）
• (b) 5%：描述 G 產生的語言（形如 1ⁿ100^m 的字串）
• 第 12 題（12%）｜六個是非小題（各 2%）
• (a) 52 張牌分成 13 堆各 4 張，必可從每堆各取一張湊齊 13 種點數（真，Hall 定理／SDR）
• (b) 圖有 Euler circuit ⟺ 每個頂點度數為偶（假，還要連通）
• (c) 每棵樹都是二分圖（真）
• (d) 度數序列 (4,4,3,3,3,2,1) 的圖有 20 條邊（假，總度數 20 ⇒ 10 條邊）
• (e) 編碼 {A,B,C} 且 P(A) = 0.5… 所需的最小位元數（熵）
• (f) (P∨Q) → R 與 (P→R) ∨ (Q→R) 是否邏輯等價（假）

這份考卷的難點

1. 第 9 題的郵票問題要完整處理三件事：是否有解（gcd(10,16) = 2 是否整除 1274）、通解的形式、非負解的範圍（決定最少與最多張數）。只寫出一組解拿不到滿分。
2. 第 12(b) 的 Euler circuit 條件少了「連通」——這是最經典的陷阱，五個不相連的偶度數頂點顯然沒有 Euler circuit。
3. 第 1 題十個是非小題涵蓋整個線代，而且多數是「看起來對但其實錯」的敘述。(b) 的 A² = A 反例（任何正交投影矩陣）與 (h) 的 A + A^T（是對稱不是斜對稱）最容易失手。
4. 第 11(b) 要「描述語言」而非只是舉例。要能寫出 L(G) = {1ⁿ100^m : n ≥ 0, m ≥ 0} 這樣的形式化描述。

準備建議

• 112 與 113 年都是全申論、寫在答案卷，而 110、111、114、115 以選擇題為主——中興的題型年年變，兩種都要準備
• Master Theorem（112 第 8 題）與大數模運算是中興反覆在考的兩個工具
• 第 1 題的十個是非小題是最好的線代觀念清單，建議逐條確認，很多在 110、114、115 年以不同形式重出
• 形式語言與文法（112 第 11 題、113 第 2 題的 Kleene 定理）是中興獨有的考點，其他七校的數學科都不考
• 丟番圖方程（郵票／錢幣問題）在禁用計算器下要靠 gcd 判定與通解公式，不能靠試誤