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

題型與配分

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

離散數學考點（1–10，單選）

• 第 1 題｜五個句子中哪一個是命題
• 第 2 題｜關於 bijection 函數哪一個敘述不正確，選項涉及 injection 與反函數、嚴格遞增函數、恆等函數、有限與無限集合的同大小定義
• 第 3 題｜兩個任意不可數集合 A、B 的差集 A − B 是有限、可數無限、不可數，或三者皆有可能
• 第 4 題｜{1,2,3,4,5,6} 的 4-combination 中，{1,2,5,6} 的下一個是哪一個
• 第 5 題｜用 divide and conquer 的快速乘法計算兩個 2n 位數的乘積，問時間複雜度
• 第 6 題｜給 4 個元素上 binary relation R 的 0/1 矩陣，判斷 reflexive closure 是否為 equivalence relation、symmetric closure 矩陣中 1 的個數、directed graph 是否 connected、有沒有 strongly connected component
• 第 7 題｜給 predicate D(x,y)（y 是 x 的倍數）與 E(x)（x 是偶數）及一個邏輯式，問哪個中文敘述是正確的解讀
• 第 8 題｜merge sort 在兩半各自排序後合併，合併步驟對大小 m 的輸入要 Θ(m√m) 步，問整體時間複雜度
• 第 9 題｜節點數大於 3 時哪個圖論敘述不正確，選項涉及 complete graph 的 Hamilton circuit、complete bipartite graph 的邊數與節點數、strongly connected directed graph 的 cycle、n 維 hypercube 任兩點間長度 n 的路徑、connected undirected graph 的樹 subgraph
• 第 10 題｜關於形式化證明哪個敘述正確，選項涉及 poset 與 induction、diagonal argument、兩集合互為子集、同 degree 節點個數與圖 isomorphism、halting problem

線性代數考點（11–20，多重選擇）

• 第 11 題｜哪些向量構成矩陣 A 的 column space 的 basis
• 第 12 題｜五組 P₃(R) 的多項式，哪一組的第一個多項式可表示為另外兩個的 linear combination
• 第 13 題｜五個線性方程組哪些有解
• 第 14 題｜determinant 的性質：交換兩列或兩行、某列乘純量、某列加另一列的倍數、upper triangular matrix 的 determinant、inverse 的 determinant
• 第 15 題｜給四個 linear transformation T : Rⁿ → R^m，選出矩陣表示 [T] 正確的選項
• 第 16 題｜A 可逆且 diagonalizable 時，A 與 A^T 的 eigenvalue 與 eigenvector、A^T 與 A⁻¹ 是否 diagonalizable
• 第 17 題｜n×n 實矩陣：eigenvalue 個數、eigenvector 個數、eigenspace 個數、各 eigenspace basis 的 linear independence、複 eigenvalue 與複 eigenvector
• 第 18 題｜A 有 QR 分解時：A 是否有 linearly independent 的 eigenvector、Q 的行與 Col A 的關係、Q^TQ、R 的形狀與可逆性
• 第 19 題｜Ax = b 不一致且有 least squares 解時：解的公式、唯一性、A^TA 不可逆的情形、Ax̂ 與 Col A 的關係、殘差與 A 的列的 orthogonality
• 第 20 題｜covariance matrix 的 symmetry、eigenvalue 是否為實數、有沒有負 eigenvalue

作答時要注意的地方

1. 第 11–20 題每個選項單獨計分，答錯扣 1 分，不答 0 分。
2. 第 5、8 題的選項是時間複雜度的階。
3. 第 6 題的矩陣是 4×4，題目要檢驗的是 reflexive closure 與 symmetric closure。

準備方向

• relation matrix 與 closure（106 第 6 題），109、112、114 也有 relation matrix。
• 把演算法複雜度放進數學卷（106 第 5、8 題），107、108、109、110、111、112、114、115 都有。
• 基數與可數性（106 第 3 題），107、109、110、115 也有。
• QR 分解與 Gram-Schmidt（106 第 18 題）。
• least squares 解（106 第 19 題），111、112、113、115 也有。