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

題型與配分

所別「資工類」，科目：離散數學與線性代數，全卷 100 分，禁用計算器。

線代的多選題號是不連續的 11–12 與 16–20，中間夾著三題單選（13–15），三段的倒扣池也不同——進場務必先把計分說明讀完再動筆。

離散數學考點（1–10）

• 第 1 題｜Q(x,y) 為「x + y = y」，判斷五種量詞組合的真假（∃x∃y、∀x∃y、∃y∀x、∀y∃x、∀x∀y）。關鍵：只有 x = 0 時成立
• 第 2 題｜鴿籠原理：75 小時內每小時至少一場比賽、總共不超過 125 場，判斷「必存在連續幾小時恰好比了 k 場」對 k = 2, 23, 24, 25 是否成立
• 第 3 題｜RSA 公鑰系統：正確性依據（費馬小定理與中國剩餘定理）、兩個大質數是否直接當公私鑰（假）、(M^e)^d = M、數位簽章的流程（選項 D 把公私鑰寫反了）
• 第 4 題｜連通平面簡單圖：r = e − v + 2（Euler 公式）、e ≤ 3v − 6（v ≥ 3）、必有度數不超過 5 的頂點、含同胚於 K₃,₃ 或 K₅ 的子圖則非平面（選項 D 寫成 K₂,₃ 是錯的）
• 第 5 題｜滿 m 元樹的五個公式：n 個頂點時內部節點數 i = (n−1)/m、葉數 l = [(m−1)n+1]/m、i 個內部節點時 l = (m−1)i+1、l 片葉時 n = (ml−1)/(m−1)、i = (l−1)/(m−1)
• 第 6 題｜|A| = 8、|B| = 3 時 f : A → B 的函數個數、單射個數（0，因為 8 > 3）、滿射個數、雙射個數（0）
• 第 7 題｜給述詞 P(i,j) 滿足反身、反對稱、遞移、完全性與「恰有一個最小元素」，判斷它描述的是等價關係／偏序／全序／格／良序
• 第 8 題｜同一個遞迴框架衍生三個演算法：程序 R(A, k) 把大小 n 的陣列切成 k 等份（花 √n 步）、對每份遞迴、再花 k 步合併、最後呼叫 Q。由此定義 X（k = 2、Q 為 Θ(m)）、Y（k = 4、Q 為 Θ(√m)）、Z（k = 9、Q 為 Θ(m)），比較三者複雜度誰優誰劣、是否相同、X 是否為 Θ(n log n)
• 第 9 題｜二項式係數恆等式：C(n,k) = C(n,n−k)、交錯和 Σ(−1)^kC(n,k) = 0、Vandermonde 卷積 ΣC(m,i)C(n,k−i) = C(m+n,k)、hockey-stick 型求和
• 第 10 題｜生成函數解遞迴：(a_n−1 − a_n−2) = 2(a_n − a_n−1)、a₀ = 5、a₁ = 9。要先把式子整理成標準的 2a_n = 3a_n−1 − a_n−2 再列生成函數

線性代數考點（11–20）

多選 11–12（逐選項倒扣）

• 第 11 題（5%）｜矩陣性質五連判：A² 是對角矩陣 ⇒ A 必為對角矩陣（假）、有完整正交單位特徵向量組 ⇒ 必為 Hermitian（假，正確條件是 normal）、AAᴴ = AᴴA ⇒ 必可對角化（真，正規矩陣定理）、rank r < n ⇒ 有 n−r 個零特徵值（假，要可對角化才成立）、一個特徵值可對應多於一個特徵向量（真）
• 第 12 題（5%）｜197×197 的有限差分矩陣（主對角線 2、上下副對角線 −1）：求 det 後 mod 5（要找出 D_n = 2D_n−1 − D_n−2 的遞迴 ⇒ D_n = n+1）、任意方陣可拆成對稱＋反對稱（真）、A = BCB^T 且 B 正交、C 對角（真，實對稱必可正交對角化）、B 為下三角的 LDL^T 型、最小特徵值是否為負（假，此矩陣正定，特徵值為 2 − 2cos(kπ/198) > 0）

單選 13–15（答錯倒扣 2 分）

• 第 13 題（5%）｜2×2 矩陣求 det 為 M、四個元素和四捨五入為 N，算 mod(M + 13N, 5)
• 第 14 題（5%）｜一題兩系統：先解一個含參數 k 的線性方程組得 M，再對一個超定方程組求最小平方解得 N，最後 mod(M+N, 5)
• 第 15 題（5%）｜兩個 4×4 行列式 M 與 N，組合成 K 後問 K 落在哪個區間——選項是 0≤K<1、1≤K<2、… 的區間判斷而非單一數值

多選 16–20（逐選項倒扣）

• 第 16 題（5%）｜相似矩陣：det 相同（真）、特徵向量相同（假）、A² 相似於 B²（真）、AB 相似於 BA、A² 相似於 B² ⇒ A 相似於 B（假）
• 第 17 題（5%）｜實方陣的特徵值：可能為複數（真）、有 λ = 0 ⇒ 不可逆（真）、有重根 ⇒ 不可對角化（假）、A = A^T ⇒ 特徵值為正實數（假，只保證實數）、可對角化時 P 與 D 不唯一（真）
• 第 18 題（5%）｜QR 分解與正交補：W 與 W⊥ 是否為子空間、(W⊥)⊥ = W、W ∩ W⊥ = ∅（假，應為 {0}）、A 可 QR 分解 ⇒ m ≥ n。(D) 的空集合陷阱與 107 年第 13(D) 題一模一樣
• 第 19 題（5%）｜哪些術語與最小平方問題無關：inconsistent system（有關）、eigenvector（無關）、diagonalizable（無關）、orthogonal projection（有關）、Gram-Schmidt（有關）——是「反向選無關」的題型
• 第 20 題（5%）｜譜分解：對一個 2×2 矩陣做 spectral decomposition，問哪些值不在解矩陣裡（與 107 年第 14、15 題同一組考點）

這份考卷的難點

1. 離散 50 分全部逐選項倒扣，而且題目密度很高（第 4、5 題各有五個公式要逐一驗證）。
2. 第 5 題的五個 m 元樹公式必須全部記熟，任一個記錯就扣分。這些公式在 Rosen 課本有完整列表。
3. 第 2 題的鴿籠原理要對每個 k 值分別構造 —— 75 小時、125 場的設定下，k = 24 可行但 k = 25 不一定。
4. 第 3(D) 的數位簽章：簽章要用自己的私鑰加密、對方用你的公鑰驗證 —— 題目刻意寫反。

準備建議

• 滿 m 元樹的五個公式（111 第 5 題）是 Rosen 課本的標準內容，建議直接背下來
• RSA 的加密／解密／簽章三種金鑰方向（110、111 連兩年）要畫表釐清
• 鴿籠原理的構造（111 第 2 題）與成大 109 第 4 題是同一類型
• 量詞順序的影響（111 第 1 題）：∃y∀x 與 ∀x∃y 的真假可能不同，這是邏輯的核心觀念