107 台大資工所考古題詳解｜軟體考點分析

題型與配分

全卷 2 頁、100 分。

倒扣規則：卷面明訂「選擇題不答零分，答錯倒扣當題分數」。2 分的題目答錯扣 2 分，5 分的題目答錯扣 5 分。

選擇題考點（1–16）

(I) 複雜度對照（第 1–7 題，各 2 分，共 14 分）

七個小題共用 O(1)、O(n)、O(lg n)、O(n lg n)、O(n²) 五個選項，問最緊的上界：quick sort 最壞、quick sort 期望、bucket sort 期望、MAX-HEAPIFY 期望、stack 的 PUSH/POP、perfect hashing 的 SEARCH 最壞、red-black tree 的 INSERT/DELETE 最壞。

(II) Min-heap（第 8–10 題，共 8 分）

依序插入 12, 8, 23, 21, 6, 1, 7, 25, 24, 22, 26 後：

• 第 8 題（2%）｜heap 的高度
• 第 9 題（3%）｜索引 3 的節點值
• 第 10 題（3%）｜值為 12 的節點其左子節點是多少

(III) Hash（第 11–12 題，共 8 分）

• 第 11 題（3%）｜chaining、h(k)=k mod 5，插入 13 個 key，問搜尋的期望比較次數
• 第 12 題（5%）｜double hashing，h₁(k)=k mod 7、h₂(k)=5−(k mod 5)、7 格，依序插入 35, 42, 3, 21，問 21 落在哪一格

(IV) BST 與 AVL（第 13–16 題，共 10 分）

同一組 10 個數字 88, 93, 76, 50, 46, 3, 32, 85, 30, 95 依序插入：

• 第 13 題（2%）｜插入 BST 後的樹高
• 第 14 題（2%）｜BST 刪除 76 後，50 的父節點
• 第 15 題（3%）｜改插入 AVL tree，76 的父節點值
• 第 16 題（3%）｜AVL 中刪除 32 後，30 的父節點

手寫題考點

• (V)(a)(1)（5%）｜舉反例說明「每次取兩端較大者」的 greedy 法解不出最大交錯和，並列出計算
• (V)(a)(2)（10%）｜設計 O(n²) 的 DP 求最佳取出序列，並用自己舉的例子說明流程
• (V)(b)(1)（6%）｜用兩個 stack 實作 queue，再延伸成實作 deque
• (V)(b)(2)（7%）｜用 accounting method 證明 n 次 queue 操作的 amortized 複雜度
• (V)(b)(3)（7%）｜證明或反證 deque 的 n 次操作 amortized 也是同樣的複雜度
• (VI)(a)（10%）｜邊權為「修復時間」、所有路同時修，求從 v_a 到 v_b 最早可通行的路徑
• (VI)(b)(1)（5%）｜所有邊權相同時，決定每條邊的方向使 v_a 到 v_b 的時間最小，要求 linear time
• (VI)(b)(2)（10%）｜邊權不同時的版本，並分析複雜度

作答時要注意的地方

1. 選擇題答錯倒扣當題分數，3 分題答錯一題扣 3 分。
2. 第 13 到 16 題共用同一組數字，BST 與 AVL 各建一次、各刪一次。
3. (V)(b)(3) 是證明或反證。
4. (VI)(a) 的目標是最早可通行，不是一般的 shortest path 長度。

準備方向

• 複雜度對照表（排序、heap 操作、hash、balanced tree）。111 年第 1–5 題又考了幾乎同一組。
• AVL 的插入與刪除旋轉，107 年一次考四題。
• amortized analysis 在 107、113、114、115 都考過。
• shortest path 的變形，例如改變路徑的目標函數。