114 中山資工所考古題詳解｜數學考點分析

題型與配分

全卷 1 頁、9 題、100 分，不可使用計算機。卷首規定每題都要寫出詳細步驟，否則該題不給分。

逐題考點

• 第 1 題（10%）｜pseudo-code：increment = 0，sum = 0，for i = 1 to 12，for j = 1 to i，for k = 1 to j，每次執行 increment = increment + 1、sum = sum + increment，問執行完後 sum 的值
• 第 2 題（10%）｜用 well-ordering principle 證明 induction 原理
• 第 3 題（10%）｜A = {1,2,…,9}，B = {a,b,c,d,e,f,g,h}，函數 f: A → B：(a) 5% f(A) = {a,b,c} 的函數個數 (b) 5% |f(A)| = 3 的函數個數
• 第 4 題（10%）｜找出由十個相異實數組成的數列，使它沒有長度為 3 的遞減或遞增子序列
• 第 5 題（10%）｜畫出 finite state machine 的 state diagram，I = O = {0,1}，辨識語言 {0,0}{1,0} ∪ {0,1}{00} 中的所有字串
• 第 6 題（20%）｜P1 每個 process 要 1 秒，P2 要 4 秒，依序執行兩個程式共 n 秒：(a) 10% 求執行方式數的 recurrence relation 並解出 (b) 10% P2 有四種不同任務，每個不同任務的 P2 process 視為不同的 process，求 recurrence relation 並解出
• 第 7 題（10%）｜Alice 要從賣豬肉、雞肉與牛肉的超市買 n 盒肉（各種肉品牌與大小相同），牛肉必須買偶數盒（牛肉買一送一），有幾種買法
• 第 8 題（10%）｜隨機產生 28 位的八進位（0 到 7）序列，3 的個數為偶數且 7 的個數為偶數的機率
• 第 9 題（10%）｜解 recurrence relation a_n+2² − 7a_n+1² + 12a_n² = 9n，n ≥ 0，a₀ = a₁ = 1（卷面各 a 項為平方）

作答時要注意的地方

1. 第 6 題 20 分，分成兩個 10 分的小題，第 3 題分成兩個 5 分的小題，其餘各題 10 分。
2. 第 2 題題目指定要用 well-ordering principle。
3. 第 4 題要給出一組十個相異實數，不是證明存在。
4. 第 9 題卷面的 recurrence 中，a_n 項都帶平方。

準備方向

• 巢狀迴圈（114 第 1 題），110 第 1 題是兩層。
• 經典定理的證明（114 第 2 題），110 第 2 題、113 第 3 題、115 B3 也有。
• 函數個數（114 第 3 題），107 第 2 題考 onto 函數的個數，109 第 3 題、113 第 6、7 題、115 A8 也有。
• 沒有 monotone subsequence 的數列（114 第 4 題），112 第 3 題也是同一類題目。
• finite state machine（114 第 5 題），111 第 2 題也有。
• scheduling 遞迴（114 第 6 題），112 第 7 題的停車位是同樣的結構。
• 偶數限制與分配（114 第 7 題），109 第 1 題、113 第 1 題也有。
• 符號個數的奇偶限制（114 第 8 題），111 第 5 題、112 第 6 題也有。
• 非齊次遞迴（114 第 9 題），110 第 6 題也有。