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

題型與配分

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

離散數學考點（1–5）

• 第 1 題（7%）｜解非齊次 recurrence a_n+2 − 4a_n+1 + 3a_n = −200（a₀ = 3000、a₁ = 3300）
• 第 2 題（10%）｜列出 generating function F(x) = √(1+x) 的前五個係數，並化簡為最簡分數
• 第 3 題（15%）｜G(x) 為 {a_k} 的 generating function，求以下數列的 generating function：(A) 3a₀, 3a₁, 3a₂, … (B) 0, 0, 0, 0, a₄, a₅, … (C) a₁, 2a₂, 3a₃, 4a₄, …，三小題各 5%
• 第 4 題（13%）｜設計 finite state machine M = (S, I, O, ν, ω)，S = {s₁,…,s₄}、輸入 {0,1,2}、輸出 {0,1}，輸入串含至少三個 1 時輸出 1，要填出 state diagram 上的問號
• 第 5 題（5%）｜10 個頂點、degree sequence 為 (1,3,1,3,2,1,1,3,1,3) 的樹有幾棵

線性代數考點（6–10）

• 第 6 題（10%）｜向量 x = (x₁,x₂,x₃,x₄) ∈ R⁴ 的 24 個重排 span subspace S，找出使 dim(S) = 3 的具體向量 x
• 第 7 題（10%）｜給 G₂、G₃、G₄ 三個 determinant 的形式（對角線為 0、其餘為 1），計算 G_n 的值
• 第 8 題（10%）｜證明：B 可逆時，AB 與 BA 有相同的 eigenvalue
• 第 9 題（10%）｜給空間中三點 P、Q、R，求第一個分量為 −1 的點 S 使 PQ 平行於 RS
• 第 10 題（10%）｜是非題，五小題各 2%
• 第 10(a) 題｜positive definite 矩陣是否必可逆
• 第 10(b) 題｜det(A−B) 是否等於 detA − detB
• 第 10(c) 題｜與 subspace W 的每個向量都 orthogonal 是否蘊含 w = 0
• 第 10(d) 題｜A 為方陣且 Ax = b 對某些 b 無解時，nullity 是否為零
• 第 10(e) 題｜若 Rⁿ 有由 A 的 eigenvector 組成的 basis，A 是否 diagonalizable

作答時要注意的地方

1. 離散部分第 1 至 5 題的配分依序是 7、10、15、13、5。
2. 第 4 題是設計 state machine，要填出 state diagram 上的問號。
3. 第 3 題 15 分，是離散部分配分最高的一題。

準備方向

• generating function 的運算：113 第 3 題，112 第 2 題也考 generating function。
• 廣義 binomial 展開（113 第 2 題）。
• finite state machine：113 第 4 題、114 第 1 題、115 第 5 題。
• 樹的計數（113 第 5 題）。
• AB 與 BA 的 eigenvalue（113 第 8 題）。
• 非齊次 recurrence：112、113、114、115 年各一題。