110 台大資工所考古題詳解｜數學考點分析

題型與配分

全卷 2 頁、10 題、100 分，每題 10 分。

作答方式：「Please draw a following table on the first page of the answer sheets and fill in the answers accordingly.」

離散數學考點（1–4）

• 第 1 題（10%）｜填空：一個圖是 bipartite graph 若且唯若它沒有 _____ 長度的 cycle；bipartite graph 可以用 _____ 種顏色 coloring
• 第 2 題（10%）｜recurrence a_n = 3·a_n/2 + 1（a₁ = 1），求 log₂a_n ~ ___ × log₂n
• 第 3 題（10%）｜binomial 隨機漫步從原點出發，恰在 2n 步後第一次回到原點的走法數
• 第 4 題（10%）｜binomial coefficient 恆等式 Σ C(...) = C(A, B) 中的 A 與 B

群論考點（5）

• 第 5 題（10%）｜(G, ∘) 為 finite group、H 為其 subgroup，證明 |H| 整除 |G|

線性代數考點（6–10）

• 第 6 題（10%）｜(a) 5% W 的 dimension 為 8、U 與 V 是相異的六維 subspace，求 dim(U ∩ V)　(b) 5% V 為 2×2 symmetric matrix 空間，T : V → P₂(R) 為 linear transformation，求 rank(T)
• 第 7 題（10%）｜已知 nonsingular 矩陣 A 的 minimal polynomial m(t) = t^r + a_r−1t^r−1 + … + a₁t + a₀，求 A⁻¹
• 第 8 題（10%）｜解 det(...) = 0 求 t，矩陣是四對角形式
• 第 9 題（10%，全部正確才給分）｜五個敘述：A 可逆、B³ = 0 且 AB = BA 時 A+B 是否可逆、恰有 N 個非零元素的序列集合是否為 subspace、任意方陣能否分解成 symmetric 加 skew-symmetric、similar matrices 是否有相同 eigenvector、rank(A−B) 與 rank(A)−rank(B) 的不等式方向
• 第 10 題（10%，全部正確才給分）｜五個敘述：differential operator 在 {sin t, cos t} 上的 eigenvalue、F(x,y,z) = (x+1, y+2) 是否線性、兩相異 eigenvalue 且 dim(E_λ1) = n−1 時是否 diagonalizable、determinant 的加法分解性質、T diagonalizable 時 T^m 是否同時 diagonalizable

作答時要注意的地方

1. 第 5 題是證明題，要寫出完整論證。
2. 第 9、10 題合計 20 分，全部正確才給分。
3. 第 3 題問的是第一次回到原點的走法數。

準備方向

• group、subgroup、coset、order 這些 group theory 基礎，110 年考過一次。
• 用 minimal polynomial 或 Cayley-Hamilton 求 inverse，在 107、110、111 都出現。
• Catalan number 的幾種場景：首次回原點、合法括號、binary tree 個數。
• 線代的敘述判斷題在 107、108、110、111、112 都有，把 similar matrices、diagonalizable、determinant 的常見命題整理成表。