107 中興資工所考古題詳解｜數學考點分析

題型與配分

全卷 2 頁、100 分，不得使用計算機。離散與線代各 50 分。

Part I 離散數學考點（50%）

第 1 題，每小題 6 分：

• (i)｜3²⁰⁰³ mod 99
• (ii)｜每個頂點 degree 都是 4 的 regular graph 有 20 條邊，求頂點數
• (iii)｜x₁ + x₂ + x₃ + x₄ = 10 的解數，分別在 x_i ∈ Z⁺ 與 x_i ∈ N = {0, 1, 2, …} 兩種條件下
• (iv)｜a_n = 2a_n−1 + f(n)、a₁ = 1，分別求 f(n) = 1 與 f(n) = n 的一般解
• (v)｜binary tree（每個節點至多 2 個子節點）高度為 4 時，節點數的範圍

第 2 題是非題，每題 2 分，答錯倒扣 1 分：

• (a)｜{1, 2, 3, 12, 18, 36} 在整除關係下不是 poset
• (b)｜相鄰矩陣能否表示有向 pseudograph
• (c)｜P → Q ≡ ¬P ∨ Q
• (d)｜P 為假、Q 為真時，P → Q 為真
• (e)｜antisymmetric 的關係一定也是 symmetric 的
• (f)｜{1, 2, 3, 4} 上的 R = {(1,1), (1,2), (2,1), (2,2)} 是否為自反關係
• (g)｜從 {1, 2, 3, 4, 5, 6} 至少要選 5 個數，才能保證有一對相加為 7
• (h)｜hypercube Q₃ 是 planar graph
• (i)｜m 為正整數、a 與 b 為整數時，(a + b) mod m = (a mod m) + (b mod m)
• (j)｜n > 2 時，complete graph K_n 有一個 n − 1 個頂點的 vertex cut

Part II 線性代數考點（50%）

• 第 1 題（25%）｜A 是 rank r 的 m×n 矩陣，Ax = (1, 0, 0)^T 無解、Ax = (1, 1, 0)^T 恰有一解。五個敘述各判斷真假（1 分），真的要簡述理由、假的要給反例或說明（4 分）：(a) n = r；(b) det(A^TA) = det(AA^T)；(c) A^TA 可逆；(d) AA^T positive definite；(e) 對每個 c ∈ R³，A^Ty = c 至少有一解
• 第 2 題（6%）｜求最接近 (−2, 0)、(−1, 0)、(0, 1)、(1, 1)、(2, 1) 五點的直線 y = cx + d
• 第 3 題（9%）｜A = [[0, 0, −2], [1, 2, 1], [1, 0, 3]]：(a) 3% 求 eigenvalue；(b) 6% A 是否 diagonalizable，要說明理由
• 第 4 題（10%）｜u₁ = (3, 1, −1)、u₂ = (1, −2, 1)、U = span{u₁, u₂}：(a) 5% 求 U 的 orthogonal complement；(b) 5% 求 U 中最接近 (2, 2, 8) 的點

作答時要注意的地方

1. 離散是非題答對 +2、答錯 −1，十題共 20 分；線代第 1 題卷面沒有寫倒扣，判斷只佔 1 分，理由或反例佔 4 分。
2. 1(iii) 一題兩問，Z⁺ 與 N 兩種範圍各算一次。
3. 1(iv) 要分別處理 f(n) = 1 與 f(n) = n 兩種情形。
4. 1(v) 沒有說明高度從 0 還是從 1 起算。
5. 線代第 1 題沒有給 m、n、r 的數值，給的是兩個方程組的解的情形。(e) 卷面寫的是 c ∈ R³。
6. 第 3(b) 要說明理由，不能只寫可或不可。

準備方向

• recurrence：107 1(iv) 的 f(n) = 1 與 108 填空 ⑥、111 計算第 2 題的 Tower of Hanoi recurrence 同型。
• 非負整數解與正整數解：107 1(iii)，108 填空 ③、113 第 5 題、115 第 1 題也有。
• 樹的高度與節點數範圍：107 1(v) 是 binary tree，106 01(v) 是 tri-ary tree。
• partial order 與關係的性質：107 是非 (a)(e)(f)，108、110 是非第 4 題、110 第 2 題、111 第 2 題也有。
• pigeonhole principle：107 是非 (g)、106 01(iv)、108 是非第 3 題。
• planar graph：107 是非 (h) 的 Q₃，110 PART I 選擇第 10 題也把 Q₃ 列為選項，106 01(ii) 考 Q₃ 的 coloring。
• 圖的 connectivity：107 是非 (j)、106 是非 (d)。
• 模運算：107 1(i) 與是非 (i)，106 是非 (a)、109 第 7 題、111 第 4、9 題也有。
• orthogonal complement 與最近點：107 第 4 題與 106 第 2 題題型相同，112 第 6 題、113 第 15 題、114 第 12 題也考 projection。
• least squares：107 第 2 題、106 第 4 題、111 計算題、114 第 13 題。
• eigenvalue 與 diagonalization：107 第 3 題，108 第 2(c) 題也要求 diagonalization。