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

題型與配分

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

兩種倒扣同時存在：多選「答錯每個選項倒扣 1 分，扣至該大題（多選題）零分為止」；單選「答錯一題倒扣 2 分，扣至該大題（單選題）零分為止」。兩個大題各自獨立觸底，不會互相吃分。

本科禁用計算器，但單選 14–20 全部是「算出一個數值 → 取絕對值 → 四捨五入 → mod 5」，等於要手算完整的矩陣運算才選得出答案。

離散數學考點（1–10）

第 1–4 題共用同一個 5×5 的 0/1 矩陣 A，A 代表一個二元關係 R——一題算錯、四題全倒。

• 第 1 題（5%）｜關係的性質：R 是否 reflexive／anti-symmetric／transitive／偏序關係，以及「R 的 symmetric closure 是否遞移」
• 第 2 題（5%）｜三種閉包要補幾個 1：reflexive closure 補 4 個、symmetric closure 補 6 個、transitive closure 補 3 個（要逐一驗算），外加「reflexive closure 是否為 poset」「symmetric closure 是否為等價關係」
• 第 3 題（5%）｜把 R 畫成有向圖：weakly connected、最長 simple path 長度是否為 4、reflexive + symmetric + transitive closure 有幾個連通分量、transitive closure 中是否存在 Hamilton path、R^∞ 是否 strongly connected
• 第 4 題（5%）｜令 S 為 R 的 symmetric + reflexive closure，把元素當命題，S 對應哪些布林運算子（∧、∨、→ …）——把關係矩陣與真值表對照
• 第 5 題（5%）｜「充分但不必要」條件的辨析（五個選項各自是一個命題邏輯陷阱）：圖同構 vs 都有 Euler circuit、g is O(n) but not Θ(n) vs g is o(2ⁿ)、集合上的等價關係 vs 分割、P 上存在良序 vs 可用數學歸納法、「P 為假」vs「P→Q 為真」
• 第 6 題（5%）｜無向圖的度數：連通圖是否必有長度 n 的 simple path、ΣD(i) 必為偶數（握手定理）、連通圖是否 ΣD(i) ≥ 2n、是否必有兩個頂點度數相同（鴿籠）、連通圖的「直接相連」關係取遞移＋反身閉包是否成為完全圖
• 第 7 題（5%）｜遞迴程序的遞迴式：程序 P 先呼叫 B（花 Θ(√m)），再用 i mod 9 = 0/3/6 把輸入切成 3 個 n/9 大小的子陣列各自遞迴。正確式子是 F_n = 3F_{n/9} + Θ(n)（迴圈本身 n 步壓過 √n）
• 第 8 題（5%）｜承上，解出 P 的複雜度等級：a = 3、b = 9、n^{log_9 3} = n^0.5，與 f(n) = n 比較屬 Master Theorem case 3 → Θ(n)，選項刻意放了 O(n log n)、O(n^1.5)、O(√n log n) 混淆
• 第 9 題（5%）｜字串計數遞迴：8 個字母的字母表，合法字串不得出現指定的連續組合，求 P_n 的遞迴關係與初始值（P₁ = 8、P₂ = ?）
• 第 10 題（5%）｜承上，用生成函數 g(z) 解 P_n：g(z)(1 − 6z − 12z²) = ...、部分分式拆成 1/(1−(3+√21)z) 與 1/(1−(3−√21)z)，最後得到含 (3±√21)ⁿ 的封閉解

線性代數考點（11–20）

多選（11–13）

• 第 11 題（5%）｜對稱矩陣：重根時是否仍有完整的正交單位特徵向量組（真）、A+B 與 AB 是否都對稱（AB 不一定）、rank r < n 時是否有 n−r 個零特徵值、特徵值必為實數
• 第 12 題（5%）｜A_m×n（m < n）：nullity + rank 是否等於 m（應為 n，陷阱）、rank = m 時 AA^T 是否可逆（真）、獨立行數與獨立列數是否可能不同（不可能）、高斯消去後零列數是否為 m − r
• 第 13 題（5%）｜特徵值判斷：8 個正 pivot 是否保證特徵值非負、AB = BA 且都可對角化是否代表特徵值相同（假，只保證可同時對角化）、相似矩陣特徵值相同（真）、AA^T 與 A^TA 特徵值相同（非零部分相同）

單選（14–20）——全部要真的算出數字

• 第 14 題（5%）｜4×4 矩陣求反矩陣 A⁻¹，把所有元素相加取絕對值四捨五入後 mod 5
• 第 15 題（5%）｜讀一段 Matlab 程式碼：11×11 全 1 矩陣、主對角線改成 0.9，求 det(A)。關鍵是 J − 0.1I 型矩陣的行列式公式（特徵值為 11−0.1 與 −0.1 重根）
• 第 16 題（5%）｜基底變換：求線性運算子 A 相對於基底 [1,1,0]^T、[0,1,1]^T、[1,2,2]^T 的表示矩陣 B = S⁻¹AS
• 第 17 題（5%）｜對 R⁴ 中三個向量做 Gram-Schmidt，依序 v₁ → v₂ → v₃ 求正交基底，答案保證是整數
• 第 18 題（5%）｜給定 A，求另一個矩陣 B 並把元素加總後 mod 5
• 第 19 題（5%）｜最小平方解：Ax = b 中 A 為 4×3、b = [4, −1, 0, 1]^T，解正規方程 A^TAx̂ = A^Tb
• 第 20 題（5%）｜正交對角化：求正交矩陣 P 使 P^TAP = D，再把 P 第一列三個元素相乘、D 對角線三個元素相乘

這份考卷的難點

1. 第 1–4 題是連環題，共 20 分綁在同一個關係矩陣上。矩陣本身只有 5×5，但 OCR 都難讀的密集 0/1，考場上要先把它抄成有向圖再逐題判斷，否則四題一起錯就是 −20 分等級的災難。
2. 單選 35 分全部是「硬算」，而且禁用計算器。第 15 題的 11×11 行列式若不知道 cI + J 型矩陣的特徵值結構，純展開是不可能算完的。
3. 第 7、8 題把演算法分析搬進數學考科——這是中央十年的固定套路（106、107、108、111 都有），而且 112 這次一次考兩題 10 分，要能從 pseudo-code 讀出 3F_{n/9} + Θ(n) 並套 Master Theorem。
4. 第 5 題的「充分但不必要」是純邏輯陷阱：五個選項分別來自圖論、複雜度、集合、良序、命題邏輯，每個都要判斷「A ⇒ B 成立嗎？B ⇒ A 成立嗎？」兩個方向。

準備建議

• 關係閉包的三件事要能手算：reflexive closure 補主對角線、symmetric closure 補 A^T、transitive closure 用 Warshall——112 第 2 題直接問「要補幾個 1」，會算就送分
• Master Theorem 要熟到能反推：112 第 7、8 題與 114 第 14 題是同一組出題人的同一個 pseudo-code 模板（連 array2/3/4、i mod 9 都一樣），把這兩年對照著看效益最高
• 生成函數解遞迴（112 第 10 題）在中央 113 第 20 題、114 第 15 題、115 第 13 題連續四年都出現，是必守題型
• 「算到底再 mod 5」的單選要練手速：Gram-Schmidt、最小平方、正交對角化各練 5 題，目標是 5 分鐘內算完一題，因為答錯倒扣 2 分，沒把握不如不答