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

題型與配分

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

選擇題配分不平均：第 4、5 題各 10 分，其餘十題各 5 分。

計分規則：

• 第 3、6 題為單選題：答對 5 分、答錯倒扣 1 分、未答 0 分
• 其餘 10 題為複選題：每個選項單獨計分，選項答對得該題的五分之一、選項答錯倒扣該題的十分之一；整題未作答則 0 分

換算成 5 分題：每個選項對 +1、錯 −0.5；10 分題則是對 +2、錯 −1。猜錯一個選項要用兩個對的來補。

選擇題考點（1–12）

• 第 1 題（5%）｜Selection problem 變形：n 個相異整數、數值介於 1 到 y，要報告最小的 x 個數。五個演算法各附複雜度宣稱要判斷真偽 —— max-heap 維持大小 x、建 min-heap 取 x 次、base-n radix sort、counting sort、quickselect 後排序。重點在各自的前提條件（x ≤ n/log n、y ≤ n² 等）是否讓宣稱成立
• 第 2 題（5%）｜Maximum Binary Tree（只要求 max-heap 性質、不要求完全二元樹）的遞迴合併函式填空，共 (a)–(j) 十個空格。選項問哪些空格填的內容相同、交換 (h)(i) 是否仍正確、兩個參數指向同一棵樹時是否還能正確運作
• 第 3 題（單選，5%）｜Dynamic Array（動態陣列）的攤銷分析：ResizeA 每次容量加常數、ResizeB 每次容量加倍，問各自的攤銷複雜度；另有一個選項描述「刪除到 1/2 就縮小」的策略，問混合插入刪除後攤銷是否仍為 O(1)（答案是會被破壞，這與 115 年第 19 題同一個觀念）
• 第 4 題（10%）｜分治法找 majority hash value：給一段不完整的 FindMajorityHashValue pseudo-code，判斷邊界情況（左右都回傳 −1 時是否仍可能有多數）、以及在 CountElement 為 Θ(c) 或 Θ(c/log c) 時整體複雜度是 O(n log n) 還是 O(n)。要會解 T(n)=2T(n/2)+Θ(n/log n)
• 第 5 題（10%）｜BST 的 Join(L, x, R) 操作：給定 L、x、R，設計把它們併成一棵樹的方法。選項問：純 BST 時有幾種可能的樹形、AVL 版本是否唯一、紅黑樹的著色有幾種可能。這是全卷最抽象的一題
• 第 6 題（單選，5%）｜Matrix chain multiplication 的遞迴式計數：對固定的 s 和 k，有多少個 m[i,j] 的右式會用到 m[s,s+k]（記為 r），以及 i=s、j=s+k 時右式有幾個相異的 m（記為 q），求 q + r
• 第 7 題（5%）｜承上，計算 m[i,j] 時必須依什麼順序才能保證右式都已算出 —— 選項是 i+j 遞增／遞減、(i−j)² 遞增等。正確答案的核心是「依 j−i 由小到大」
• 第 8 題（5%）｜樹高與 level 的定義題：葉節點的 l(v) 是 1 還是 0、內部節點的 l(v) 是否為子節點最大值、DFS 走訪是否 O(n)
• 第 9 題（5%）｜樹的重新選根（re-rooting）：定義 r(v) 為從 v 往上經父節點到最遠葉的距離，問新樹高是否為 max(l(v), r(v))、r(v) 能否由上而下計算（只看父節點的 r 與兄弟的 l）、能否在 O(n) 完成。這是「換根 DP」的標準題
• 第 10 題（5%）｜從序列中移除 k 個數字切成 k+1 段，最小化各段總和的最大值，五個選項是五條遞迴式，要挑出正確的。注意正確式子必須把 k 拆給左右兩邊（v+w = k−1）
• 第 11 題（5%）｜承上題的性質判斷：是否一定移除最大的數、初始值 m(i,i,0) 應為何、k 超過範圍時的初始值
• 第 12 題（5%）｜DAG 上的 p 處理器排程：判斷排程函式 s 的性質 —— 每個時間步最多 p 個任務、路徑上的先後順序、所需時間步的下界是否為 min(⌈n/p⌉, L)、處理器無限多時是否為 L 步（L 是最長路徑上的任務數）

非選擇題考點（13）

第 13 題（30%）｜Vertex Cover 的近似演算法

給兩個近似演算法：VC-Arbitrary（任選一條未覆蓋的邊，把兩端點都放進覆蓋集）與 VC-Max-Degree（每次選覆蓋最多未覆蓋邊的頂點）。

• (a) 10%｜分別舉例：一個讓 VC-Arbitrary 產生至少兩倍於最小覆蓋的例子；一個讓 VC-Max-Degree 無論如何破平手都必定大於最小覆蓋的例子。每個例子頂點數不得超過十個，且要寫出演算法找到的覆蓋與最小覆蓋
• (b) 10%｜證明或反證 VC-Arbitrary 的 ratio bound 比 VC-Max-Degree 小，且界要盡可能緊。這題的答案違反直覺 —— 看似笨拙的 VC-Arbitrary 有 2-近似保證，而貪婪的 VC-Max-Degree 只有 O(log n)
• (c) 10%｜把 weighted vertex cover 寫成整數線性規劃（ILP）

這份考卷的難點

1. 題目敘述極長。 第 1、4、5 題每題都要先讀完半頁以上的演算法描述，再逐一判斷五個選項。6 頁的卷子閱讀量比 110、111 大得多。
2. 第 13(b) 是整份考卷的分水嶺。 直覺會認為 max-degree 比較好，但正確答案是 arbitrary 的 2-近似優於 max-degree 的 Θ(log n)，而且要能證明。
3. 第 5 題的紅黑樹著色計數需要同時掌握 join 操作與紅黑性質，是選擇題裡最難的 10 分。
4. 倒扣下的 10 分題風險加倍（每個錯選項扣 1 分），第 4、5 題全猜錯可以扣掉 10 分。

準備建議

• 近似演算法在台大已連續出現（113 的 vertex cover、114 的 (1−ε)-近似），CLRS 第 35 章的 2-近似 vertex cover 與 greedy set cover 的 ln n 界建議完整讀過
• 整數線性規劃的建模（每個頂點一個 0/1 變數、每條邊一條限制式）要能寫出來，113(c) 與 114 的第 16 題都用到
• 換根 DP（第 9 題）與區間切段 DP（第 10 題）是近年常見的進階 DP 型態
• 攤銷分析的動態陣列（加倍 vs 加常數、縮小門檻 1/2 vs 1/4）在 113 與 115 連續兩年考，務必弄懂為什麼 1/2 會壞掉