115 師大資工所數學考點分析

題型與配分

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

申論卷、寫在答案卷上、標明題號、不必抄題、沒有倒扣。卷首 Some notations 定義了 column vector、linear operator、正交補 S⊥。

115 年的離散只考兩個主題：圖的自補性（35 分）與中國剩餘定理（15 分）。這是六年來離散涵蓋面最窄、但單一主題挖最深的一份。

線性代數考點（1–4，50%）

• 第 1 題（16%）
• (a) 8%：由 RREF 與三行反推矩陣 A：已知 A 的 reduced row echelon form R，以及 A 的第 2、4、6 行，決定 A。與 113 年第 1(a) 題同型
• (b) 8%：求使 T 不可對角化的所有 c：R³ 上的線性算子 T 含未知純量 c，求特徵多項式後找出幾何重數 < 代數重數的 c 值。與 113 年第 2(b) 題同型
• 第 2 題（11%）｜QR 分解：題目先把 QR 分解的定義寫清楚（Q 為 m×n 且行構成單位正交集、R 為 n×n 上三角），要求算出 Q 與 R。做法是對 A 的行做 Gram-Schmidt，R = Q^TA
• 第 3 題（11%）｜正交分解 v = w + z：W 是兩個方程式的解集合，求唯一的 w ∈ W 與 z ∈ W⊥ 使 v = w + z。也就是先算 P_W v 得 w，再用 z = v − w
• 第 4 題（12%）｜構造正交算子：找 R³ 上的正交算子 T 使 T(v) = w（v 與 w 皆為給定的單位向量）。要驗證 ‖v‖ = ‖w‖，再把 v 與 w 各自擴充成單位正交基底。與 110 年第 5 題同型

離散數學考點（5–7，50%）

• 第 5 題（5%）｜寫出圖同構的定義：「兩個圖 G 與 H 同構若且唯若 ⋯」。這 5 分是純背定義——要寫出存在雙射 φ : V(G) → V(H) 使得 uv ∈ E(G) ⟺ φ(u)φ(v) ∈ E(H)
• 第 6 題（30%）｜自補圖（self-complementary graph）：G 的補圖 H 滿足「u、v 在 G 中相鄰 ⟺ 在 H 中不相鄰」；若 G 與其補圖同構則稱 G 為自補圖
• (i) 10%：證明或反證「每個自補圖都是連通的」（真——若 G 不連通則其補圖必連通，而兩者同構，所以 G 必須連通）
• (ii) 20%：畫出所有 5 頂點的自補圖，並論證正確性。提示要你先列出所有合法的度數序列：5 個頂點的圖有 C(5,2) = 10 條可能的邊，自補圖必須恰有 5 條邊，且度數序列要與補圖的度數序列（5−1−d_i = 4−d_i 重排後）相同。答案是兩個：C₅（五邊形）與 P₄ 加一點的「牛角」形
• 第 7 題（15%）｜由已知解微調的中國剩餘定理：求滿足
• x ≡ 59 (mod 314)、x ≡ 97 (mod 159)、x ≡ 32 (mod 263)

的一個特解。題目先告訴你 x = 6,549,784 是「x ≡ 58 (mod 314)、x ≡ 97 (mod 159)、x ≡ 32 (mod 263)」的解。 關鍵洞察：兩個系統只差在第一式的 58 → 59，所以只要找到一個數 δ 滿足 δ ≡ 1 (mod 314)、δ ≡ 0 (mod 159)、δ ≡ 0 (mod 263)，答案就是 6549784 + δ。而 δ = 159×263×[(159×263)⁻¹ mod 314]。題目還明說「可以用算式表示答案」，不必算出最終數字

這份考卷的難點

1. 第 6(ii) 的 20 分要「畫出全部並論證」：先推出自補圖必有 C(n,2)/2 = 5 條邊，再列出所有度數和為 10 且與「4−d_i」自洽的度數序列，最後逐一檢驗同構。漏掉一個或多畫一個都會扣分，而且「論證正確性」意味著要說明為什麼沒有其他可能。
2. 第 7 題若沒看出「只差一個數」的結構，就會硬解完整的 CRT（模數 314×159×263 = 13,130,538），在沒有計算機的情況下幾乎算不完。這題考的是觀察力而不是計算力。
3. 第 1(b) 的不可對角化條件：特徵多項式有重根只是必要條件，還要對每個候選 c 實際算特徵空間維度。若 c 讓兩個原本相異的特徵值合併，就要檢查合併後的幾何重數。
4. 第 4 題的正交算子構造：正交算子保長度，所以先驗證 ‖v‖ = ‖w‖（題目給的 v 與 w 都已單位化），再各自擴充成單位正交基底 {v, v₂, v₃} 與 {w, w₂, w₃}，令 T 把前者映到後者。

準備建議

• 115 與 113 有兩題完全同型（由 RREF 反推 A、求使 T 不可對角化的 c），把 113 練熟等於先拿 16 分
• 正交投影／正交分解／正交算子是師大線代的三大支柱，六年全中，每年至少 20 分
• 中國剩餘定理三年連續（113、114、115），而 115 年的「微調」變形顯示師大喜歡在標準題上加一層觀察——練習時要多想「有沒有更快的路」
• 自補圖（115 第 6 題）在其他七校完全沒出現過，是師大獨有的考點。相關公式：n 頂點的自補圖必須 n ≡ 0 或 1 (mod 4)、邊數為 C(n,2)/2
• 圖同構的定義要能默寫（115 第 5 題直接考定義 5 分），這類「背定義就有分」的題目在師大時常出現