107 台大資工所軟體考點分析

題型與配分

科目「資料結構與演算法」（題號 418、節次 1），全卷 2 頁、100 分。

倒扣規則：卷面明訂「選擇題不答零分，答錯倒扣當題分數」。也就是 2 分的題目答錯扣 2 分、5 分的題目答錯扣 5 分 —— 答錯一題等於損失兩題的分數，是台大十年間最嚴苛的選擇題倒扣方式。

選擇題考點（1–16）

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

七個小題共用 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 最壞。純記憶題，是全卷最該穩拿的 14 分。

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

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

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

三題都要完整手動跑完 11 次插入（含上浮），是選擇題裡最花時間的一段。

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

• 第 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（10%，第 13–16 題）

同一組 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 的父節點

這四題必須把 BST 和 AVL 各建一次、再各刪一次，AVL 的旋轉只要錯一步後面三題全垮，加上答錯倒扣，是全卷風險最高的區塊。

手寫題考點

• (V) deque（35%）
• (a)(1)（5%）｜舉反例說明「每次取兩端較大者」的貪婪法解不出最大交錯和，並列出計算
• (a)(2)（10%）｜設計 O(n²) 的 DP 求最佳取出序列，並用自己舉的例子說明流程
• (b)(1)（6%）｜用兩個 stack 實作 queue，再延伸成實作 deque
• (b)(2)（7%）｜用 accounting method 證明 n 次 queue 操作的攤銷複雜度是 O(n)
• (b)(3)（7%）｜證明或反證 deque 的 n 次操作攤銷也是 O(n) —— 這小題的答案與 (b)(2) 相反，兩個 stack 實作 deque 時會出現來回搬移的最壞情況
• (VI) 校園道路圖論（25%）
• (a)（10%）｜邊權為「修復時間」、所有路同時修，求從 v_a 到 v_b 最早可通行的路徑 —— 這是 minimax path（bottleneck shortest path），不是一般最短路徑
• (b)(1)（5%）｜所有邊權相同時，決定每條邊的方向使 v_a 到 v_b 的時間最小，要求 linear time
• (b)(2)（10%）｜邊權不同時的版本，並分析複雜度

這份考卷的難點

1. 答錯倒扣當題分數，16 題選擇裡只要錯 4 題（假設都是 3 分題），等於直接損失 24 分。沒把握就該留白。
2. 第 13–16 題連鎖風險高。 AVL 建樹與刪除的旋轉容易出錯，且四題共用同一棵樹。
3. (V)(b)(3) 是真正的分水嶺。 多數人會直覺認為 deque 也是 O(n)，但兩個 stack 實作 deque 時可以構造出反覆倒堆疊的序列，攤銷不再是常數。
4. (VI)(a) 的 bottleneck path 不是課本最短路徑的標準題型，要想到改用「最小化路徑上的最大邊權」。

準備建議

• 複雜度對照表（各種排序、heap 操作、hash、平衡樹）要背到反射，這是 107 年最穩的 14 分
• AVL 的插入旋轉與刪除旋轉必須練到手穩，台大 107 一次考了四題
• 攤銷分析的三種方法（aggregate／accounting／potential）都要會，台大在 107、114、115 三年都考過
• Bottleneck path（可用 MST 或二分搜＋BFS 解）建議補一下，是最短路徑的常見變形