111 交大資工所考古題詳解｜數學考點分析

題型與配分

全卷 3 頁、9 題、100 分，不可使用計算機。

第 6(c) 與第 7(b) 兩題有倒扣，卷面寫著「不會寫請留白，答錯最多倒扣 5 分（第 7(b) 為 2 分），扣至本題組 0 分為止」。

逐題考點

第 1 題｜Tower of Hanoi 的多柱推廣（25%）

• (a) 2%｜3 根柱子時 H³(n) 的 recurrence 與 closed-form solution
• (b) 3%｜4 根柱子時的 H⁴(n) recurrence 與解，以及 H³(n) 與 H⁴(n) 的關聯
• (c) 10%｜5 根柱子時 H⁵(n) 與前兩者的關聯
• (d) 10%｜一般 m 根柱子的 H^m(n)，以及 H^m(n) 與 H^m−1(n) 的關係

第 2–5 題｜圖論（25%）

• 第 2 題（5%）｜判斷 G₁ 是否為 bipartite graph，並論證
• 第 3 題（5%）｜7 個頂點、其中兩個 degree 為 3、其餘 degree 為 2 的圖是否有 Euler path，有的話要構造出來
• 第 4 題（5%）｜planar graph 有 12 個面、11 個頂點，其中六個三角形、四個四邊形，剩下兩個面各有幾條邊
• 第 5 題（10%）｜(a) 2% 圖 G₃ 的 chromatic number χ(G) (b) 3% chromatic polynomial P_G (c) 5% 使 P_G(n) > 0 的最小 P_G(n) 值

第 6–9 題｜線性代數（50%）

• 第 6 題（25%）｜(a) 6% 把向量 b projection 到 A 的 null space (b)(i) 8% 用 Gram-Schmidt 求 orthonormal 向量，題目明訂必須依行的順序處理，否則零分 (b)(ii) 3% 補上額外的 orthonormal 向量使其 span R⁴ (c) 8% 證明 N(A^TA) = N(A)，答錯倒扣 5 分
• 第 7 題（6%）｜(a) 3% 計算一個 4×4 determinant (b) 3% 證明 orthogonal matrix 的 determinant 是 ±1，答錯倒扣 2 分
• 第 8 題（12%）｜(a) 6% 檢查三個矩陣是否 diagonalizable，可以的話 diagonalize，不行的話說明原因 (b) 3% 求 A⁸ 與 A⁹ (c) 3% 用 eigenvalue 求 det(B + 6I)
• 第 9 題（7%）｜(a) 3% 求矩陣的 SVD（U、Σ、V） (b) 4% 由 SVD 的結果寫出 C(A^T)、N(A)、C(A)、N(A^T) 的 orthonormal basis

作答時要注意的地方

1. 第 1 題 25 分，(c)(d) 合計 20 分。
2. 第 6(b)(i) 明訂必須依行的順序做 Gram-Schmidt，否則零分。
3. 第 6(c) 答錯倒扣 5 分、第 7(b) 答錯倒扣 2 分，都扣至本題組 0 分為止。
4. 第 9(b) 要寫出四個基本 subspace 的 orthonormal basis。

準備方向

• SVD 與四個基本 subspace 的關係（111 第 9 題）。
• N(A^TA) 與 N(A) 的關係證明（111 第 6(c) 題）。
• Euler's formula 與 planar graph 的面邊計數（111 第 4 題）。
• 倒扣題型：110、111、113、115 年都出現「不會寫請留白」的證明題。