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

題型與配分

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

複選題規則：「請選出所有正確答案，正確答案可能有 0 到 5 個；若全部都不對，寫 none；不想作答就留白。」十個答案必須寫在答案卷第一頁、第 n 題寫在第 n 行，不照規定寫會直接不計分。

值得注意的是：這一年的複選題沒有倒扣。在「可能一個都不對」的設計下，留白與猜測的取捨和倒扣年度完全不同。

複選題考點（1–10）

這一區幾乎全是「精確定義」的檢驗，而不是計算。

• 第 1 題｜三層巢狀迴圈（i→j→k 遞增巢狀）的加法次數 f(n)，五個選項都是 O(·) 的上界 —— 注意 O 是上界，不只有最緊的那個是對的
• 第 2 題｜兩條已排序 linked list 遞迴合併的最少比較次數 f(n,m) 的 Ω 下界
• 第 3 題｜承上，用該合併法做 bottom-up merge sort 的最大總比較次數，五個選項全是 little-o 記號
• 第 4 題｜10 個節點的 binary min-heap：第二小是否必在 level 1、最大值是否必為葉、第二大是否必為葉、樹高是否 Θ(log n)、能否用 O(1) 次比較找第三小
• 第 5 題｜bottom-up 建堆的比較次數：最小是否 Θ(n)、最大是否 Θ(n)、「每次 heapify 最多 O(log n)、共 O(n) 個 key 所以 O(n log n)」這個推論哪裡有問題、比較次數是否與所有 key 的原始 level 總和同階
• 第 6 題｜randomized quicksort：已排序時比較次數是否最大、max(|K₁|,|K₂|) 的期望是否為 3n/4、k_i 與 k_j 被比較的機率是否為 2/(i−j+1)、期望總比較次數的求和式
• 第 7 題｜用 linked list 實作 stack：push 的四行程式、pop 的四行程式（free(head) 寫在讀取 head->data 之前，是明顯的 use-after-free）、空判斷、加 tail 指標或改雙向串列能否提升效率
• 第 8 題｜randomized 插入排序建串列：每個 key 是否恰停一次、最小的 1 是否不跳過任何 key、最大的 n 是否跳過 n−1 個、key i 的期望跳過數是否 Θ(i)、期望總比較次數是否 Θ(n²)
• 第 9 題｜BST：找最小值是否 O(h)、n 個節點的樹高是否 O(log n)、找最大值是否 O(log n)、以及用 successor 或 predecessor 刪除雙子節點的兩種寫法是否正確
• 第 10 題｜red-black tree：若放棄「根為黑」但保留另外兩條性質，樹高還能否保證 O(log n)、10 萬節點能否完全沒有紅節點、新插入的節點染紅／染黑各會違反哪一條性質

手寫題考點（11–15）

• 第 11 題（5%）｜同時找最大與最小值，要求少於 1.67n 次比較。(a) 設計演算法 (b) 推導比較次數。標準解是兩兩配對後再比，3n/2 ≈ 1.5n
• 第 12 題（15%）｜海岸鐵路開咖啡廳：選一部分車站使總收益最大，限制是任兩個選中車站的距離必須大於 T。(a) 9% 定義遞迴式給出 O(n²) 解 (b) 6% 當相鄰車站距離都是 1 時，給出 O(n) 解。這是 weighted interval scheduling 的變形，(b) 的關鍵是限制變成固定的索引位移
• 第 13 題（15%）｜Disjoint set。(a) 9% 用 union-by-height 且不做路徑壓縮的 UNION/FIND 判斷一張無向圖是不是樹，並分析最壞複雜度 (b) 6% 比較 union-by-height 與 union-by-descendant（依子孫數合併）哪個漸進較好、為什麼
• 第 14 題（20%）｜樹的直徑與中心，三題都是 prove or disprove：(a) 5% 是否存在有三條不同直徑且有兩個中心的樹 (b) 5% 是否存在有三個中心的樹 (c) 10% 任一中心是否必定落在直徑上
• 第 15 題（15%）｜SNP 標記選擇問題（Problem W）：給宇集 U 與子集族 F，找最小的子族覆蓋 U —— 這就是 Set Cover。(a) 5% 證明或反證貪婪法必得最佳解 (b) 10% 證明 Problem W 是 NP-complete

這份考卷的難點

1. 手寫佔 70%，而且有三題是 prove or disprove。 第 14 題整整 20 分全是證明，第 15(b) 還要完整寫出 NP-complete 的兩個步驟（屬於 NP＋歸約）。
2. 複選題「可能 0 到 5 個正確」。 這個設計讓「至少選一個」的直覺失效，必須逐一判斷每個選項。
3. 第 15 題的偽裝很深。 通篇在講基因與單核苷酸多型性，要讀到最後才發現是 set cover；認不出來就寫不出歸約。
4. 第 13(a) 限定不做路徑壓縮，複雜度分析和背起來的 α(n) 不一樣，要真的自己推。

準備建議

• Set cover、vertex cover、subset sum 這三個經典 NP-complete 問題的歸約要能默寫，台大在 109、113、114 都考到
• 找最大最小值的 3n/2 配對法、median of medians 這類「比較次數下界」題型要熟
• 樹的直徑與中心（兩次 BFS 求直徑）建議補齊，這是 109 唯一一題純圖論證明
• 複選題那一區的重點是定義精確度：O 與 o 的差別、heap 的哪些性質是「必然」哪些只是「通常」、red-black tree 各條性質分別擋住什麼 —— 這些在 113、114、115 年繼續以複選題形式出現