110 成大資工所數學考點分析｜國立成功大學

離散部分全是證明題（反證法、鴿籠、分治遞迴），線代則連考最小平方、QR 分解、偽逆與循環矩陣。離散排在前面是十年首次。

題型與配分

編號 204，系所「電機資訊學院－資訊聯招」，科目：計算機數學，考試日期 110 年 2 月 2 日第 3 節，全卷 3 頁、6 題、100 分，不可使用計算機。

110 年起離散數學排在線性代數之前（106–109 都是線代在前）。

區段	題號	配分
一、離散數學	1–3	50%
二、線性代數	4–6	50%

第 1 題（10%）｜(a) 5% 給一張圖，假設每個頂點有唯一 id，問有幾棵不同的生成樹 (b) 5% 給一個把 (x,y) 映到整數的對角線編號規則（(1,1)→1、(1,2)→2、(2,1)→3、(1,3)→4…），問哪個 (x,y) 對應到 465
第 2 題（10%）｜(a) 5% 證明 x⁵−2x⁴+x³−2x²−7x−1 = 0 有一個整數解 (b) 5% 給 4×82 的格子、每個頂點塗三色之一，證明必能找到四個同色頂點構成的矩形（鴿籠原理）
第 3 題（30%）｜(a) 10% 用反證法（contrapositive）證明「若 2^N − 1 是質數，則 N 是質數」 (b) 10% 證明 N ≥ 24 時必存在非負整數 n、m 使 5n + 7m = N（數學歸納法） (c) 10% 給分治的 FindMaxMin 演算法（每次切成兩半），求比較次數 T(N)（N = 2^k）。答案是 3N/2 − 2

第 4 題（10%）｜求曲線 y = C(−2)^x + D(−1)^x + E 對點 (0,0)、(1,4)、(2,6) 的最小平方擬合
第 5 題（30%）｜(a) 15% 求 A 的 Gram-Schmidt QR 分解，並用它解最小平方問題 (b) 15% 求 A 的偽逆（pseudoinverse）
第 6 題（10%）｜給一個 4×4 循環矩陣，已知兩個特徵向量，求 λ₀ 與 λ₁（與 108 年第 1 題完全同型）

第 3 題（30 分）全是證明，而且三種方法各一（反證法／歸納法／遞迴分析），是全卷最重的一題。
第 2(b) 的 4×82 格子染色是鴿籠原理的兩層應用：先看每一行（4 個頂點、3 色）必有兩個同色，配對方式有 C(4,2)×3 = 18 種，82 > 18×4 保證有兩行的同色配對相同。
第 3(c) 的 3N/2 − 2 要正確建立遞迴 T(N) = 2T(N/2) + 2 並解出來。
第 1(b) 的對角線編號要先看出規則是「按反對角線分組」，第 k 條對角線有 k 個元素，再定位 465。