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

題型與配分

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

全卷 20 題都是多重選擇題，計分方式：「每題 5 分、每一選擇答對給 1 分、答錯倒扣 1 分、不答 0 分」。

100 分全部都在逐選項倒扣的規則下 —— 這是中央數學最嚴苛的一年。

離散數學考點（1–10）

• 第 1 題｜驗證兩個複合命題邏輯等價的正確方法（p ↔ q 是恆真式、p ⊕ q 是矛盾式、真值表部分相同是否足夠…）
• 第 2 題｜兩個可數無限集合 A、B：2^A 與 2^B 是否不可數、A − B 可能是空集／有限／可數無限／不可數
• 第 3 題｜計數公式判斷：|A| = r、|B| = n 時函數個數、非負整數解、長度 n 恰 r 個 1 的位元串、10 件物品放入 4 個相同空盒、橋牌發牌
• 第 4 題｜圖的定義：pseudograph 能否有自環、W_n（輪圖）的節點數、n-cube Q_n 的邊數（n·2ⁿ⁻¹）、握手定理、長度 n 的路徑是否必含迴圈
• 第 5 題｜給 Hasse 圖判斷偏序集的性質（全序？反身？{a,c} 的最小上界？是否為格（lattice））
• 第 6 題｜綜合判斷：1-1 映射是否蘊含同基數、等價關係是否總能形成分割（真）、數學歸納法與全序集、長度 n 的路徑數相同是否蘊含圖同構（假）、big-O 定義中是否必須找最小的 c 與 k
• 第 7–8 題｜給一個遞迴程序 P（Q 把長度 m 陣列切成 4 段花 √m 步、R 合併兩段花 2√m 步），求步驟數的遞迴式 p(n) 與複雜度 C_p
• 第 9 題｜「任何人的資深者中至少有一位是他的朋友」的正確邏輯式
• 第 10 題｜用生成函數解 a_n = 6a_n−1 − 9a_n−2（a₀ = 1、a₁ = 6），判斷 g(z) 與 a_n 的正確形式（重根 3，a_n = (n+1)3ⁿ）

線性代數考點（11–20）

• 第 11 題｜線性獨立的概念：Ax = b 有唯一解是否蘊含 A 的行獨立、換底矩陣 P 的行是否獨立、線性相依集合的子集是否也相依（假）、A^TA 可逆是否蘊含 A 的行獨立（真）
• 第 12 題｜A 可對角化且有特徵值 λ 時：A⁻¹ 是否有 1/λ（真）、A² 是否有 2λ（假，是 λ²）、A = PDP⁻¹ 中 P、D 是否唯一（假）
• 第 13 題｜W 與 W⊥ 的正交基底：聯集是否為正交集、是否張成 Rⁿ、dim W + dim W⊥ = n、W ∩ W⊥ 是否為空集（應為 {0} 而非 ∅）
• 第 14 題｜譜分解（spectral decomposition）：A 可以是任意方陣嗎（假，須對稱／正規）、m ≤ n、最小特徵值是否非負、所有 λ_i 是否相異、u_i 是否正交歸一
• 第 15 題｜求 2×2 矩陣的 SVD，問哪些值不在 U 或 V 中
• 第 16 題｜給 Gauss-Jordan 法的 pseudo-code，判斷解存放在哪裡、X 應該是什麼（a_kk）
• 第 17 題｜哪些變換不是線性的（含常數平移的、指數的）
• 第 18 題｜求使矩陣不可逆的 k 值
• 第 19 題｜求齊次方程組解空間的基底
• 第 20 題｜給 LU 分解的 pseudo-code，判斷各個空格 a、b、c、d、X 應填什麼

這份考卷的難點

1. 100 分全部逐選項倒扣，是中央十年最嚴的一年。全卷共 100 個選項，每個都要獨立判斷。
2. 第 16、20 題給 pseudo-code 要填空（Gauss-Jordan 與 LU），需要真的理解演算法的索引細節，而不只是會手算。
3. 第 7、8 題連動：先建立遞迴式再解複雜度，前者錯後者必錯。
4. 第 13(D) 的陷阱：W ∩ W⊥ 是 {0}（含零向量的集合）而不是空集合 ∅。

準備建議

• 107 年全卷逐選項倒扣，若 116 年延續，策略必須是「只填確定的選項」
• Gauss-Jordan 與 LU 分解的 pseudo-code（107 第 16、20 題）在中央出現，要能讀懂索引
• 譜分解與 SVD（107 第 14、15 題）是中央線代的進階考點
• 中央很愛把演算法複雜度放進數學考科（106 第 5、8 題，107 第 7、8 題），這是資工類的特色