113 年 國立臺灣大學資料科學碩士學位學程《資料結構與演算法》

好的，同學你好！這題是國立臺灣大學資訊工程學研究所 113 年資料結構與演算法考題的第一題，主要在考驗你對「選擇問題 (Selection Problem)」及其變形問題的理解，以及各種排序與選擇演算法（如堆積排序、基數排序、計數排序、快速選擇等）的時間複雜度分析能力，特別是在不同輸入規模與資料特性（$n$、$x$、$y$）下的表現。這類問題是資料結構與演算法的經典考題，務必掌握各種演算法的適用情境與複雜度。

完整解題過程

題目要求從給定的 $n$ 個相異整數序列 $S = (a_1, a_2, ..., a_n)$ 中，找出最小的 $x$ 個數字，並以遞增順序回報。序列中的每個數字介於 $1$ 到 $y$ 之間。我們將逐一分析每個演算法的描述與其時間複雜度。

A. Algorithm A: 使用最大堆積 (Max-Heap)

演算法描述：
此演算法初始化一個空的 Max-Heap。依序將 $S$ 中的數字插入堆積。在插入過程中，如果堆積的大小超過 $x$，則移除堆積中的最大元素。最後，將堆積中剩餘的 $x$ 個數字使用堆積排序 (Heapsort) 進行排序並回報。

時間複雜度分析：

1. 初始化 Max-Heap： $O(1)$。
2. 插入 $n$ 個數字並維護堆積大小： 對於序列 $S$ 中的每個數字 $a_i$：
   • 將 $a_i$ 插入 Max-Heap。此操作的時間複雜度為 $O(\log k)$，其中 $k$ 是堆積的當前大小。由於堆積大小最多為 $x+1$，因此每次插入為 $O(\log x)$。
   • 如果堆積大小超過 $x$，則移除最大元素（即堆積的根）。此操作的時間複雜度為 $O(\log x)$。
   • 總共有 $n$ 個數字，因此此階段的總時間複雜度為 $O(n \log x)$。
3. 對堆積中剩餘的 $x$ 個數字進行排序： 堆積中包含 $x$ 個最小的數字。使用 Heapsort 對這 $x$ 個數字進行排序，時間複雜度為 $O(x \log x)$。
4. 總時間複雜度： $O(n \log x + x \log x) = O(n \log x)$。

判斷條件： 如果 $x \le n/\log n$，演算法 A 在最壞情況下運行時間為 $O(n)$。
將 $x \le n/\log n$ 代入總時間複雜度 $O(n \log x)$：
$O(n \log x) \le O(n \log(n/\log n)) = O(n (\log n - \log(\log n)))$。
顯然，$O(n (\log n - \log(\log n)))$ 不等於 $O(n)$。例如，當 $x$ 接近 $n/\log n$ 時，時間複雜度會是 $O(n \log n)$ 級別，而非 $O(n)$。

結論： 選項 A 的描述是錯誤的。

B. Algorithm B: 使用最小堆積 (Min-Heap)

演算法描述：
此演算法首先從所有 $n$ 個數字中建構一個 Min-Heap，然後從中提取最小元素 $x$ 次。

時間複雜度分析：

1. 建構 Min-Heap： 從 $n$ 個數字建構一個 Min-Heap 的時間複雜度為 $O(n)$。
2. 提取最小元素 $x$ 次： 每次提取最小元素（即堆積的根）並重新堆積的時間複雜度為 $O(\log n)$。總共提取 $x$ 次，因此此階段的總時間複雜度為 $O(x \log n)$。
3. 總時間複雜度： $O(n + x \log n)$。

判斷條件： 如果 $x \le n/\log n$，演算法 B 在最壞情況下運行時間為 $O(n)$。
將 $x \le n/\log n$ 代入總時間複雜度 $O(n + x \log n)$：
$O(n + (n/\log n) \log n) = O(n + n) = O(n)$。

結論： 選項 B 的描述是正確的。

C. Algorithm C: 使用基數排序 (Radix Sort)

本題考驗的核心觀念是遞迴式二元樹合併 (Recursive Binary Tree Merging)，特別是針對最大二元樹 (Maximum Binary Tree, MaxBT) 的合併操作。MaxBT 遵循最大堆積性質 (max-heap property)，即每個節點的值都大於或等於其子節點的值，但不要求是完全二元樹。解題關鍵在於理解遞迴合併的基底情況 (base cases) 和遞迴步驟 (recursive steps)，以及如何透過遞迴呼叫來維護 MaxBT 的性質。

完整解題過程：

首先，我們需要根據 MaxBT 的性質和遞迴合併的邏輯，推導出空白處應填入的內容，以確保函數能「正常運作 (proper functioning)」。

一個 MaxBT 合併函數的標準邏輯如下：

1. 基底情況 (Base Cases):
   • 如果 root1 為 nil，則合併結果就是 root2。
   • 如果 root2 為 nil，則合併結果就是 root1。
2. 遞迴步驟 (Recursive Step):
   • 比較 root1.data 和 root2.data。為了簡化邏輯，我們通常會確保 root1 總是指向值較大的那個根節點。如果 root1.data < root2.data，則交換 root1 和 root2。
   • 現在，root1 擁有較大的值，它將成為合併後 MaxBT 的根節點。
   • 將值較小的樹 (root2) 遞迴地合併到 root1 的其中一個子樹中（例如，右子樹 root1.right）。
   • 返回 root1 作為合併後的根節點。

根據上述邏輯，我們來填寫題目中的偽程式碼：

1: function MergeMaxBinaryTrees (root1, root2)
2:   if root1 == nil then return (a)
3:   end if
4:   if root2 == nil then return (b)
5:   end if
6:   if root1.data > root2.data then
7:     (c) = MergeMaxBinaryTrees(root1, (d))
8:     return (e)
9:   else // root2.data >= root1.data
10:    (f) = MergeMaxBinaryTrees((g), root2)
11:    return (h)
12:  end if
13: end function

填寫空白處：

• 第 2 行： if root1 == nil then return (a)

  • 如果 root1 為空，則合併結果就是 root2。
  • 所以，(a) 應為 root2。

• 第 4 行： if root2 == nil then return (b)

  • 如果 root2 為空，則合併結果就是 root1。
  • 所以，(b) 應為 root1。

• 第 6-8 行 (if root1.data > root2.data):

  • 此時 root1 的值較大，它將成為合併後的根節點。
  • 所以，(e) 應為 root1。
  • 值較小的樹 (root2) 需要被合併到 root1 的子樹中。通常會選擇其中一個子節點（例如 root1.right 或 root1.left）。我們假設選擇 root1.right。
  • 遞迴呼叫的目的是將 root2 合併到 root1.right 中，並將結果賦值給 root1.right。
  • 因此，第 7 行的正確形式應為 root1.right = MergeMaxBinaryTrees(root1.right, root2)。
  • 對應到 (c) = MergeMaxBinaryTrees(root1, (d))，這表示題目中的偽程式碼在 MergeMaxBinaryTrees 的第一個參數 root1 處有誤植。為了使函數「正常運作」，我們必須假設其意圖是 root1.right。
  • 所以，(c) 應為 root1.right (代表 root1.right 這個變數被賦值)。
  • (d) 應為 root2 (代表被合併的較小樹的根節點)。

• 第 9-11 行 (else, 即 root2.data >= root1.data):

  • 此時 root2 的值較大，它將成為合併後的根節點。
  • 所以，(h) 應為 root2。
  • 值較小的樹 (root1) 需要被合併到 root2 的子樹中。同樣假設選擇 root2.right。
  • 遞迴呼叫的目的是將 root1 合併到 root2.right 中，並將結果賦值給 root2.right。
  • 因此，第 10 行的正確形式應為 root2.right = MergeMaxBinaryTrees(root2.right, root1)。

本題主要考驗考生對動態陣列 (Dynamic Array) 的核心概念、記憶體管理方式，以及在不同擴容 (resize) 策略下，插入 (Insert) 和刪除 (Delete) 操作的攤還時間複雜度 (amortized time complexity) 的理解。特別是對於攤還分析 (amortized analysis) 的掌握，是解題的關鍵。

完整解題過程

A. DArray is not suitable for random access because its memory may be relocated.

• 說明： 陣列 (Array) 的一個基本特性是它支援隨機存取 (random access)，即透過索引 (index) 在 $O(1)$ 時間內存取任何元素。這是因為陣列的元素在記憶體中是連續儲存的。
• 動態陣列在容量不足時會進行記憶體重新配置 (relocation)，將所有資料搬移到一個新的、更大的記憶體區塊。然而，這個重新配置的動作並不會改變動態陣列在完成配置後，其內部元素仍然是連續儲存的事實。一旦新的記憶體區塊被分配並資料搬移完成，對 D.data[i] 的存取仍然是 $O(1)$ 時間。記憶體重新配置只影響陣列本身的基底位址，不影響其內部元素的隨機存取特性。
• 結論： 此敘述不正確。動態陣列仍然適合隨機存取。

B. DArray can only be allocated in the heap memory due to its dynamic memory nature.

• 說明： 動態陣列的核心特性是其大小可以動態調整。這意味著其底層的資料儲存區塊 (即 D.data 指向的記憶體) 必須在程式執行時動態分配和釋放。在 C/C++ 等語言中，這種動態記憶體分配通常發生在堆積 (heap) 記憶體上 (例如使用 malloc 或 new)。
• 相較之下，堆疊 (stack) 記憶體用於儲存局部變數和函數呼叫資訊，其大小在編譯時或函數進入時就已固定，不允許在執行時動態改變大小。因此，動態陣列的底層資料儲存區塊必須在堆積上分配，才能實現其動態調整大小的功能。
• 然而，如果嚴格解釋「DArray」是指整個動態陣列物件 (包含 D.data 指標、D.size 和 D.capacity 等屬性)，那麼這個物件本身是可以被宣告在堆疊上的 (例如 DArray D;)。但其內部指向實際資料的指標 D.data 仍需指向堆積記憶體。
• 鑑於題目強調「dynamic memory nature」，通常是指其核心的資料儲存區塊。但「only」這個詞語使得此選項在嚴格語義上可能存在爭議。不過，在資料結構的語境中，動態陣列的「動態」特性確實依賴於堆積記憶體。
• 結論： 此敘述在一般理解下是正確的，但若嚴格區分物件本身與其底層資料儲存，則「only」可能不夠精確。

C. If ResizeA(D) is considered, the amortized time complexity of Insert(D, x) is O(1).

• 說明： ResizeA(D) 策略是每次將 D.capacity 增加一個常數 (例如 10)。我們使用聚合分析法 (aggregate analysis) 來計算 $n$ 次 Insert 操作的總成本。
• 假設容量每次增加 $C$。初始容量為 1。
• 當 D.size 達到 D.capacity 時，會觸發 Resize。假設容量從 $k$ 增加到 $k+C$，則需要複製 $k$ 個元素，成本為 $O(k)$。
• 考慮從空陣列開始插入 $n$ 個元素。Resize 會在容量達到 $1, 1+C, 1+2C, \dots, 1+kC$ 時發生，直到容量至少為 $n$。
• 總複製成本約為 $\sum_{i=0}^{k-1} (1+iC)$，其中 $1+(k-1)C < n \le 1+kC$，所以 $k \approx n/C$。
• 這個求和是一個等差數列，其和約為 $C \cdot \frac{(n/C)^2}{2} = O(n^2/C)$。
• 因此，總複製成本為 $O(n^2)$。每次插入操作本身還有 $O(1)$ 的成本。
• 總成本為 $O(n^2)$。
• 攤還時間複雜度為 總成本 / 操作次數 $= O(n^2) / n = O(n)$。
• 結論： 此敘述不正確。攤還時間複雜度為 $O(n)$。

D. If ResizeB(D) is considered, the amortized time complexity of Insert(D, x) is O(1).

• 說明： ResizeB(D) 策略是每次將 D.capacity 加倍。我們使用聚合分析法來計算 $n$ 次 Insert 操作的總成本。
• 假設容量每次加倍。初始容量為 1。
• 當 D.size 達到 D.capacity 時，會觸發 Resize。假設容量從 $k$ 加倍到 $2k$，則需要複製 $k$ 個元素，成本為 $O(k)$。
• 考慮從空陣列開始插入 $n$ 個元素。

這題考查的核心觀念是分治法 (Divide and Conquer) 演算法的設計與時間複雜度分析，特別是應用於尋找陣列中多數元素 (Majority Element) 的問題。多數元素指的是在一個序列中出現次數嚴格超過一半的元素。此外，也考驗了對遞迴關係式 (Recurrence Relation) 的建立與主定理 (Master Theorem) 的應用，以分析演算法的時間複雜度。

完整解題過程

首先，我們來分析 FindMajorityHashValue 函式的邏輯。這個函式採用分治策略來尋找多數雜湊值。

1. 基本情況 (Base Case)：如果 low = high，表示子陣列只有一個元素，那麼這個元素的雜湊值就是該子陣列的「多數」雜湊值（因為它出現了 1 次，而長度為 1 的子陣列，多數條件是 > 1/2，即至少 1 次）。

2. 遞迴步驟 (Recursive Step)：

   • 將子陣列 A[low..high] 分成左右兩半：A[low..mid] 和 A[mid+1..high]。
   • 遞迴呼叫 FindMajorityHashValue 找出左右兩半的多數雜湊值候選 leftMajority 和 rightMajority。
   • 關鍵邏輯：如果整個陣列 A[low..high] 存在一個多數雜湊值 X，那麼 X 必須是 leftMajority 或 rightMajority 之一（如果它們不是 -1）。
     • 證明：假設 X 是 A[low..high] 的多數雜湊值，但它既不是 A[low..mid] 的多數雜湊值，也不是 A[mid+1..high] 的多數雜湊值。
       • 令子陣列 A[low..high] 的長度為 $L = \text{high} - \text{low} + 1$。
       • 左半部分 A[low..mid] 的長度為 $L_L = \text{mid} - \text{low} + 1$。
       • 右半部分 A[mid+1..high] 的長度為 $L_R = \text{high} - (\text{mid}+1) + 1$。
       • 由於 X 是 A[low..high] 的多數雜湊值，所以 $\text{count}(X, \text{low}, \text{high}) > L/2$。
       • 如果 X 不是 A[low..mid] 的多數雜湊值，則 $\text{count}(X, \text{low}, \text{mid}) \le L_L/2$。
       • 如果 X 不是 A[mid+1..high] 的多數雜湊值，則 $\text{count}(X, \text{mid}+1, \text{high}) \le L_R/2$。
       • 將兩者相加：
         $\text{count}(X, \text{low}, \text{high}) = \text{count}(X, \text{low}, \text{mid}) + \text{count}(X, \text{mid}+1, \text{high})$
         $\le \frac{L_L}{2} + \frac{L_R}{2} = \frac{L_L + L_R}{2} = \frac{L}{2}$
       • 這與 $\text{count}(X, \text{low}, \text{high}) > L/2$ 矛盾。因此，如果 A[low..high] 存在多數雜湊值，它必然是 leftMajority 或 rightMajority 之一（如果它們不是 -1）。
   • 因此，函式只需要檢查這兩個候選值 leftMajority 和 rightMajority 是否在整個 A[low..high] 範圍內滿足多數條件即可。這就是為什麼第 7 和 8 行的 CountElement 呼叫是針對 A[low..high] 整個範圍進行計數的原因。

接下來，我們逐一分析每個選項：

(A) If leftMajority = rightMajority = -1, A[low..high] may still have a majority hash value.

• 分析：根據上述證明，如果 leftMajority = -1，表示 A[low..mid] 中不存在多數雜湊值，即對於任何值 v，其在 A[low..mid] 中的出現次數 $\text{count}(v, \text{low}, \text{mid}) \le (\text{mid} - \text{low} + 1)/2$。
• 同理，如果 rightMajority = -1，表示 A[mid+1..high] 中不存在多數雜湊值，即對於任何值 v，其在 A[mid+1..high] 中的出現次數 $\text{count}(v, \text{mid}+1, \text{high}) \le (\text{high} - (\text{mid}+1) + 1)/2$。
• 如果 leftMajority = rightMajority = -1，那麼對於任何值 v，其在 A[low..high] 中的總出現次數為：
  $\text{count}(v, \text{low}, \text{high}) = \text{count}(v, \text{low}, \text{mid}) + \text{count}(v, \text{mid}+1, \text{high})$
  $\le \frac{\text{mid} - \text{low} + 1}{2} + \frac{\text{high} - (\text{mid}+1) + 1}{2}$
  $= \frac{(\text{mid} - \text{low} + 1) + (\text{high} - \text{mid})}{2} = \frac{\text{high} - \text{low} + 1}{2}$
• 這表示任何值 v 在 A[low..high] 中的出現次數都不會嚴格超過一半。因此，A[low..high] 不可能有多數雜湊值。
• 結論：選項 (A) 為錯誤。

**(B) If A[low..high] has a majority hash value and rightMajority = -1, the function should retur

核心觀念

$Join(L,x,R)$ 必須維持 BST 的大小順序，因此從 $L$ 選 $T'$ 時，只能沿 $L$ 的最右路徑選取；從 $R$ 選時，只能沿 $R$ 的最左路徑選取，路徑末端的空子樹也可選。AVL 樹要求每個節點左右子樹高度差至多為 $1$；紅黑樹則要求根與 NIL 葉為黑色、沒有紅紅相鄰，且每條根至 NIL 的路徑黑高相同。

解題方法

圖中 $L_2$ 是根節點 $2$、左右子節點 $1、3$；$x_2=4$。$R_2$ 以 $10$ 為根，左子樹根為 $7$（其左右子樹根為 $5、9$，且 $5$ 的右子為 $6$、$9$ 的左子為 $8）；右子樹根為$13$（其左右子樹根為$11、15$，$11$的右子為$12$，$15$的左右子為$14、16$，而$16$的右子為$17$）。

合法的 $T'$ 選擇共有七個：在 $L_2$ 可選根 $2$、根 $3$，或 $3$ 的空右子樹；在 $R_2$ 可選根 $10$、根 $7$、根 $5$，或 $5$ 的空左子樹。選根 $2$ 與選根 $10$ 都會得到以 $4$ 為根、$L_2$ 與 $R_2$ 分居左右的相同形狀，因此七種選擇只形成六種樹形。

選項分析

A. 正確。 七種合法選擇中，選整棵 $L_2$ 或整棵 $R_2$ 的結果相同，其餘選擇各形成不同樹形，故共有六種。

B. 錯誤。 $L_2、R_2$ 都是 AVL 樹，但至少有兩種 Join 結果仍為 AVL 樹。以葉節點高度 $0$ 計，$L_2$ 高度為 $1$，根為 $7$ 的子樹高度為 $2$，根為 $5$ 的子樹高度為 $1$，根為 $13$ 的子樹高度為 $3$。

• 選根 $7$ 為 $T'$：$4$ 的左右子樹高度為 $1、2$，故 $4$ 的高度為 $3$；根 $10$ 的左右子樹高度為 $3、3$。
• 選根 $5$ 為 $T'$：$4$ 的左右子樹高度為 $1、1$，故 $4$ 的高度為 $2$；根 $7$ 的左右子樹高度為 $2、1$，根 $10$ 的左右子樹高度則為 $3、3

這題考驗考生對動態規劃經典問題「矩陣鏈乘法 (Matrix Chain Multiplication)」的遞迴關係式理解，並要求計算特定條件下遞迴式中相關項的數量。

核心觀念：

1. 矩陣鏈乘法遞迴關係式：$m_{i,j}$ 表示計算矩陣 $M_i \dots M_j$ 所需的最小乘法次數。其遞迴關係式為 $m_{i,j} = \min_{i<k<j} (m_{i,k} + m_{k+1,j} + r_i \cdot c_k \cdot c_j)$。這個關係式適用於 $j-i \ge 2$ 的情況。
2. 基本情況 (Base Cases)：
   • $m_{i,i} = 0$ (單一矩陣不需要乘法)。
   • $m_{i,i+1} = r_i \cdot c_i \cdot c_{i+1}$ (兩個矩陣相乘只需要一次乘法)。
3. 計數問題分析：根據題目給定的 $m_{s,s+k}$，計算兩個數量 $x$ 和 $y$。

完整解題過程：

題目給定的條件是 $1 < s < s+k < n$。這意味著：

• $s \ge 2$ (因為 $s > 1$)
• $s+k \le n-1$ (因為 $s+k < n$)
• $k \ge 1$ (因為 $s+k > s$)
• 對於遞迴關係式 $m_{i,j} = \min_{i<k<j} (\dots)$，其適用條件是 $j-i \ge 2$。因此，對於 $m_{s,s+k}$，我們必須有 $(s+k)-s \ge 2$，即 $k \ge 2$。如果 $k=1$，則 $m_{s,s+1}$ 是一個基本情況，不使用此遞迴式。然而，我們將證明即使 $k=1$，最終的公式 $n+k-4$ 仍然成立。

第一部分：計算 $y$
$y$ 是當 $i=s$ 且 $j=s+k$ 時，在 Equation 1 的右側出現的不同 $m$ 項的數量。
考慮 $m_{s,s+k}$ 的遞迴式：
$m_{s,s+k} = \min_{s<p<s+k} (m_{s,p} + m_{p+1,s+k} + r_s \cdot c_p \cdot c_{s+k})$
其中 $p$ 是分割點。
$p$ 的可能取值範圍是 $s+1, s+2, \dots, s+k-1$。
$p$ 的數量為 $(s+k-1) - (s+1) + 1 = k-1$ 個。

對於每一個 $p$ 值，右側會出現兩個 $m$ 項：$m_{s,p}$ 和 $m_{p+1,s+k}$。

1. $m_{s,p}$ 項的集合：
   當 $p$ 取 $s+1, s+2, \dots, s+k-1$ 時，這些項分別是：
   $m_{s,s+1}, m_{s,s+2}, \dots, m_{s,s+k-1}$。
   這些項共有 $k-1$ 個，且它們都是不同的 (因為第二個索引不同)。

2. $m_{p+1,s+k}$ 項的集合：
   當 $p$ 取 $s+1, s+2, \dots, s+k-1$ 時，這些項分別是：
   $m_{s+2,s+k}, m_{s+3,s+k}, \dots, m_{s+k,s+k}$。
   這些項共有 $k-1$ 個，且它們都是不同的 (因為第一個索引不同)。

3. 判斷是否有重複：
   第一個集合中的所有項的起始索引都是 $s$。
   第二個集合中的所有項的起始索引都是 $s+2$ 或更大 (因為 $p \ge s+1 \Rightarrow p+1 \ge s+2$)。
   由於 $s < s+2$，這兩個集合中的所有項都是不同的。

因此，$y$ 的總數是兩個集合的項數之和：
$y = (k-1) + (k-1) = 2k-2$
這個公式對於 $k \ge 1$ 都成立。如果 $k=1$，則 $y=0$，因為 $s<p<s+1$ 沒有整數 $p$。

第二部分：計算 $x$
$x$ 是有多少個 $m_{i,j}$ 項在其遞迴計算的右側包含 $m_{s,s+k}$。
這意味著 $m_{s,s+k}$ 必須是某個 $m_{i,j}$ 計算中的 $m_{i,p}$ 或 $m_{p+1,j}$。

本題考查的核心觀念是動態規劃 (Dynamic Programming) 的計算順序。在解決具有重疊子問題 (overlapping subproblems) 和最佳子結構 (optimal substructure) 的問題時，動態規劃通常會將問題分解為更小的子問題，並依序解決這些子問題，以確保當計算一個較大的問題時，其所需的子問題結果都已經備妥。

對於矩陣鏈乘法問題的遞迴關係式：
$M_{i,j} = \min_{i < k < j} (M_{i,k} + M_{k+1,j} + r_i c_k c_j)$
其中 $M_{i,j}$ 代表計算從第 $i$ 個矩陣到第 $j$ 個矩陣連乘的最小乘法次數。

觀察遞迴關係式，要計算 $M_{i,j}$ 的值，我們需要 $M_{i,k}$ 和 $M_{k+1,j}$ 的值。

• $M_{i,j}$ 代表的矩陣鏈長度 (span 或 length) 為 $j-i+1$。
• $M_{i,k}$ 代表的矩陣鏈長度為 $k-i+1$。
• $M_{k+1,j}$ 代表的矩陣鏈長度為 $j-(k+1)+1 = j-k$。

由於 $i < k < j$，我們可以推斷出：

• $k-i+1 < j-i+1$ (因為 $k < j$)
• $j-k < j-i+1$ (因為 $i < k+1$)

這表示 $M_{i,k}$ 和 $M_{k+1,j}$ 都是比 $M_{i,j}$ 更短的矩陣鏈乘法子問題。因此，動態規劃的計算順序必須確保在計算任何一個 $M_{i,j}$ 之前，所有比它短的子問題 (即 $M_{i,k}$ 和 $M_{k+1,j}$) 都已經被計算出來。最直接且常見的順序就是依據矩陣鏈的長度 (或跨度) 遞增計算。

現在我們來分析每個選項：

A. decreasing order of $i+j$
假設我們依 $i+j$ 的遞減順序計算。考慮 $M_{1,3}$，其 $i+j = 1+3=4$。
它可能需要 $M_{2,3}$ (當 $k=1$ 時，需要 $M_{1,1}$ 和 $M_{2,3}$；$M_{2,3}$ 的 $i+j = 2+3=5$)。
由於 $M_{2,3}$ 的 $i+j$ 值 (5) 大於 $M_{1,3}$ 的 $i+j$ 值 (4)，在遞減順序中 $M_{2,3}$ 會在 $M_{1,3}$ 之前計算。這部分沒問題。
但它也可能需要 $M_{1,2}$ (當 $k=2$ 時，需要 $M_{1,2}$ 和 $M_{3,3}$；$M_{1,2}$ 的 $i+j = 1+2=3$)。
在遞減順序中 $M_{1,2}$ 的 $i+j$ 值 (3) 小於 $M_{1,3}$ 的 $i+j$ 值 (4)，這表示 $M_{1,2}$ 會在 $M_{1,3}$ 之後計算，但 $M_{1,3}$ 卻需要 $M_{1,2}$ 的結果。這會導致錯誤。
因此，選項 A 不正確。

B. increasing order of $i+j$
假設我們依 $i+j$ 的遞增順序計算。考慮 $M_{1,3}$，其 $i+j = 1+3=4$。
它需要 $M_{2,3}$ (當 $k=1$ 時，需要 $M_{1,1}$ 和 $M_{2,3}$；

同學你好，我是你們的資深補教名師。這題主要在考驗同學對樹高 (height) 與節點深度 (level) 這些基本樹狀結構概念的理解，以及如何利用常見的圖形遍歷演算法（如 BFS 和 DFS）來計算這些屬性，同時評估其時間複雜度。理解這些定義的細微差異以及不同演算法的適用性與效率，是解題的關鍵。

解題過程：

首先，我們明確題目給出的定義：

• 樹高 (height of a tree)：從根節點到任一葉節點的最大邊數 (maximum number of edges from the root to a leaf)。根據此定義，一個只有單一節點的樹（該節點既是根也是葉）其高度為 0。
• 節點 $v$ 的 level ($l(v)$)：以 $v$ 為根的子樹的高度 (height of the subtree rooted at $v$)。

接下來，我們逐一分析每個選項：

A. If v is a leaf, then l(v) = 1.

• 根據定義，如果 $v$ 是一個葉節點，則以 $v$ 為根的子樹只包含 $v$ 本身。
• 該子樹的高度是從 $v$ 到它自身（作為葉節點）的最大邊數，也就是 0 條邊。
• 因此，若 $v$ 是葉節點，則 $l(v) = 0$。
• 此敘述與定義不符。
• 【答案】：錯誤

B. If v is an internal node, l(v) = max{l(s) | s is the set of children of v}.

• 若 $v$ 是一個內部節點，則以 $v$ 為根的子樹的高度，應該是 $v$ 到其任何一個子代葉節點的最長路徑的邊數。
• 這條最長路徑必然會經過 $v$ 的某個子節點 $s$。從 $v$ 到 $s$ 有 1 條邊。
• 從 $s$ 到其子樹內的葉節點的最長路徑邊數是 $l(s)$。
• 因此，以 $v$ 為根的子樹的高度應該是 $1 + \max\{l(s) | s \text{ is a child of } v\}$。
• 此敘述缺少了從 $v$ 到其子節點的那 1 條邊。
• 【答案】：錯誤

C. We can compute l(v) by starting a breadth-first-search (BFS) from v, traversing all nodes of the subtree rooted at v, and computing the maximum distance to a leaf as l(v). Since there are no more than n v's and each BFS takes O(n) time, the total time complexity is O(n^2).

• 方法正確性：從節點 $v$ 開始進行廣度優先搜尋 (BFS)，確實可以找到從 $v$ 到其子樹中所有節點的最短距離。而 $l(v)$ 正是以 $v$ 為根的子樹中，從 $v$ 到任一葉節點的最大距離（邊數）。因此，透過 BFS 找到所有葉節點並取其與 $v$ 之間的最大距離，確實能計算出 $l(v)$。
• 時間複雜度分析：
  • 對於樹中的單一節點 $v$，在其子樹上執行一次 BFS 的時間複雜度為 $O(N_v + M_v)$，其中 $N_v$ 是 $v$ 子樹中的節點數，$M_v$ 是 $v$ 子樹中的邊數。由於是樹， $M_v = N_v - 1$，所以是 $O(N_v)$。
  • 在最壞情況下，如果 $v$ 是整棵樹的根，那麼 $N_v = n$ (總節點數)。因此，單次 BFS 可能需要 $O(n)$ 時間。
  • 如果要計算所有 $n$ 個節點的 $l(v)$ 值，並且對每個 $v$ 都執行一次 BFS，則總時間複雜度為 $n \times O(n) = O(n^2)$。
• 此敘述在方法和時間複雜度分析上均正確。
• 【答案】：正確

本題考查的核心觀念是二元樹的性質、樹的高度計算，以及「樹的重新紮根 (re-rooting)」技巧，這是一種常見的樹形動態規劃 (Tree DP) 問題，通常用於計算每個節點作為根時，樹的某些性質。

完整解題過程

題目定義了兩個值：

• $l(v)$: 節點 $v$ 在原始樹 $T$ 中，其子樹的高度。根據資料結構與演算法中樹高的標準定義，通常是指從 $v$ 到其子樹中最遠葉節點的邊數。若葉節點的高度為 0，則 $l(v) = 1 + \max(l(\text{left\_child}), l(\text{right\_child}))$，對於葉節點 $v$ 則 $l(v) = 0$。
• $r(v)$: 節點 $v$ 作為新根時，從 $v$ 向上走到其父節點，再向下走到最遠葉節點的距離。這代表了從 $v$ 往上走，進入原始樹中不屬於 $v$ 子樹的「其他部分」所能達到的最遠距離。

當 $v$ 被選為新根時，新樹的高度將是從 $v$ 出發，到新樹中最遠葉節點的距離。這個最遠路徑可以有兩種情況：

1. 路徑向下進入 $v$ 原始的子樹。最長路徑長度為 $l(v)$。
2. 路徑向上走到 $v$ 的原始父節點，然後再向下進入原始樹中不屬於 $v$ 子樹的任何其他部分。最長路徑長度為 $r(v)$。

因此，新樹的高度將是 $\max(l(v), r(v))$。

現在我們逐一分析每個選項：

(A) The new tree after selecting a new root is always a binary tree.

• 分析： 在原始二元樹中，每個節點最多有兩個子節點。當我們將節點 $v$ 重新紮根為新根時，它原始的左子節點和右子節點（如果存在）仍然是它的子節點。此外，如果 $v$ 在原始樹中有一個父節點 $p$，那麼當 $v$ 成為新根時，$p$ 將成為 $v$ 的一個子節點。
• 如果 $v$ 在原始樹中同時擁有左子節點、右子節點和父節點，那麼當 $v$ 成為新根時，它將會有三個子節點。這違反了二元樹中每個節點最多只能有兩個子節點的定義。
• 結論： 該敘述不正確。

(B) The height of the tree after making v the new root is max(l(v), r(v)).

• 分析： 如前所述，當 $v$ 成為新根時，從 $v$ 到新樹中最遠葉節點的路徑有兩種可能性：
  1. 路徑向下進入 $v$ 原始的子樹，其最長距離為 $l(v)$。
  2. 路徑向上經過 $v$ 的原始父節點，然後進入原始樹中不屬於 $v$ 子樹的其他部分，其最長距離為 $r(v)$。
• 這兩種情況涵蓋了所有從新根 $v$ 到葉節點的可能路徑。因此，新樹的總高度就是這兩種最長路徑中的最大值。
• 結論： 該敘述正確。

(C) We can compute r(v) for all tree node v's in a top-down manner. We assume that the r value of v's parent in T is known, so v only needs to consider the value of its parent and the l value of its sibling in T, in order to compute its own r.

• 分析： 計算 $r(v)$ 是一個典型的樹形動態規劃問題，通常採用兩次深度優先搜尋 (DFS) 來解決。
  1. 第一次 DFS (Post-order traversal，由下而上)： 計算所有節點的 $l(v)$ 值。對於每個節點 $v$，其 $l(v)$ 值取決於其子節點的 $l$ 值。
     • 若 $v$ 是葉節點，$l(v) = 0$。

這題考驗的核心觀念是動態規劃 (Dynamic Programming)，特別是處理序列分割 (sequence partitioning) 問題，並在分割過程中分配有限資源（此處為移除數字的數量）的技巧。這類問題通常會定義一個狀態 $m(i, j, k)$ 代表子問題的解，然後透過枚舉分割點來遞迴地求解。

完整解題過程：

1. 理解問題定義：
   我們有一個數字序列 $(v_1, \dots, v_n)$。目標是從中移除 $k$ 個數字，使得剩下的數字形成 $k+1$ 個非空連續區段 (segments)。我們希望最小化這 $k+1$ 個區段中，所有區段和的最大值。
   $m(i, j, k)$ 被定義為處理子序列 $(v_i, \dots, v_j)$ 時，移除 $k$ 個數字後所能得到的最小最大區段和。

2. 分析基礎情況 (Base Case)：
   當 $k=0$ 時，表示不移除任何數字。此時，整個子序列 $(v_i, \dots, v_j)$ 形成一個單一區段。因此，其區段和就是所有數字的和。
   $m(i, j, 0) = \sum_{p=i}^{j} v_p$
   如果 $i > j$，表示這是一個空序列，其區段和應為 $0$ (或在某些情況下定義為 $-\infty$，但對於最大和問題，0 更合理)。

3. 推導遞迴關係 (Recurrence Relation)：
   考慮如何計算 $m(i, j, k)$ 當 $k > 0$ 時。我們需要移除 $k$ 個數字。
   核心思想是：我們必須在某處進行一次「分割」，而這次分割會消耗掉一個「移除」的額度。
   假設我們選擇在 $v_x$ 和 $v_{x+1}$ 之間進行分割。這表示 $v_x$ 會是左半部分序列的最後一個元素，而 $v_{x+1}$ 會是右半部分序列的第一個元素。這次分割本身被視為消耗了 $k$ 個移除額度中的一個。
   因此，我們剩下 $k-1$ 個移除額度，需要分配給左半部分 $(v_i, \dots, v_x)$ 和右半部分 $(v_{x+1}, \dots, v_j)$。

   • 左半部分 $(v_i, \dots, v_x)$ 需要進行 $v$ 次移除。
   • 右半部分 $(v_{x+1}, \dots, v_j)$ 需要進行 $w$ 次移除。
   • 總共的移除次數為 $1 + v + w = k$，所以 $v+w = k-1$。
   • $v$ 和 $w$ 都必須是非負整數 ($v, w \ge 0$)。

   對於一個特定的分割點 $x$ 和移除額度分配 $v, w$，其結果是左右兩部分各自的最小最大區段和中的較大者：$\max(m(i, x, v), m(x+1, j, w))$。
   由於我們要最小化這個最大區段和，我們需要遍歷所有可能的分割點 $x$ 以及所有可能的移除額度分配 $v, w$，並取其中的最小值。

   分割點 $x$ 的範圍：
   $x$ 代表左半部分序列的結束索引。

   • 左半部分至少要包含一個元素，所以 $x \ge i$。

本題考查的核心觀念是動態規劃 (Dynamic Programming) 問題的性質與邊界條件 (Base Cases)。具體來說，是針對「從序列中移除 $k$ 個數字，使剩餘的 $n-k$ 個數字形成 $k+1$ 個非空連續子序列，並最小化這些子序列中最大和」這個問題的性質進行判斷。

完整解題過程：

首先，我們需要明確問題 10 中 $m(i, j, k)$ 的定義。根據題目描述，對於子序列 $(v_i, \dots, v_j)$，我們移除 $k$ 個數字，使其形成 $k+1$ 個非空連續子序列。$m(i, j, k)$ 是在這種情況下，所有可能移除方案中，所形成 $k+1$ 個子序列的最大和的最小值。

假設我們移除了 $k$ 個數字 $v_{p_1}, v_{p_2}, \dots, v_{p_k}$，其中 $i \le p_1 < p_2 < \dots < p_k \le j$。
這些移除的數字將原始子序列 $(v_i, \dots, v_j)$ 分割成 $k+1$ 個連續子序列：
$S_0 = (v_i, \dots, v_{p_1-1})$
$S_1 = (v_{p_1+1}, \dots, v_{p_2-1})$
...
$S_k = (v_{p_k+1}, \dots, v_j)$

根據題目要求，所有這些 $k+1$ 個子序列都必須是「非空」的。這對移除的索引 $p_x$ 施加了以下限制：

1. 第一個子序列 $S_0$ 非空：$p_1-1 \ge i \implies p_1 \ge i+1$。
2. 最後一個子序列 $S_k$ 非空：$j \ge p_k+1 \implies p_k \le j-1$。
3. 中間的子序列 $S_x$ 非空：$p_{x+1}-1 \ge p_x+1 \implies p_{x+1} \ge p_x+2$。

接下來，我們逐一分析每個選項：

A. We can always find an optimal solution that removes one of the largest $v_i$.
（我們總能找到一個最佳解，其中移除了其中一個最大的 $v_i$。）
這個說法是錯誤的。我們可以構造一個反例：
考慮序列 $S = (1, 100, 1, 100, 1)$，其中 $n=5$，我們要移除 $k=1$ 個數字。
根據上述限制，可移除的索引 $p_1$ 必須滿足 $1+1 \le p_1 \le 5-1$，即 $p_1 \in \{2, 3, 4\}$。
序列中最大的數字是 $100$ (即 $v_2$ 和 $v_4$)。

1. 如果移除 $v_2=100$ (最大的 $v_i$)：形成的子序列是 $(v_1)$ 和 $(v_3, v_4, v_5)$，即 $(1)$ 和 $(1, 100, 1)$。最大和為 $\max(1, 1+100+1) = \max(1, 102) = 102$。
2. 如果移除 $v_4=100$ (最大的 $v_i$)：形成的子序列是 $(v_1, v_2, v_3)$ 和 $(v_5)$，即 $(1, 100, 1)$ 和 $(1)$。最大和為 $\max(1+100+1, 1) = \max(102, 1) = 102$。
3. 如果移除 $v_3=1$ (非最大的 $v_i$)：形成的子序列是 $(v_1, v_2)$ 和 $(v_4, v_5)$，即 $(1, 100)$ 和 $(100, 1)$。最大和為 $\max(1+100, 100+1) = \max(101, 101) = 101$。
   在此例中，最佳解是移除 $v_3=1$，其最大和為 $101$。而移除最大的 $v_i$ (無論是 $v_2$ 或 $v_4$) 都會得到 $102$，並非最佳解。因此，此敘述為假。

B. We can always find an optimal solution that does not remove one of the smallest $v_i$.
（我們總能找到一個最佳解，其中沒有移除任何一個最小的 $v_i$。）
這個說法也是錯誤的。我們可以構造一個反例：
考慮序列 $S = (100, 1, 100)$，其中 $n=3$，我們要移除 $k=1$ 個數字。
根據上述限制，可移除的索引 $p_1$ 必須滿足 $1+1 \le p_1 \le 3-1$，即 $p_1=2$。

這題考驗的是對有向無環圖 (DAG) 上的任務排程基本概念的理解，特別是關於任務依賴性、處理器限制以及關鍵路徑的影響。

完整詳解

這題的核心觀念是理解在有向無環圖 (DAG) 中，任務排程如何受到任務依賴性 (dependency) 和處理器數量 (processor count) 的限制。它結合了圖論中的拓撲排序 (topological sort) 和排程理論中的關鍵路徑 (critical path) 概念。

我們逐一分析每個選項：

A. For every positive integer i, |{v | s(v) ≤ i}| ≤ p.
這個敘述表示「對於任何正整數時間步 $i$，在時間步 $i$ 或之前完成的任務總數不超過 $p$ 個」。
這與題目中「系統在一個時間步內最多只能處理 $p$ 個任務」的定義不符。題目中的限制是指在單一時間步 $i$ 內，正在執行的任務數量不能超過 $p$ 個，即 $|\{v \mid s(v) = i\}| \le p$。
如果 $s(v) \le i$，這代表任務 $v$ 在時間 $1, 2, \dots, i$ 中的某個時間步完成。累積到時間 $i$ 完成的任務總數可以遠大於 $p$。例如，如果有 $n$ 個任務，且 $n > p$，那麼在所有任務完成時（假設在時間 $T$），$|\{v \mid s(v) \le T\}| = n$，而 $n$ 可能遠大於 $p$。
因此，選項 A 是錯誤的。

B. If there is a path $(v_1, v_2, ..., v_k)$ in G, then $s(v_1) < s(v_2) < ... < s(v_k)$.
題目定義：「如果從任務 $v$ 到任務 $w$ 有一條邊，表示我們需要先完成 $v$ 才能開始 $w$」。這直接意味著任務 $v$ 的排程時間必須早於任務 $w$ 的排程時間，即 $s(v) < s(w)$。
如果圖 $G$ 中存在一條路徑 $(v_1, v_2, \dots, v_k)$，這表示存在一系列的依賴關係：$v_1 \to v_2$, $v_2 \to v_3$, $\dots$, $v_{k-1} \to v_k$。
根據依賴性規則，我們有：
$s(v_1) < s(v_2)$
$s(v_2) < s(v_3)$
$\dots$
$s(v_{k-1}) < s(v_k)$
將這些不等式串聯起來，我們得到 $s(v_1) < s(v_2) < \dots < s(v_k)$。
因此，選項 B 是正確的。

C. The number of time steps required is at least $\min(\lceil n/p \rceil, L)$, where L is the number of tasks along the longest path in G.
設總共所需的時間步數為 $T$。
我們有兩個主要的下界 (lower bound)：

1. 處理器限制的下界：總共有 $n$ 個任務，每個任務需要 1 個時間單位。總工作量為 $n$ 個時間單位。如果有 $p$ 個處理器，在最理想的情況下，所有處理器都持續忙碌，則完成所有任務至少需要 $\lceil n/p \rceil$ 個時間步。
2. 依賴性限制的下界 (關鍵路徑)：$L$ 是圖 $G$ 中最長路徑上的任務數量。

本題主要考驗考生對於圖論中「頂點覆蓋問題 (Vertex Cover Problem)」的理解，特別是兩種近似演算法 (Approximation Algorithms) 的特性與效能分析，以及如何將加權頂點覆蓋問題 (Weighted Vertex Cover Problem) 建模為整數線性規劃 (Integer Linear Program, ILP)。這是一道綜合性題目，涵蓋了演算法設計、分析與數學建模等多個面向。

(a) 舉例說明兩種近似演算法的表現

Algorithm VC-Arbitrary 的例子

目標： 找出一個例子，使得 Algorithm VC-Arbitrary 得到的解至少是最小頂點覆蓋的兩倍大。

圖例： 考慮一個包含 5 個頂點的簡單路徑圖 $P_5$。
$V = \{v_1, v_2, v_3, v_4, v_5\}$
$E = \{(v_1, v_2), (v_2, v_3), (v_3, v_4), (v_4, v_5)\}$

最小頂點覆蓋 (Minimum-size Vertex Cover, $C^*$):
我們可以選擇 $C^* = \{v_2, v_4\}$。

• $v_2$ 覆蓋了邊 $(v_1, v_2)$ 和 $(v_2, v_3)$。
• $v_4$ 覆蓋了邊 $(v_3, v_4)$ 和 $(v_4, v_5)$。
  所有邊都被覆蓋。因此，最小頂點覆蓋的大小為 $|C^*| = 2$。

Algorithm VC-Arbitrary 找到的頂點覆蓋 ($C_{alg}$):

1. 步驟 1： 演算法任意選擇一條未覆蓋的邊。假設選擇邊 $(v_1, v_2)$。
   將 $v_1$ 和 $v_2$ 加入覆蓋集合 $C_{alg}$。此時 $C_{alg} = \{v_1, v_2\}$。
   移除所有與 $v_1$ 或 $v_2$ 相連的邊：$(v_1, v_2)$ 和 $(v_2, v_3)$。
   剩餘未覆蓋的邊：$\{(v_3, v_4), (v_4, v_5)\}$。
2. 步驟 2： 演算法再次選擇一條未覆蓋的邊。假設選擇邊 $(v_3, v_4)$。
   將 $v_3$ 和 $v_4$ 加入覆蓋集合 $C_{alg}$。此時 $C_{alg} = \{v_1, v_2, v_3, v_4\}$。
   移除所有與 $v_3$ 或 $v_4$ 相連的邊：$(v_3, v_4)$ 和 $(v_4, v_5)$。
   剩餘未覆蓋的邊：$\emptyset$。
3. 終止： 沒有未覆蓋的邊，演算法終止。
   Algorithm VC-Arbitrary 找到的頂點覆蓋為 $C_{alg} = \{v_1, v_2, v_3, v_4\}$，其大小為 $|C_{alg}| = 4$。