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

題型與配分

全卷 6 頁、20 題、100 分，作答於答案卡。

單選第 14–20 題的答案都是一個數值取絕對值、四捨五入後再 mod 5。

離散數學考點（1–10）

第 1–4 題共用同一個 6×6 的 0/1 矩陣 A，A 描述 binary relation R。

• 第 1 題（5%）｜R 是否 reflexive、anti-symmetric、transitive、partial order 關係，以及 R 的 symmetric closure 是否 transitive
• 第 2 題（5%）｜三種 closure 各要補幾個 1（reflexive 補 4 個、symmetric 補 6 個、transitive 補 3 個是否成立），reflexive closure 是否為 partial order、symmetric closure 是否為 equivalence relation
• 第 3 題（5%）｜R 的 directed graph G：是否 weakly connected、最長 simple path 的長度是否為 4、reflexive＋symmetric＋transitive closure 是否有 2 個 connected component、transitive closure 是否有 Hamilton path、R^∞ 是否 strongly connected
• 第 4 題（5%）｜令 S 為 R 的 symmetric＋reflexive closure，每個元素視為命題，S 反映哪些布林運算子的行為（∧、∨、¬、→、↔）
• 第 5 題（5%）｜哪些是「充分但不必要」的條件：圖 isomorphism 與兩圖都有 Euler circuit、「g 是 O(n) 但不是 Θ(n)」與「g 是 o(2ⁿ)」、集合上存在 equivalence relation 與可依它分割、P 上存在 well-ordering 與可用 induction 證明、「P 為假」與「P → Q 為真」
• 第 6 題（5%）｜n 個節點的 undirected graph，直接相連就有一條邊，D(a) 為節點 a 的 degree：connected 時是否必有長度 n 的 simple path、ΣD(i) 是否為偶數、connected 時 ΣD(i) 的下界、是否必有兩個節點 degree 相同、connected 時「直接相連」關係的 transitive reflexive closure 是否構成 complete graph
• 第 7 題（5%）｜遞迴程序 P：先呼叫 B（Θ(√m)），再依 i mod 9 = 0、3、6 把元素分進 array2、array3、array4，對三個 subarray 各遞迴一次。問描述複雜度的 recurrence
• 第 8 題（5%）｜承第 7 題，問程序 P 的時間複雜度等級，選項有 O(n log n)、O(n^1.5)、O(√n log n) 等
• 第 9 題（5%）｜字母表 {a₁,…,a₈} 組成字串，合法字串不得在任何位置出現指定的連續字母組合，P_n 為長度 n 的合法字串數，問 recurrence relation 與初始值
• 第 10 題（5%）｜承第 9 題，用 generating function g(z) 解 P_n，判斷各選項

線性代數考點（11–20）

多選（11–13）

• 第 11 題（5%）｜symmetric matrix：eigenvalue 重複時是否仍有完整的 orthonormal eigenvector 組、A + B 與 AB 是否 symmetric、rank 為 r 時零 eigenvalue 的個數、eigenvalue 是否為實數
• 第 12 題（5%）｜A 為 m×n（m < n）：nullity 與 rank 的和、rank = m 時 AA^T 是否可逆、獨立行數與獨立列數是否相同、Gaussian elimination 後零列數
• 第 13 題（5%）｜eigenvalue 判斷：8 個正 pivot 與 eigenvalue 的符號、AB = BA 且都 diagonalizable 時 A 與 B 的 eigenvalue、similar matrices 的 eigenvalue、AA^T 與 A^TA 的 eigenvalue

單選（14–20）

• 第 14 題（5%）｜給一個 4×4 矩陣，求 inverse A⁻¹，所有元素之和為 b，|b| 四捨五入為 c，求 mod(c, 5)
• 第 15 題（5%）｜讀 Matlab 程式：a = 11，A 是 11×11 的全 1 矩陣，主對角線改成 0.9，d = det(A)，c = abs(d × 10^a + 7)，輸出 mod(c, 5)
• 第 16 題（5%）｜linear operator A 的 transformation matrix 已知，求 A 相對於 basis [1,1,0]^T、[0,1,1]^T、[1,2,2]^T 的矩陣 B，所有元素之和取絕對值四捨五入為 b，求 mod(b, 5)
• 第 17 題（5%）｜R⁴ 中 v₁ = [1,1,1,1]^T、v₂ = [1,1,2,4]^T、v₃ = [1,2,−4,−3]^T，依序 Gram-Schmidt 得 u₁ = [1,1,1,1]^T、u₂ = [−1,a,b,c]^T、u₃ = [1,d,e,f]^T，求 mod(|a+b+c+d+e+f|, 5)
• 第 18 題（5%）｜A = [[0,0,−2],[1,2,1],[1,0,3]]，B = A¹²，B 的所有元素之和為 b，求 mod(|b|, 5)
• 第 19 題（5%）｜Ax = b 的 least squares 解，A 為 4×3，b = [4,−1,0,1]^T，c 為解 x 各元素之和四捨五入的整數，求 mod(|c|, 5)
• 第 20 題（5%）｜把 A = [[1,−1,2],[−1,1,2],[2,2,2]] orthogonal diagonalization P^TAP = D，b 為 P 第一列三個元素的乘積，d 為 D 主對角線三個元素的乘積，c 為 |b × d × 6| 四捨五入的整數，求 mod(c, 5)

作答時要注意的地方

1. 第 1–4 題共 20 分綁在同一個 relation matrix 上。
2. 單選第 14–20 題答錯倒扣 2 分，扣至單選題 0 分為止。
3. 第 7、8 題的 pseudo-code 含迴圈本身與呼叫 B 兩部分的步數。
4. 多選題扣至多選題 0 分為止，兩個大題各自獨立。

準備方向

• relation matrix 與三種 closure（112 第 1–4 題），106、109、114 也有。
• 把關係對應到布林運算子（112 第 4 題），114 第 12 題改成集合運算子。
• pseudo-code 的 recurrence 與複雜度（112 第 7、8 題），114 第 14 題用同一個模板。
• 計數遞迴與 generating function（112 第 9、10 題），107、110、111、113、114、115 也有 generating function 解遞迴。
• symmetric matrix、similar matrices 與 eigenvalue 的性質判斷（112 第 11、13 題）。
• 單選計算題：inverse、determinant、change of basis、Gram-Schmidt、矩陣高次冪、least squares、orthogonal diagonalization（112 第 14–20 題），113 到 115 年的單選也是同類。