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

題型與配分

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

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

選擇題 1–10，每題 2 分：

• 第 1 題｜A = {a, b, c}、B = P(A)，判斷 ∅ ⊆ B、∅ ∈ B、A ∈ B、A ⊆ B 哪些正確
• 第 2 題｜equivalence relation 下 a 與 b 等價時，aRb、bRa、[a] = [b]、[a] ∩ [b] ≠ ∅ 哪些正確
• 第 3 題｜哪些命題與 p → q 等價
• 第 4 題｜哪個數是 Z₁₃ 的 primitive root，選項 2、3、5、7
• 第 5 題｜哪個是質數，選項 2⁶−1、2⁷−1、2⁸−1、2⁹−1
• 第 6 題｜postfix 式 7 2 3 * - 4 ^ 9 3 / + 的值，^ 代表次方
• 第 7 題｜full m-ary tree，m = 3、n = 100 個頂點，選項涉及邊數、內部頂點數、高度、葉數
• 第 8 題｜哪個集合可數：(0, 1)、Z⁺、{N, Z, Q}、P(N)
• 第 9 題｜哪個條件足以用 induction 證明 P(n) 對所有正整數成立
• 第 10 題｜哪個圖是 planar graph：K₄、Q₃、K₃,₃、W₄

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

• 第 1 題｜任何 simple graph 的 incidence matrix 是否為 symmetric matrix
• 第 2 題｜Q 與 Z 的基數是否相同
• 第 3 題｜100 人中是否至少有 9 人同月出生
• 第 4 題｜S = {1, 2, 4} 時，(P(S), ⊆) 是否為 poset
• 第 5 題｜¬p → q 是否邏輯等價於 ¬(q ↔ p)
• 第 6 題｜4 個可區分的球放入 3 個不同的盒子是否有 81 種放法
• 第 7 題｜traveling salesman problem 是否就是找成本最小的 Euler circuit
• 第 8 題｜小於 100000 且各位數字和為 12 的正整數是否有 1250 個
• 第 9 題｜planar graph coloring 所需的最少顏色數是否不超過 5
• 第 10 題｜簡單 weighted graph 是 connected，是否若且唯若它有 minimum spanning tree

計算題 1–2，每題 5 分：

• 第 1 題｜{1, 2, 3, 4, 5, 6} 的 permutation 中，字典序排在 326541 之後的下一個 permutation
• 第 2 題｜從 5 元素集合到 7 元素集合的一對一函數個數

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

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

• 第 1 題｜B 為方陣時，B − B^T 是否為 skew-symmetric matrix
• 第 2 題｜3×3 矩陣與「第一列加上第二列」後的矩陣，determinant 是否不相等
• 第 3 題｜p₁ = 6 − x² 與 p₂ = 1 + x + 4x² 在 P₂ 中是否 linearly independent
• 第 4 題｜(1, 6, 4)、(2, 4, −1)、(−1, 2, 5) 是否為 R³ 的 basis
• 第 5 題｜R² 旋轉 π/4 的變換 T 是否 rank = 2、nullity = 1
• 第 6 題｜similar matrices 的 determinant 是否相同
• 第 7 題｜給定一個 3×3 矩陣是否 diagonalizable
• 第 8 題｜tr(ABC) 是否等於 tr(ACB)
• 第 9 題｜n×n 矩陣的 eigenvalue 重數總和是否等於 n
• 第 10 題｜給定一個 3×3 symmetric matrix 是否不是 positive definite

選擇題 1–5，每題 4 分：

• 第 1 題｜哪些矩陣是 elementary matrix
• 第 2 題｜哪些矩陣是 A、B、C 三個 2×2 矩陣的 linear combination
• 第 3 題｜哪些矩陣是 Hermitian matrix
• 第 4 題｜2×3 矩陣 A 的 singular values 是哪些，選項 1、√2、√3、√6
• 第 5 題｜T : R² → R² 是 linear transformation，已知 T(1, 2) = (2, 3)、T(1, −1) = (4, −1)，求 T(1, 0) + T(0, −1)

計算題（10%）：

• 把 3×3 矩陣 A 寫成 A = LDU，L 為主對角線全 1 的 lower triangular matrix，U 為 upper triangular matrix，D 為 diagonal matrix

作答時要注意的地方

1. 兩個 PART 各有 10 題是非題，共 40 分落在答錯倒扣 1 分的規則下。
2. PART I 選擇題標明單選或多重選擇，每題要逐選項判斷。
3. PART II 選擇題 4 問的是 singular values，不是 eigenvalue。
4. 禁用計算機，PART I 第 4 題的原根與第 5 題的質數判斷要手算。

準備方向

• PART I 是非題 1–7 與 108 年是非題 1–7 是同一組題目，只有第 1 題的措辭略有不同。
• partial order 與 power set（110 PART I 第 1 題、是非第 4 題），108 是非第 4 題、111 PART I 第 2、7 題也有。
• 與 p → q 等價的命題：110 第 3 題、111 第 3 題、114 第 1 題。
• 哪個 2ⁿ−1 是質數：110 第 5 題、111 第 5 題。
• full m-ary tree 的頂點與邊數關係：110 第 7 題，115 第 4 題也有。
• 可數性判斷：110 第 8 題、111 第 8 題，108 是非第 2 題也有基數比較。
• planar graph 與 coloring：110 第 10 題、是非第 9 題。
• permutation 與函數計數：110 計算題，111 計算題第 4、6 題也有計數。
• LU 與 LDU 分解：109 第 5 題、110 計算題、111 PART II 是非題第 9 題。
• similar matrices、trace 與 determinant 的性質：110 PART II 是非題 2、6、8、9。
• Singular values 與 Hermitian matrix：110 PART II 選擇題 3、4 題。