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

題型與配分

全卷 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 後排序
• 第 2 題（5%）｜Maximum Binary Tree（只要求 max-heap 性質、不要求 complete binary tree）的遞迴合併函式填空，共 (a)–(j) 十個空格。選項問哪些空格填的內容相同、交換 (h)(i) 是否仍正確、兩個參數指向同一棵樹時是否還能正確運作
• 第 3 題（單選，5%）｜Dynamic Array 的 amortized analysis：ResizeA 每次容量加常數、ResizeB 每次容量加倍，問各自的 amortized 複雜度；另有一個選項描述「刪除到 1/2 就縮小」的策略，問混合插入刪除後 amortized 是否仍為 O(1)
• 第 4 題（10%）｜divide and conquer 找 majority hash value：給一段不完整的 FindMajorityHashValue pseudo-code，判斷邊界情況、以及在 CountElement 為 Θ(c) 或 Θ(c/log c) 時整體複雜度
• 第 5 題（10%）｜BST 的 Join(L, x, R) 操作：給定 L、x、R，設計把它們併成一棵樹的方法。選項問純 BST 時有幾種可能的樹形、AVL 版本是否唯一、red-black tree 的 coloring 有幾種可能
• 第 6 題（單選，5%）｜Matrix chain multiplication 的 recurrence 計數：對固定的 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)² 遞增等
• 第 8 題（5%）｜樹高與 level 的定義：葉節點的 l(v) 是 1 還是 0、內部節點的 l(v) 是否為子節點最大值、DFS traversal 是否 O(n)
• 第 9 題（5%）｜樹的重新選根（re-rooting）：定義 r(v) 為從 v 往上經父節點到最遠葉的距離，問新樹高是否為 max(l(v), r(v))、r(v) 能否由上而下計算、能否在 O(n) 完成
• 第 10 題（5%）｜從序列中移除 k 個數字切成 k+1 段，最小化各段總和的最大值，五個選項是五條 recurrence，要挑出正確的
• 第 11 題（5%）｜承上題的性質判斷：是否一定移除最大的數、初始值 m(i,i,0) 應為何、k 超過範圍時的初始值
• 第 12 題（5%）｜DAG 上的 p 處理器 scheduling：判斷 scheduling 函式 s 的性質，包含每個時間步最多 p 個任務、路徑上的先後順序、所需時間步的下界、處理器無限多時需要幾個時間步

非選擇題考點（13）

第 13 題（30%）｜Vertex Cover 的 approximation algorithm

給兩個 approximation algorithm：VC-Arbitrary（任選一條未覆蓋的邊，把兩端點都放進 cover）與 VC-Max-Degree（每次選覆蓋最多未覆蓋邊的頂點）。

• (a) 10%｜分別舉例：一個讓 VC-Arbitrary 產生至少兩倍於 minimum vertex cover 的例子；一個讓 VC-Max-Degree 無論如何破平手都必定大於 minimum vertex cover 的例子。每個例子頂點數不得超過十個，且要寫出演算法找到的 cover 與 minimum vertex cover
• (b) 10%｜證明或反證 VC-Arbitrary 的 ratio bound 比 VC-Max-Degree 小，且界要盡可能緊
• (c) 10%｜把 weighted vertex cover 寫成整數線性規劃（ILP）

作答時要注意的地方

1. 第 1、4、5 題都要先讀完半頁以上的演算法描述。
2. 第 4、5 題各 10 分，複選每個錯選項扣 1 分。
3. 第 13(a) 的例子限十個頂點以內，要寫出兩個 cover。
4. 第 13(b) 是證明或反證。

準備方向

• approximation algorithm 在 113 的 vertex cover、114 的 (1−ε)-近似連續出現，CLRS 第 35 章有 vertex cover 與 set cover。
• 整數線性規劃的建模，113(c) 與 114 第 16 題都用到。
• 換根 DP（第 9 題）與區間切段 DP（第 10 題）。
• dynamic array 的 amortized analysis 在 113 第 3 題與 115 第 19 題連續兩年考，縮小門檻的設計也要會。