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

題型與配分

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

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

第 01 題計算，每題 4 分：

• (i)｜十進位 899 的十六進位與二進位表示
• (ii)｜complete graph K₄ 與 hypercube Q₃ coloring 所需的最少顏色數
• (iii)｜K₄ 中任兩個頂點之間長度為 4 的 path 數
• (iv)｜52 張撲克牌四種花色各 13 張，不看牌隨機抽，要抽幾張才能保證有同花色的 4 張，以及要抽幾張才能保證有 4 張紅心；題幹第一問的英文有缺字
• (v)｜tri-ary tree（每個節點有 3 個子節點或沒有子節點），高度為 4 時節點數的最小值與最大值

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

• (a)｜p 為質數、a 不被 p 整除時，a^p−1 ≡ 1 (mod p)
• (b)｜f(n) = 10n² log n + 3n² + 100 是否為 O(n³)
• (c)｜有理數 Q 與整數 Z 的基數是否相同
• (d)｜完全二部圖 K₅,₃ 的 edge connectivity 是否為 5
• (e)｜¬(∃x f(x)) 是否邏輯等價於 ∃x ¬f(x)
• (f)｜planar graph coloring 所需的最少顏色數是否不超過 5
• (g)｜整數上的關係 (a, b) ∈ R 若且唯若 a ≡ b (mod 99)，R 是否為 equivalence relation
• (h)｜simple graph 中每個頂點的 degree 都是偶數時，是否必有 Hamilton circuit

第 03 題，L(x, y) 表示「x loves y」，x 與 y 的 domain of discourse 都是全世界的人，用 quantifier 寫出：

• a（6 分）｜Somebody loves everybody
• b（8 分）｜There are exactly two persons who love Trump

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

• 第 1 題（25%）｜A、B 為方陣且 AB = I，五個敘述各判斷真假（1 分），真的要證明、假的要給反例（4 分）：(a) 0 不是 B 的 eigenvalue；(b) A diagonalizable；(c) (A − B)x = 0 只有零解；(d) A 與 B row equivalent；(e) A^TB^T = I
• 第 2 題（10%）｜u₁ = (3, 2, 1)、u₂ = (2, 3, 0)、U = Span{u₁, u₂}：(a) 5% 求 U 的 orthogonal complement；(b) 5% 求 (1, 1, −1) 在 U 上的 orthogonal projection
• 第 3 題（10%）｜T(x) = Ax，A 是 rank 3 的 5×4 矩陣：(a) 5% 求 T 的 domain、kernel、值域的 dimension；(b) 5% 舉出一個這樣的 A 並說明理由
• 第 4 題（5%）｜用 least squares 求 y = ax² + b 最符合三個資料點 (−1, 1)、(0, 1)、(1, 2) 的式子

作答時要注意的地方

1. 離散是非題答錯倒扣 1 分，八題共 16 分；線代第 1 題卷面沒有寫倒扣，但每小題判斷只佔 1 分，證明或反例佔 4 分。
2. 01(iii) 問的是 path，題目沒有另外說明頂點能不能重複。
3. 01(iv) 一題問兩件事，兩問的「保證」對象不同（同花色 4 張、4 張紅心）。
4. 01(v) 沒有說明高度從 0 還是從 1 起算。
5. 第 4 題要配的式子是 y = ax² + b。

準備方向

• 是非 02(c) 的 Q 與 Z 基數，108、110 是非第 2 題也考同一件事。
• 是非 02(f) planar graph coloring 的最少顏色數，110 PART I 是非第 9 題是同一個敘述；01(ii) 的 Q₃ 也出現在 107 是非 (h)，K₄ 與 Q₃ 都是 110 PART I 選擇第 10 題的 planar graph 選項。
• quantifier 翻譯：106 第 03 題、108 填空 ④⑤。
• 樹的高度與節點數範圍：106 01(v) 是 tri-ary tree，107 1(v) 是 binary tree，110 第 7 題、115 第 4 題考 full m-ary tree。
• pigeonhole principle：106 01(iv)、107 是非 (g)、108 是非第 3 題。
• congruence 與模運算：106 是非 (a)、107 1(i)、109 第 7 題。
• 圖的 connectivity：106 是非 (d) 考 edge connectivity，107 是非 (j) 考 vertex cut。
• orthogonal complement 與 orthogonal projection：106 第 2 題與 107 第 4 題題型相同（R³ 中兩個向量 span 的 U），112 第 6 題、113 第 15 題、114 第 12 題也考 projection。
• least squares：106 第 4 題、107 第 2 題、111 計算題、114 第 13 題。
• 線代「判斷真假並證明或給反例」：106 第 1 題與 107 第 1 題同一種格式，配分也相同。