114 師大資工所考古題詳解｜數學考點分析

題型與配分

全卷 2 頁、9 大題、100 分，卷面沒寫倒扣。卷面注意事項是「請依序在答案卷上作答，並標明題號，不必抄題」與「答案必須寫在指定作答區內，否則依規定扣分」。卷首有 Some notations，定義 column vector、B-coordinate vector [v]_B 與 dim W。

第 6–9 題前面的說明是「simply put the answers on the answer sheet. No explanations are needed」，並說明 N 與 Z 分別表示正整數集與整數集。

線性代數考點（1–5，50%）

• 第 1 題（9%）｜A 是 m×n 矩陣，reduced row echelon form 為 R，r_i = Re_i 表示 R 的第 i 行，求下列矩陣的 reduced row echelon form
• 第 1(a) 題（3%）｜[A 0]，其中 0 是零行
• 第 1(b) 題（3%）｜[a₁ a₂ … a_k]，k < n，其中 a_i = Ae_i
• 第 1(c) 題（3%）｜[A cA]，其中 c 是任意純量
• 第 2 題（9%）｜A 是 4×4 矩陣，沒有非實 eigenvalue，恰好有兩個實 eigenvalue 5 與 −9，W₁、W₂ 分別是對應 5 與 −9 的 eigenspace，寫出符合下列資訊的所有可能的 characteristic polynomial
• 第 2(a) 題（4%）｜dim W₁ = 3
• 第 2(b) 題（5%）｜dim W₂ = 2
• 第 3 題（10%）｜A = {u₁, …, u_n} 是 Rⁿ 的 basis，B = {v₁, …, v_n} 也是 basis，其中 v_i = u_i + u_i+1 + … + u_n（i = 1, …, n），已知 [v]_A = (a₁, …, a_n)^T，求 [v]_B
• 第 4 題（12%）｜u = (4, 1, 3, −1)^T，W 是 R⁴ 中矩陣 [[2, −2, 3, 4], [1, −1, 1, 1]] 的 row space
• 第 4(a) 題（8%）｜求 W 的 orthogonal projection 矩陣 P_W
• 第 4(b) 題（4%）｜求 W 中離 u 最近的唯一向量 w
• 第 5 題（10%）｜求 3×3 矩陣 A，eigenvalue 為 −2、−2、4，對應的 eigenvector 為 (1/√2)(1, −1, 0)^T、(1/√6)(1, 1, −2)^T、(1/√3)(1, 1, 1)^T

離散數學考點（6–9，50%）

• 第 6 題（5%）｜undirected graph G 有 n 個頂點、m 條邊，每個頂點的 degree 都是 3，求 n/m
• 第 7 題（15%）｜degree sequence 是頂點 degree 由大到小（nonincreasing）排成的序列。G 是有 5 個頂點的 connected simple undirected graph，且頂點的 degree 恰好有三種不同的值，列出所有可能的 degree sequence
• 第 8 題（10%）｜x ∈ N、y ∈ Z，求使 314x + 159y = 26 成立的第二小的 x
• 第 9 題（20%）｜對 n ∈ N ∪ {0}，a_n 是 n 個元素的集合上既 symmetric 又 reflexive 的 binary relation 個數，b_n 是 symmetric 但不是 reflexive 的 binary relation 個數，a₀ = 1、b₀ = 0
• 第 9(a) 題（5%）｜求 a₁ 與 b₁
• 第 9(b) 題（10%）｜f : N → N、g : N → N 是兩個函數，使得 n > 0 時 b_n = f(n)·b_n−1 + g(n)·a_n−1，求 f(n) 與 g(n)
• 第 9(c) 題（5%）｜求 b_n 的 closed form，closed form 可用的運算是四則運算、次方、階乘與 binomial coefficient

作答時要注意的地方

1. 第 1–5 題是申論題，第 6–9 題只要寫答案，卷面註明不必解釋。
2. 第 2 題兩小題問的是不同的 eigenspace：(a) 是 W₁（eigenvalue 5），(b) 是 W₂（eigenvalue −9）。
3. 第 3 題的 v_i 是 u_i 加到 u_n。
4. 第 5 題給的三個 eigenvector 已經是單位向量。
5. 第 7 題問的是所有可能的 degree sequence，圖要是 connected simple graph。
6. 第 8 題要求第二小的 x。
7. 第 9 題 (b) 的 recurrence 形式由題目給定，(c) 要用 closed form 的允許運算作答。

準備方向

• RREF、rank 與四大 subspace：114 第 1 題；106 第 1、2 題、107 第 1 題、108 第 1 題、109 第 2 題、110 第 2 題、111 第 6 題、112 第 1 題、113 第 1 題、115 第 1(a) 題也有。
• eigenvalue、diagonalization 與 eigenspace：114 第 2、5 題；106 第 4 題、107 第 3、5 題、108 第 3 題、109 第 3、5 題、111 第 9 題、112 第 4 題、113 第 2(b)、4 題、115 第 1(b) 題也有。
• basis、座標與 B-矩陣：114 第 3 題；106 第 3 題、108 第 2 題、111 第 8 題、112 第 3 題也有。
• orthogonal projection、reflection 與最近向量：114 第 4 題；108 第 4 題、109 第 4 題、110 第 3、4 題、111 第 10 題、112 第 5 題、113 第 3 題、115 第 3 題也有。
• 圖論：114 第 6、7 題；106 第 7(4) 題、107 第 6(d) 題、108 第 6(4)、8(4) 題、109 第 9(1) 題、110 第 8(2) 題、111 第 5 題、112 第 9 題、113 第 5 題、115 第 5、6 題也有。
• congruence 與數論：114 第 8 題；106 第 7(2)(3)、10 題、107 第 10 題、108 第 8(1)、12(1) 題、109 第 10 題、111 第 4(2) 題、112 第 7 題、113 第 7 題、115 第 7 題也有。
• recurrence 與遞迴定義：114 第 9(b) 題；107 第 8(a) 題、109 第 7 題、110 第 7 題、111 第 1 題也有。
• 計數（permutation、binomial、pigeonhole principle、關係計數）：114 第 9 題；106 第 8 題、107 第 8(b)、9(a) 題、108 第 6(1)(2)、8(2) 題、110 第 9(1) 題、111 第 2 題、112 第 10 題也有。
• 關係與函數：114 第 9 題；106 第 9(2)、12 題、107 第 6(b)、9(b)(c)(d) 題、108 第 6(3)、8(3) 題、109 第 9(2) 題、110 第 8(1) 題、111 第 3 題、112 第 6、8 題也有。