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

題型與配分

全卷 6 頁、15 題、100 分。

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

複選題考點（1–10）

• 第 1 題｜三層巢狀迴圈（i→j→k 遞增巢狀）的加法次數 f(n)，五個選項都是 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 建 heap 的比較次數：最小是否 Θ(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 的四行程式、空判斷、加 tail pointer 或改 doubly linked list 能否提升效率
• 第 8 題｜randomized insertion sort 建 linked list：每個 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) 推導比較次數
• 第 12 題（15%）｜海岸鐵路開咖啡廳：選一部分車站使總收益最大，限制是任兩個選中車站的距離必須大於 T。(a) 9%：定義 recurrence 給出 O(n²) 解　(b) 6%：當相鄰車站距離都是 1 時，給出 O(n) 解
• 第 13 題（15%）｜Disjoint set。(a) 9%：用 union-by-height 且不做 path compression 的 UNION/FIND 判斷一張 undirected graph 是不是樹，並分析最壞複雜度　(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。(a) 5%：證明或反證 greedy 法必得最佳解　(b) 10%：證明 Problem W 是 NP-complete

作答時要注意的地方

1. 手寫佔 70%，第 14 題 20 分全是證明，第 15(b) 要寫出 NP-complete 的證明。
2. 複選題的正確答案可能是 0 個，要逐一判斷每個選項。
3. 第 15 題通篇在講基因與單核苷酸多型性，題面沒有提到經典問題的名字。
4. 第 13(a) 限定不做 path compression。

準備方向

• NP-complete 的 reduction，109 第 15 題、110 第 19、20 題、111 第 12 題、114 第 17、19 題、115 第 5、6 題都考。
• 同時找最大與最小值的比較次數、median of medians 這類比較次數的題型。
• 樹的直徑與中心，109 年這題是唯一的純圖論證明。
• 複選題考的是定義的精確度，例如 O 與 o 的差別、heap 與 red-black tree 的各條性質，113、114、115 年繼續以選擇題的形式出現。