115 中山資工所軟體考點分析
作業系統 60%（填空 20 分＋問答 30 分）＋資料結構 40%。資料結構部分回到最標準的題型：走訪重建、double hashing、Prim、排序複雜度。
題型與配分
科目名稱「作業系統與資料結構」【資工系碩士班甲組】，題號 434003，考試時間 100 分鐘，不可以使用計算機（問答申論題），全卷 2 頁、9 題、100 分。
| 題號 | 主題 | 配分 |
|---|---|---|
| 1 | 填空題（10 格） | 20% |
| 2 | 行程放棄 CPU 的情況＋warm cache | 10% |
| 3 | 死結處理方式＋copy-on-write | 10% |
| 4 | Sector sparing 的五個步驟 | 10% |
| 5 | C 程式輸出（位元運算＋遞迴） | 10% |
| 6 | 由 inorder＋postorder 求 preorder | 10% |
| 7 | Double hashing | 10% |
| 8 | Prim 演算法＋複雜度 | 10% |
| 9 | 五種排序的最壞複雜度 | 10% |
作業系統 50%（1–4）、資料結構 50%（5–9）。
逐題考點
作業系統部分（1–4）
- 第 1 題（20%，10 格各 2%）｜填空：multiprogramming 的 degree、modify bit 又稱 dirty bit、dispatcher、critical-section 問題、nonvolatile（NVM） memory devices、device-driver modules、死結條件中「resource holding」蘊含 hold and wait、檔案是 named collection、need-to-know principle、confidentiality 的破壞
- 第 2 題（10%）｜(a) 6% 造成執行中行程非自願放棄 CPU 的三種情況，並說明它會被放入哪個佇列 (b) 4% 從 processor affinity 的角度解釋 warm cache
- 第 3 題（10%）｜(a) 6% 處理死結的三種常見方式（預防／避免、偵測與復原、忽略） (b) 4% 從記憶體管理角度解釋 copy-on-write
- 第 4 題（10%）｜典型的 sector sparing（磁區備援）交易包含哪五個步驟
資料結構部分（5–9）
- 第 5 題（10%）｜(a) 5%
x=12, y=25，求x ^ y & ~x | y << 2的輸出 —— 要非常小心運算子優先序（~><<>&>^>|） (b) 5% 一支帶static int count的遞迴函式mystery(arr, 3)，陣列為 {15, 5, 20, 8, 30}，只累加大於 10 的元素。注意 static 變數跨呼叫累積 - 第 6 題（10%）｜給 inorder
ABCDEFGHIJ與 postorder，求 preorder - 第 7 題（10%）｜大小 M = 11 的雜湊表、double hashing：h1(k) = k mod 11、h2(k) = 7 − (k mod 7)，依序插入 11, 33, 66, 7, 77，畫出最終的表格狀態
- 第 8 題（10%）｜給 adjacency matrix：(a) 8% 從頂點 A 出發跑 Prim，寫出邊加入的順序（用權重表示） (b) 2% 用 adjacency list + binary heap 實作 Prim 的時間複雜度（O(E log V)）
- 第 9 題（10%，5 小題各 2%）｜bubble／insertion／quick／merge／heap sort 的最壞時間複雜度
這份考卷的難點
- 第 5(a) 的運算子優先序（5 分）是最容易失分的地方：
x ^ y & ~x | y << 2實際上是x ^ (y & (~x)) | (y << 2)，再依^先於|結合。 - 第 7 題的 double hashing 中 11, 33, 66, 77 都是 11 的倍數，h1 全部撞在索引 0，要靠 h2 逐一探測 —— 這是刻意設計的極端碰撞。
- 第 1 題的填空 20 分橫跨 OS 全書，其中「resource holding 蘊含 hold and wait」這格需要對死結四條件的關係有精確理解。
- 第 2(a) 要同時說出三種情況與對應的佇列，只寫情況拿不到滿分。
準備建議
- 115 年的資料結構部分是十年來最標準的一次（走訪重建、double hashing、Prim、排序複雜度），把基本功練穩就能拿滿 50 分
- C 運算子優先序（115 第 5(a) 題）務必背熟，中山連年在這裡設陷阱
- 填空題連三年出現（113、114、115 各 20 分），是投報率最高的準備項目
- double hashing 的 h2 設計（h2(k) = 7 − (k mod 7) 永不為 0）是重點，中山 110、115 都考過自訂 rehash