資工所考古題詳解中山資工所考古題詳解軟體十年大統整（106–115）
各章配分
表中數字是各題的卷面配分，依主題加總。有子題的照子題分，沒有子題的整題算在主要考點。作業系統、資料結構與演算法、C 程式三個領域分開列，各自依十年合計排序，顏色越深，占當年總分的比例越高。fork、pipe、Pthreads 的程式輸出算在作業系統，遞迴的程式輸出算在 Algorithm Design 的 Recursion，bitwise operation 與 pointer 算在 Programming。112–114 年自行推導的計數與 recurrence 算在 Dynamic Programming（111 年第 2 題 stack 輸出序列計數算在 Stack & Queue）。
| 章／細項 | 106 | 107 | 108 | 109 | 110 | 111 | 112 | 113 | 114 | 115 | 合計 | 占比 | 年數 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Operating Systems | 50 | 64 | 60 | 70 | 50 | 50 | 50 | 50 | 50 | 50 | 544 | 54% | 10 |
| Storage & File Systems | 20 | 12 | 30 | 20 | 20 | 10 | 4 | 10 | 14 | 140 | 14% | 9 | |
| Disk Scheduling & Management | 10 | 6 | 20 | 10 | 10 | 4 | 12 | 72 | 7% | 7 | |||
| File Allocation & Free Space | 10 | 10 | 10 | 10 | 40 | 4% | 4 | ||||||
| File System Design & Semantics | 4 | 10 | 2 | 6 | 2 | 24 | 2% | 5 | |||||
| RAID | 2 | 2 | 4 | <1% | 2 | ||||||||
| Memory Management | 10 | 9 | 8 | 10 | 10 | 30 | 6 | 4 | 16 | 103 | 10% | 9 | |
| Paging, Page Tables & TLB | 10 | 9 | 4 | 10 | 10 | 20 | 4 | 14 | 81 | 8% | 8 | ||
| Contiguous Allocation & Fragmentation | 4 | 10 | 14 | 1% | 2 | ||||||||
| Address Binding & Memory Layout | 6 | 2 | 8 | <1% | 2 | ||||||||
| Processes & Threads | 10 | 5 | 8 | 10 | 10 | 7 | 2 | 6 | 58 | 6% | 8 | ||
| fork / wait / exec | 10 | 10 | 20 | 2% | 2 | ||||||||
| IPC & Signals | 4 | 10 | 4 | 18 | 2% | 3 | |||||||
| Process States & Context Switch | 4 | 7 | 11 | 1% | 2 | ||||||||
| Threads & Concurrency | 1 | 4 | 2 | 2 | 9 | <1% | 4 | ||||||
| Virtual Memory | 10 | 6 | 4 | 10 | 10 | 4 | 6 | 6 | 56 | 6% | 8 | ||
| Page Replacement | 10 | 2 | 10 | 10 | 32 | 3% | 4 | ||||||
| Virtual Memory & Demand Paging | 4 | 4 | 6 | 14 | 1% | 3 | |||||||
| Thrashing & Working Set | 4 | 4 | 2 | 10 | 1% | 3 | |||||||
| Protection & Security | 15 | 20 | 2 | 6 | 4 | 47 | 5% | 5 | |||||
| Synchronization | 7 | 8 | 5 | 12 | 8 | 2 | 42 | 4% | 6 | ||||
| Critical Section & Race Condition | 7 | 4 | 2 | 2 | 8 | 2 | 25 | 2% | 6 | ||||
| Classic Problems & Transactions | 10 | 10 | 1% | 1 | |||||||||
| Semaphores, Mutex & Monitors | 4 | 3 | 7 | <1% | 2 | ||||||||
| CPU Scheduling | 1 | 10 | 5 | 12 | 2 | 12 | 42 | 4% | 6 | ||||
| Scheduling Algorithms | 10 | 2 | 6 | 2 | 12 | 32 | 3% | 5 | |||||
| Real-time Scheduling | 1 | 3 | 6 | 10 | 1% | 3 | |||||||
| I/O Systems | 3 | 8 | 2 | 4 | 6 | 2 | 25 | 2% | 6 | ||||
| Deadlock | 5 | 4 | 4 | 2 | 8 | 23 | 2% | 5 | |||||
| Deadlock Characterization & Handling | 5 | 4 | 4 | 2 | 8 | 23 | 2% | 5 | |||||
| OS Structure | 1 | 2 | 2 | 5 | <1% | 3 | |||||||
| OS Structure & Design Goals | 1 | 2 | 2 | 5 | <1% | 3 | |||||||
| Other | 3 | 3 | <1% | 1 | |||||||||
| Distributed Systems | 3 | 3 | <1% | 1 | |||||||||
| Data Structures & Algorithms | 40 | 35 | 40 | 30 | 40 | 45 | 45 | 45 | 35 | 45 | 400 | 40% | 10 |
| Algorithm Design | 10 | 15 | 10 | 30 | 25 | 15 | 5 | 110 | 11% | 7 | |||
| Recursion | 10 | 10 | 10 | 10 | 10 | 5 | 55 | 6% | 6 | ||||
| Dynamic Programming | 20 | 15 | 15 | 50 | 5% | 3 | |||||||
| Greedy | 5 | 5 | <1% | 1 | |||||||||
| Sorting & Searching | 10 | 4 | 4 | 10 | 15 | 15 | 10 | 10 | 10 | 88 | 9% | 9 | |
| Sort Comparison & Lower Bound | 4 | 10 | 10 | 10 | 34 | 3% | 4 | ||||||
| Elementary Sorts | 1 | 15 | 16 | 2% | 2 | ||||||||
| Heapsort | 15 | 15 | 2% | 1 | |||||||||
| Quicksort | 10 | 3 | 13 | 1% | 2 | ||||||||
| Linear-time Sorts | 10 | 10 | 1% | 1 | |||||||||
| Trees | 21 | 12 | 25 | 10 | 10 | 10 | 88 | 9% | 6 | ||||
| AVL Tree | 15 | 10 | 25 | 2% | 2 | ||||||||
| Tree Basics & Traversal | 4 | 10 | 10 | 24 | 2% | 3 | |||||||
| B-Tree / B+ Tree | 10 | 8 | 18 | 2% | 2 | ||||||||
| Binary Search Tree | 2 | 10 | 12 | 1% | 2 | ||||||||
| Red-Black Tree | 5 | 4 | 9 | <1% | 2 | ||||||||
| Linear Structures | 10 | 4 | 4 | 10 | 10 | 38 | 4% | 5 | |||||
| Infix / Postfix | 10 | 3 | 4 | 17 | 2% | 3 | |||||||
| Stack & Queue | 1 | 10 | 11 | 1% | 2 | ||||||||
| Array & Linked List | 10 | 10 | 1% | 1 | |||||||||
| Hashing | 1 | 4 | 15 | 10 | 30 | 3% | 4 | ||||||
| Collision Resolution | 4 | 15 | 10 | 29 | 3% | 3 | |||||||
| Hash Functions | 1 | 1 | <1% | 1 | |||||||||
| Shortest Paths & MST | 5 | 10 | 15 | 2% | 2 | ||||||||
| Minimum Spanning Tree | 5 | 10 | 15 | 2% | 2 | ||||||||
| Heaps | 5 | 8 | 13 | 1% | 2 | ||||||||
| Advanced Heaps | 5 | 8 | 13 | 1% | 2 | ||||||||
| Complexity Analysis | 10 | 10 | 1% | 1 | |||||||||
| Recurrences | 10 | 10 | 1% | 1 | |||||||||
| Graph Traversal | 8 | 8 | <1% | 1 | |||||||||
| Representation & BFS / DFS | 4 | 4 | <1% | 1 | |||||||||
| Connectivity | 4 | 4 | <1% | 1 | |||||||||
| Programming | 10 | 10 | 5 | 5 | 5 | 15 | 5 | 55 | 6% | 7 | |||
| C / C++ Basics | 10 | 10 | 5 | 5 | 5 | 15 | 5 | 55 | 6% | 7 | |||
| Expressions & Operators | 10 | 5 | 5 | 6 | 5 | 31 | 3% | 5 | |||||
| Pointers | 10 | 5 | 15 | 2% | 2 | ||||||||
| Control Flow & Loops | 9 | 9 | <1% | 1 | |||||||||
| Computer Organization | 1 | 1 | <1% | 1 | |||||||||
| Memory Hierarchy | 1 | 1 | <1% | 1 | |||||||||
| Cache Organization | 1 | 1 | <1% | 1 |
作業系統這邊 Storage & File Systems 合計 140 分最多（i-node、disk scheduling、讀檔時間），Memory Management 103 分次之。資料結構這邊 Algorithm Design 110 分，包括 C 程式的遞迴追蹤與 112–114 年的計數推導；Sorting & Searching 十年考九年。
四個固定題型
1. C 程式輸出題（106 年與 109 到 115 年都有，10 到 20 分）
110、112、113、115 年各有一小題考 bitwise operation 或運算子，114 年是位移的迴圈，106、109、111 年沒有。另一小題考遞迴、pointer 或 system call。107、108 年沒有程式輸出題。
| 年度 | bitwise operation 與運算子 | 其他 |
|---|---|---|
| 106 | — | fork 與 Pthreads 的輸出（另有第 6 題寫出 array pointer 的宣告） |
| 109 | — | fork 與 Pthreads 的輸出 |
| 110 | (a & (-a)) >> 2、XOR 運算式 | pipe、fork、dup 與 exec |
| 111 | — | pointer 算術 &e[2]+4 與 &e[2+4]、全排列遞迴 |
| 112 | (a&~b)|(~a&b) | 帶副作用的遞迴 h(9) |
| 113 | (d & (-d+1)) + 3 | divide and conquer 求最大值，要寫出各層輸出 |
| 114 | for(c=1;b>0;b>>=1) 的迴圈 | array 的多輪累加 |
| 115 | x ^ y & ~x | y << 2 | 帶 static 變數的遞迴 |
106 年第 1 題與 109 年第 4 題都是 fork、waitpid 加上 Pthread 把傳入整數減 1 的程式，fork 的層數與印出的運算不同。
2. 作業系統的計算題
| 題型 | 出現年度 |
|---|---|
| disk scheduling（總移動距離或服務順序） | 107（SSTF 與 C-LOOK，6 分）、109（五種，20 分）、110（五種，10 分） |
| UNIX i-node 的檔案大小或區塊數 | 106、109、110、111 |
| TLB hit rate（要達到某平均開銷） | 106、110、111 |
| 磁碟讀檔時間（隨機放置與叢集放置） | 106、111 |
| page table 項目數 | 109、111 |
| 2D array 的 page fault 計數 | 109、110 |
| page fault 次數的上下界 | 106 |
| CPU scheduling 的 average waiting time | 109、113 |
| page fault 率與 effective access time | 107、113 |
| bit map 的大小 | 111 |
這幾類在 106 年與 109 到 111 年密集出現。106 第 3 題與 110 第 3 題、111 第 6 題的 TLB 題，以及 106 第 5 題與 111 第 7 題的讀檔時間題，都是同一個題型換數字；106 第 4 題與 109 第 5 題的 i-node 只差區塊大小。
3. 自行推導計數與 recurrence
- 111 第 2 題：stack 的不可能輸出序列個數
- 112 第 4 題：郵票組合數 g(i,j)，3 元與 4 元缺貨
- 113 第 4 題：2×m 區塊用 L 形與正方形拆分的方法數 d(m)
- 114 第 4 題：n 對括號的合法序列數 p(n)
106 第 8 題是給定 recurrence 求 closed form，113 年第 2 題另有依表格排列的 array N[i][j] 的通式。
4. 填空題（113 年起，每年 20 分）
113、114、115 連三年各出 10 格、每格 2 分，涵蓋 process 與 thread、synchronization、scheduling、記憶體管理、deadlock、儲存裝置、檔案、安全等主題。113、114 年放在第 8 題，115 年放在第 1 題。
名詞解釋的重複題
107 年與 108 年都以名詞解釋為主，有幾小題幾乎一字不差：
| 題目 | 出現年度 |
|---|---|
| 除了非紅即黑，還要怎麼處理才會成為 red-black tree | 107 第 5(4) 題、108 第 1(3) 題 |
| paging 的兩個好處 | 107 第 2(2) 題、108 第 4(1) 題 |
| deadlock prevention 與 deadlock avoidance 的差別 | 107 第 1(4) 題、108 第 3(2) 題 |
| principle of least privilege 與 Sun（Solaris 10）的實作 | 107 第 4(1) 題、108 第 5(1) 題 |
| 兩種基本的 IPC 模型 | 107 第 1(1) 題、114 第 6(b) 題 |
| B*-tree | 107 第 6(2) 題、108 第 2(3) 題（與 B+-tree 的差別） |
優先準備的五個主題
- 作業系統全書。各年度作業系統都佔 50 分以上，scheduling、記憶體、file system、I/O、deadlock、synchronization 與安全都出現過。
- C 程式輸出（bitwise operation、運算子優先序、遞迴追蹤、fork）。106 年與 109 到 115 年都有。
- 填空題的作業系統名詞。113 年起每年 20 分。
- 計數與 recurrence 的自行推導。111 到 114 年每年一題。
- Sorting（複雜度、穩定性、逐趟結果、quicksort 分析）。106 到 109 年與 111 到 115 年都有，111 年是 heap sort 的建堆過程。
考試形式
- 108 年起卷面印考試時間 100 分鐘，106、107 年卷面沒有印
- 不可以使用計算機
- 卷面名稱是問答申論題，沒有選擇題，卷面沒有標示倒扣；107 年第 7 題是 10 個 O／X 是非題
- 卷首註明「若題目不清楚或你認為需要做某些假設，請在答案開頭清楚說明你的假設」的是 106 年與 109 到 114 年，107、108、115 年沒有印
- 全卷 2 到 3 頁，108 年 5 大題 25 小題，其餘年度 7 到 10 大題
作業系統與資料結構的比重
| 年度 | 作業系統 | 資料結構與程式 | 題數 | 內容 |
|---|---|---|---|---|
| 106 | 50% | 50% | 10 題 | 作業系統五題都是計算或程式輸出，另一半是 C pointer、Ackermann、recurrence、quicksort、運算式轉換 |
| 107 | 60%（另有是非 5 分） | 30%（另有是非 5 分） | 7 大題 | 以名詞解釋與說明為主，第 4 題 15 分是保護與安全，第 7 題 10 個是非題 |
| 108 | 60% | 40% | 5 大題 25 小題 | 以名詞解釋與說明差異為主，另有 prefix 轉 infix、BFS／DFS traversal、Fibonacci heap 的 decrease-key，含 20 分保護與安全 |
| 109 | 70% | 30% | 10 題 | 作業系統以計算題為主 |
| 110 | 50% | 50% | 9 題 | 第 8、9 題各 15 分 |
| 111 | 50% | 50% | 9 題 | 前 4 題程式與資料結構，後 5 題作業系統計算 |
| 112 | 50% | 50% | 9 題 | 作業系統第 5 到 9 題都是解釋名詞與說明 |
| 113 | 50% | 50% | 8 題 | 第一次出現 20 分填空題 |
| 114 | 50% | 50% | 8 題 | 填空題延續 |
| 115 | 50% | 50% | 9 題 | 填空題延續，放在第 1 題 |
比重以各題配分加總。fork、pipe、Pthreads 這類 system call 的程式輸出（106 第 1 題、109 第 4 題、110 第 1 題）算在作業系統，bitwise operation、pointer、遞迴的程式輸出與資料結構歸在右欄。107 年第 7 題的是非題，第 1 到 5 小題是資料結構，第 6 到 10 小題是作業系統與 cache。保護與安全在 107 年第 4 題（15 分）、108 年第 5 題（20 分）整題出現，之後在 112 年第 9(c) 題、113 年第 8 題 (h)(i)(j)、115 年第 1 題 (i)(j) 以名詞或填空的形式出現。
給 116 年考生的準備方向
- 作業系統與資料結構都要準備，作業系統各年度佔 50 到 70 分，資料結構歸在其餘題目。
- 108 年起卷面印考試時間 100 分鐘，109 到 115 年是 8 到 10 大題，108 年是 5 大題 25 小題。
- 106 到 115 年沒有出現過 NP、approximation algorithm、複雜度證明。
- 113、114、115 年連續三年都有 20 分的填空題。
- 卷面名稱是問答申論題，卷面沒有標示倒扣。107 年第 2(4)、5(2) 題與 113 年第 6 題卷面註明要列出計算過程，113 年第 6 題還寫明否則不給分。
- 106 年與 109 到 114 年卷首允許說明假設，題目條件不清楚時可以在答案開頭寫出假設。107、108、115 年卷首沒有印這句。
- 106、107 年的 TLB、i-node、讀檔時間、名詞解釋題，在 108 到 114 年都有換數字或原句再考的題目，可以和後面幾年一起練。
本頁的題型、配分都取自各年度試卷上的標示，各章配分是逐題分類後加總的。如果發現有誤，歡迎來信指正。
最後更新：2026-10-23