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

題型與配分

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

第 1–40 題都是 True／False。第 41–50 題是五選一的單選。

線性代數是非題考點（1–40）

• 第 1–5 題｜A、B、C 為矩陣、r 為純量：AB = BA、消去律、AB = 0 是否蘊含 A = 0 或 B = 0、(AB)^T = A^TB^T、(rA)⁻¹ = rA⁻¹
• 第 6–10 題｜determinant：det(A+B)、det(AB)、det(AB) 與 det(BA)、det(rA)、det(A⁻¹)
• 第 11–15 題｜Ax = b 是一致的線性系統，b ≠ 0 與 b = 0 兩種情形下，解集合是否為 subspace
• 第 16–20 題｜A 與 B 為可逆且 A 與 B similar：det、A² 與 B²、A^T 與 B^T、A⁻¹ 與 B⁻¹、AB 與 BA 是否 similar
• 第 21–25 題｜n×n 矩陣 A diagonalizable：是否有 n 個相異 eigenvalue、是否有 n 個 linearly independent 的行、A^T 與 A⁻¹ 是否 diagonalizable、是否沒有零 eigenvalue、與 eigenspace 的關係
• 第 26–30 題｜Nul A 與 Row A 的 orthogonal complement 關係、W⊥ 是否為 subspace、(W⊥)⊥ = W、v 與 w orthogonal 時 Av 與 Aw 是否 orthogonal、W 與 W⊥ 的 direct sum 是否為 Rⁿ
• 第 31–35 題｜給 2×2 矩陣 A 與一組 basis B，求 x ↦ Ax 相對於 B 的矩陣，逐題判斷某兩個數是否出現在 B-矩陣中
• 第 36–40 題｜對給定矩陣做 QR 分解，逐題判斷某個數是否不在 R 矩陣中

離散數學考點（41–50，各 5%，不倒扣）

• 第 41 題｜四人中恰有一人說謊，各人的陳述互相指涉，問是誰做的
• 第 42 題｜哪個敘述最不恰當：N、Z、Q、R、2^Z 之間哪些 bijection 存在
• 第 43 題｜3³⁰² 對 5、7、11、385 的餘數，問哪個敘述最不恰當
• 第 44 題｜給關係 R 的矩陣，判斷 antisymmetric、transitive、equivalence relation 等性質，問哪個敘述最不恰當
• 第 45 題｜兩個 undirected graph G₁、G₂ isomorphism 的條件：頂點數、邊數、各 degree 的頂點數、subgraph、以上全部
• 第 46 題｜哪個敘述無法由 Gödel 不完備定理支持
• 第 47 題｜哪個運算具有結合律：集合差、除法、命題蘊涵、最大公因數、集合的 Cartesian product
• 第 48 題｜遞迴演算法 A：輸入大小 m 時，先花 Θ(√m) 步準備並切成 4 個大小約 m/4 的子集，各子集遞迴呼叫 A，再花 Θ(√m) 步合併。問時間複雜度
• 第 49 題｜餐廳訂位：1 人可用 email 或網頁訂，2 人一組可用電話、email 或網頁訂，問訂 n 個有順序的座位共有幾種方式
• 第 50 題｜10 人的團體，每人至少喜歡其他 4 人，被至少 3 人喜歡者稱為 happy，問可以下什麼結論

作答時要注意的地方

1. 第 1–30 題每題 1 分、答錯倒扣 1 分，第 31–40 題每題 2 分、答錯倒扣 2 分。
2. 第 41–50 題明訂答錯不倒扣。
3. 第 11–15 題是同一個觀念的五種表述。
4. 第 42、43、44 題問的是「最不恰當」的敘述，第 46 題問的是「無法支持」的敘述。

準備方向

• similar matrices 的性質（109 第 16–20 題），111 第 16 題、112 第 13 題、114 第 6 題也有。
• diagonalizable 的常見誤解（109 第 21–25 題），107、110、111 也有。
• 矩陣乘法與 determinant 的基本性質（109 第 1–10 題），106、107、108、110 也有。
• 基數與 bijection（109 第 42 題），106、107、110、115 也有。
• 3³⁰² 的模運算（109 第 43 題），108 第 3 題是同一個底數。
• relation matrix（109 第 44 題），106、112、114 也有。
• Gödel 不完備定理（109 第 46 題），115 第 14 題也考數學史與基礎。
• 演算法複雜度放進數學卷（109 第 48 題），106、107、108、110、111、112、114、115 都有。