110 中興資工所考古題詳解｜軟體考點分析

題型與配分

全卷 10 頁、100 分，不得使用計算機，卷首註明請依序作答。卷子分成 PART I（作業系統與計算機組織）與 PART II（資料結構與演算法），各佔 50%。全部是選擇題，卷面沒有標示倒扣。

PART I 的 20 個小題見硬體 110 年頁。

PART II 資料結構與演算法考點（50%）

第 6 題組（6%）

• 6-A｜操作 doubly linked list 的 C 函式，逐一交換每個節點的 prev 與 next，對 1↔2↔3↔4↔5↔6 呼叫後的 linked list
• 6-B｜open addressing 與 linear probing，h(k) = k mod 10，插入 6 個值後得到指定的 hash table，問哪個插入順序是可能的
• 6-C｜依序把 40、60、55、15、20、5、25、30 插入 Red-Black tree，求紅色節點的數字總和

第 7 題組（10%）

• 7-A｜BFS、DFS、Prim、Kruskal 四個演算法各自適合的資料結構
• 7-B｜給一棵 binary tree，判斷關於 post-order traversal 序列的五個敘述
• 7-C｜依序把 34、44、62、29、56、61、100 插入 array 式 max heap，求最後的 array 內容
• 7-D｜遞迴函式 f(n) 在 n > 100 時回傳 n − 10，否則回傳 f(f(n + 11))，求 f(91)
• 7-E｜對應的 infix 式與 postfix 式的敘述

第 8 題組（8%）

• 8-A｜activity network 的 critical path 長度
• 8-B｜哪個排序演算法的最壞時間是 O(n log n)：bubble、quick、merge、insertion、selection
• 8-C｜flow network 從 s 到 t 的 minimum cut 容量
• 8-D｜100 個字元的檔案只有 a–f 六種字元，頻率為 40、12、13、9、16、10，用 Huffman code 需要幾個 bit

第 9 題組（10%）

• 9-A｜7 個物品、背包容量 16 的 0/1 背包，求最大價值
• 9-B｜A₁（10×5）、A₂（5×20）、A₃（20×10）、A₄（10×5）相乘所需的最少 scalar multiplication 次數
• 9-C｜給一張圖，問哪條邊不會出現在 minimum spanning tree 中
• 9-D｜關於 shortest path 問題的錯誤敘述：DAG 與 topological sort、Bellman-Ford、Floyd-Warshall、DAG 的時間複雜度、Dijkstra 遇到 cycle
• 9-E｜關於 NP 理論的正確敘述：NP-hard 與 NP-complete、NP 的多項式驗證、reduction、P = NP 與整數分解、reduction 到 SAT

第 10 題組：多重選擇（16%，每小題 4%）

• 10-A｜哪個 degree sequence 不可能是任何 simple graph 的 degree sequence
• 10-B｜哪些是 greedy algorithm：Prim、Dijkstra、Bellman-Ford、Kruskal、Floyd-Warshall
• 10-C｜把 N、N¹·⁵、N²、N log N、N log(log N)、N log² N、N log(N²)、2ᴺ、N² log N、N³ 這十個函數依漸近成長速度由大到小排列，再判斷五個關於排序位置的敘述（2ᴺ 是第一個、N log N 是第 9 個、N log² N 是第 5 個、N log(N²) 是第 6 個、N³ 是第二個）哪些正確
• 10-D｜weighted graph 的性質：邊權加常數與 shortest path、MST 上的路徑與 shortest path、樹是否為 bipartite graph、bipartite graph maximum matching 與 max flow、增加邊容量與 max flow

作答時要注意的地方

1. 卷面沒有標示倒扣，題組 10 標明為多重選擇，每小題 4 分。
2. 卷首註明請依序作答。
3. 6-C 的 Red-Black tree 要插入 8 個節點。
4. 10-C 的函數有十個。
5. PART I 的 20 個小題佔一半分數。

準備方向

• BFS、DFS、Prim、Kruskal 的資料結構與演算法典範：110 第 7-A、10-B 題，111 第 2-III 題也有 Kruskal。
• hash table linear probing：110 第 6-B 題問插入順序，111 第 3-III 題問最後的表。
• Red-Black tree：110 第 6-C 題，114 第 17、18 題有 red-black tree 的插入。AVL 與 B-Tree 見 113 第 2 題、114 第 16 題。
• array 式 heap 的插入：110 第 7-C 題，111 第 1-III 題、114 Part 2 第 5 題也有。
• 遞迴函式求值：110 第 7-D 題，109 第 6 題、111 第 3-VII 題、112 B 第 3、4 題、113 第 10 題也有。
• Huffman 編碼的位元數：110 第 8-D 題，113 第 3 題也有。
• 矩陣鏈乘法：110 第 9-B 題，112 D-III 題也有。
• 0/1 背包：110 第 9-A 題，114 第 8 題也有。
• shortest path 的性質：110 第 9-D、10-D 題，111 第 1-VI 題、113 第 14 題、114 第 4 題也有。
• NP 理論：110 第 9-E 題，111 第 1-IV、1-V 題、112 D-V 題、113 B-2 第 2 題、114 第 5 題也有。
• max flow 與 min cut：110 第 8-C 題，112 D-II 題、113 B-1 第 4 題也有。