108 中山資工所軟體考點分析
科目是「作業系統與資料結構」，資料結構佔 40%、作業系統佔 60%。全卷 25 個小題、每題 4 分，幾乎全是「解釋名詞／說明差異」的觀念題。
題型與配分
科目名稱「作業系統與資料結構」【資工系碩士班甲組】，題號 434003，考試時間 100 分鐘，不可以使用計算機（問答申論題），全卷 2 頁、5 大題、25 小題、100 分。
這是中山軟體考科最需要先知道的事：科目名稱叫「作業系統與資料結構」，代表作業系統佔了一半以上。只準備資料結構與演算法會直接失去六成分數。
| 大題 | 主題 | 配分 |
|---|---|---|
| 1 | Basic Data Structures | 20% |
| 2 | Advanced Data Structures | 20% |
| 3 | Process and Synchronization | 20% |
| 4 | Memory and I/O | 20% |
| 5 | Protection and Security | 20% |
每個大題固定 5 個小題、每小題 4 分，結構非常規律。
逐題考點
第 1 題｜基礎資料結構（20%）
- (1) 4%｜把 prefix 運算式轉成 infix 並計算結果
- (2) 4%｜什麼是 simple uniform hashing？m 格、n 筆資料、chaining 時失敗搜尋的期望時間（答案 Θ(1+α)）
- (3) 4%｜除了「每個節點非紅即黑」外，還要滿足哪些條件才能讓 BST 成為紅黑樹
- (4) 4%｜heap sort／insertion sort／bubble sort／quick sort 的平均時間複雜度
- (5) 4%｜給 adjacency matrix，寫出 BFS 與 DFS 的走訪順序（有多重選擇時依字母序）
第 2 題｜進階資料結構（20%）
- (1) 4%｜什麼是強連通元件（SCC）
- (2) 4%｜B-tree 為何能降低磁碟存取成本
- (3) 4%｜**B-tree 與 B\*-tree 的差別**
- (4) 4%｜binomial heap 的兩個性質
- (5) 4%｜給一個 Fibonacci heap，把 key 50 降為 18、再把 key 37 降為 7，畫出結果
第 3 題｜行程與同步（20%）
race condition 的定義與解法、deadlock prevention 與 avoidance 的差別、何時需要 condition variable、asynchronous 與 deferred cancellation 的差別、造成行程終止的四個常見條件
第 4 題｜記憶體與 I/O（20%）
paging 的兩個好處、working set 與 thrashing、external 與 internal fragmentation 的差別、synchronous 與 asynchronous I/O 的差別、I/O 裝置的四個常見暫存器
第 5 題｜保護與安全（20%）
最小權限原則與 Solaris 10 的實作、電腦病毒與蠕蟲的差別、UNIX 中 setuid-on 問題的兩個常見解法、masquerading 與 replay attack、認證的目的與 non-repudiation
這份考卷的難點
- 作業系統佔 60%（第 3、4、5 題），而且第 5 題整整 20 分全是資訊安全（病毒、蠕蟲、setuid、重放攻擊、不可否認性）—— 這在其他學校的軟體考科幾乎不會出現。
- 全部是問答申論題，沒有選擇題，每個小題都要用文字寫清楚，100 分鐘要寫 25 個小題，平均每題只有 4 分鐘。
- 第 2 題的進階結構（SCC、B\*-tree、binomial heap、Fibonacci heap）合計 20 分，都是課本後段的內容。
- 第 2(5) 的 Fibonacci heap 要實際做兩次 decrease-key 並畫出結果，是唯一要動手畫圖的題目。
準備建議
- 中山的軟體考科必須把作業系統讀完整（Silberschatz 的恐龍書），包含保護與安全那幾章 —— 這是和其他學校最大的差異
- 資料結構部分偏觀念解釋而非計算：「什麼是 X」「X 與 Y 的差別」「X 的兩個性質」，要能用兩三句話講清楚
- Fibonacci heap 與 binomial heap 在中山多次出現，cascading cut 的規則要熟
- 時間分配是關鍵：25 個小題、100 分鐘，每題最多 4 分鐘，不要在單題上卡住