114 中山資工所軟體考點分析

題型與配分

科目名稱「作業系統與資料結構」【資工系碩士班甲組】，題號 434003，考試時間 100 分鐘，不可以使用計算機（問答申論題），全卷 2 頁、8 題、100 分。

逐題考點

資料結構部分（1–4，50%）

• 第 1 題（15%）｜(a) 6% a=2, b=13，一段 for (c=1; b>0; b = b>>1) { if (b%2==1) c*=a; a*=a; } 的輸出 —— 這就是快速冪，算的是 2¹³ = 8192 (b) 9% 一個 64 元素陣列跑三輪 a[j] = a[j] + a[j+c]（c 依序為 1, 2, 4），問 a[0]、a[5]、a[14] 的值。這是 prefix sum 的倍增寫法
• 第 2 題（10%）｜輸入 642, 374, 73, 29, 284, 252 做 radix sort（base 10）：(a) 5% 第一趟後的序列 (b) 5% 第二趟後的序列
• 第 3 題（10%）｜給一棵 AVL 樹：(a) 5% 插入 1 後的樹 (b) 5% 改成插入 4（不插入 1）後的樹。兩題獨立，不連動
• 第 4 題（15%）｜合法括號序列計數：p(n) 為 n 對括號的合法字串數，已知 p(0)=1、p(1)=1、p(2)=2：
• (a) 5%｜求 p(3)（答案 5）
• (b) 10%｜寫出 n ≥ 3 時的遞迴關係式 —— 答案是 Catalan 的卷積形式 p(n) = Σ_k=0ⁿ⁻¹ p(k)·p(n−1−k)

作業系統部分（5–8，50%）

• 第 5 題（10%）｜(a) 6% 除了名稱外，檔案的其他六個常見屬性並簡述 (b) 4% interrupt chaining 如何運作
• 第 6 題（10%）｜(a) 6% 解決 critical-section 問題的三種常見硬體支援（disable interrupt、test-and-set、compare-and-swap） (b) 4% 兩種基本的 IPC 模型（共享記憶體、訊息傳遞）
• 第 7 題（10%）｜說明 TLB 運作的五個步驟
• 第 8 題（20%，10 格各 2%）｜填空：daisy chain、行程記憶體佈局的 heap、race condition、死結的四個條件之一（hold and wait）、reentrant code、inverted page table 的 address-space identifier、HDD 隨機存取時間的 rotational latency、turnaround time、Pthreads 是 POSIX 標準、swap space 的 raw partition

這份考卷的難點

1. 第 1(b) 的倍增前綴和（9 分）要模擬三輪、每輪 16 次加法的結果，必須非常有耐心地追蹤陣列變化。
2. 第 4(b) 的 Catalan 卷積式（10 分）不能只寫出 p(3) = 5，要能寫出通式並說明「以第一個左括號配對的右括號位置」來拆分的思路。
3. 第 1(a) 的快速冪要看出它在算 a^b，而不是逐步模擬（b 是 13 = 1101₂）。
4. 填空題 20 分橫跨 OS 全書，daisy chain、reentrant code、raw partition 這些名詞不常在課堂強調。

準備建議

• Catalan number 在中山考了兩次（111 第 2 題的 stack 序列、114 第 4 題的括號序列），卷積遞迴式要能默寫
• 位元技巧與快速冪（114 第 1(a) 題）是中山每年必有的送分題，b>>1 搭配 b%2==1 的模式要一眼認出
• 填空題 20 分是穩定的得分區（113、114 連兩年），把 Silberschatz 每章的粗體名詞整理一遍，投報率極高
• Radix sort 的逐趟結果、AVL 的旋轉都是中山年年出現的基本題