114 交大資工所考古題解答｜數學考點分析

離散與線代各 50%。第 6 題把是非題與計算題放在同一題組，是非題答錯倒扣 4 分並要說明為什麼錯，計算題答錯不倒扣。

題型與配分

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

題號	主題	配分
1	Connect Four 的邏輯式翻譯	11%
2	真值集合與可數集合	14%
3	8 個任務分配到 3 台伺服器	12%
4	關係的性質與 partial order	7%
5	圖 isomorphism	6%
6	線代是非題＋計算題	25%
7	determinant 展開的非零項數	5%
8	quadratic form 的 orthogonal diagonalization	10%
9	linear transformation 的矩陣表示	10%

第 6 題的計分：(a)–(d) 是非題答對 +4、答錯 −4、未答 0，且答錯要說明為什麼錯；(e)–(g) 計算題答對 +3、答錯或未答 0。卷面註明總分若為負數會調整為 0 分。

第 1 題（11%）｜Connect Four（四子棋）的邏輯式翻譯：用 Y(i,j)、R(i,j)、B(i,j) 三個 predicate 與指定的連接詞，翻譯三個敘述：(a) 4% 第 2 列有連續四個紅子 (b) 4% 每一行至少有一個黃子 (c) 3% 有子的格子必為紅或黃但不能同時是兩者
第 2 題（14%）｜(a) 4% 給定域 D 與兩個 predicate，R、S 為其真值集合，選出永遠為真的敘述 (b) 10% 舉出兩個無限集合，說明 ℵ₀ + ℵ₀ = ℵ₀
第 3 題（12%）｜8 個相異任務分配到 3 台相同伺服器：(a) 4% 無限制時的分法數 (b) 2% 每台至少一個任務 (c) 2% 每台至少一個且沒有一台處理 5 個以上 (d) 4% 改成伺服器有標號時的分法數
第 4 題（7%）｜關係 R = {(a,b),(b,c),(c,d),(d,e),(a,e)}：(a)(b)(c) 各 1% 判斷 reflexive、symmetric、transitive (d) 4% 是否為 partial order？若不是，最少要加幾個有序對才能變成 partial order
第 5 題（6%）｜判斷兩個圖 G、H 是否 isomorphic：(a) 2% 是或否 (b) 4% 是的話給出保持鄰接的映射，不是的話詳細說明理由

第 6 題（25%）｜(a) 4% A 可逆 ⟺ λ = 1 是 A 的 eigenvalue (b) 4% W 是 Rⁿ 的 subspace 時，W⊥ 是否也是 subspace (c) 4% E 為 elementary matrix 時，N(EA) 是否等於 N(A) (d) 4% h = 1+x² 是否在 span{cos²x, sin²x} 中 (e) 3% 5×7 且 rank = 3 的矩陣，Ax = 0 的通解有幾個參數 (f) 3% 5×6 矩陣的解空間為二維時，rank(A) 是多少 (g) 3% 求 k 使 (k, 21, −12) 是兩個給定向量的 linear combination
第 7 題（5%）｜給一個大部分為 0 的矩陣，問 determinant 展開後有幾個非零乘積項
第 8 題（10%）｜求 orthogonal matrix Q（且 q₁₁ > 0、q₂₂ > 0）與 diagonal matrix D，使 quadratic form 6x² + 24xy − y² diagonalize
第 9 題（10%）｜求給定 linear transformation 的矩陣表示

邏輯式翻譯：106、107、112、113、114 年都出現。
物件、容器相異或相同的分配計數（114 第 3 題）。
quadratic form 的 orthogonal diagonalization（114 第 8 題），112 第 1-1 題也考 quadratic form。
可數集合與基數運算（114 第 2(b) 題、112 第 7 題）。