106 中央資工所數學考點分析

題型與配分

所別「資工類」，科目：離散數學與線性代數，全卷 5 頁、20 題、100 分，本科考試禁用計算器，作答於答案卡。

多重選擇題的逐選項倒扣是中央數學的固定設計：每題五個選項，全對得 5 分，但每錯一個選項就扣 1 分。沒把握的選項寧可不填。

離散數學考點（1–10，單選）

• 第 1 題｜哪一個是命題（proposition）（要有明確真假值）
• 第 2 題｜關於雙射函數哪一個敘述不正確（「f 是單射則反函數必存在」是錯的，還需滿射）
• 第 3 題｜兩個任意不可數集合的差集 A − B 可能是什麼（以上皆有可能）
• 第 4 題｜{1,2,3,4,5,6} 的 4-組合中，{1,2,5,6} 之後的下一個是什麼（字典序）
• 第 5 題｜用分治法的快速乘法（Karatsuba）計算兩個 2n 位數乘積的複雜度（Θ(n^log₂3)）
• 第 6 題｜給二元關係 R 的矩陣，判斷其反身閉包／對稱閉包／強連通元件的性質
• 第 7 題｜給述詞 D(x,y)（y 是 x 的倍數）與 E(x)（x 是偶數），判斷邏輯敘述的正確解讀
• 第 8 題｜merge sort 的變形：合併步驟需要 Θ(m√m) 步時的總複雜度（Θ(n√n)）
• 第 9 題｜節點數 > 3 時，哪個圖論敘述不正確（完全圖有 Hamilton 迴路、完全二分圖的邊數、n 維超立方體中任兩點是否有長度 n 的路徑…）
• 第 10 題｜關於形式化證明哪一個敘述正確（偏序集與數學歸納法、對角線論證是否只能用於有限集合、兩集合相等的條件、停機問題）

線性代數考點（11–20，多重選擇）

• 第 11 題｜哪些向量構成矩陣 A 的行空間（column space）的基底
• 第 12 題｜五組 P₃(R) 的多項式中，哪一組的第一個多項式可表示為另外兩個的線性組合
• 第 13 題｜五個線性方程組中哪些有解
• 第 14 題｜行列式的性質：交換兩列／乘常數／加倍數對 det 的影響、上三角矩陣的行列式、det(Q⁻¹) = [det(Q)]⁻¹
• 第 15 題｜給四個線性變換 T : Rⁿ → R^m，選出矩陣表示 [T]_γ^β 正確的選項
• 第 16 題｜A 可逆且可對角化時：A 與 A^T 是否有相同特徵值（真）／相同特徵向量（假）、A^T 與 A⁻¹ 是否也可對角化
• 第 17 題｜n×n 實矩陣：是否恰有 n 個特徵值（含重數才對）、是否恰有 n 個特徵向量（假）、特徵空間的基底是否線性獨立、複特徵值是否蘊含複特徵向量
• 第 18 題｜QR 分解的性質：Q 的行是否為 Col A 的正交歸一基底（真）、Q^TQ = I、R 是否為對角線元素為正的上三角可逆矩陣
• 第 19 題｜最小平方解的性質：x̂ = (A^TA)⁻¹A^Tb、是否唯一、A^TA 不可逆時的情形、b − Ax̂ 是否與 A 的每個列正交
• 第 20 題｜共變異數矩陣的性質：是否對稱、是否有實特徵值、是否沒有負特徵值（半正定）

這份考卷的難點

1. 多重選擇的逐選項倒扣（50 分）是最大變因。 每題五個選項，全猜的期望值是 0，必須逐一確認。
2. 第 17 題的「恰有 n 個特徵值」要小心：含重數計算才是 n 個（在複數域上），不含重數則可能少於 n。
3. 第 5 題的 Karatsuba：分治法把 4 次乘法降到 3 次，所以是 Θ(n^log₂3) ≈ Θ(n^1.585)。
4. 第 8 題的變形 merge sort：T(n) = 2T(n/2) + Θ(n√n)，用 Master theorem case 3 得 Θ(n√n)。

準備建議

• 中央數學的科目全名是「離散數學與線性代數」，兩科各半、全部選擇題、作答於答案卡，十年結構穩定
• 逐選項倒扣是中央的招牌（106–115 每年都有），策略上要「確定的才填」
• 線代的性質判斷題佔一半（第 11–20 題），建議把 Lay《Linear Algebra》每章的定理整理成判斷卡
• 分治法的複雜度（第 5、8 題）橫跨數學與演算法兩科，是中央的特色