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

題型與配分

全卷 2 頁、7 大題、100 分，不可使用計算機，卷面名稱為問答申論題。第 7 題是 10 個是非題，每題 1%，用 O 或 X 作答。

作業系統佔 60 分（第 1 到 4 題），資料結構佔 30 分（第 5、6 題），第 7 題的 10 個是非題，第 1 到 5 小題是資料結構，第 6 到 10 小題是作業系統與 cache。

逐題考點

第 1 題｜process 管理（15%）

• (1) 4%｜兩種基本的 inter-process communication 模型
• (2) 2%｜race condition 什麼時候會發生
• (3) 3%｜critical-section 問題的解法要滿足的三個要求
• (4) 4%｜deadlock prevention 與 deadlock avoidance 的差別
• (5) 2%｜process synchronization 中 priority inversion 什麼時候會發生

第 2 題｜記憶體管理（15%）

• (1) 3%｜哪個裝置負責 address translation，什麼情況下不會用到這個裝置
• (2) 4%｜使用 paging 的兩個好處
• (3) 2%｜有沒有系統使用 optimal page replacement，為什麼
• (4) 4%｜平均 page fault 時間 70 μs、記憶體存取時間 250 ns，要讓 effective access time 小於 285 ns，page fault rate 要多少，要列出計算過程
• (5) 2%｜什麼是 reentrant code

第 3 題｜儲存與 I/O 管理（15%）

• (1) 4%｜UNIX 開啟檔案時保存的四項檔案資訊
• (2) 6%｜磁碟 queue 的請求依序為 cylinder 100、185、40、120、2、138、75、87，磁頭目前在 cylinder 60，最大 cylinder 為 200，寫出 SSTF 與 C-LOOK scheduling 的結果
• (3) 2%｜RAID 的 parity bit 如何運作
• (4) 3%｜CPU 得知 I/O 裝置的資料是否就緒的三種方法

第 4 題｜保護與安全（15%）

• (1) 4%｜principle of least privilege 是什麼，Sun Microsystems 的作業系統如何實作
• (2) 3%｜為什麼 language-based protection 可能不安全
• (3) 4%｜polymorphic 與 tunneling 病毒如何躲過防毒軟體的偵測
• (4) 2%｜digital-signature 演算法如何運作
• (5) 2%｜DDoS 如何運作

第 5 題｜基礎資料結構（15%）

• (1) 3%｜一棵 binary tree 的 DFS 結果為 c, b, e, f, d, h, i, g, k, a, j，BFS 結果為 c, b, g, e, d, k, j, f, h, i, a，畫出這棵樹
• (2) 3%｜計算 postfix 運算式 2 4 + 6 × 9 8 − 3 5 + × − 的結果，要列出計算過程
• (3) 2%｜什麼是 binary search tree，說明它的性質
• (4) 4%｜除了每個節點非紅即黑，還要怎麼處理，BST 才會成為 red-black tree
• (5) 3%｜證明 quicksort 的最壞時間複雜度是 O(n²)

第 6 題｜進階資料結構（15%）

• (1) 8%｜n 個 key、minimum degree 為 t 的 B-tree，樹高的上界是多少，並證明
• (2) 2%｜什麼是 B*-tree
• (3) 5%｜證明 binomial tree B_k 在深度 i 恰有 C(k,i) 個節點，C(k,i) 為組合數

第 7 題｜是非題（10%，每小題 1%，用 O 或 X 作答）

• (1)｜selection sort 的平均時間複雜度是 O(n lg n)
• (2)｜LIFO 與 FIFO 分別可以用 queue 與 stack 實作
• (3)｜hash 沒有反函數
• (4)｜有 k 個內部節點的 red-black tree，高度不超過 2lg(k−1)
• (5)｜樹不含 cycle
• (6)｜同一個 process 中的 thread 可以直接共用記憶體與共同變數
• (7)｜在任何情況下，user process 都不能使用 kernel 的資料結構
• (8)｜hard real-time OS 可以用 preemptive、priority-based scheduling 實作
• (9)｜wait-die 是 deadlock prevention 的 preemptive-based 解法
• (10)｜對 cache 而言，write-through 比 write-back 可靠

作答時要注意的地方

1. 前 6 大題各 15 分，小題配分 2 到 8 分，第 6(1) 題 8 分最高。
2. 第 2(4) 題與第 5(2) 題卷面要求列出計算過程。
3. 第 3(2) 題卷面沒有指定磁頭移動的方向。
4. 第 5(1) 題卷面只寫 DFS result 與 BFS result。
5. 第 7 題 10 個是非題用 O 或 X 作答，卷面沒有標示倒扣。
6. 卷首沒有印「題目不清楚可自行假設」的說明，106 年與 109 到 114 年有。

準備方向

• process synchronization 與 deadlock（107 第 1 題），108 第 3(1)(2) 題也問 race condition 與 deadlock prevention、avoidance 的差別，112 第 8(a) 題、115 第 3 題也有 deadlock。
• IPC 的兩種模型（107 第 1(1) 題），114 第 6(b) 題相同。
• Paging 的好處（107 第 2(2) 題），108 第 4(1) 題相同。
• effective access time 與 page fault rate（107 第 2(4) 題），113 第 6(b) 題同型。
• disk scheduling（107 第 3(2) 題），109 第 6 題、110 第 2 題也有。
• 保護與安全（107 第 4 題），108 第 5 題 20 分也整題是保護與安全，第 4(1) 題的 principle of least privilege 與 108 第 5(1) 題相同。
• 由兩種 traversal 結果重建 binary tree（107 第 5(1) 題），110 第 7 題、115 第 6 題也有。
• 運算式（107 第 5(2) 題），106 第 10 題、108 第 1(1) 題也有。
• BST 與 red-black tree（107 第 5(3)(4) 題），第 5(4) 題與 108 第 1(3) 題相同，111 第 3 題考 BST 刪除。
• B-tree 家族與 binomial tree（107 第 6 題），108 第 2(2)(3)(4) 題也有 B-tree、B*-tree 與 binomial heap。
• 排序（107 第 5(5) 題、第 7(1) 題），106 第 9 題、108 第 1(4) 題、109 第 9 題、112 第 2 題、113 第 3 題、114 第 2 題、115 第 9 題也有。