中山資工所軟體考古題八年大統整（108–115）
考試形式（八年不變）
- 考試時間 100 分鐘
- 不可以使用計算機
- 全部是問答申論題，沒有選擇題、沒有倒扣
- 卷面固定註明：「若題目不清楚或你認為需要做某些假設，請在答案開頭清楚說明你的假設」（109–114）
- 全卷只有 2–3 頁，但題數多（8–10 大題、20–25 個小題）
時間壓力是中山最大的特點：100 分鐘要寫完 20 個以上的小題，平均每題 4–5 分鐘。
OS 與資料結構的比重變化
| 年度 | 作業系統 | 資料結構 | 題數 | 特色 |
|---|---|---|---|---|
| 108 | 60% | 40% | 25 小題 | 全是「解釋名詞／說明差異」，含 20 分資訊安全 |
| 109 | 70% | 30% | 10 題 | OS 全面轉為計算題 |
| 110 | 50% | 50% | 9 題 | 比重最平衡 |
| 111 | 45% | 55% | 9 題 | 資料結構比重最高 |
| 112 | 50% | 50% | 9 題 | OS 回到解釋名詞 |
| 113 | 60% | 40% | 8 題 | 首次出現 20 分填空題 |
| 114 | 55% | 45% | 8 題 | 填空題延續 |
| 115 | 50% | 50% | 9 題 | 填空題延續，資料結構回到最標準 |
108 年是唯一一次考資訊安全（整整 20 分：病毒與蠕蟲、setuid、masquerading、replay attack、non-repudiation），之後沒有再出現。
中山的四個固定題型
這四類題目每年都出現，是最值得針對性準備的：
1. C 程式輸出題（每年 10–15 分）
八年全中，而且風格穩定 —— 一小題考位元運算、一小題考遞迴追蹤：
| 年度 | 位元運算小題 | 遞迴／指標小題 |
|---|---|---|
| 110 | (a & (-a)) >> 2（取最低位的 1） | — |
| 111 | — | 指標算術 &e[2]+4 vs &e[2+4]、全排列遞迴 |
| 112 | (a&~b)|(~a&b)（就是 XOR） | 帶副作用的遞迴 h(9) |
| 113 | (d & (-d+1)) + 3 | 分治求最大值，要寫出所有中間輸出 |
| 114 | 快速冪 for(c=1;b>0;b>>=1) | 倍增前綴和 |
| 115 | x ^ y & ~x | y << 2（考運算子優先序） | 帶 static 變數的遞迴 |
必背：a & (-a) 取最低位的 1、(a&~b)|(~a&b) 是 XOR、C 運算子優先序 ~ > << > & > ^ > |。
2. 作業系統的四類計算題
| 題型 | 出現年度 |
|---|---|
| 磁碟排程（FCFS／SSTF／SCAN／C-SCAN／LOOK／C-LOOK 的總移動距離） | 109、110 |
| UNIX i-node 的最大／最小檔案大小 | 109、110、111 |
| TLB 命中率（要達到某平均開銷需多少命中率） | 110、111 |
| Page table 項目數 / page fault 計數 | 109、110、111 |
這四類在 109–111 年密集出現，公式建議整理成一張表背起來。
3. 自行推導遞迴式（近年重點）
- 111 第 2 題｜stack 的合法／不可能輸出序列（Catalan number）
- 113 第 4 題｜2×m 磚塊用 L 形與正方形分解的方法數 d(m)
- 114 第 4 題｜n 對括號的合法序列數 p(n)（Catalan 的卷積形式）
- 112 第 4 題｜郵票組合計數 g(i,j)（無限背包，且有面額缺貨）
Catalan number 在中山考了兩次（111、114），卷積遞迴式要能默寫。
4. 填空題（113 年起，每年 20 分）
113、114、115 連三年各出 10 格、每格 2 分，全部來自作業系統教科書的粗體名詞：TLB、MMU、thrashing、dispatcher、dirty bit、reentrant code、daisy chain、raw partition、RAID 6 的 P+Q、AES 金鑰長度、polymorphic virus …
這是投報率最高的準備項目 —— 把 Silberschatz 每章的關鍵名詞整理成卡片，20 分幾乎可以全拿。
資料結構主題出現年度
| 主題 | 出現年度 |
|---|---|
| 排序（複雜度／穩定性／radix 逐趟） | 108、109、112、113、114、115 |
| 樹的走訪與重建 | 110、115 |
| AVL 樹 | 110、114 |
| 雜湊（chaining／自訂 rehash／double hashing） | 108、110、115 |
| MST（Kruskal／Prim） | 109、115 |
| Heap（heap sort／Fibonacci heap／binomial heap） | 108、111 |
| BST 插入與刪除 | 111 |
| 最佳二元搜尋樹 | 112 |
| 遞迴式推導（Catalan 等） | 111、112、113、114 |
| 圖的走訪（BFS／DFS） | 108 |
| Huffman tree | 109 |
| **B-tree／B\*-tree／SCC** | 108 |
必守的五個主題
- 作業系統全書 —— 這是中山和其他學校最大的差異，佔了一半以上的分數。Silberschatz 的排程、記憶體、檔案系統、I/O、死結都要讀完整
- C 程式輸出（位元運算＋遞迴追蹤）—— 八年全中，每年 10–15 分，練熟就是穩分
- 填空題的 OS 名詞 —— 113 年起每年 20 分，投報率最高
- 遞迴式的自行推導 —— 近四年的重點，Catalan number 與「枚舉最後一步」的思路要熟
- 排序的複雜度與穩定性 —— 幾乎年年出現，是純記憶分
給 116 年考生的策略
- 先把作業系統讀完整再讀資料結構。 中山的 OS 比重平均 55%，而且很多是可以直接拿分的名詞解釋與填空
- 100 分鐘、20 個以上小題，時間分配比深度更重要。看到不會的題目先跳過，把會的寫完
- 不考演算法設計與證明（NP、近似演算法、複雜度證明都沒出現過），準備時可以把這部分的優先級降低
- 113 年起的 20 分填空題很可能延續，這是最該優先準備的區塊
- 全卷沒有倒扣，每一題都應該寫，就算只寫得出部分觀念也可能拿到部分分數
- 卷面允許「說明你的假設」，題目條件不清楚時要主動寫出假設而不是留白
本頁的題型、配分、科目名稱均直接取自各年度試卷標示；主題出現年度為逐題比對後的整理。若發現有誤，歡迎來信指正。