112 師大資工所數學考點分析｜國立臺灣師範大學

線代 50＋離散 50。第 9 題的「n−1 個頂點度數兩兩相異」是十年來最漂亮的圖論題，第 10 題要推導 Σ C(n,k)/(k+1) 的封閉式。

題型與配分

科目「數學基礎」，適用系所：資訊工程學系，全卷 2 頁、10 大題、100 分。

區段	題號	配分
線性代數	1–5	50%（每題 10 分）
離散數學	6–10	50%

申論卷、寫在答案卷上、標明題號、不必抄題、沒有倒扣。卷首附 Some notation 定義區（column vector、span、transpose、[T]_B）。

第 1 題（10%）｜span 與四大子空間
(a) 4%：求使 v 落在 span S 中的參數 r（解線性方程組）
(b) 6%：求給定矩陣的 column space 與 null space 的基底
第 2 題（10%）｜由三個像決定線性變換：T : R³ → R³，已知 T 在三個（非標準基底的）向量上的像，求 T 對任意 (x₁,x₂,x₃)^T 的公式
第 3 題（10%）｜階梯式基底的座標變換：𝒜 = {u₁,…,u_n} 是 Rⁿ 的基底，ℬ = {u₁, u₁+u₂, …, u₁+u_n} 也是基底。已知 [v]_𝒜 = (a₁,…,a_n)^T，求 [v]_ℬ。這是純代數推導，不需要具體數字——要從 v = Σa_iu_i 反推 ℬ 的係數
第 4 題（10%）｜正交對角化：對給定的對稱矩陣 A，求正交矩陣 P 與對角矩陣 D 使 P^TAP = D
第 5 題（10%）｜正交投影
(a) 6%：求子空間 W 的正交投影矩陣 P_W
(b) 4%：求 W 中離 v = (2,−1,1,2)^T 最近的向量 w

第 6 題（15%）｜函數計數（|A| = m、|B| = n）
(a) f : A → B 的個數 → n^m
(b) 一對一函數的個數 → n(n−1)…(n−m+1) = P(n,m)（m > n 時為 0）
(c) n = 2 時的滿射個數 → 2^m − 2
第 7 題（5%）｜Wilson 定理的變形：p 為質數、x 為正整數，證明若 1·2·…·(p−1) ≡ 1·2·…·(p−1)·x (mod p)，則 x ≡ 1 (mod p)。關鍵是 (p−1)! 與 p 互質（p 為質數，所有 1..p−1 都不被 p 整除），因此可以兩邊同除（乘反元素）
第 8 題（10%）｜找出所有「既非反身也非遞移」的關係：A = {a,b}，A 上的二元關係共有 2⁴ = 16 個，要逐一列出符合「不反身且不遞移」的那些，或說明不存在
第 9 題（15%）｜度數兩兩相異的連通圖：G 是 n 個頂點、m 條邊的連通簡單圖，且有 n−1 個頂點的度數兩兩相異
(a) 5%：證明恰有兩個頂點的度數為 ⌊n/2⌋
(b) 10%：已知 m + n = 155，求 n 與 m
這題是師大六年最精巧的一題：連通簡單圖的度數落在 1..n−1（共 n−1 種值），n−1 個頂點度數相異表示這 n−1 種值恰好各出現一次，剩下的那個頂點必須「補」一個重複值
第 10 題（5%）｜二項式恆等式的封閉式：推導 Σ_k=0ⁿ C(n,k)/(k+1) 的封閉公式。技巧是 C(n,k)/(k+1) = C(n+1,k+1)/(n+1)，因此總和 = (2ⁿ⁺¹ − 1)/(n+1)

第 9 題需要真正的圖論洞察：連通簡單圖中度數範圍是 1 到 n−1，共 n−1 種可能值。若有 n−1 個頂點度數兩兩相異，這 n−1 個值就被用光了，第 n 個頂點只能重複其中一個——再證明重複的必定是 ⌊n/2⌋。(b) 小題則要用 (a) 的結論把 m 表示成 n 的函數再解 m + n = 155。
第 3 題是純符號推導，沒有具體數字。要能寫出 v = Σa_iu_i 並把它改寫成 ℬ 的線性組合，最後得到 [v]_ℬ 的每個分量。很多人習慣代數字，遇到純符號會卡住。
第 10 題的技巧性恆等式：若看不出 C(n,k)/(k+1) = C(n+1,k+1)/(n+1)，就只能用積分技巧 ∫₀¹(1+x)ⁿdx。兩種方法都要會。
第 8 題要「窮舉」：A = {a,b} 上只有 16 個關係，但要逐一檢查反身性與遞移性，而且題目問的是「既不反身也不遞移」（兩個條件同時成立），容易漏掉。