112 中山資工所考古題詳解｜軟體考點分析

題型與配分

全卷 2 頁、9 題、100 分，考試時間 100 分鐘，不可使用計算機，全部是問答申論題。卷首註明：題目不清楚或需要做某些假設時，在答案開頭清楚說明假設。

第 1 到 4 題共 50 分，第 5 到 9 題共 50 分。

逐題考點

• 第 1 題（15%）｜寫出下列 C 程式的輸出：(a) 5% int a=40, b=24; printf("%d \n", (a&(~b))|((~a)&b));，~ 為 bitwise NOT、& 為 AND、| 為 OR (b) 10% array b[] = {30, 31, …, 42} 與函式 h(int i)：i == 1 時印出 b[i] 並回傳 b[1]；i 為偶數時印出 b[i]、做 b[i/2] += i/2、回傳 h(i/2)；i 為奇數時做 b[i+1]++、回傳 h(i+1)；主程式呼叫 h(9)
• 第 2 題（15%）｜給 insertion sort 的 pseudo-code（輸入存在 a[1] 到 a[n]，for i = 2 to n，j = i，while j ≥ 2 且 a[j] < a[j−1] 時 Swap(a[j], a[j−1])、j = j−1）：(a) 5% 輸入為 3、9、6、5、8、2 時，Swap() 要執行幾次 (b) 5% 輸入是 {1,2,…,n} 的 permutation，什麼 permutation 使 Swap() 執行次數最少，共幾次 (c) 5% 什麼 permutation 使 Swap() 執行次數最多，共幾次
• 第 3 題（10%）｜6 個資料 A、B、C、D、E、F（A < B < … < F）的搜尋頻率分別為 4、9、1、6、8、7，畫出使搜尋成本最小的 optimal BST
• 第 4 題（10%）｜郵票有 1、2、3、4、5 元五種，要貼出剛好 j 元，g(i,j) 為只用 1 到 i 元的郵票湊出 j 元的組合數（1 ≤ i ≤ 5、1 ≤ j ≤ n）。例如 g(2,3) = 2、g(3,4) = 4。今天 3 元與 4 元郵票賣完了，其他郵票數量無限，寫出計算 g(i,j) 的 recurrence，可以假設 g(i,0) = 1，且 1 ≤ i ≤ 5、j ≤ −1 時 g(i,j) = 0
• 第 5 題（10%）｜(a) 7% process control block 的七個常見組成 (b) 3% mutex、semaphore 與 condition variable 的用途
• 第 6 題（10%）｜(a) 6% 指令與資料在 compile time、load time、execution time 繫結到記憶體位址的差別 (b) 4% 如何用 working-set model 解決 thrashing
• 第 7 題（10%）｜(a) 6% 檔案的 sequential、direct、index 三種存取方式 (b) 4% file system 的 consistency semantics
• 第 8 題（10%）｜(a) 4% deadlock prevention 如何運作 (b) 3% real-time system 關心的三種 latency (c) 3% distributed file system 不使用 caching 的三個理由
• 第 9 題（10%）｜說明下列名詞：(a) vectored I/O (b) safety-critical system (c) logic bomb (d) turnaround time (e) race condition，各 2%

作答時要注意的地方

1. 第 1、2 題各 15 分，各分成小題；第 5 到 8 題每題都是 (a)(b) 或 (a)(b)(c) 的小題。
2. 第 1(b) 的函式會修改 array 元素再遞迴。
3. 第 4 題題目給了 g(2,3) 與 g(3,4) 兩個例子，並指定 3 元與 4 元缺貨。
4. 第 2(b)(c) 要回答的是 permutation 的形式與次數兩項。

準備方向

• 位元運算的輸出（112 第 1(a) 題），110 第 6 題、113 第 1(a) 題、115 第 5(a) 題也有，114 第 1(a) 題用到位移。
• 遞迴與 array 的輸出追蹤（112 第 1(b) 題），111 第 1 題、113 第 1(b) 題、114 第 1(b) 題、115 第 5(b) 題也有。
• 排序的次數與複雜度（112 第 2 題），109 第 9 題、113 第 3 題、114 第 2 題、115 第 9 題也有排序。
• optimal BST（112 第 3 題）。
• 計數的 recurrence（112 第 4 題），113 第 4 題、114 第 4 題也有。
• PCB、synchronization、address binding、file system、deadlock（112 第 5 到 8 題），108 第 3、4 題也是同類的作業系統問答，113 第 5 到 7 題、114 第 5 到 7 題、115 第 2 到 4 題也是問答。
• 名詞解釋（112 第 9 題），113 年起改成每年 20 分的填空題。