113 中正資工所數學考點分析

題型與配分

系所組別「資訊工程學系－甲組、乙組」，科目名稱：數學，第 1 節考，本科目共 2 頁、9 大題、100 分。

第 1–4 題每題都註明「Note that there may be multiple answers to this question」——是複選題而非單選，但仍寫在答案卷上、沒有倒扣。

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

• 第 1 題（10%，複選）｜純量三重積與外積：u·(v×w) = −4
• (a) v·(u×w) = −4（假，交換兩個向量會變號，應為 +4）
• (b) v·(w×w) = 0（真，w×w = 0）
• (c) u×(v×w) 是否落在 v 與 w 決定的平面上（真，BAC-CAB 公式）
• (d) (u×v)×w 是否落在 u 與 v 決定的平面上（真）
• (e) (u×v)×w 與 u×(v×w) 是否相同（假，外積不滿足結合律）
• 第 2 題（10%，複選）｜哪些是 R³ 的子空間：(a,0,0)（是）、(a,1,0)（否，不含零向量）、(a,b,c) 且 b = a+c（是）、(a,b,c) 且 c = a−b（是）、(a,−a,0)（是）。判準是「含零向量、對加法與純量乘法封閉」
• 第 3 題（10%，單選）｜外積矩陣的秩：u = (1,3,5,7,9)^T、v = (11,13,15,17,19)^T，求 rank(uv^T)。任兩個非零向量的外積矩陣秩恆為 1 → 答案 (a) 1
• 第 4 題（10%，複選）｜下三角矩陣的高次冪特徵值：A 為下三角，對角線是 2、−1、0.5、0，所以 A 的特徵值就是這四個數。A⁷ 的特徵值 = 2⁷ = 128、(−1)⁷ = −1、0.5⁷ = 1/128、0⁷ = 0 → 正解是 (b) −1 與 (e) 128
• 第 5 題（10%）｜用給定內積畫出 R² 的單位圓：內積被一個權重矩陣改寫，單位圓 ⟨v,v⟩ = 1 會變成橢圓。要能把 ⟨v,v⟩ = 1 展開成二次式再判斷圖形

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

• 第 6 題（10%）｜述詞邏輯翻譯（x 的論域是所有人、y 是所有電影）：用 S(x,y)「x 看過 y」、L(x,y)「x 喜歡 y」、A(y)「y 得獎」、C(y)「y 是喜劇」寫出五句話，每句 2 分
• (a) 沒有喜劇得獎 → ∀y(C(y) → ¬A(y))
• (b) Lois 看了《北非諜影》但不喜歡 → S(Lois, Casablanca) ∧ ¬L(Lois, Casablanca)
• (c) 有些人看過每一部喜劇 → ∃x∀y(C(y) → S(x,y))
• (d) 沒有人喜歡他看過的每一部電影 → ¬∃x∀y(S(x,y) → L(x,y))
• (e) Ben 從沒看過得獎電影 → ∀y(A(y) → ¬S(Ben, y))
• 第 7 題（10%）｜T 型骨牌鋪滿棋盤的歸納證明：證明任意 2ⁿ × 2ⁿ（n > 1）棋盤都能用 T-omino 鋪滿。基底是 4×4 棋盤（用四個 T 拼成），歸納步驟把 2ⁿ⁺¹ 切成四個 2ⁿ 區塊
• 第 8 題（10%）｜平面性判定：給一張圖，判斷是否為平面圖並提出證明或理由。工具是 Euler 公式 v − e + f = 2、e ≤ 3v − 6、以及尋找 K₅ 或 K₃,₃ 的細分
• 第 9 題（20%）｜圖論十格填空，每格 2 分：
• (a) 999 個頂點的樹有幾條邊（998，樹的邊數 = n−1）
• (b) 4 個頂點的非同構有根樹有幾棵（4，與 111 第 10(b) 題同題）
• (c) 把 3n − (k+5) 寫成前序表示法（prefix notation）（− * 3 n + k 5）
• (d) 循環圖 C_n 的生成樹個數（n，拿掉任一條邊都是一棵）
• (e) Q₄ 每邊權重為 1 時，最小生成樹的成本（Q₄ 有 16 個頂點 ⇒ 15）
• (f) 101 個頂點的滿二元樹最小高度
• (g) 有 50 片葉的滿二元樹頂點數（滿二元樹 n = 2l − 1 ⇒ 99）
• (h) 輪圖 W_n 的關聯矩陣有幾列幾行（列 = 頂點數、行 = 邊數）
• (i) 列出所有使 K_n 有 Euler circuit 的 n（度數 n−1 須為偶 ⇒ n 為奇數）
• (j) 列出所有使 K_m,n 有 Hamilton path 但沒有 Hamilton circuit 的 m、n（|m − n| = 1，或 m = n = 1）

這份考卷的難點

1. 第 9 題的十格填空覆蓋整個圖論章節，而且每格都是一個獨立公式：樹的邊數、有根樹枚舉、前序表示法、生成樹計數、超立方體、滿二元樹的葉子與頂點關係、關聯矩陣的形狀、Euler／Hamilton 的存在條件。沒把公式背熟就是一路空白。
2. 第 7 題的 T-omino 歸納證明比常見的「L-omino 鋪缺一格棋盤」難：T 型骨牌不能用「切四塊 + 中央補一塊」的經典技巧，要從 4×4 可鋪 當基底，再說明 2ⁿ⁺¹ 可切成四個 2ⁿ。
3. 第 1(a) 的純量三重積變號：u·(v×w) = v·(w×u) = w·(u×v)（循環置換不變號），但 v·(u×w) 是交換了兩個位置，所以變號成 +4。這一步最容易直覺答錯。
4. 第 5 題的「加權內積下的單位圓」是中正特有的考法——多數人沒想過單位圓的形狀會隨內積定義改變。

準備建議

• 圖論的小公式要整理成一張表：樹 e = v−1、滿 m 元樹 n = (ml−1)/(m−1)、C_n 有 n 棵生成樹、K_n 有 nⁿ⁻² 棵生成樹、Q_n 有 2ⁿ 頂點與 n2ⁿ⁻¹ 邊、K_n 有 Euler circuit ⟺ n 為奇數、K_m,n 有 Hamilton circuit ⟺ m = n
• 外積與三重積的性質（113 第 1 題）在中正是新考點，要記住「循環置換不變號、交換兩項變號、外積不結合」
• rank(uv^T) = 1（113 第 3 題）這類「一眼看穿結構」的題目在中正越來越多，硬算 5×5 矩陣會浪費十分鐘
• 述詞邏輯翻譯（113 第 6 題）與真假判斷（110、112、114）是中正每年必有的 10–18 分，Rosen 第 1 章要讀熟
• 歸納法證明的書寫（113 第 7 題、115 第 11 題）要練到能完整寫出「基底 → 歸納假設 → 歸納步驟」三段