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

題型與配分

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

離散數學考點（1–10）

• 第 1 題｜量詞的邏輯等價哪些不正確（∀ 對 ∧ 可分配、∀ 對 ∨ 不可分配、∃ 對 ∨ 可分配、∃ 對 ∧ 不可分配）
• 第 2 題｜用中文政治人物對話包裝的基數比較：單射／雙射／滿射各代表什麼大小關係。這是集合基數的定義題
• 第 3 題｜整數性質哪些不正確：gcd(a,b) = 1 時 pa+qb = n 是否有解（真）、模反元素存在的條件、中國剩餘定理、費馬小定理、RSA 用誰的金鑰加密（選項 E 寫反了）
• 第 4 題｜給 Hasse 圖判斷哪些敘述不正確（關係、極小元素、是否為格）
• 第 5 題｜給有向圖判斷：強連通？弱連通？Euler path？Hamilton path？平面圖？
• 第 6 題｜關係 R = {(x,y) : x 的質因數個數不多於 y} 是否為偏序／全序／等價關係
• 第 7 題｜用 AI 軟體與「有價值問題」包裝的基數論證：S（所有程式，可數）與 V（與 R 等勢，不可數）的比較。核心是「程式是可數的、實數是不可數的」
• 第 8 題｜用 1 元與 2 元鈔票買 n 元票的方法數 a_n 的遞迴式（Fibonacci）
• 第 9 題｜演算法複雜度判斷：merge sort Θ(n log n)（真）、Euclid 演算法 Θ(log max(a,b))（真）、bubble sort Θ(n log n)（假）、Roy-Warshall 的傳遞閉包是否 Θ(n²)（假，是 Θ(n³)）、TSP 是否 NP-hard（真）
• 第 10 題｜用生成函數解 a_n = a_n−1 + 20a_n−2（a₀ = −1、a₁ = −1），判斷 G(z) 與部分分式的形式

線性代數考點（11–35）

• 第 11–15 題（複選，全對才給分）｜給出矩陣分解的必要條件，從 (A) 方陣但非對稱 (B) 方陣且對稱 (C) 行線性獨立 (D) 特徵向量線性獨立 (E) 正定 中選出：
• 11｜A = PDP⁻¹（可對角化 → 特徵向量線性獨立）
• 12｜A = QR（行線性獨立）
• 13｜A = PDP^T（方陣且對稱）
• 15｜A = R^TR（Cholesky）（正定）
• 第 16–35 題（單選是非，各 1 分，答錯 −1）｜A 可對角化時：0 是否不可能是特徵值（假）、是否有 n 個相異特徵值（假）、是否可逆（假）、A^T 是否也可對角化（真）…等 20 個性質判斷
• 第 36 題（多選，5%）｜解線性方程組各種方法的成本比較（高斯消去、LU、反矩陣、Cramer 法則的運算量級）
• 第 37 題（多選，5%）｜哪些方法可以用來解 Ax = b
• 第 38 題（多選，5%）｜哪一組向量是 R³ 的基底
• 第 39 題（多選，5%）｜哪些向量構成 nul(A) 的基底
• 第 40 題（多選，5%）｜讀一段 Python 函式，判斷它在做哪一種矩陣運算——與 107 年的 Gauss-Jordan／LU pseudo-code 填空同一路數

這份考卷的難點

1. 三段各自獨立的倒扣規則（離散多選逐選項、線代複選全對才給分、線代單選逐題），要分別計算風險。
2. 第 3(E) 的 RSA 方向：加密用接收者的公鑰、解密用接收者的私鑰 —— 題目選項刻意寫反。
3. 第 7 題的可數性論證：所有程式（有限長度的二進位串）是可數的，而有價值問題與 R 等勢是不可數的，所以必有問題無法被程式解決。
4. 第 11–15 題全對才給分且答錯倒扣，每題只有 1 分但風險不低。

準備建議

• 矩陣分解的必要條件（110 第 11–15 題）是很好的複習清單：PDP⁻¹ 要特徵向量獨立、QR 要行獨立、PDP^T 要對稱、Cholesky 要正定
• RSA 與數論（110 第 3 題、111 第 3 題連兩年）是中央離散的固定考點，公鑰／私鑰的方向務必記清楚
• 可數與不可數的論證（110 第 2、7 題）在中央幾乎年年出現
• Euler 公式與平面圖（110 第 5 題、111 第 4 題）也是連年考點