106 台大資工所考古題詳解｜數學考點分析

題型與配分

全卷 3 頁、12 題、100 分。

線性代數考點（1–5，各 10%）

• 第 1 題｜求一個 3×3 實矩陣的 inverse
• 第 2 題｜eigenvalue 只有 0 與 1 的 diagonalizable 複矩陣 A，求最小的正整數 k 使 A^k = A 恆成立
• 第 3 題｜R² 上對通過原點與 (x,y) 的直線 L 做 orthogonal projection，求其在 standard basis 下的矩陣表示
• 第 4 題｜給一個 bilinear form f : R²×R² → R，已知 u = (1,0)，要找出向量 w 使 f 在 {u, w} 這組 basis 下化成 s₁t₁ + s₂t₂ 的標準形
• 第 5 題｜求一個 2×2（或 3×2）矩陣的 pseudo-inverse（Moore-Penrose pseudo-inverse）

離散數學考點（6–12）

• 第 6 題（10%）｜|A| = m 時，A 上既不是 reflexive 也不是 irreflexive 的關係有幾個
• 第 7 題（10%）｜邏輯推論填空：[(p∨q)∧(¬p∨r)] ⇒ (＿∨＿)
• 第 8 題（10%）｜recurrence a_n+2 = a_n+1 + a_n（Fibonacci）的解具有 A·αⁿ + B·βⁿ 的形式，要以任意初始條件 a₀、a₁ 表示出 A、B、C、D
• 第 9 題（5%）｜證明 n ≥ 2 時 n−1 與 n 互質
• 第 10 題（5%）｜填空：一個圖是 _____ 若且唯若它所有的 cycle 都是偶數長度
• 第 11 題（5%）｜n 為奇數時，化簡 C(n,0) + C(n,2) + … 這類 binomial coefficient 的和
• 第 12 題（5%）｜給一個 directed graph，在第二張圖上畫出它的 transitive closure

作答時要注意的地方

1. 離散數學第 6、7、8 題各 10 分，第 9 到 12 題各 5 分。
2. 第 9 題是全卷唯一的證明題，5 分。

準備方向

• 線代與離散各佔一半，兩邊都要準備。
• pseudo-inverse 在 106、109、113、115 都出現過，定義與計算要熟。
• 關係的計數（reflexive、symmetric、transitive 的各種組合）在 106、107、111 都考過。
• recurrence 的通解形式，加上以初始條件表示係數，出現在 106、107、108、109、111、112、113、114。