106 成大資工所考古題詳解｜軟體考點分析

題型與配分

全卷 2 頁、9 題、100 分，不可使用計算機，全部是手寫題。

卷面註明「於本試題紙上作答者，不予計分」。

一、資料結構考點（1–5）

• 第 1 題（10%）｜給 inorder JHKFIDGBEAC 與 preorder ABDFHJKIGEC：(a) 5% 重建 binary tree (b) 5% 寫出 postorder
• 第 2 題（10%）｜11 個槽（從 250 開始），要設計一個 division method 的 hash function，讓 42, 77, 85, 113, 315, 433, 474, 479, 574, 582, 698 完全沒有 collision，並畫出 hash table
• 第 3 題（10%）｜高度 h 的 heap，元素數量的最小值與最大值各是多少
• 第 4 題（10%）｜設計 O(n lg k) 的演算法，把 k 條已排序 linked list 合併成一條（n 為總元素數）
• 第 5 題（10%）｜optimal BST：給 6 個鍵值與其機率、7 個 dummy key 與其機率，依題目給的期望搜尋成本公式求最佳 BST 的成本

二、演算法考點（6–9）

• 第 6 題（18%）｜little-o 記號的六個是非題，包含 n = o(8n)、2ⁿ = o(n³)、2ⁿ = o(4ⁿ)、n = o(lg n) 等
• 第 7 題（12%）｜設計 O(V) 時間的演算法，判斷 undirected graph 是否含 cycle
• 第 8 題（10%）｜用 Master method 解 T(n) = 7T(n/2) + Θ(n²)
• 第 9 題（10%）｜semiconnected：directed graph G 中任兩點必有一方可達另一方，設計線性時間演算法判定

作答時要注意的地方

1. 作答要寫在答案卷上，寫在試題紙上不予計分。
2. 第 6 題 18 分，是全卷配分最高的一題。
3. 第 2 題是反向設計題，要自己決定 hash function。
4. 第 5 題要填一張大型 DP 表，且不可使用計算機。

準備方向

• optimal BST：106 第 5 題、111 第 14 題、112 第 14 題。
• O(V) 判斷 undirected graph 有無 cycle：106 第 7 題、108 第 5 題。
• Master theorem：106 第 8 題、107 第 9 題、108 第 7 題、109 Part II 第 5 題。
• little-o 與 big-O 的定義（106 第 6 題）。
• directed graph 的 strongly connected 與 semiconnected 判定（106 第 9 題）。
• heap 的元素數量：106 第 3 題、107 第 5 題。