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

作業系統 50%＋資料結構 50%，是十年間比重最平衡的一年。第 8 題的自訂 rehash 函式與第 9 題的 AVL 連動插入是資料結構部分的重點。

題型與配分

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

題號	主題	配分
1	fork + pipe + exec 的輸出	10%
2	磁碟排程五種演算法	10%
3	TLB 命中率	10%
4	i-node 的檔案大小	10%
5	二維陣列的 page fault（LRU）	10%
6	位元運算的輸出	10%
7	由 preorder＋inorder 求 postorder	10%
8	自訂 rehash 函式	15%
9	AVL 樹（定義＋兩次插入）	15%

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

第 1 題（10%）｜一段用 pipe + fork + dup + execl 的 C 程式，寫出輸出。父行程把 pipe 讀端 dup 到 stdin、子行程把寫端 dup 到 stdout 後 exec /bin/echo hello world!，再用 scanf("%s") 讀 —— 關鍵是 %s 只讀一個 token，所以 n = 1、buf = "hello"
第 2 題（10%，5 小題各 2%）｜1001 個磁柱、目前在 175（前一個在 125），請求 50, 500, 225, 825, 350, 550, 400, 600, 100，求 FCFS／LOOK／C-LOOK／SCAN／C-SCAN 的總移動距離
第 3 題（10%）｜page table 讀取要 500 nsec、TLB 查詢 50 nsec，要讓平均開銷降到 150 nsec 以下，需要多少命中率。列式：50 + (1−h)×500 ≤ 150
第 4 題（10%）｜i-node 有 16 個直接區塊與四層間接（含 quadruple），指標 8 bytes、區塊 8 KB：(a) 最小檔案 (b) 最大檔案
第 5 題（10%）｜double a[400][400]、page 400 bytes、3 個 page frame、LRU、陣列以 row-major 儲存，比較 (a) column-major 迴圈 (b) row-major 迴圈各產生幾次 page fault。(a) 幾乎每次都 fault，(b) 效率高很多

資料結構部分（6–9，50%）

第 6 題（10%）｜(a) 5% a = 48，求 (a & (-a)) >> 2 的輸出（取最低位的 1，48 = 110000₂，a&(-a) = 16，右移 2 得 4） (b) 5% 另一段位元運算
第 7 題（10%）｜preorder 為 ABCDEFGH、inorder 為 ABDCFGHE，求 postorder
第 8 題（15%）｜自訂的 rehash 函式 h_i(x) = (5i + x) mod 13：碰撞時依序套用 h₁、h₂、h₃…，依序插入 35, 22, 9, 24, 16, 19, 3, 5 到大小 13 的空表，畫出最終的雜湊表。這是全卷最花時間的一題
第 9 題（15%）｜AVL 樹：(a) 5% 寫出 AVL 二元搜尋樹的定義 (b) 5% 依序插入 8, 9, 6, 3, 2 後畫出樹 (c) 5% 再插入 5 後畫出樹。(b)(c) 連動，(b) 錯 (c) 必錯

第 8 題（15 分）的自訂 rehash 不是標準的 linear／quadratic probing，探測序列是 x, x+5, x+10, … (mod 13)，要逐一手算八次插入。
第 1 題的 pipe + dup + exec 需要完整理解檔案描述符的重導向，以及 scanf("%s") 的 token 行為 —— 很多人會答 2: hello world!，正確是 1: hello。
第 5 題要同時考慮 page 大小、LRU 與只有 3 個 frame，兩種迴圈順序的 fault 數差異極大。
第 9(b)(c) 連動，AVL 插入 8, 9, 6, 3, 2 過程中會發生旋轉，算錯一步後面全錯。