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

題型與配分

全卷 2 頁、9 題、100 分，考試時間 100 分鐘，不可使用計算機，卷面名稱為問答申論題。卷首沒有印「題目不清楚可自行假設」的說明，106 年與 109 到 114 年有。

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

逐題考點

• 第 1 題（20%）｜填空（每格 2 分）：(a) 目前在記憶體中的 process 數稱為 degree of ？ (b) modify bit 的另一個名稱 (c) CPU scheduling 功能中，把 CPU core 的控制權交給 CPU scheduler 選出的 process 的模組 (d) 要滿足 mutual exclusion、progress 與 bounded waiting 三項要求的問題 (e) 主要的大容量儲存系統由硬碟與哪一種記憶體裝置組成 (f) kernel 為了封裝不同 I/O 裝置的細節，採用 device-？ modules (g) deadlock 的必要條件中，哪一個條件蘊含 hold and wait (h) 檔案是記錄在輔助儲存裝置上的什麼相關資訊集合 (i) process 任何時候只能存取它完成工作當下所需資源的原則 (j) 未經授權讀取資料是破壞什麼
• 第 2 題（10%）｜(a) 6% 造成執行中的 process 非自願放棄 CPU core 的三種情況，並說明它會被放進哪個 queue (b) 4% 從 processor affinity 的角度說明 warm cache
• 第 3 題（10%）｜(a) 6% 作業系統處理 deadlock 的三種常見方式 (b) 4% 從記憶體管理的角度說明 copy-on-write
• 第 4 題（10%）｜典型的 sector-sparing 交易包含哪五個步驟
• 第 5 題（10%）｜寫出下列 C 程式的輸出：(a) 5% int x = 12; int y = 25; printf("%d\n", x ^ y & ~x | y << 2);，^ 為 XOR、& 為 AND、~ 為 NOT、| 為 OR、<< 為左移 (b) 5% 函式 int mystery(int *p, int n) 內有 static int count = 0，每次呼叫 count++，n <= 0 時回傳 count；p > 10 時回傳 p + mystery(p+1, n−1)，否則回傳 mystery(p+1, n−1)；主程式 int arr[] = {15, 5, 20, 8, 30}，印出 mystery(arr, 3)
• 第 6 題（10%）｜binary tree 的 inorder traversal 為 ABCDEFGHIJ、postorder traversal 為 ABDCGIHJFE，求 preorder traversal
• 第 7 題（10%）｜大小 M = 11 的 hash table，每個 bucket 只能放一個 key，使用 double hashing，h₁(k) = k mod 11、h₂(k) = 7 − (k mod 7)，依序把 11、33、66、7、77 插入空表，畫出全部插入後的 hash table
• 第 8 題（10%）｜給 undirected graph 的 adjacency matrix（頂點 A 到 F，權重為矩陣中的數字，0 代表沒有邊）：(a) 8% 從頂點 A 開始用 Prim 演算法，寫出邊加入 minimum spanning tree 的順序，用權重表示 (b) 2% V、E 分別為頂點數與邊數，用 adjacency list 與 binary heap 實作 Prim 的時間複雜度
• 第 9 題（10%）｜用 Big-O 寫出下列排序的最壞時間：(a) bubble sort (b) insertion sort (c) quick sort (d) merge sort (e) heap sort，各 2%

作答時要注意的地方

1. 第 1 題 20 分，共 10 格，與 113、114 年的填空題同一格式。
2. 第 5(a) 的運算式混用 ^、&、~、|、<<，題目附了各符號的意思。
3. 第 8(a) 要求用邊的權重表示加入的順序。
4. 106 年與 109 到 114 年卷首都有「題目不清楚可自行假設」的說明，115 年沒有。

準備方向

• 填空題（115 第 1 題），113 第 8 題、114 第 8 題也有每年 20 分的填空題。
• deadlock（115 第 3(a) 題），108 第 3(2) 題、112 第 8(a) 題、114 第 8(d) 題也有。
• Copy-on-write 與記憶體管理（115 第 3(b) 題），108 第 4 題、112 第 6 題、114 第 7 題也是記憶體問答。
• 運算子與位元運算的輸出（115 第 5(a) 題），110 第 6 題、112 第 1(a) 題、113 第 1(a) 題也有。
• 帶 static 變數的遞迴（115 第 5(b) 題），111 第 1(b) 題、112 第 1(b) 題、113 第 1(b) 題也有遞迴程式的輸出。
• 樹的 traversal order（115 第 6 題），110 第 7 題也有。
• hash table 與探測（115 第 7 題），108 第 1(2) 題、110 第 8 題也有。
• Prim 與 MST（115 第 8 題），109 第 7 題的 Kruskal 也有。
• 排序的最壞時間（115 第 9 題），108 第 1(4) 題、109 第 9 題、112 到 114 年也有排序。