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

題型與配分

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

作業系統佔 50 分（第 1 到 5 題），其餘 50 分是程式與資料結構（第 6 到 9 題）。

逐題考點

作業系統（第 1 到 5 題）

• 第 1 題（10%）｜一段 C 程式，建立 pipe 後 fork，parent process 關閉 fd[1] 與 fd[0]、用 close(0) 與 dup(fd[0]) 把讀端接到標準輸入，waitpid 後用 scanf("%s") 讀入並以 printf("%d:%s\n", n, buf) 印出；child process 關閉 fd[0]、用 close(1) 與 dup(fd[1]) 把寫端接到標準輸出，再 execl("/bin/echo", "echo", "hello", "world!", (void*) 0)，寫出程式的輸出
• 第 2 題（10%）｜磁碟有 1001 個 cylinder（編號 0 到 1000），目前在 cylinder 175 服務請求，前一個請求在 cylinder 125，FIFO 等待 queue 為 50、500、225、825、350、550、400、600、100，各演算法滿足所有請求的磁頭總移動距離：(a) FCFS (b) LOOK (c) C-LOOK (d) SCAN (e) C-SCAN，各 2%
• 第 3 題（10%）｜process 的 address space 有 2048 個 page，page table 放在記憶體，讀取 page table 一個字的開銷是 500 nsec，電腦有一個 TLB，可存 32 組 (page, frame)，查詢時間 50 nsec，假設先查 TLB 再讀 page table，要把平均開銷降到 150 nsec 以下，需要多高的 hit rate
• 第 4 題（10%）｜UNIX i-node 有 16 個 direct block 與 single、double、triple、quadruple 四層 indirect block，pointer 8 bytes、block 8 KB：(a) 5% 最小檔案大小（bytes） (b) 5% 最大檔案大小
• 第 5 題（10%）｜double a[][] = new double[400][400]，每個 double 8 bytes，a[0][0] 在位置 400，page 大小 400 bytes，process 在 page 0（位置 0 到 399）。三個 page frame、LRU replacement、frame 0 放 process、其餘兩個一開始是空的、array 以 row-major 存放：(a) 5% 外層 j、內層 i 的迴圈 (b) 5% 外層 i、內層 j 的迴圈，各產生幾次 page fault

程式與資料結構（第 6 到 9 題）

• 第 6 題（10%）｜寫出下列程式的輸出：(a) 5% int a=48; printf("%d \n", (a&(-a)) >>2); (b) 5% int a=68, b=34, c=25; printf("%d %d \n", a^a^a^b^a, (a^b^c^b^a^c^a)+17);，其中 ^ 為 XOR
• 第 7 題（10%）｜binary tree 的 preorder 序列為 ABCDEFGH，inorder 序列（卷面印成 ABDAFGHE），求 postorder 序列
• 第 8 題（15%）｜hashing 使用 rehash 函式 h_i(x) = (5i + x) mod 13，第一次 collision 套用 h₁，再 collision 套用 h₂，依此類推，依序把 35、22、9、24、16、19、3 插入大小為 13（索引 0 到 12）的空 hash table，問最後 hash table 的內容
• 第 9 題（15%）｜(a) 5% AVL binary search tree 的定義 (b) 5% 從空的 AVL tree 依序插入 8、9、6、3、2，畫出樹 (c) 5% 再插入 5，畫出樹

作答時要注意的地方

1. 第 8、9 題各 15 分，其餘 7 題各 10 分。
2. 第 7 題卷面的 inorder 序列印成 ABDAFGHE，A 出現兩次。
3. 第 8 題的 rehash 函式是題目自訂的，不是標準的 linear probing。
4. 第 9 題 (c) 接續 (b) 畫出來的樹。

準備方向

• 位元運算的輸出（110 第 6 題），112 第 1(a) 題、113 第 1(a) 題、115 第 5(a) 題也有，114 第 1(a) 題用到位移。
• fork 與 pipe 的輸出（110 第 1 題），106 第 1 題、109 第 4 題也有 fork 與 Pthreads 的輸出。
• disk scheduling（110 第 2 題），107 第 3(2) 題、109 第 6 題也有。
• TLB hit rate（110 第 3 題），106 第 3 題、111 第 6 題也有。
• i-node 的檔案大小（110 第 4 題），106 第 4 題、109 第 5 題、111 第 5 題也有。
• 2D array 的 page fault（110 第 5 題），109 第 3 題也有。
• 樹的 traversal 與重建（110 第 7 題），107 第 5(1) 題、115 第 6 題也有。
• hash table 的 rehash（110 第 8 題），108 第 1(2) 題、115 第 7 題也有 hash。
• AVL tree（110 第 9 題），114 第 3 題也有。