109 中山資工所考古題詳解｜軟體考點分析

題型與配分

全卷 3 頁、10 題、100 分，考試時間 100 分鐘，不可使用計算機，全部是問答申論題。卷首註明：題目不清楚或需要做某些假設時，在答案開頭清楚說明假設。

作業系統佔 70 分（第 1 到 6 題），資料結構佔 30 分（第 7 到 10 題）。

逐題考點

• 第 1 題（10%）｜五個 process P₁ 到 P₅ 依序同時在時間 0 到達，burst time 為 10、1、2、1、5 ms，priority 為 3、1、4、5、2：(a) 5% non-preemptive priority scheduling（數字小的 priority 高）下 P₁ 的完成時間 (b) 5% SJF scheduling 的平均 waiting time
• 第 2 題（10%）｜64 位元 virtual address、32 位元 physical address、page 大小 32 KB，page table 需要幾個項目
• 第 3 題（10%）｜double a[][] = new double[250][250]，每個 double 8 bytes，a[0][0] 在位置 200，page 大小 200 bytes，process 本身在 page 0（位置 0 到 199）。三個 page frame、LRU replacement、frame 0 放 process、其餘兩個一開始是空的、array 以 column-major 存放：(a) 5% 外層 i、內層 j 的初始化迴圈產生幾次 page fault (b) 5% 外層 j、內層 i 的迴圈產生幾次 page fault
• 第 4 題（10%）｜一段用 Pthreads API 的 C 程式，主程式 fork 後，parent process、child process 與 grandchild process 各有 waitpid 與 printf，child process 另建一個 Pthread 去把傳入的整數減 1，寫出程式的輸出
• 第 5 題（10%）｜UNIX i-node 有 10 個 direct block 與 single、double、triple 三層 indirect block，pointer 8 bytes、block 4 KB：(a) 5% 允許的最小檔案大小（bytes） (b) 5% 允許的最大檔案大小
• 第 6 題（20%）｜磁碟有 1024 個 cylinder（編號 0 到 1023），目前在 cylinder 200 服務請求，前一個請求在 cylinder 125，等待 queue 依 FIFO 順序是 50、500、250、800、350、550、400、600、100，從目前磁頭位置開始，各演算法滿足所有請求的磁頭總移動距離：(a) SSTF (b) SCAN (c) LOOK (d) C-SCAN (e) C-LOOK，各 4%
• 第 7 題（5%）｜給一張 6 個頂點（A 到 F）的 weighted graph，用 Kruskal 演算法列出加入 minimum cost spanning tree 的邊的順序，要用邊的權重表示，只需寫出順序
• 第 8 題（5%）｜priority queue 中有 A 到 J 十個節點，頻率依序為 6、9、12、14、18、24、27、29、35、45，畫出 Huffman tree
• 第 9 題（10%）｜輸入大小為 n，k₁ 代表最大位數、k₂ 代表桶數，(a) selection sort (b) merge sort (c) heap sort (d) radix sort (e) bucket sort 的平均執行時間
• 第 10 題（10%）｜Ackermann function A(m,n) 的定義：m = 0 時為 n+1，m > 0 且 n = 0 時為 A(m−1, 1)，m > 0 且 n > 0 時為 A(m−1, A(m, n−1))，題目說明 A(4,1) = 65533，問 A(3,2) 與 A(2,4) 的值

作答時要注意的地方

1. 第 6 題 20 分，是全卷配分最高的單題，一共五種 disk scheduling 演算法。
2. 第 3 題限定三個 page frame、LRU replacement、column-major 存放，且 process 本身占用 frame 0。
3. 第 4 題的程式有行號，行號只是為了方便參照。
4. 全卷不可使用計算機，第 6 題的移動距離與第 2、5 題的位元數、檔案大小都要手算。

準備方向

• CPU scheduling 的計算（109 第 1 題），113 第 6(a) 題也有。
• Page table 的項目數（109 第 2 題），111 第 9 題也有。
• 2D array 的 page fault（109 第 3 題），110 第 5 題也有。
• fork 與 Pthreads 的輸出（109 第 4 題），106 第 1 題也是 fork、waitpid 加 Pthread 的程式，110 第 1 題有 fork、pipe 與 exec 的輸出。
• UNIX i-node（109 第 5 題），106 第 4 題、110 第 4 題、111 第 5 題也有。
• disk scheduling（109 第 6 題），107 第 3(2) 題、110 第 2 題也有，106 第 5 題、111 第 7 題是磁碟讀檔時間。
• MST（109 第 7 題的 Kruskal），115 第 8 題考 Prim。
• Huffman tree（109 第 8 題）。
• 排序的平均時間（109 第 9 題），106 第 9 題、107 第 5(5) 題、108 第 1(4) 題、112 第 2 題、113 第 3 題、114 第 2 題、115 第 9 題也有。
• 遞迴函式的展開（109 第 10 題），106 第 7 題也是 Ackermann function（卷面舉例寫 A(1,1) = 65533），111 第 1(b) 題、112 第 1(b) 題、113 第 1(b) 題、115 第 5(b) 題也有遞迴程式的輸出。