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

題型與配分

全卷 4 頁、20 題、100 分，禁用計算器。

離散數學考點（1–10）

單選（1–5，各 5%）

• 第 1 題｜五個中文句子中，哪一個不太可能是命題
• 第 2 題｜關於 Fibonacci 數哪個敘述不正確，選項涉及起始值的定義、線性與指數成長的上界與下界
• 第 3 題｜3³⁰² mod 11
• 第 4 題｜S = {1,…,9} 上整除關係構成的 poset：是否為 total order、有沒有 maximal element、有沒有 greatest lower bound、是否為格
• 第 5 題｜給一張 weighted graph，從節點 a 跑 Dijkstra：到 z 的 shortest path 成本、加入 a、c 之後下一個加入的節點、shortest path 是否邊數最少、shortest path 是否唯一

多選（6–10，各 5%，答錯每選項 −1）

• 第 6 題｜R 是 total order 關係時，哪些邏輯敘述為真，涉及 antisymmetry、totality 與 R⁻¹
• 第 7 題｜遞迴程序 P：n < 3 時結束，否則呼叫 Q（Θ(√m) 步）把 array 切成三個等大的 subarray，只對其中 2 個遞迴呼叫 P。問步驟數 p(n) 的 recurrence 與複雜度 f_P
• 第 8 題｜整數 i、j 定義 i ~ j 若 2i + 3j = 5n（n 為某整數），判斷 ~ 是否 reflexive、symmetric、transitive、equivalence relation、partial order
• 第 9 題｜f : A → B 與 g : B → C 的合成函數：g∘f 為 one-to-one 時 f、g 是否 one-to-one，g∘f 為 onto 時 f、g 是否 onto，g∘f 為 bijection 時 f、g 是否 bijection
• 第 10 題｜用 generating function 解 a_n = −6a_n−1 + 7a_n−2（n ≥ 2，a₀ = −5、a₁ = 3），判斷 g(z) 與 a_n 的各選項

線性代數考點（11–20）

• 第 11 題（多選，5%）｜triangular matrix 的 eigenvalue、A 可逆與 A^T 可逆、A、B 可逆時 AB 是否可逆、AB 是否可能不等於 BA、是否存在實矩陣 A 使 A² = −I
• 第 12 題（多選，5%）｜symmetric matrix 的 eigenvalue 與 diagonalizable、diagonalizable 可逆矩陣的 inverse、A 可逆時 AB 與 BA 是否 similar、兩個 diagonalizable 矩陣的乘積、元素全正的 symmetric matrix 的二次式是否 positive definite
• 第 13 題（單選，5%）｜給一個 3×3 symmetric matrix（對角線依序為 0.6、0.9、0.8），求所有 eigenvalue 之和
• 第 14 題（單選，5%）｜A 以 L、U 兩個 5×5 矩陣的乘積給出，右邊是 5 維向量 b，求 Ax = b 的解
• 第 15 題（單選，5%）｜求一個 3×3 矩陣的 inverse
• 第 16 題（多選，5%）｜實方陣 A 有 eigenvalue λ：λ 為複數時共軛是否也是 eigenvalue、對應的 eigenvector 是否為複向量、A symmetric 時 λ 是否為實數、A symmetric 時各 eigenspace 是否 orthogonal、A^TA 的 eigenvalue
• 第 17 題（多選，5%）｜x̂ 是 Ax = b 的 least squares 解：x̂ 的公式、A^TA 不可逆時 x̂ 是否存在、x̂ 是否唯一、b ∈ Col A 時 x̂ 與 x 的關係、用 QR 表示 x̂
• 第 18 題（多選，5%）｜哪些敘述錯誤：A 可逆是否就 diagonalizable、非方陣是否不能 QR 分解、A 不 symmetric 是否不能 PDP^T 分解、有 n 個相異 eigenvalue 是否就有 spectral decomposition、A symmetric 是否有 SVD
• 第 19 題（多選，5%）｜矩陣可做 Cholesky 分解的必要條件：方陣、行 linearly independent、足夠多的 linearly independent eigenvector、eigenvalue 全為正、symmetric
• 第 20 題（多選，5%）｜把 3×3 矩陣 A（對角線為 1、其餘元素為 5）orthogonally diagonalize 成 A = PDP^T，問哪些值不在 P 或 D 中

作答時要注意的地方

1. 第 6–10 題與第 16–20 題明訂扣到該大題 0 分為止，第 11–12 題是逐選項 ±1。
2. 第 7 題的程序把 array 切成三段，只對其中兩段遞迴呼叫。
3. 單選第 1–5、13–15 題卷面沒有寫倒扣。

準備方向

• 3³⁰² mod 11（108 第 3 題），109 第 43 題也考同一個底數。
• 整除關係的 poset 與格（108 第 4 題），107、110、114 也有。
• diagonalizable、symmetric matrix、similar matrices 的性質判斷（108 第 11、12、16 題）。
• 矩陣分解的存在條件：QR、PDP^T、spectral decomposition、SVD、Cholesky（108 第 18、19 題），107、110、111、113、114、115 也有。
• least squares 解（108 第 17 題）。
• 演算法複雜度放進數學卷（108 第 7 題）。