113 中山資工所軟體考點分析｜國立中山大學

資料結構 40%＋作業系統 60%（含 20 分填空題）。第 2 題的螺旋矩陣公式與第 4 題的 2×m 磚塊鋪法遞迴，是十年來最像數學競賽的兩題。

題型與配分

科目名稱「作業系統與資料結構」【資工系碩士班甲組】，題號 434008，考試時間 100 分鐘，不可以使用計算機（問答申論題），全卷 2 頁、8 題、100 分。

題號	主題	配分
1	C 程式輸出（位元運算＋分治遞迴）	15%
2	螺旋矩陣的通式	10%
3	五種排序是否穩定	10%
4	2×m 磚塊鋪法的遞迴式	15%
5	即時系統位址轉換與中斷	10%
6	排程平均等待時間＋page fault 率	10%
7	Timestamp ordering protocol	10%
8	填空題（10 格）	20%

資料結構部分（1–4，50%）

第 1 題（15%）｜(a) 5% d = 48，求 (d & (-d+1)) + 3 的輸出 (b) 10% 一支分治求最大值的遞迴函式 max(1,5)，要寫出每一層的 cout 輸出順序（不只最終答案）。注意 max(mid+1, right) 被呼叫了兩次，會多印出東西
第 2 題（10%）｜給一個螺旋排列的二維陣列（0, 3, 4, 15, 16… / 1, 2, 5, 14, 17… / 8, 7, 6, 13, 18…），推導 M[i][j] 的通式（以 i、j 表示）。這是純數學推導題
第 3 題（10%）｜bubble／heap／quick／merge／radix sort 各自是否為穩定排序。（答案：bubble 穩定、heap 不穩定、quick 不穩定、merge 穩定、radix 穩定）
第 4 題（15%）｜2×m 的磚塊可分解成 L 形（3 格）與正方形（1 格），d(m) 表示分解方法數，已知 d(0)=1、d(1)=1、d(2)=5：
(a) 5%｜求 d(3)
(b) 10%｜寫出 d(m) = a·d(m−1) + b·d(m−2) + c·d(m−3) 中的 a、b、c
這是全卷最難的一題，要枚舉所有可能的右端切法

作業系統部分（5–8，50%）

第 5 題（10%）｜(a) 6% 即時系統中位址轉換的三種方法 (b) 4% maskable 與 non-maskable 中斷的差別
第 6 題（10%）｜(a) 6% 五個行程給定 burst time 與 priority，求 round-robin（quantum=1）、SJF、非搶占優先權三種排程的平均等待時間 (b) 4% 記憶體存取 150 ns、page fault 60000 ns，要讓有效存取時間低於 175 ns，page fault 率需為多少。題目註明「必須列出計算過程，否則不給分」
第 7 題（10%）｜Timestamp ordering protocol：說明它如何檢查非序列排程是否為 conflict serializable（提示：分別說明 read(Q) 與 write(Q) 時的判斷）。這是資料庫的內容
第 8 題（20%，10 格各 2%）｜填空：thread 的 program counter、critical-section 的第三個要求（bounded waiting）、TLB、MMU、thrashing、volume、RAID 6 的冗餘方式（P+Q）、RBAC 的 privilege、AES 的金鑰長度（192）、polymorphic virus

第 4 題（15 分）的磚塊鋪法需要自己枚舉右端的所有收尾方式才能導出 d(m) = d(m−1) + 4·d(m−2) + … 這類遞迴式，是全卷區分度最高的一題。
第 1(b) 要寫出所有中間輸出，而不只是回傳值 —— 程式裡 max(mid+1, right) 在條件判斷與 else 分支各呼叫一次，會重複執行並多印一行。
第 2 題的螺旋矩陣通式要分「i ≥ j」與「i < j」兩種情況討論，並找出與 max(i,j) 的平方關係。
第 7 題的 timestamp ordering 屬於資料庫系統，不在一般 OS 或資料結構課本中。