111 交大資工所數學考點分析

題型與配分

科目「線性代數與離散數學（1102）」，系所班別資訊聯招，考試日期 111 年第 2 節，全卷 3 頁、9 題、100 分，不可使用計算機。

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

逐題考點

第 1 題｜河內塔的多柱推廣（25%）

這是交大數學十年來最大的單題，四小題層層推廣：

• (a) 2%｜3 根柱子時 H³(n) 的遞迴式與封閉解（H³(n) = 2H³(n−1)+1 = 2ⁿ−1）
• (b) 3%｜4 根柱子時的 H⁴(n) 遞迴式與解，以及 H³(n) 與 H⁴(n) 的關聯（Frame-Stewart 演算法）
• (c) 10%｜5 根柱子時 H⁵(n) 與前兩者的關聯
• (d) 10%｜一般 m 根柱子的 H^m(n)，以及 H^m(n) 與 H^m−1(n) 的關係

這題沒有標準課本答案（4 柱以上的最佳解至今仍是 Frame-Stewart 猜想），考的是能不能一步步建立遞迴並說清楚推廣的邏輯。

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

• 第 2 題（5%）｜判斷 G₁ 是否為二分圖，並論證
• 第 3 題（5%）｜7 個頂點、其中兩個度數為 3、其餘度數為 2 的圖是否有 Euler path，有的話要構造出來
• 第 4 題（5%）｜平面圖有 12 個面、11 個頂點，其中六個三角形、四個四邊形，剩下兩個面各有幾條邊（用 Euler 公式 v−e+f = 2 與面邊關係 2e = Σ邊數）
• 第 5 題（10%）｜(a) 2% 圖 G₃ 的著色數 χ(G) (b) 3% 著色多項式 P_G (c) 5% 使 P_G(n) > 0 的最小 P_G(n) 值

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

• 第 6 題（25%）｜(a) 6% 把向量 b 投影到 A 的零空間 (b)(i) 8% 用 Gram-Schmidt（題目明訂必須依行的順序處理，否則零分）求正交歸一向量 (b)(ii) 3% 補上額外的正交歸一向量使其張成 R⁴ (c) 8% 證明 N(A^TA) = N(A)（答錯倒扣 5 分）
• 第 7 題（6%）｜(a) 3% 計算一個 4×4 行列式 (b) 3% 證明正交矩陣的行列式是 ±1（答錯倒扣 2 分）
• 第 8 題（12%）｜(a) 6% 檢查三個矩陣的可對角化性，可以的話對角化、不行的話說明原因 (b) 3% 求 A⁸ 與 A⁹ (c) 3% 用特徵值求 det(B + 6I)
• 第 9 題（7%）｜(a) 3% 求矩陣的 SVD（U、Σ、V） (b) 4% 由 SVD 的結果寫出 C(A^T)、N(A)、C(A)、N(A^T) 的正交歸一基底

這份考卷的難點

1. 第 1 題（25 分）的多柱河內塔沒有課本標準解，(c)(d) 合計 20 分要自己建立推廣的遞迴式並論證關聯性 —— 這是全卷區分度最高的地方。
2. 第 6(b)(i) 明訂「必須依行的順序處理，否則零分」，Gram-Schmidt 的順序不能自己調整。
3. 兩題證明有倒扣（第 6(c) 扣 5 分、第 7(b) 扣 2 分），沒把握就該留白。
4. 第 9(b) 要由 SVD 直接讀出四個基本子空間的基底，需要理解 U 的前 r 行張成 C(A)、V 的後 n−r 行張成 N(A) 等對應關係。

準備建議

• SVD 與四個基本子空間的關係（111 第 9 題）是交大線代的重點，Strang 的「四個基本子空間」圖要熟
• N(A^TA) = N(A) 的證明（111 第 6(c) 題）是最小平方法的理論基礎，務必會寫
• Euler 公式與平面圖的面邊計數（111 第 4 題）是離散圖論的固定考點
• 交大在 110、111、113 都出現「答錯倒扣、不會寫請留白」的證明題，沒把握真的要留白