109 中山資工所軟體考點分析

題型與配分

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

卷首註明：「若題目不清楚或你認為需要做某些假設，請在答案開頭清楚說明你的假設。」這句話 109–114 年都有，代表寫出假設是被鼓勵的。

作業系統佔 70%、資料結構佔 30%。

逐題考點

• 第 1 題（10%）｜五個行程同時到達，給 burst time 與 priority：(a) 5% 非搶占優先權排程下某行程的完成時間 (b) 5% SJF 的平均等待時間
• 第 2 題（10%）｜64-bit 虛擬位址、32-bit 實體位址、page 大小 32 KB，page table 需要幾個項目（2⁶⁴ / 2¹⁵ = 2⁴⁹）
• 第 3 題（10%）｜double a[250][250]、每個 double 8 bytes、page 大小 200 bytes，比較 row-major 與 column-major 兩種迴圈順序各產生幾次 page fault
• 第 4 題（10%）｜一段同時用 fork() 與 Pthreads 的 C 程式，寫出完整輸出。要同時掌握行程複製與執行緒共享記憶體的差異
• 第 5 題（10%）｜UNIX i-node 有 10 個直接區塊與三層間接（single／double／triple），指標 8 bytes、區塊 4 KB：(a) 5% 最小檔案大小 (b) 5% 最大檔案大小
• 第 6 題（20%，5 小題各 4%）｜1024 個磁柱、目前在 200（前一個請求在 125），請求佇列為 50, 500, 250, 800, 350, 550, 400, 600, 100，求 SSTF／SCAN／LOOK／C-SCAN／C-LOOK 各自的磁頭總移動距離。這是全卷配分最高的一題
• 第 7 題（5%）｜給帶權圖，寫出 Kruskal 加入邊的順序
• 第 8 題（5%）｜給 9 個節點的頻率，畫出 Huffman tree
• 第 9 題（10%）｜selection／merge／heap／radix／bucket sort 的平均複雜度（radix 要用 k₁ 位數、bucket 要用 k₂ 個桶表示）
• 第 10 題（10%）｜Ackermann function 的定義已給，求 A(3,2) 與 A(2,4) 的值。純遞迴展開，但層數很多

這份考卷的難點

1. 第 6 題（20 分）要算五種磁碟排程的總移動距離，禁用計算器且每種規則不同（SCAN 走到底、LOOK 走到最後一個請求、C-SCAN 回頭不服務…），錯一個規則就扣 4 分。
2. 第 4 題的 fork + pthread 混合是全卷最難判讀的：fork 後父子行程各自有 value 的副本，但 pthread 共享，輸出順序與數值都要精確推導。
3. 第 10 題的 Ackermann function 要手動展開遞迴，A(3,2) = 29、A(2,4) = 11，展開層數多容易算錯。
4. 第 3 題要算 page fault 數，得先算出每個 page 能放幾個 double（200/8 = 25 個），再判斷兩種迴圈順序的存取模式。

準備建議

• 磁碟排程五兄弟（FCFS／SSTF／SCAN／C-SCAN／LOOK／C-LOOK）是中山的必考題（109、110 連兩年），每種的規則差異要背清楚
• UNIX i-node 的最大檔案計算在 109、110、111 連三年出現，公式要熟：直接 + 單層 + 雙層 + 三層
• fork() 與 pthread 的輸出追蹤是中山特有的考法（109、110 都有），要理解「fork 複製記憶體、thread 共享記憶體」
• Ackermann function 雖然少見，但展開規則簡單，練一次就會