107 中央資工所考古題詳解｜數學考點分析

題型與配分

全卷 6 頁、20 題、100 分，禁用計算器，作答於答案卷（卡）。

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

離散數學考點（1–10）

• 第 1 題｜驗證兩個複合 propositional logic 等價的方法：p ↔ q 是否為 tautology、是否為矛盾式、truth table 是否只在部分列相同、用等價律由 q 推到 p 或由 p 推到 q
• 第 2 題｜兩個可數無限集合 A、B：2^A 與 2^B 是否不可數、A − B 是否可能為空集、有限、可數無限、不可數
• 第 3 題｜計數公式：函數個數、x₁+x₂+x₃+x₄ = 10 的非負整數解個數、長度 n 且恰有 r 個 1 的位元串個數、10 件物品放入 4 個相同空盒的方法數、橋牌四家各發 13 張牌的方法數
• 第 4 題｜圖的定義：pseudograph 是否允許 self-loop、輪圖的節點數、n-cube Q_n 的邊數、undirected graph 的 degree 總和、n 個節點 simple graph 中長度 n 的路徑
• 第 5 題｜給 Hasse 圖，判斷 poset 是否為 total order、是否遞移、是否反身、{a, c} 的 least upper bound、是否為格
• 第 6 題｜1-1 映射與集合大小、equivalence relation 與分割、induction 與 total order 集、各長度的路徑數相同與圖 isomorphism、證明 f 是 O(g) 時常數的選取
• 第 7 題｜遞迴程序 P：n < 4 時結束，否則呼叫 Q 把長度 m 的 array 切成 4 段（√m 步），對其中 2 段遞迴呼叫 P，再呼叫 R 合併（2√m 步）。問步驟數 p(n) 的 recurrence 與複雜度 C_p
• 第 8 題｜|A| = 3、|B| = 5：A 到 B 的函數個數、1-1 函數個數、onto 函數個數、A × B 上 binary relation 個數、A × B 上 symmetric binary relation 個數
• 第 9 題｜哪些邏輯式與「任何人的資深者中至少有一位是他的朋友」同義，以 S(x,y)（x 是 y 的資深者）、F(x,y)（x 是 y 的朋友）表示
• 第 10 題｜用 generating function 解 a_n = 6a_n−1 − 9a_n−2（a₀ = 1、a₁ = 6），判斷 g(z) 與 a_n 的各選項

線性代數考點（11–20）

• 第 11 題｜linearly independent：Ax = b 有唯一解與 A 的行、換座標矩陣 P 的行、linearly dependent 集合的子集、A diagonalizable、A^TA 可逆
• 第 12 題｜A diagonalizable 且有 eigenvalue λ：A⁻¹、A² 的 eigenvalue、B 有 eigenvalue λ 時 A 與 B 是否 similar、eigenvector basis、A = PDP⁻¹ 中 P 與 D 是否唯一
• 第 13 題｜W 是 Rⁿ 的 subspace，各有一組 orthogonal basis，W⊥ 同樣有：兩組 basis 的聯集是否為 orthogonal set、是否 span Rⁿ、dim W + dim W⊥、x ∈ W ∪ W⊥、W ∩ W⊥
• 第 14 題｜n×n 矩陣 A 的 spectral decomposition A = λ₁u₁u₁^T + … + λ_mu_mu_m^T：A 能否是任意方陣、m 與 n 的關係、最小 eigenvalue 是否 ≥ 0、λ_i 是否相異、u_i 是否 orthonormal
• 第 15 題｜給一個 2×2 矩陣 A，求 SVD A = UΣV^T，問哪些值不在 U 或 V 中
• 第 16 題｜Gauss-Jordan 法的 pseudo-code（外層 k = 1 到 n，內層對 j 與 i 做 row operation），問解存放在哪裡、X 該填什麼
• 第 17 題｜哪些變換不是線性的：繞 x₁ 軸旋轉 π/2、T[x₁,x₂,x₃]^T = [x₁+1, x₂−1, x₃]^T、T[x₁,x₂]^T = [x₁−x₂, x₁]^T、多項式映射 T(ax²+bx+c) = (a+b)x+(b+c)、T[x] = e^x
• 第 18 題｜求使給定矩陣不可逆的 k 值
• 第 19 題｜齊次線性方程組（三式四個未知數）的解空間，問哪些向量構成它的 basis
• 第 20 題｜LU 分解的 pseudo-code，問迴圈上下界 a、b、c、d 與式子中的 X 各該填什麼

作答時要注意的地方

1. 100 分都是逐選項倒扣，全卷共 100 個選項。
2. 第 16、20 題是 pseudo-code 填空。
3. 第 7 題與 108 年第 7 題同一個模板，差別在切成幾段、遞迴幾段。
4. 第 13 題有集合記號的選項（x ∈ W ∪ W⊥、W ∩ W⊥）。

準備方向

• Gauss-Jordan 與 LU 的 pseudo-code 讀解（107 第 16、20 題），110 第 40 題、112 第 15 題也有讀程式的題目。
• spectral decomposition 與 SVD（107 第 14、15 題），111 第 20 題、114 第 8(e) 題也有。
• Hasse 圖與格（107 第 5 題），108、110、114 也有。
• 可數集合與基數（107 第 2 題），106、109、110、115 也有。
• 演算法複雜度放進數學卷（107 第 7 題），106、108、109、110、111、112、114、115 都有。
• generating function 解遞迴（107 第 10 題），108、110 到 115 年也有。