113 中央資工所考古題詳解｜數學考點分析

題型與配分

全卷 7 頁、20 題、100 分，禁用計算器。

單選與多選的順序和 112 年相反，112 年是多選在前、單選在後。這一年單選全部是線代，多選全部是離散。

線性代數考點（1–10，單選）

第 1–4、6–10 題的答案都要再 % 5（第 1、3 題先向下取整，第 2 題是 0 的個數，其餘四捨五入或取絕對值），第 5 題直接問 dimension。

• 第 1 題（5%）｜A = [[2,4,2],[1,5,2],[4,−1,9]] 的 LU 分解，L 的未知元 a、b、c 與 U 的未知元 d 到 i 相加取整後 % 5
• 第 2 題（5%）｜P₃ 中從 ordered basis [1, x, x²] 換到 [1, 2x, 4x² − 2]，transition matrix S 中 0 的個數 D，求 D % 5
• 第 3 題（5%）｜4×4 矩陣 A 的 reduced row echelon form 已知，A 的前兩行已知，第三行為 [a,b,c,d]^T，求 ⌊a+b+c+d⌋ % 5
• 第 4 題（5%）｜合成旋轉：yaw 45°、pitch −90°、roll −45°，求矩陣所有元素之和取絕對值後 % 5
• 第 5 題（5%）｜4×4 upper triangular matrix A（對角線全為 1），問 A 的 eigenvector span 的 dimension
• 第 6 題（5%）｜A = [[5,2,2],[3,6,3],[6,6,9]]，B = A³ − 20A² + 92A − 120I，D = det B，求 |D| % 5
• 第 7 題（5%）｜R⁴ 中 v₁ = [1,−1,−1,1]^T、v₂ = [1,2,−3,2]^T、v₃ = [3,3,0,−2]^T span U，用 Gram-Schmidt 求 orthonormal basis t₁、t₂ = [m,n,p,q]^T、t₃ = [r,s,x,y]^T，求 Round{1/(n²s²)} % 5
• 第 8 題（5%）｜承第 7 題，V = U⊥，把 w = [10,0,8,2]^T 拆成 w = v + u（v = [a,b,c,d]^T ∈ V、u = [e,f,g,h]^T ∈ U），求 Round{c² + g²} % 5
• 第 9 題（5%）｜A = [[4,1,−1],[2,5,−2],[1,1,2]]，diagonalization P⁻¹AP = D（a ≤ b ≤ c，P 的部分元素已給），求 Round{|a+b+c+d+e+f+g+h+j|} % 5
• 第 10 題（5%）｜用拋物線 C + Dt + Et² 擬合 t = (0,1,3,4) 上的 v = (0,2,2,5)，求 Round{|C + D + E| × 256} % 5

離散數學考點（11–20，多選）

• 第 11 題（5%）｜K₅、K₆、K₃,₃、K₃,₄、K₄,₄ 哪些非 planar graph 在移除任一頂點與其 incident edge 後會變成 planar graph
• 第 12 題（5%）｜64 個頂點代表西洋棋盤的格子，兩格間若騎士一步可到就連邊：是否為 bipartite graph、最大 degree 是否為 10、最小 degree 是否為 4、degree 為 2 的頂點是否有四個、degree 為 3 的頂點是否有八個
• 第 13 題（5%）｜哪些序列是 simple graph 的 degree sequence：(5,4,3,2,1,0)、(6,5,4,3,2,1)、(2,2,2,2,2,2)、(3,3,3,2,2,2)、(3,3,2,2,2,2)
• 第 14 題（5%）｜給一張圖，找出所有 cut vertex 與 cut edge，選項是各種組合
• 第 15 題（5%）｜G 至少三個頂點：任兩點間有 Hamilton path 是否蘊含有 Hamilton cycle、每個頂點都有從它出發的 Hamilton path 是否蘊含有 Hamilton cycle、任兩點間有 Eulerian trail 是否蘊含有 Eulerian circuit，以及 K_m,n 有 Hamilton cycle 與有 Eulerian circuit 的充要條件
• 第 16 題（5%）｜把「P → Q 為真」當成命題 P、Q 之間的關係 R(P,Q)：是否 reflexive、anti-symmetric、transitive、partial order，R 的 transitive closure 是否等於 R
• 第 17 題（5%）｜|S| = 3，f : S × S → S：函數總數、1-to-1 個數、onto 個數、bijection 個數
• 第 18 題（5%）｜Josephus 問題：n 人依序圍成圓圈，每次淘汰第二個人，最後留下的是 J(n)，判斷 J(n+1)、J(2n)、J(2n+1) 的 recurrence
• 第 19 題（5%）｜Euclid 演算法在兩數已質因數分解時的複雜度、weighted graph 中最小權重 Hamilton path 是否不可計算、格是否為 poset 的特例、bipartite graph 能否表示任意函數、and／or／not 是否足以描述任何邏輯運算
• 第 20 題（5%）｜2a_n = 7a_n−1 − 6a_n−2（n ≥ 2，a₀ = 3/2、a₁ = 11/4），判斷 characteristic polynomial、generating function 的式子、partial fraction 與 closed-form solution

作答時要注意的地方

1. 單選與多選各自扣到整大題 0 分為止。
2. 單選答錯倒扣 2 分，多選每選項倒扣 1 分。
3. 第 7、8 兩題連動。
4. 第 15 題最後兩個選項問 K_m,n 有 Hamilton cycle 與有 Eulerian circuit 的充要條件。

準備方向

• LU 分解（113 第 1 題）。
• change of basis 與 transition matrix（113 第 2 題），112 第 16 題、114 第 1 題、115 第 10 題也有。
• Gram-Schmidt 與 orthogonal decomposition（113 第 7、8 題），112 第 17 題、114 第 2 題、115 第 7 題也有。
• diagonalization（113 第 9 題）與 least squares 擬合（113 第 10 題）。
• planar graph（113 第 11 題），110、111、114、115 也有。
• degree sequence、cut vertex 與 cut edge（113 第 13、14 題）。
• Euler 與 Hamilton 的條件（113 第 15 題），114、115 也有 Euler circuit。
• 把關係當成命題間的關係（113 第 16 題），112 第 1 題也考關係性質。
• 函數計數（113 第 17 題），107 第 8 題、111 第 6 題也有。
• generating function 解遞迴（113 第 20 題）。