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

資料結構 50%＋作業系統 50%。第 2 題把 insertion sort 的 Swap 次數拆成三小問（最少、最多、給定輸入），第 4 題的郵票組合是經典的無限背包計數。

題型與配分

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

資料結構 50%（1–4）、作業系統 50%（5–9）。

資料結構部分（1–4）

第 1 題（15%）｜(a) 5% a=40, b=24，求 (a & (~b)) | ((~a) & b) 的輸出 —— 這就是 XOR，答案 48 (b) 10% 一支會修改陣列元素再遞迴的函式 h(9)，寫出所有輸出。遞迴規則：i 為偶數時 b[i/2] += i/2 再遞迴 h(i/2)、奇數時 b[i+1]++ 再遞迴 h(i+1)。要小心副作用
第 2 題（15%）｜給 insertion sort 的 pseudo-code（相鄰交換版）：
(a) 5%｜輸入 3, 9, 6, 5, 8, 2 時 Swap() 執行幾次（答案是逆序對個數）
(b) 5%｜什麼樣的排列讓 Swap 最少？幾次？（已排序，0 次）
(c) 5%｜什麼樣的排列讓 Swap 最多？幾次？（完全逆序，n(n−1)/2 次）
核心觀念：相鄰交換版 insertion sort 的交換次數 = 逆序對（inversion）數
第 3 題（10%）｜6 個元素 A–F（已排序）搜尋頻率 4, 9, 1, 6, 8, 7，求成本最小的最佳二元搜尋樹
第 4 題（10%）｜郵票組合計數：有 1, 2, 3, 4, 5 元五種郵票，g(i,j) 表示只用 1..i 元郵票湊出 j 元的組合數。但今天 3 元與 4 元賣完了，寫出 g(i,j) 的遞迴式。核心是 g(i,j) = g(i−1,j) + g(i, j−i)，並對缺貨的面額跳過

作業系統部分（5–9）

第 5 題（10%）｜(a) 7% PCB 的七個常見組成 (b) 3% mutex／semaphore／condition variable 各自的用途
第 6 題（10%）｜(a) 6% compile time／load time／execution time 三種位址繫結的差別 (b) 4% 如何用 working-set model 解決 thrashing
第 7 題（10%）｜(a) 6% 檔案的 sequential／direct／index 三種存取方式 (b) 4% 檔案系統的 consistency semantics
第 8 題（10%）｜(a) 4% 死結預防如何運作 (b) 3% 即時系統關心的三種延遲 (c) 3% 分散式檔案系統不使用快取的三個理由
第 9 題（10%，5 個各 2%）｜名詞解釋：vectored I/O、safety-critical system、logic bomb、turnaround time、race condition

第 2 題（15 分）需要真正理解 insertion sort 的交換次數 = 逆序對數，三小題環環相扣；(b)(c) 還要說出「什麼樣的排列」而不只是給數字。
第 1(b) 的遞迴副作用（10 分）：函式會邊遞迴邊修改陣列，必須逐步追蹤 b[] 的變化才能寫出正確輸出。
第 4 題的郵票計數要注意「3 元與 4 元缺貨」這個轉折 —— 遞迴式要能表達「跳過某些面額」。
第 3 題的最佳 BST 要填 6×6 的 DP 表，禁用計算器很耗時。