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

題型與配分

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

第 1 到 4 題共 50 分，第 5 到 8 題共 50 分。這一年第一次出現填空題。

逐題考點

• 第 1 題（15%）｜寫出下列 C 程式的輸出：(a) 5% int d=48; printf("%d \n", (d&(-d+1)) + 3);，& 為 bitwise AND (b) 10% array x[] = {8, 5, 3, 9, 7, 4, 6, 2}，函式 max(left, right) 取 mid = (left+right)/2，left == right 時 b = x[mid]，否則 c = max(left, mid)，若 c > max(mid+1, right) 則 b = c，否則 b = max(mid+1, right)，每次都 cout << b << endl 並回傳 b，主程式呼叫 max(1,5)
• 第 2 題（10%）｜2D array N 依表格的排法存放非負整數（N[0][0] = 0、N[0][1] = 3、N[0][2] = 4、N[1][0] = 2 等，表格第一列為 0、3、4、15、16、…，第二列 1、2、5、14、17、…，第三列 8、7、6、13、18、…，第四列 9、10、11、12、19、…，第五列 24、23、22、21、20、…），寫出 N[i][j] 以 i、j 表示的通式
• 第 3 題（10%）｜判斷 bubble sort、heap sort、quick sort、merge sort、radix sort 各是否為 stable sort
• 第 4 題（15%）｜高 2 單位、寬 m 單位的區塊（2×m）可以拆成 L 形（3 個單位）與正方形（1 個單位）兩種小塊，例如 2×1 只有一種拆法（兩個正方形），2×2 有五種拆法，d(m) 為 2×m 區塊的拆法數，已知 d(1) = 1、d(2) = 5，假設 d(0) = 1：(a) 5% d(3) 的值 (b) 10% 把 d(m) 寫成 a·d(m−1) + b·d(m−2) + c·d(m−3)（m ≥ 4），求 a、b、c
• 第 5 題（10%）｜(a) 6% real-time system 中轉換位址的三種方法 (b) 4% non-maskable 與 maskable interrupt 的差別
• 第 6 題（10%）｜(a) 6% 五個 process P1 到 P5 在時間 0 到達，burst time 為 10、1、2、1、5，priority 為 3、1、3、4、2（數字小的 priority 高），求 round-robin（quantum = 1）、SJF 與 non-preemptive priority 三種 scheduling 的平均 waiting time (b) 4% 記憶體存取時間 150 ns、平均 page fault 時間 60,000 ns，要讓 demand paging 的 effective access time 低於 175 ns，page fault rate 要多少。題目註明答案要列出計算過程，否則不給分
• 第 7 題（10%）｜每個 transaction T_i 有唯一的 timestamp TS(T_i)，每個資料項 Q 有 W-timestamp(Q) 與 R-timestamp(Q)，說明 timestamp ordering protocol 如何檢查 nonserial schedule 是否為 conflict serializable，提示可以說明 T_i 發出 read(Q) 與 write(Q) 時協定如何運作
• 第 8 題（20%）｜填空（每格 2 分）：(a) 每個 thread 用來指示下一個要執行的指令位址的東西 (b) critical-section 問題的解法必須滿足的三項要求中，除了 mutual exclusion 與 progress 以外的一項 (c) 可視為 page table 的 cache 的 buffer (d) 把邏輯 page 對應到記憶體實體 page frame 的單元 (e) process 花在 paging 的時間多於執行的情形 (f) 含有 file system 的實體的通稱 (g) RAID level 6 使用的冗餘方式 (h) role-based access control 中，執行某個 system call 或使用其選項的權利 (i) AES 的金鑰長度，128、？、256 位元 (j) 藉修改可能被用來偵測的系統部分來躲避偵測的病毒

作答時要注意的地方

1. 第 1、4 題各 15 分，各分成兩個小題；第 8 題 20 分，共 10 格。
2. 第 6 題要列出計算過程，只寫答案不給分。
3. 第 1(b) 要輸出的是每一層呼叫印出的 b，不是只有最後的回傳值。
4. 第 4 題題目給了 d(1)、d(2) 的值，也說明可假設 d(0) = 1。
5. 第 2 題題目文字寫 N[1][0] = 2，表格裡 N[1][0] 的位置是 1，表格的第二列是 1、2、5、14、17。

準備方向

• 位元運算的輸出（113 第 1(a) 題），110 第 6 題、112 第 1(a) 題、115 第 5(a) 題也有，114 第 1(a) 題用到位移。
• 遞迴程式的輸出追蹤（113 第 1(b) 題），111 第 1(b) 題、112 第 1(b) 題、115 第 5(b) 題也有。
• 排序的性質（113 第 3 題），109 第 9 題、112 第 2 題、114 第 2 題、115 第 9 題也有排序。
• 推導 recurrence（113 第 4 題），112 第 4 題、114 第 4 題也有。
• scheduling 的平均 waiting time（113 第 6(a) 題），109 第 1 題也有。
• Page fault 率與 effective access time（113 第 6(b) 題），107 第 2(4) 題同型，106 第 3 題、110 第 3 題、111 第 6 題也是存取時間的計算。
• Timestamp ordering（113 第 7 題）。
• 填空題（113 第 8 題），114 第 8 題、115 第 1 題也有每年 20 分的填空題。