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

題型與配分

系所「資工類」，科目：離散數學與線性代數，全卷 100 分，共 9 頁，20 題——是中央十年來頁數最多的一份。

80 分落在逐選項倒扣的多選題上，是中央十年來逐選項倒扣比重第二高的一年（僅次於 107 年的全卷 100 分）。兩部分都註明「扣到該〔整大題〕0 分為止」。

本科考試禁用計算器，但單選 1–4 依然是「算完 → 取絕對值 → ⌊·⌋ → mod 5」。

線性代數考點

單選 1–4（全部要算出數值）

• 第 1 題（5%）｜非標準基底下的線性變換：L : R² → R³ 在標準基底下已知，求它相對於 B₂、B₃ 兩組非標準基底的表示矩陣 [L]_B3,B2，把六個元素加總
• 第 2 題（5%）｜QR 分解：對一個 4×3 矩陣做 Gram-Schmidt QR，取 Q、R 中指定元素
• 第 3 題（5%）｜矩陣多項式：p(x) = x²⁰ − x⁶ + 1，求 p(A) 的四個元素和。關鍵是先對角化或找 A 的最小多項式，不能硬乘二十次
• 第 4 題（5%）｜么正對角化（unitary diagonalization）：給定複矩陣 A，求 U 使 U 對角化 A，元素寫成 a + ib 形式後取實部相加

多選 5–10

• 第 5 題（5%）｜零空間：判斷五個向量哪些屬於 A 的 nullspace——只要代入乘開，是本卷最容易的 5 分
• 第 6 題（5%）｜特徵值的合成律：λ_A × λ_B 是否為 AB 的特徵值（假）、AB 與 BA 特徵值相同（真）、AB 與 BA 特徵向量是否相同（假）、相似矩陣 B = M⁻¹AM 特徵值相同（真）、normal matrix（AAᴴ = AᴴA）時 A 與 Aᴴ 特徵值是否相同（共軛關係）
• 第 7 題（5%）｜對稱矩陣：A⁻¹ 是否對稱（真）、是否必有 N 個正交單位特徵向量（真）、A² = A（冪等）⇒ 特徵值只能是 0 或 1（真）、每行和為 1 ⇒ 1 是特徵值（真，隨機矩陣性質）、AB 是否必對稱（假）
• 第 8 題（5%）｜單位圓上的反射與旋轉——本卷最難的一題，五個選項各是一個獨立小題：
• (a) 粒子從 A(0,−1) 出發、∠OAB = 15°，在單位圓上反覆反射，求 P₂₀ 的座標（要看出每次反射轉過固定角度，變成 30° 的等分點問題）
• (b)(c) 同一個 2×2 矩陣反覆作用 N 次，問 Q₁₀₀₀、Q₂₀₀₀ 的座標與相鄰兩點距離的比值（考矩陣冪次的收斂／發散速率）
• (d) 旋轉矩陣 R(K) 與鏡射矩陣 M 的複合 Q = R₁₅ M₁₅ R₃₀ M₃₀ R₄₅，問第一象限的點變換後是否仍在第一象限（偶數個鏡射 = 旋轉是解題關鍵）
• (e) 單位圓經 N = S·T 變換成橢圓 Z，求原點到 Z 的最長與最短距離之和——這就是 SVD 的奇異值 σ₁ + σ₂
• 第 9 題（5%）｜列運算與線性方程組：3×4 矩陣經列運算化成指定形式，結合外積 |（a₁,a₂,a₃) × (d₁,d₂,d₃)| 與「方程組是否有唯一解」的判斷
• 第 10 題（5%）｜哪些行列式為零：五個 5×5 矩陣逐一判斷。要靠反對稱矩陣（奇數階必為 0）、列相依、循環結構等技巧快速判定，硬展開絕對算不完

離散數學考點（11–20）

• 第 11–12 題（各 5%）｜共用一個 5×5 關係矩陣（與 112 年第 1–4 題同一套路）。第 11 題問 reflexive／anti-symmetric／transitive／偏序／遞移閉包是否對稱；第 12 題把元素當集合，問 S（R 的遞移閉包）可以對應哪些集合運算子：∩、∪、⊆、−（差集）、⊇
• 第 13 題（5%）｜整除偏序集：S = {1, 2, 3, 4, 6, 8, 12, 24} 配整除關係。判斷是否全序（假，3 與 4 不可比）、是否良序（假）、有最大下界 1（真）、是否為格（真，任兩元素的 lcm 與 gcd 都落在 S 內）、有極大元 24（真）
• 第 14 題（5%）｜反推子程序的複雜度上限：程序 P 呼叫 B 後用 i mod 9 = 1/4/7 切成 3 個 n/9 的子陣列遞迴，要讓 P 的複雜度是 O(n)，B 可以是多複雜？由 F(n) = 3F(n/9) + Θ(n) + B(n)，n^log₉3 = n^0.5，只要 B 的指數 ≤ 1 就仍是 Θ(n) → (a) O(m^1/2)、(b) O(m¹)、(d) O(m^1/4) 成立；(c) O(m^√2) 與 (e) O(m²) 會把整體拉到 n^√2 與 n²
• 第 15 題（5%）｜生成函數：a_n = 4a_n−1 − 4a_n−2、a₀ = 0、a₁ = 1/2。特徵方程 (x−2)² 是重根，齊次解為 a_n = n·2ⁿ⁻²。選項刻意塞進 1/(1+z) 與 (−1)ⁿ 項——重根遞迴不會冒出 (−1)ⁿ，這是辨識陷阱的關鍵
• 第 16 題（5%）｜Euler circuit：C₅、W₅、K₅、K₅,₅、Q₅ 逐一檢驗「所有頂點度數皆為偶數」。C₅（全為 2）與 K₅（全為 4）成立；W₅ 的軸心度數 5、K₅,₅ 度數 5、Q₅ 度數 5 都是奇數
• 第 17 題（5%）｜握手謎題：你與伴侶加上三對夫妻共 8 人，除你以外的 7 人握手次數全不相同 ⇒ 必為 0～6。把 6 與 0、5 與 1、4 與 2 配成夫妻，剩下的 3 就是你的伴侶。推出你也握了 3 次——正解是 (c) 你握 3 次 + (e) 伴侶握 3 次
• 第 18 題（5%）｜偶數個 0 的十進位碼字（Rosen 經典題）：正解是 a_n = 8a_n−1 + 10ⁿ⁻¹、a₁ = 9，封閉解 a_n = (10ⁿ + 8ⁿ)/2。選項 (a) 的 9a_n−1、(d)(e) 的 8ⁿ + 10ⁿ⁻¹ 都是變形陷阱
• 第 19 題（5%）｜點連通度與邊連通度：看圖求 vertex connectivity 與 edge connectivity，五個選項把 1、2、3 排列組合
• 第 20 題（5%）｜同胚於 K₃,₃：四張圖逐一判斷是否為 K₃,₃ 的細分（subdivision）——要會把度數 2 的頂點「縮邊」還原

這份考卷的難點

1. 第 8 題一題 5 分塞進五個獨立難題：單位圓反射的角度追蹤、矩陣冪次的漸近行為、鏡射複合的奇偶性、SVD 奇異值。這一題幾乎等於一份小考卷，而且每錯一個選項就 −1。
2. 第 10 題的五個 5×5 行列式在禁用計算器下，只能靠結構識別（反對稱、列相依、循環矩陣）秒殺，硬算必定超時。
3. 80 分逐選項倒扣意味著「部分懂」的題目非常危險。以第 6、7 題這種「五個選項四真一假」的設計，全選的期望值是 4 − 1 = 3 分，但若是三真兩假就只剩 1 分。
4. 第 15 題的陷阱在選項而不在題目：遞迴式本身是最單純的重根型，但五個選項全部帶著 1/(1+z) 與 (−1)ⁿ，逼你去驗算而不是憑印象勾選。

準備建議

• 114 第 14 題與 112 第 7、8 題是同一個 pseudo-code 模板（連 array2/3/4、i mod 9、call B 都一樣），只是 112 問「複雜度是多少」、114 反過來問「B 最多可以多慢」。兩年一起練，等於掌握中央的固定送分題
• Rosen 課本的計數章節要背熟三題：偶數個 0 的碼字（114 第 18 題）、無相鄰同類排列（115 第 16 題）、字串禁止子字串（112 第 9 題）——中央三年各考一題
• 握手謎題的「0–6 配對」解法（114 第 17 題）是固定套路，n 對夫妻時伴侶必握 n−1 次
• 旋轉與鏡射矩陣（114 第 8 題）要記住：兩次鏡射 = 一次旋轉、鏡射行列式為 −1、旋轉為 +1。這是判斷 (d) 的唯一捷徑
• 單選只有 20 分但答錯倒扣 2 分，建議先把 80 分的多選做完再回頭算——時間不夠時空白比亂猜好