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

題型與配分

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

單選第 1–4 題的答案是數值取整（⌊·⌋）後再 % 5。

線性代數考點

單選 1–4

• 第 1 題（5%）｜linear transformation L : R² → R³ 在 standard basis 下已知，求它相對於 R² 與 R³ 兩組非 standard basis 的矩陣表示，六個元素 a 到 f 相加取整後 % 5
• 第 2 題（5%）｜對一個矩陣做 Gram-Schmidt QR 分解，由 Q、R 中的指定元素組合出 ⌊·⌋ % 5
• 第 3 題（5%）｜p(x) = x²⁰ − x⁶ + 1，A 為 2×2 矩陣，p(A) 的四個元素相加取整後 % 5
• 第 4 題（5%）｜給定複矩陣 A，求把它 diagonalize 的 unitary matrix U，元素寫成 a + ib 的形式，由其中的 a、c、e、g 相加取整後 % 5

多選 5–10

• 第 5 題（5%）｜哪些向量屬於給定矩陣 A 的 nullspace
• 第 6 題（5%）｜A、B 為 N×N 方陣：λ_A × λ_B 是否為 AB 的 eigenvalue、AB 與 BA 的 eigenvalue 與 eigenvector、B = M⁻¹AM 時 A 與 B 的 eigenvalue、AAᴴ = AᴴA 時 A 與 Aᴴ 的 eigenvalue
• 第 7 題（5%）｜A 為 N×N symmetric matrix：A⁻¹ 是否 symmetric、是否有 N 個 orthonormal eigenvector、A² = A 時的 eigenvalue、每行和為 1 時是否有 eigenvalue 1、與另一個 symmetric matrix B 的乘積是否 symmetric
• 第 8 題（5%）｜單位圓與二維 linear transformation，五個選項各是一個獨立小題：(a) 粒子從 A(0,−1) 出發、∠OAB = 15°，在單位圓上反覆反射，判斷 P₁₂₀ 的座標；(b) 矩陣 J = [[1,2],[2,−1]] 作用在 A(0,−1) 上 N 次得 Q_N = (x_N, y_N)，判斷 x₁₀₀₁ 的值；(c) 承 (b)，Q₁₀₀₀ 與 Q₁₀₀₁ 的距離 M、Q₉₉₉ 與 Q₁₀₀₀ 的距離 N，判斷 M/N 的大小；(d) rotation matrix R_K 與 reflection matrix M_K，Q = R₁₅M₁₅R₃₀M₃₀R₄₅，第一象限的點變換後是否仍在第一象限；(e) 單位圓經 N = SJT 變換成 Z，判斷原點到 Z 的最遠與最近距離之和
• 第 9 題（5%）｜3×4 矩陣經 row operation 化成 [[1,2,3,5],[2,5,7,13],[0,0,1,0]]：兩個 determinant 是否相等、能否化成另一個指定矩陣、三個向量的 cross product 長度、一個二元系統與一個三元系統是否有唯一解
• 第 10 題（5%）｜五個 5×5 矩陣，哪些的 determinant 為零

離散數學考點（11–20）

• 第 11 題（5%）｜給 6×6 的 0/1 矩陣 A 描述 binary relation R：是否 reflexive、anti-symmetric、transitive、partial order、transitive closure 是否 symmetric
• 第 12 題（5%）｜承第 11 題，S 為 R 的 transitive closure，每個元素視為集合，S 反映哪些集合運算子的行為（∩、∪、⊆、−、⊇ 等）
• 第 13 題（5%）｜S = {1, 2, 3, 4, 6, 8, 12, 24} 上的整除關係：是否為 total order、well-ordering、有沒有 greatest lower bound、是否為格、有沒有 maximal element
• 第 14 題（5%）｜程序 P：n < 9 時結束，呼叫 B 後依 i mod 9 = 1、4、7 把元素分進三個 subarray，各遞迴呼叫一次。要讓 P 的複雜度為 O(n)，問 B 的複雜度可以是 O(m^1/2)、O(m)、O(m^√2)、O(m^1/4)、O(m²) 中的哪些
• 第 15 題（5%）｜a_n = 4a_n−1 − 4a_n−2（a₀ = 0、a₁ = 1/2），判斷 generating function 與通項的各選項
• 第 16 題（5%）｜C₅、W₅、K₅、K₅,₅、Q₅ 哪些有 Euler circuit
• 第 17 題（5%）｜派對上你與伴侶遇到另外三對夫妻，規定不跟自己或自己的伴侶握手、不重複握手，除你以外的 7 人握手次數全都不同，問你與伴侶各握了幾次手
• 第 18 題（5%）｜十進位數字串中含偶數個 0 才是有效碼字，a_n 為 n 位有效碼字數，判斷 recurrence 與 closed form 的各選項
• 第 19 題（5%）｜給一張圖，求 vertex connectivity 與 edge connectivity，選項是 1、2、3 的各種組合
• 第 20 題（5%）｜四張圖哪些與 K₃,₃ homeomorphic

作答時要注意的地方

1. 80 分在逐選項倒扣的多選題上，單選與多選各自扣到整大題 0 分為止。
2. 第 8 題一題 5 分，五個選項是五個獨立小題，每錯一個選項 −1。
3. 第 10 題禁用計算器，題目是五個 5×5 determinant。
4. 第 11、12 題共用一個 6×6 的 relation matrix。

準備方向

• change of basis（114 第 1 題），112 第 16 題、113 第 2 題、115 第 10 題也有。
• QR 分解（114 第 2 題），112 第 17 題、113 第 7 題、115 第 7 題用 Gram-Schmidt 或 QR。
• 矩陣多項式與高次冪（114 第 3 題），112 第 18 題、115 第 6 題也有。
• symmetric matrix、similar matrices 與 eigenvalue 的性質（114 第 6、7 題）。
• 單位圓上的變換、旋轉與鏡射（114 第 8 題）。
• determinant 為零的判斷（114 第 10 題）。
• relation matrix（114 第 11、12 題），106、109、112 也有。
• 整除 poset 與格（114 第 13 題），107、108、110 也有。
• pseudo-code 的複雜度（114 第 14 題），與 112 第 7、8 題是同一個模板。
• generating function 解遞迴（114 第 15 題）與計數遞迴（114 第 18 題）。
• Euler circuit（114 第 16 題），113、115 也有。
• connectivity（114 第 19 題）與 homeomorphic（114 第 20 題）。