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

題型與配分

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

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

逐題考點

• 第 1 題（15%）｜寫出下列 C 程式的輸出：(a) 6% int a=2, b=13, c; for (c=1; b>0; b = b>>1) { if (b%2 == 1) c = c*a; a = a*a; } printf("%d \n", c); (b) 9% int a[64] = {0,1,2,…,15}; int c = 1;，for i = 1 to 3：for j = 0 to 15 做 a[j] = a[j] + a[j+c]，每輪結束 c *= 2，最後 printf 印出 a[0]、a[5]、a[14]
• 第 2 題（10%）｜radix sort 的輸入為 642、374、73、29、284、252，基數為 10：(a) 5% 第一趟結束後的序列 (b) 5% 第二趟結束後的序列
• 第 3 題（10%）｜給一棵 AVL tree（根 8，左子樹 3，其下為 2 與 6，右子樹 9）：(a) 5% 插入新元素 1 後的 AVL tree (b) 5% 插入新元素 4 後的 AVL tree（不插入 1）
• 第 4 題（15%）｜只含左右括號的字串中，每一對左括號與右括號，左括號要先出現，其間可以夾零對或多對括號，例如 ()()、(())、(())() 合法，)(、())(、))()(( 不合法。p(n) 為 n 對括號的合法字串數，p(0) = 1、p(1) = 1、p(2) = 2：(a) 5% p(3) 的值 (b) 10% n ≥ 3 時計算 p(n) 的 recurrence relation
• 第 5 題（10%）｜(a) 6% 除了名稱以外，檔案的其他六個常見屬性並簡述 (b) 4% interrupt chaining 如何運作
• 第 6 題（10%）｜(a) 6% 處理 critical-section 問題的三種常見硬體支援 (b) 4% 兩種基本的 IPC 模型
• 第 7 題（10%）｜說明 TLB 運作的五個步驟
• 第 8 題（20%）｜填空（每格 2 分）：(a) 裝置 A 接到 B、B 接到 C、C 接到電腦上的埠，這種安排稱為什麼 chain (b) process 的記憶體配置包含 text、data、？與 stack 區段 (c) 多個 process 同時存取同一份資料時，執行結果取決於存取順序的情形 (d) deadlock 的四個條件：mutual exclusion、？、no preemption、circular wait (e) 不會自我修改、執行中不會改變的程式碼 (f) inverted page table 每個項目要存放的識別碼 (g) HDD 的隨機存取時間由 seek time 與什麼組成 (h) 從 process 提交到完成的時間間隔 (i) thread 的 Pthreads 是一種什麼 (j) 可以建在不放 file system 與目錄結構的 partition 中的空間

作答時要注意的地方

1. 第 1、4 題各 15 分，各分成兩個小題；第 8 題 20 分，共 10 格。
2. 第 1(b) 的 printf 在兩層迴圈結束後才執行一次。
3. 第 3 題 (a)(b) 各自對題目給的那棵 AVL tree 插入一個元素，(b) 不包含 (a) 的 1。
4. 第 4 題題目給了 p(0)、p(1)、p(2) 與 ()()、(()) 的例子。

準備方向

• 迴圈與位元運算的輸出（114 第 1(a) 題），110 第 6 題、112 第 1(a) 題、113 第 1(a) 題、115 第 5(a) 題也有位元運算。
• array 與迴圈的追蹤（114 第 1(b) 題），111 第 1 題、112 第 1(b) 題、113 第 1(b) 題也有。
• Radix sort（114 第 2 題），109 第 9 題、112 第 2 題、113 第 3 題、115 第 9 題也有排序。
• AVL tree 的插入（114 第 3 題），110 第 9 題也有。
• 推導 recurrence（114 第 4 題），112 第 4 題、113 第 4 題也有，111 第 2 題的 stack 輸出序列也是計數題。
• critical section 與 synchronization（114 第 6(a) 題），108 第 3 題、112 第 5(b) 題、113 第 8(b) 題也有。
• IPC 的兩種模型（114 第 6(b) 題），107 第 1(1) 題相同。
• TLB（114 第 7 題），106 第 3 題、110 第 3 題、111 第 6 題也有 TLB hit rate。
• 填空題（114 第 8 題），113 第 8 題、115 第 1 題也有每年 20 分的填空題。