115 中央資工所數學考點分析

題型與配分

系所「資工類」，科目：離散數學與線性代數，全卷 100 分，共 7 頁，20 題。

三個大題各自獨立觸底：第一部分「倒扣至多選題第 1 至 5 題零分為止」、第二部分「倒扣至單選題第 6 至第 10 題零分為止」、第三部分「倒扣直到多選題第 11 至第 20 題零分為止」。這是中央十年來第一次把倒扣切成三個互不相通的池子——某一段崩盤不會拖累另外兩段。

本科考試禁用計算器。

線代考法大轉向：114 以前線代幾乎都是「算出數字再 mod 5」，115 把線代拆成理論多選 25 分（1–5）＋ 計算單選 25 分（6–10），前半完全不用動筆算，是十年來最好拿分的線代區段。

線性代數考點

一、理論多選 1–5（純觀念，會就是送分）

• 第 1 題（5%）｜行列式性質：det(A) ≠ 0 ⇒ A 的列構成 Rⁿ 的基底（真）、det(cA) = c·det(A)（假，應為 cⁿ）、rank r < n ⇒ det = 0（真）、三角矩陣行列式為對角線乘積（真）、AB = BA ⇒ det(A+B) = det(A)+det(B)（假）
• 第 2 題（5%）｜向量空間與基底：任何線性獨立子集可擴充成基底（真）、有限維時任何生成集都是基底（假，可能有多餘向量）、任兩組基底元素個數相同（真）、向量空間有唯一基底（假）、生成 ⇒ 獨立（假）
• 第 3 題（5%）｜線性變換：T 單射 ⟺ ker(T) = {0}（真）、T 滿射 ⟺ dim(V) = dim(Image(T))（假，應為 dim(W) = dim(Image)）、基底的像是否仍為 W 的基底（假）、dim(V) = dim(W) 且單射 ⇒ 滿射（真）、表示矩陣依基底而定（真）
• 第 4 題（5%）｜正交性：u⊥v 且 u⊥w ⇒ u⊥(v+w)（真）、非零正交集必線性獨立（真）、每個單位正交集都是基底（假，要夠多個）、畢氏定理 ‖u+v‖² = ‖u‖² + ‖v‖²（真）、u⊥v ⟺ ‖u+v‖ = ‖u‖+‖v‖（假，那是同向）
• 第 5 題（5%）｜Hermitian 矩陣：特徵值皆為實數（真）、相異特徵值的特徵向量正交（真）、兩個 Hermitian 相加仍 Hermitian（真）、可由么正矩陣對角化（真）、兩個 Hermitian 的乘積必為 Hermitian（假，除非可交換）——四真一假的典型設計

二、計算單選 6–10（沿用「算完 mod 5」格式）

• 第 6 題（5%）｜矩陣高次冪：求 A²⁰ 相關量 → 先對角化或找遞迴
• 第 7 題（5%）｜QR 分解：對 4×3 矩陣做 QR，把 R 中所有非零元素相乘取絕對值後四捨五入 mod 5
• 第 8 題（5%）｜5×5 行列式手算，求 |K| mod 5
• 第 9 題（5%）｜投影到行空間：把 b = [1 2 3 4]^T 投影到 A 的 column space，得到 c 後把元素全部相乘
• 第 10 題（5%）｜兩組基底間的座標轉換：S = {v₁,v₂,v₃}、T = {u₁,u₂,u₃} 為 R³ 的有序基底，已知 V 相對於 T 的座標為 [2 3 1]^T，求相對於 S 的座標 [M N P]^T

離散數學考點（11–20）

• 第 11 題（5%）｜分治遞迴分析：演算法 A 在 n ≤ 4 時終止，否則切成 4 等份、取其中 2 份各遞迴一次，再用整合程序 I（花 Θ(√(m/4))）合併。得 T(n) = 2T(n/4) + Θ(√n)，而 n^log₄2 = √n 恰與 f(n) 同階 → Master Theorem case 2 → Θ(√n log n)。正解是 (b) 分治式遞迴 + (e) Θ(√n log n)
• 第 12 題（5%）｜述詞邏輯的自然語言翻譯：D(x,y)「y 是 x 的倍數」、C₃(x,y)「x ≡ y (mod 3)」、C₆(x,y)「x ≡ y (mod 6)」，把一個含否定與蘊涵的公式對照五種中英文敘述。五個選項的差別只在「if…then」與「it is possible that」的量詞範圍
• 第 13 題（5%）｜生成函數解遞迴：a_n = −a_n−1 + 6a_n−2、a₀ = 0、a₁ = 5。特徵方程 x² + x − 6 = (x+3)(x−2) → 根為 2 與 −3，解得 a_n = 2ⁿ − (−3)ⁿ，生成函數滿足 G(x)(1 + x − 6x²) = 5x
• 第 14 題（5%）｜數學史與基礎：「集合」是否在微積分之前被形式定義（假，Cantor 在 1870 年代，微積分早了兩百年）、所有無窮集是否同基數（假，Cantor 對角論證）、Hilbert's program 是否成功（假，被 Gödel 不完備定理推翻）、經驗主義是否主張知識全由邏輯證成（假，那是邏輯主義）→ 正解是 (e) none of the above
• 第 15 題（5%）｜合成函數與基數：f : C → D、g : A → B，已知 f∘g 是滿射，反推 |A|、|B|、|C|、|D| 之間可能的大小關係
• 第 16 題（5%）｜無兩男相鄰的排隊數：a_n = a_n−1 + a_n−2、a₁ = 2、a₂ = 3（給定 a₃ = 5 驗證），即 Fibonacci 平移。正解是 (a) 遞迴式 + (d) 2,3,5,8,13 + (e) a_n = F_n+2；(b) 的 2a_n−1 − a_n−2 與 (c) 的錯誤初始值是陷阱
• 第 17 題（5%）｜Hamilton 與連通度：有 Hamilton cycle ⇒ 無割點（真）、無割點 ⇒ Hamiltonian（假，這是最容易誤選的反向陷阱）、Hamiltonian ⇒ 2-connected（真）、存在非 3-connected 的 Hamiltonian 圖（真，例如 C_n）、最小度 ≥ 2 ⇒ Hamiltonian（假，Dirac 條件要 ≥ n/2）
• 第 18 題（5%）｜Euler circuit：逐一判斷 C₆、W₆（輪圖）、K₅、K₄,₄、Q₄ 五個圖有沒有 Euler 迴路——判準只有一條：所有頂點的度數都是偶數。與 114 第 16 題幾乎是同一題換數字
• 第 19 題（5%）｜二分圖：不含奇圈（真）、每個二分圖都是平面圖（假，K₃,₃ 就不是）、K₃,₃ 是二分圖（真）、每棵樹都是二分圖（真）、有 Hamilton cycle ⇒ 兩邊等大（真）
• 第 20 題（5%）｜平面圖不等式：m ≤ 3n − 6（真）、每個面度數 ≥ 4 ⇒ m ≤ 2n − 4（真）、平面圖可含 K₅ 或 K₃,₃ 的細分（假，Kuratowski 定理反過來）、每個平面圖都有 Hamilton cycle（假）、四色定理（真）

這份考卷的難點

1. 第 11 題的 Master Theorem case 2 最容易踩雷：n^log₄2 剛好等於 √n，與整合成本 Θ(√n) 同階，所以答案是 Θ(√n log n) 而不是 Θ(√n)。選項裡同時放了 Θ(n²)、Θ(n√n)、Θ(√n log n) 三個相近答案。
2. 第 14 題考數學史——中央十年唯一一次。Hilbert's program 與 Gödel、Cantor 的關係屬於離散課本序章的「延伸閱讀」，多數人根本沒讀，而正解偏偏是 (e) 以上皆非，亂猜四個選項就是 −4 分。
3. 第 12 題的述詞翻譯在逐選項倒扣下極度危險：五個選項的中文敘述長得幾乎一樣，差別只在否定與蘊涵的作用範圍，要逐字拆解才分得出來。
4. 第 3 題 (b) 的 dim(V) = dim(Image(T)) 是精心設計的偷天換日——正確的滿射條件是 dim(W) = dim(Image(T))，只改一個字母。

準備建議

• 115 的線代理論多選（1–5）是十年來最好拿的 25 分：只要把「行列式性質、基底唯一性、秩—零化度定理、正交集獨立性、Hermitian 四性質」這五組課本定理背熟就能全拿，強烈建議優先把這五題做完再回頭算單選
• 圖論的「充要條件」要背成對背：Euler circuit ⟺ 連通且所有度數為偶（114 第 16 題、115 第 18 題連兩年）、Hamiltonian ⇒ 2-connected 但反向不成立（115 第 17 題）、二分圖 ⟺ 無奇圈（115 第 19 題）、Kuratowski 定理（115 第 20 題、111 第 4 題）
• 生成函數解遞迴連續四年必考（112 第 10 題、113 第 20 題、114 第 15 題、115 第 13 題），而且四年都是二階常係數，把「列式 → 部分分式 → 封閉解」三步驟練到反射動作
• Master Theorem 的三個 case 要能判：112 第 8 題是 case 3、114 第 14 題是反推、115 第 11 題是 case 2——中央把演算法複雜度當數學考科考了十年，這是本校最穩定的特色
• 三個大題各自獨立觸底是 115 的新規則：即使離散那 50 分全軍覆沒，線代的 50 分仍完整保留。先掃自己最有把握的那一段拿滿，策略價值比往年更高