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

題型與配分

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

第 1 到 4 題共 50 分，是程式與資料結構；第 5 到 9 題共 50 分，是作業系統。

逐題考點

• 第 1 題（15%）｜寫出下列 C 程式的輸出：(a) 5% 函式 f(int v[], int w, int x, int y[], int z[]) 內做 w[2] += 4，再印出 v[0]、w[2]、x[5]、*(y+3)、z[2]；主程式 int e[] = {10,11,…,20}，呼叫 f(&e[2]+4, &e[2+4], e, e+4, &e[2]) (b) 10% 遞迴函式 g(char a[], k, m)：k == m 時印出 a[0] 到 a[m]，否則對 i 從 k 到 m，swap(a[k], a[i])、g(a, k+1, m)、再 swap(a[k], a[i])，主程式 char a[] = "abcde"，呼叫 g(a, 0, 2)
• 第 2 題（10%）｜A、B、C、D 四個符號依序輸入 stack，使用四次 PUSH 與四次 POP，PUSH 與 POP 的所有組合中有些輸出序列不可能出現，分別給出以 A、B、C、D 開頭（AXXX、BXXX、CXXX、DXXX）的不可能序列個數
• 第 3 題（10%）｜依序把 3、6、4、5、2、7、1 放入空的 BST，再刪除 3，刪除非葉節點時以 inorder successor 取代它的位置，畫出刪除 3 之後的樹
• 第 4 題（15%）｜用 heap sort 把 14、4、19、2、18、7、17、9、16、13 排成遞增：(a) 10% 第一階段建 maximum heap，畫出第一階段結束後的 heap 樹 (b) 5% 第二階段輸出第一個最大值並還原 heap 後，畫出 heap 樹
• 第 5 題（10%）｜i-node 有 10 個 direct block 與三層 indirect block，pointer 8 bytes、block 8 KB：(a) 5% 最小檔案需要幾個 block (b) 5% 最大檔案需要幾個 block
• 第 6 題（10%）｜process 的 address space 有 4096 個 page，page table 放在記憶體，讀取 page table 一個字的開銷是 500 nsec，TLB 可存 128 組 (page, frame)，查詢時間 50 nsec，假設只有 miss 時才查 page table，要把平均開銷降到 100 nsec 以下，需要多高的 hit rate
• 第 7 題（10%）｜磁碟有 10000 個 cylinder，每個 cylinder 10 個 track、每個 track 512 個 block，seek 每移動一個 cylinder 要 1 msec。若不把檔案的 block 放在一起，邏輯上連續的兩個 block 平均 seek 要 5 msec；若作業系統把相關 block 叢集起來，block 間平均距離縮為 2 個 cylinder、平均 seek 為 500 微秒。rotational latency 10 msec、每 block 傳輸 20 微秒，兩種情況讀取 100 個 block 的檔案各需要多久
• 第 8 題（10%）｜電腦有 8 GB 的 RAM，以 4 KB 為單位配置，若用 bit map 追蹤空閒記憶體，需要多少 KB
• 第 9 題（10%）｜virtual address 48 位元、physical address 32 位元、page 4 KB，page table 需要幾個項目

作答時要注意的地方

1. 第 1、4 題各 15 分，分成兩個小題，其餘各題 10 分。
2. 第 1(a) 的 f 有五個參數，呼叫時傳入的是不同寫法的位址。
3. 第 6 題限定只有 TLB miss 才查 page table，110 年第 3 題是先查 TLB 再讀 page table。
4. 第 2 題的答案要按首字母 A、B、C、D 分成四組。

準備方向

• C 程式的輸出（111 第 1 題），106 年與 109 到 115 年每年都有。
• 遞迴產生所有 permutation（111 第 1(b) 題），112 第 1(b) 題、113 第 1(b) 題、115 第 5(b) 題也有遞迴程式的輸出。
• Stack 的輸出序列（111 第 2 題），114 第 4 題的括號序列也是計數題。
• BST 的刪除（111 第 3 題），110 第 9 題、114 第 3 題有 AVL tree 的插入。
• Heap sort（111 第 4 題），108 第 2(4)(5) 題也有 heap。
• i-node（111 第 5 題），106 第 4 題、109 第 5 題、110 第 4 題也有。
• TLB hit rate（111 第 6 題），106 第 3 題、110 第 3 題也有。
• 磁碟讀檔時間（111 第 7 題），106 第 5 題同型，109 第 6 題、110 第 2 題也是磁碟題。
• Bit map（111 第 8 題）。
• Page table 項目數（111 第 9 題），109 第 2 題也有。