110 中央資工所考古題詳解｜數學考點分析

題型與配分

全卷 7 頁、40 題、100 分，禁用計算器，作答於答案卷（卡）。

離散數學考點（1–10）

• 第 1 題｜哪些 quantifier 的邏輯等價式不正確，涉及全稱與存在 quantifier 對 ∧、∨ 的分配，以及 x 不在 A 中自由出現時 ∀x(P(x) → A) 的改寫
• 第 2 題｜四個人用各自政黨的黨員數對話，以 injection、bijection、surjection 映射推論集合大小，問哪幾句有誤
• 第 3 題｜整數性質哪些不正確：gcd(a,b) = 1 時 pa + qb = n 的解、modular inverse 存在的條件、模數為質數的 congruence equation 組、Fermat's little theorem、RSA 中加密與解密所用的金鑰
• 第 4 題｜給 Hasse 圖，判斷 cRh、mRm、dRa、a 是否為 minimal element、R 是否為格
• 第 5 題｜給 directed graph G：strongly connected、weakly connected、Euler path、Hamilton path、planar graph
• 第 6 題｜R = {(x,y) ∈ N×N | x 的質因數個數不多於 y} 是否為 partial order、total order、equivalence relation，以及 R 對應的 directed graph 有幾個 weakly connected component
• 第 7 題｜有價值問題的集合 V 與 R 之間有 bijection，所有 AI 軟體的集合 S 中每個軟體以一長串二進位 machine code 表示。判斷 S 與 R 之間有沒有 bijection、|S| 的大小、|V| 與 |S| 的關係
• 第 8 題｜只能用 1 元與 2 元鈔票買 n 元票的方法數 a_n（a₀ = 1、a₁ = 1），哪個 recurrence 可以描述它
• 第 9 題｜演算法複雜度：merge sort、Euclid 演算法、bubble sort、Roy-Warshall transitive closure（位元運算數）、traveling salesman problem
• 第 10 題｜用 generating function 解 a_n = a_n−1 + 20a_n−2（a₀ = −1、a₁ = −1），判斷 G(z) 與 partial fraction 的各選項

線性代數考點（11–40）

• 第 11–15 題（複選，全對才給分）｜問下列矩陣分解各自存在的必要條件：A = PDP⁻¹、A = QR、A = PDP^T、A = λ₁u₁u₁^T + … + λ_nu_nu_n^T、A = R^TR（Cholesky）。選項是 (A) 方陣但不 symmetric (B) 方陣且 symmetric (C) 行 linearly independent (D) eigenvector linearly independent (E) positive definite
• 第 16–20 題（單選，是非）｜n×n 矩陣 A diagonalizable：0 是否不是 eigenvalue、是否有 n 個相異 eigenvalue、是否可逆、A^T 是否也 diagonalizable、diagonalization 是否唯一
• 第 21–25 題（單選，是非）｜T : V → W 的 standard matrix 為 A，給 V 的 basis β（兩個向量）與 W 的 basis C（三個向量），求 T 相對於 β 與 C 的矩陣 M，逐題判斷某三個數是否出現在 M 中
• 第 26–30 題（單選，是非）｜Ax = b 不一致且有 least squares 解 x̂：b 是否不在 Col A、x̂ 是否唯一、A^TA 不可逆時是否無解、Ax̂ 是否總在 Col A、b − Ax̂ 是否在 Nul A^T 中
• 第 31–35 題（單選，是非）｜n×n covariance matrix C：是否有 n 個 orthogonal eigenvector、是否有 n 個相異實 eigenvalue、是否有正 eigenvalue 與負 eigenvalue 而無零 eigenvalue、是否可寫成 AA^T、是否 positive definite
• 第 36 題（多選，5%）｜解 n×n 線性系統 Ax = b 的各方法成本：LU 分解、對稠密 upper triangular matrix 做 back substitution、每列至多 3 個非零元時 Jacobi 法每次迭代的成本
• 第 37 題（多選，5%）｜A 為 symmetric、diagonally dominant 的方陣時，哪些方法可用來解 Ax = b：complete pivoting 的 LU、normal equation、Gauss-Seidel、Jacobi
• 第 38 題（多選，5%）｜哪一組向量是 R³ 的 basis
• 第 39 題（多選，5%）｜給一個 3×5 矩陣 A，哪些向量構成 Nul(A) 的 basis
• 第 40 題（多選，5%）｜讀一段 Python 函式 Fun(m)（對第一列遞迴展開，2×2 時回傳 m₀₀m₁₁ − m₀₁m₁₀），問哪些輸入矩陣會讓輸出為 0

作答時要注意的地方

1. 四段計分各自獨立，每段都明訂扣到該大題 0 分為止。
2. 第 11–15 題全對才給分，同時答錯倒扣 1 分。
3. 第 16–35 題每題 1 分，答錯倒扣 1 分。
4. 第 2、7 題用生活情境包裝集合基數的比較。

準備方向

• 矩陣分解的必要條件（110 第 11–15 題），107、108、111、113、114、115 也有。
• diagonalizable 的常見誤解（110 第 16–20 題），107、109、111 也有。
• RSA 與數論（110 第 3 題），111 第 3 題也考 RSA，108、109 考 Fermat's little theorem。
• 可數與不可數、基數比較（110 第 2、7 題），106、107、109、115 也有。
• least squares 解（110 第 26–30 題），106、108、111、112、113、115 也有。
• 讀程式或 pseudo-code（110 第 40 題），107 第 16、20 題、112 第 15 題也有。
• planar graph（110 第 5 題），111、113、114、115 也有。
• generating function 解遞迴（110 第 10 題）。