110 成大資工所考古題詳解｜數學考點分析

題型與配分

全卷 3 頁、6 題、100 分，不可使用計算機。

這一年離散數學排在線性代數之前，106 至 109 年是線代在前。

離散數學考點（1–3）

• 第 1 題（10%）｜(a) 5% 給一張圖，假設每個頂點有唯一 id，問有幾棵不同的 spanning tree (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% 給 divide and conquer 的 FindMaxMin 演算法（每次切成兩半），求比較次數 T(N)（N = 2^k）

線性代數考點（4–6）

• 第 4 題（10%）｜求曲線 y = C(−2)^x + D(−1)^x+1 對點 (0,0)、(1,4)、(2,6) 的 least squares 擬合
• 第 5 題（30%）｜(a) 15% 求 A 的 Gram-Schmidt QR 分解，並用它解 least squares 問題 (b) 15% 求 A 的 pseudo-inverse
• 第 6 題（10%）｜給一個 4×4 circulant matrix，已知兩個 eigenvector，求 λ₀ 與 λ₁，與 108 第 1 題同型

作答時要注意的地方

1. 離散部分的第 2 題與第 3(a)(b) 題是證明題，第 3(c) 題是求比較次數。
2. 第 3、5 題各 30 分，是配分最高的兩題。
3. 第 1(b) 題的編號規則以題目給的前幾項為準。

準備方向

• contrapositive、pigeonhole principle 與證明題：110 第 2、3 題、109 第 4 題。
• Gram-Schmidt QR 分解與 least squares 解：109 第 2 題、110 第 5 題，交大 108、112 年也有同型題。
• pseudo-inverse（110 第 5(b) 題）。
• circulant matrix 的 eigenvalue：108 第 1 題、110 第 6 題。
• divide and conquer 演算法的比較次數（110 第 3(c) 題）。