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

題型與配分

所別「資工類」，科目：離散數學與線性代數，全卷 100 分，共 7 頁，20 題。

兩部分都寫明「扣到該〔整大題〕0 分為止」，各自獨立觸底。

本科考試禁用計算器（每一頁頁首都印了這行）。

與 112 年結構對調：112 是「多選 13 題 65 分在前、單選 7 題 35 分在後」，113 改成「單選 10 題 50 分在前、多選 10 題 50 分在後」，而且單選全部給線代、多選全部給離散，切得比 112 更乾淨。

線性代數考點（1–10，單選，全部要算出數值再 mod 5）

十題的答案格式完全一致：算出一個量 → 取絕對值 → 取整（⌊·⌋ 或 Round{·}）→ mod 5，五個選項固定是 0/1/2/3/4。也就是說猜的期望值是負的（答對 +5、答錯 −2）。

• 第 1 題（5%）｜LU 分解：給定 A 求其 LU 分解，再把指定元素組合起來 mod 5
• 第 2 題（5%）｜P₂ 的基底變換：從有序基底 {1, x, x²} 換到 {1, 2x, 4x² − 2}（Chebyshev 型基底），求轉移矩陣 S，數 S 裡有幾個 0 記為 D，求 D % 5
• 第 3 題（5%）｜由 RREF 反推原矩陣：已知 4×4 矩陣 A 的 reduced row echelon form V 與 A 的前兩行，求第三行的四個分量
• 第 4 題（5%）｜3D 旋轉矩陣的合成：yaw 45° → pitch −90° → roll −45° 三個旋轉相乘，求所有元素和。要注意合成的左右順序
• 第 5 題（5%）｜給定上三角型 A，求其冪次／特徵結構相關量
• 第 6 題（5%）｜行列式 D 的計算，求 |D| % 5
• 第 7 題（5%）｜Gram-Schmidt：R⁴ 中由 v₁ = [1,−1,−1,1]^T、v₂ = [1,2,3,2]^T、v₃ = [3,3,0,−2]^T 張成的子空間 U，求單位正交基底
• 第 8 題（5%）｜承第 7 題，正交補與正交分解：V = U⊥，把 w = [10,0,8,2]^T 拆成 w = v + u（v ∈ V、u ∈ U），求指定分量平方和
• 第 9 題（5%）｜對角化：求 P 使 P⁻¹AP = D，把 P 的九個元素加總取絕對值
• 第 10 題（5%）｜最小平方擬合拋物線：找 C + Dt + Et² 最貼近 t = (0,1,3,4) 上的 v = (0,2,2,5)，求 |C + D + E| × 256 後 mod 5

離散數學考點（11–20，多選，逐選項倒扣）

圖論一口氣佔了 11、12、13、14、15 五題共 25 分，是十年來圖論比重最高的一份。

• 第 11 題（5%）｜非平面圖的「移除任一頂點即變平面」性質：K₅、K₆、K₃,₃、K₃,₄、K₄,₄ 逐一檢驗（K₅ 與 K₃,₃ 成立，K₆ 拿掉一點還是 K₅ 不成立）
• 第 12 題（5%）｜騎士圖（knight's graph）：西洋棋盤 64 格建圖，馬走日連邊。判斷是否二分圖（真，馬每步換格色）、最大度數是否為 10（應為 8）、最小度數是否為 4（應為 2）、恰有四個度數 2 的頂點（四個角，真）、有幾個度數 3 的頂點
• 第 13 題（5%）｜可圖序列（graphic sequence）：用 Erdős–Gallai 或 Havel–Hakimi 逐一檢驗 (5,4,3,2,1,0)、(6,5,4,3,2,1)、(2,2,2,2,2,2)、(3,3,3,2,2,2)、(3,3,2,2,2,2)。注意度數不能 ≥ 頂點數
• 第 14 題（5%）｜割點與割邊：看圖找出所有 cut vertex 與 cut edge（bridge），選項刻意把 b、c、d、e 的組合排列組合
• 第 15 題（5%）｜Hamilton 與 Euler 的充要條件：任兩點間有 Hamilton path ⇒ 有 Hamilton cycle？任兩點間有 Euler trail ⇒ 有 Euler circuit？K_m,n 有 Hamilton cycle ⟺ m = n > 1、K_m,n 是 Eulerian ⟺ m 與 n 都是偶數
• 第 16 題（5%）｜把蘊涵當關係：定義 R(P,Q) 為「P → Q 為真」，判斷它是否 reflexive（真）、anti-symmetric（假，P ↔ Q 時互推）、transitive（真）、偏序（假）、遞移閉包是否為自己（真）
• 第 17 題（5%）｜函數計數：|S| = 3，考慮 f : S × S → S。總數 3⁹、1-to-1 的個數（0，因為 9 > 3）、滿射個數用排容原理 3⁹ − 3·2⁹ + 3、雙射個數
• 第 18 題（5%）｜Josephus 問題：n 人圍圈每隔一人淘汰，記存活者為 J(n)。判斷 J(2n) = 2J(n) − 1 與 J(2n+1) = 2J(n) + 1 兩條遞迴式（這兩條是對的，其餘是變號陷阱）
• 第 19 題（5%）｜綜合觀念：已質因數分解時 Euclidean algorithm 是否仍最佳、最小權重 Hamilton path 是否不可計算（假，是 NP-hard 但可計算——這是最容易誤選的選項）、格是偏序集的特例（真）、二分圖能否表示任意函數、and/or/not 是否功能完備（真）
• 第 20 題（5%）｜生成函數解遞迴：2a_n = 7a_n−1 − 6a_n−2，a₀ = 3/2、a₁ = 11/4。判斷特徵多項式 6x² − 7x + 2 = 0、生成函數式 G(z)(2 − 7z + 6z²)、部分分式與封閉解 a_n = (1/2)ⁿ + 2ⁿ 型

這份考卷的難點

1. 單選 50 分全部是純計算且禁用計算器。第 4 題的三次 3D 旋轉合成、第 10 題的 |C+D+E| × 256，任何一步算術失手就是 −2 分而非 0 分。時間分配上，單選部分幾乎會吃掉整場一半以上的時間。
2. 第 12 題的騎士圖要能在腦中建出 8×8 棋盤的度數分布：角落 2、邊緣 3/4、中央 8。這題五個選項全部圍繞度數統計，沒真的畫過就只能亂猜，而亂猜每個錯選項 −1。
3. 第 19(b) 的「un-computable」是精心設計的語意陷阱——最小權重 Hamilton path 是 NP-hard 但完全可計算。把「難算」誤當「不可計算」是常見的觀念混淆。
4. 第 15 題的 K_m,n 兩個充要條件（Hamiltonian 要 m = n、Eulerian 要 m、n 皆偶）必須記死，而且要注意 Hamiltonian 那條還附帶 n > 1。

準備建議

• 113 與 112 的離散題源高度重疊：關係性質（112 第 1 題 / 113 第 16 題）、函數計數（112 第 9 題 / 113 第 17 題）、生成函數（112 第 10 題 / 113 第 20 題），把兩年並排讀
• 圖論在 113 佔 25 分，而 114 第 16、19、20 題、115 第 17、18、19、20 題同樣重壓圖論——Euler／Hamilton／平面圖／二分圖四大塊是中央近三年的主戰場
• Havel–Hakimi 與 Erdős–Gallai（113 第 13 題）要會實際跑一遍，不能只認得名字
• Josephus 遞迴式（113 第 18 題）建議直接背 J(2n) = 2J(n) − 1、J(2n+1) = 2J(n) + 1，並理解其「把 n 寫成 2^m + l 後 J(n) = 2l + 1」的閉式
• 面對「答錯倒扣 2 分」的單選，算不完就空白——十題全猜的期望值是 −4 分