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

題型與配分

全卷 2 頁、8 題、100 分，不可使用計算機。

Part I 資料結構考點

• 第 1 題（30%）｜是非題，答錯要寫出正確答案，五小題各 6%
• 第 1(1) 題｜static hashing 中 open addressing 成功搜尋最壞 O(n)，改用平衡搜尋樹能否降到 O(log n)
• 第 1(2) 題｜圖中所有頂點的 degree 總和與邊數的關係 e = Σd_i 是否正確
• 第 1(3) 題｜MST 上 u 到 v 的路徑是否也是 shortest path，與 108 第 1(2) 題相同
• 第 1(4) 題｜圖用 adjacency list 表示時 DFS 是否需要 O(e²)
• 第 1(5) 題｜AOV network 可行時，topological order 是否不唯一
• 第 2 題（10%）｜Bloom filter 的錯誤率：m 個位元、h 個獨立均勻 hash function，做了 u 次更新後，任意查詢發生 filter error 的機率是多少
• 第 3 題（10%）｜給一張 weighted graph，求最小成本並建出 MST

Part II 演算法考點

• 第 1 題（10%）｜判斷 5ⁿ⁺¹ = O(5ⁿ) 是否成立、6²ⁿ = O(6ⁿ) 是否成立
• 第 2 題（10%）｜求 T(n) = √n·T(√n) + n 的漸進上下界，要盡可能緊
• 第 3 題（10%）｜說明如何讓 quicksort 的時間複雜度達到 O(n lg n)
• 第 4 題（10%）｜求 <1,0,0,1,0,1,0,1> 與 <0,1,0,1,1,0,1,1,0> 的 LCS
• 第 5 題（10%）｜If possible, use the master method to solve T(n) = 27T(n/3) + Θ(n³/lg n)

作答時要注意的地方

1. Part I 第 1 題的是非題答錯要寫出正確答案。
2. Part II 的題號從 1 重新編起，引用時要分 Part。
3. Part II 第 5 題題目寫「if possible」。

準備方向

• Master theorem：106 第 8 題、107 第 9 題、108 第 7 題、109 Part II 第 5 題，112 第 11 題與 109 Part II 第 5 題相同。
• 是非題與 108 年重複：MST 路徑與 shortest path、DFS 複雜度、hashing。
• Bloom filter：109 第 2 題、111 第 4 題、113 第 5 題、115 題組 A。
• 變數代換解 recurrence：109 Part II 第 2 題，台大 106、114 也有。
• LCS：109 Part II 第 4 題、113 第 13 題。