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

題型與配分

全卷 5 頁、20 題、100 分。

離散數學考點（1–10）

• 第 1 題｜Q(x,y) 為「x + y = y」，判斷 ∃x∃y、∀x∃y、∃y∀x、∀y∃x、∀x∀y 五種 quantifier 組合的真假
• 第 2 題｜75 小時內每小時至少比一場、總共不超過 125 場，判斷是否存在一段連續時間恰好比了 2、23、24、25 場
• 第 3 題｜RSA 公鑰系統：正確性的依據、兩個大質數與公私鑰的關係、(M^e)^d = (M^d)^e = M、以數位簽章證明身分的流程
• 第 4 題｜connected planar simple graph G：Euler's formula r = e + v − 2、e ≤ 3v − 6、是否有 degree 不超過 5 的頂點、含與 K₃,₃ 或 K₅ homeomorphic 的 subgraph 是否為非 planar graph
• 第 5 題｜滿 m 元樹：由頂點數 n、內部節點數 i、葉數 l 互相表示的五個關係式
• 第 6 題｜|A| = 8、|B| = 3，f : A → B 的函數個數、1-1 個數、onto 個數、反函數個數、bijection 個數
• 第 7 題｜predicate P(i,j) 滿足 reflexive、antisymmetric、transitive、totality，且恰有一個最小元素，問它描述的是 equivalence relation、partial order、total order、格還是 well-ordering
• 第 8 題｜遞迴程序 R(A, k)：n < k 時結束，否則花 √n 步把 array 切成 k 等份、對每份遞迴、再花 k 步合併、最後呼叫 Q。X 取 k = 2、Q 為 Θ(m)，Y 取 k = 4、Q 為 Θ(√m)，Z 取 k = 9、Q 為 Θ(m)。比較三者的複雜度，並判斷 X 是否為 Θ(n log n)
• 第 9 題｜binomial coefficient 恆等式：symmetry、交錯和、Vandermonde convolution、累加型求和
• 第 10 題｜用 generating function 解 (a_n−1 − a_n−2) = 2(a_n − a_n−1)（a₀ = 5、a₁ = 9），判斷 f(z) 與 a_n 的各選項

線性代數考點（11–20）

多選 11–12

• 第 11 題（5%）｜A² 為 diagonal matrix、有完整的 orthonormal eigenvector 組、AAᴴ = AᴴA、rank r < n 時零 eigenvalue 的個數、一個 eigenvalue 對應的 eigenvector 個數
• 第 12 題（5%）｜197×197 的有限差分矩陣（主對角線 2、上下副對角線 −1）：determinant D 的 mod 運算、拆成 symmetric 加 skew-symmetric、A = BCB^T（B 為 orthogonal 或 lower triangular、C 為 diagonal）、最小 eigenvalue 的正負

單選 13–15

• 第 13 題（5%）｜給 A⁵ = [[32, 100000], [0, 3125]]，A 的 determinant 為 M，四個元素的和四捨五入為 N，求 mod(M + 13N, 5)
• 第 14 題（5%）｜先解含參數 k 的三元線性系統（k = a 時有多組解、k = b 時無解），c = |a − b|，M = mod(c, 5)。再對一個 4 式 3 個未知數的方程組求 least squares 解，N 為 ỹ × 50 的最接近整數，求 mod(M + N, 5)
• 第 15 題（5%）｜5×5 矩陣 A 的 determinant 為 M，4×4 矩陣 B 的 determinant 為 N，K = |M/N| × 1/10000，問 K 落在哪個區間

多選 16–20

• 第 16 題（5%）｜A 與 B similar：det、eigenvector、A² 與 B²、AB 與 BA，以及 A² 與 B² similar 時 A 與 B 是否 similar
• 第 17 題（5%）｜n×n 實方陣的 eigenvalue：是否可能為複數、eigenvalue 為 0 與可逆性、eigenvalue 重複與 diagonalizable、A = A^T 時 eigenvalue 是否為正、P 與 D 是否唯一
• 第 18 題（5%）｜A 為 m×n 且可 QR 分解，W 是 A 所有行的集合，W⊥ 是其 orthogonal complement：W、W⊥ 是否為 subspace、(W⊥)⊥、W ∩ W⊥、m ≥ n
• 第 19 題（5%）｜哪些術語與 least squares 問題無關：inconsistent system、eigenvector、diagonalizable、orthogonal projection、Gram-Schmidt
• 第 20 題（5%）｜對一個 2×2 矩陣做 spectral decomposition，問哪些值不在解矩陣中

作答時要注意的地方

1. 線代多選題號是 11–12 與 16–20，中間的 13–15 是單選。三段各有各的倒扣池。
2. 第 13–15 題答錯倒扣 2 分，扣到所有單選題 0 分為止。
3. 第 19 題問的是「無關」的術語。
4. 第 8 題的 X、Y、Z 三個演算法由同一個遞迴程序衍生。

準備方向

• quantifier 組合的真假（111 第 1 題），106、107、110、115 也有邏輯題。
• RSA（111 第 3 題），110 第 3 題也有。
• planar graph（111 第 4 題），110、113、114、115 也有。
• 函數計數（111 第 6 題），107 第 8 題、113 第 17 題也有。
• 把演算法複雜度放進數學卷（111 第 8 題），106、107、108、109、110、112、114、115 都有。
• generating function 解遞迴（111 第 10 題）。
• similar matrices（111 第 16 題）與 diagonalizable（111 第 17 題）。
• QR 分解與 orthogonal complement（111 第 18 題），107 第 13 題也有 W⊥。
• least squares（111 第 14、19 題）與 spectral decomposition（111 第 20 題）。