113 年 國立中央大學資訊工程學系AI碩士班《資料結構與演算法》

核心觀念

Kruskal 演算法依邊權重由小到大檢查邊；若一條邊連接兩個不同的連通分量，就選入生成樹，若會形成環就略過。權重相同的邊可任意排序。這張圖有 6 個頂點，因此最小生成樹須選入 5 條邊。

解題方法

圖中各邊權重為：$AB=1$、$DF=1$；$CD=2$、$BF=2$、$CF=2$；$BC=3$、$DE=3$；$BD=4$、$CE=4$；$EF=5$、$AC=6$。頁首標示本題為複選題；判斷各序列時，需同時檢查所選邊的權重順序，以及每條邊是否會形成環。

選項分析

• (A) 可以。 先選 $DF$、$AB$，兩者權重均為 1。再依序選 $DC$、$BF$，兩者權重均為 2，且各自連接不同分量。最後選 $DE$，權重為 3，將頂點 $E$ 接入。整個序列權重不遞減，且沒有形成環。

• (B) 不可以。 選入 $DF$、$AB$、$BF$ 後，$C$ 仍與其他頂點分開。

核心觀念

本題考查常見五大排序演算法（Quick Sort、Heap Sort、Merge Sort、Insertion Sort、Radix Sort）之時間複雜度、**穩定性（Stability）以及比較型與非比較型排序（Comparison-based vs. Non-comparison based Sorting）**等核心性質。

關鍵定義與定理整理如下：

1. 比較型排序的時間複雜度下界（Lower Bound for Comparison Sorts）：
   任何基於元素間比較（Comparison-based）的排序演算法，在最壞情況下的時間複雜度下界為 $\Omega(n \log n)$。
2. 近乎排序（Nearly Sorted）資料之處理：
   當資料中逆序對（Inversions）的數量為 $O(1)$ 或 $O(n)$ 時，Insertion Sort 的時間複雜度為 $O(n)$，此時執行效能優於一般的 $O(n \log n)$ 演算法。
3. 穩定性（Stability）：
   排序後若鍵值（Key）相同的元素能保持其在原始陣列中的相對前後順序，則稱為穩定排序（Stable Sort）。
   • 穩定排序：Insertion Sort, Merge Sort, Radix Sort, Counting Sort, Bucket Sort。
   • 不穩定排序：Quick Sort, Heap Sort, Selection Sort。
4. 非比較型排序（Non-comparison Sorts）：
   Radix Sort 藉由將元素按位數（Digit/Character）分配至桶子（Buckets）來排序，不透過直接比較兩元素的大小關係，屬於非比較型排序。

解題方法

針對題目說明的五種排序演算法進行分類與性質分析：

據此逐一核對選項 (A)、(B)、(C)、(D) 的敘述正確性。

選項分析

• (A) 正確。
  Insertion Sort 的時間複雜度正比於陣列中「逆序對（Inversions）」的個數 $I$，總時間複雜度為 $O(n + I)$。

核心觀念

1. 二元搜尋樹（Binary Search Tree, BST）之新增（Insertion）運算機制：
   在二元搜尋樹中新增一個元素時，從根節點（Root）開始與待插入之鍵值進行比較：

   • 若待插入鍵值小於當前節點，走入左子樹。
   • 若待插入鍵值大於當前節點，走入右子樹。
   • 重複此過程直至找到對應的空指標位置（$NIL$）並建立新節點。

   因此，新增操作在每個節點僅做一次常數時間 $O(1)$ 的比較與指針移動，且僅沿著從根節點至葉節點的單一走訪路徑（Single Path）向下深入，絕不會同時遞迴搜尋左右兩棵子樹。

2. 樹形結構（Tree Topology）與遞迴關係式（Recurrence Relation）：

   • 最佳狀況（Best Case）：樹型為完全平衡二元樹（Perfectly Balanced Tree）。根節點的左右子樹節點數量大致相等（規模各約為 $n/2$）。每次比較後，搜尋範圍縮減為原本的一半，其時間複雜度遞迴式為：
     $T(n) = T(n/2) + O(1), \quad T(1) = T(0) = O(1)$
     根據主定理（Master Theorem）可解得 $T(n) = O(\log n)$。
   • 最差狀況（Worst Case）：樹型嚴重傾斜退化為單向鏈結串列（Skewed Tree / Degenerate Tree），例如輸入序列已完全排序。每次比較僅能排除當前根節點，剩餘需搜尋的子樹規模縮減 $1$（規模為 $n-1$），其時間複雜度遞迴式為：
     $T(n) = T(n-1) + O(1), \quad T(1) = T(0) = O(1)$
     經展開累加可解得 $T(n) = O(n)$。

解題方法

分析二元搜尋樹新增運算複雜度的遞迴關係式時，應著眼於兩項關鍵參數：

1. 遞迴項係數（Branching Factor）：代表每次遞迴呼叫的次數。因為 BST 的新增只選擇左或右其中一條分支，故遞迴項係數必然為 $1$。若係數為 $2$（如 $2T(n/2)$），代表同時遍歷左右兩棵子樹（例如二元樹的走訪或分治法）。
2. 規模縮減量（Subproblem Reduction Rate）：
   • 平衡樹（最佳狀況）：每次將規模縮減一半（$n \to n/2$）。

核心觀念

本題考查**動態規劃（Dynamic Programming, DP）**的基本定義、適用條件、求解順序及其時間複雜度特性。

動態規劃適用於解決具備以下兩大特性的最佳化問題：

1. 最佳子結構（Optimal Substructure）：原問題的最佳解可以由其子問題的最佳解組合而成。
2. 重疊子問題（Overlapping Subproblems）：在遞迴求解過程中，相同的子問題會重複出現，可透過記憶化（Memoization）或自底向上填表（Tabulation）將子問題解答儲存，避免重複計算。

在計算時間複雜度時，動態規劃演算法的時間複雜度通常可表示為：
$\text{時間複雜度} = O(\text{狀態總數} \times \text{每個狀態轉移所需時間})$

解題方法

解題切入點為檢驗選項中關於動態規劃兩大核心要件（最佳子結構、重疊子問題）、求解順序特性以及複雜度一般性的描述：

1. 對比動態規劃與分治法（Divide and Conquer）：兩者皆具備最佳子結構，但動態規劃處理的是「重疊子問題」，分治法處理的是「獨立子問題」。
2. 釐清求解順序：動態規劃起源於多階段決策過程（Sequential Decision Process），依據狀態依賴關聯圖（DAG）按順序（Sequential manner）由小狀態推進求解至大狀態。
3. 分析複雜度泛用性：動態規劃的時間複雜度取決於具體問題的狀態空間與轉移代價，並不存在固定的 $O(n^2)$ 複雜度上限或下限。

選項分析

• (A) 正確
  • 分析：動態規劃適用的必要條件之一即為「最佳子結構（Optimal Substructure）」。這代表問題的最佳解包含了其內部相關子問題的最佳解。若問題不具備最佳子結構，則無法透過組合子問題的最佳解來獲得整體最佳解。
• (B) 正確
  • 分析：動態規劃的核心做法是將複雜問題分解為較小且彼此「重疊的子問題（Overlapping Subproblems）」。藉由將已計算過的子問題答案記錄在記憶體中（Memoization），下次再次遇到相同子問題時即可直接查表，避免重複計算。
• (C) 正確

核心觀念

1. 走訪順序（Traversals）之終點節點（Last Visited Node）定義

   • 前序走訪（Preorder Traversal）：順序為「根 $\to$ 左子樹 $\to$ 右子樹」。
     • 若樹不為空，最後走訪的節點 $\text{LASTPRE}$ 會從根節點開始，優先走右分支；若某節點無右子樹則走左分支，直到抵達葉節點（Leaf Node）。
   • 中序走訪（Inorder Traversal）：順序為「左子樹 $\to$ 根 $\to$ 右子樹」。
     • 最後走訪的節點 $\text{LASTIN}$ 恆為整棵二元樹最右側的節點（Rightmost Node，即從根節點不斷往右子節點走到底的節點）。
   • 後序走訪（Postorder Traversal）：順序為「左子樹 $\to$ 右子樹 $\to$ 根」。
     • 最後走訪的節點 $\text{LASTPOST}$ 恆為整棵二元樹的根節點（Root Node）。

2. 二元樹型態定義

   • 滿二元樹（Full Binary Tree）：
     • 在標準資料結構教材（如 Horowitz）定義中，深度為 $k$ 的滿二元樹擁有 $2^k - 1$ 個節點（即每一層皆填滿，亦稱 Perfect Binary Tree）；另一常見定義為所有內部節點（Internal Node）皆恰有 2 個子節點（Strict / Proper Binary Tree）。在這兩種定義下，所有內部節點均同時具備左、右子節點。
   • 完全二元樹（Complete Binary Tree）：
     • 若樹深為 $k$，則第 $1$ 至 $k-1$ 層皆填滿，且第 $k$ 層的節點由左至右依序連續填入。

解題方法

分析三種走訪最後走訪節點的通用結構特徵：

1. $\text{LASTPOST}$ 恆等於根節點 $\text{Root}$。
2. $\text{LASTIN}$ 恆等於樹的最右側節點（從 $\text{Root}$ 出發一路向右走到底）。
3. $\text{LASTPRE}$ 為：從 $\text{Root}$ 開始，若有右子節點則走右邊，無右子節點但有左子節點則走左邊，直至到達葉節點。

對於 滿二元樹（Full Binary Tree）：
由於所有非葉節點均含有右子節點，從根節點尋找 $\text{LASTPRE}$ 時，每一步均選擇走右子樹，最終抵達最右側葉節點；而 $\text{LASTIN}$ 亦為一路往右走到底的最右側葉節點。因此在滿二元樹中，$\text{LASTIN}$ 與 $\text{LASTPRE}$ 必指向同一節點。

對於 完全二元樹（Complete Binary Tree）：
當節點個數為特定數值（例如 $N=6$）時，最右側子樹的內部節點可能僅有左子節點而無右子節點，導致 $\text{LASTIN}$ 與 $\text{LASTPRE}$ 走訪順序不同，且兩者均不等於根節點 $\text{LASTPOST}$。

選項分析

• (A) 錯誤。
  • 說明：在任何非空二元樹中，$\text{LASTPOST}$ 恆為根節點。而對於節點數 $N \ge 3$ 的完全二元樹，根節點含有右子樹，中序走訪最後走訪的 $\text{LASTIN}$ 在右子樹中，與根節點 $\text{LASTPOST}$ 不相等。
  • 反例：設完全二元樹有 $3$ 個節點（根節點為 $1$，左子節點為 $2$，右子節點為 $3$）。
    • 中序走訪順序：$2 \to 1 \to 3$，故 $\text{LASTIN} = 3$。

核心觀念

本題考最小生成樹（MST）及「指定頂點為葉節點」的限制。

• 無向圖的邊 $\{i,j\}$ 只有一個權重，因此權重矩陣必須滿足 $W_{ij}=W_{ji}$。
• 生成樹的「根」只是指定走訪起點，不影響所選邊及總成本。
• 若要求頂點 $0$ 為葉節點，則它的度數必須為 $1$，只能以一條邊接入其餘頂點形成的生成樹。

解題方法

原卷第 $2$ 頁的矩陣確實寫成 $W_{13}=5$、$W_{31}=4$，以及 $W_{04}=5$、$W_{40}=4$；其餘對稱位置的數值一致。這兩組數值違反無向圖權重矩陣的對稱性，題目缺少一致的邊權重定義，以下分別列出以上三角、下三角為準的結果。

一、未限制頂點 $0$ 為葉節點

兩種取法都有以下四條邊：

選取它們會形成一棵生成樹，連接關係為 $1-0-3-4-2$，成本為

這四個權重也是全圖最小的四個邊權重；任何五頂點生成樹都需要四條邊，因此成本至少為 $7$，上述生成樹已達到下界。

把這棵樹的根指定為 $0$，最低成本是 $7$；把根指定為其他頂點，最低成本仍是 $7$。

二、限制頂點 $0$ 為葉節點

刪除葉節點 $0$ 及其唯一相接的邊後，剩下的四個頂點必須形成一棵生成樹。因此：

兩種取法中，頂點 $0$ 的最便宜接入邊都是權重 $1$ 的 $\{0,1\}$ 或 $\{0,3\}$。

核心觀念

本題考查**中序運算式（Infix Expression）轉換為後序運算式（Postfix Expression / Reverse Polish Notation, RPN）**的邏輯與推導。主要涉及以下核心要素：

1. 運算子優先順序（Operator Precedence）：
   • 高優先順序：乘法 $*$ 與除法 $/$。
   • 低優先順序：加法 $+$ 與減法 $-$。
2. 結合律（Associativity）：
   • 四則運算子皆具備左結合性（Left-to-Right Associativity）。當運算子優先順序相同時，由左至右依序處理。
3. 後序運算式定義：
   • 將二元運算子寫在兩個運算元之後，即 $(A \text{ op } B) \implies A B \text{ op}$。後序運算式不需要括號即可唯一確定運算順序。

解題方法

轉換中序運算式至後序運算式最嚴謹的方法為完全括號法（Parenthesization Method）：

1. 依優先順序與結合律加括號：明確每一個子運算的範疇。
2. 運算子後移：將每一個括號內的運算子移動到該括號的右邊界之外。
3. 移除所有括號：去除括號後即得正確的後序運算式。

題目中二算式之推導步驟：

算式一（對應選項 A、B）：$A+B-D*E/F+B*C$

1. 加括號：
   • 乘除優先且左結合：$((D * E) / F)$ 與 $(B * C)$
   • 加減左結合：$(((A + B) - ((D * E) / F)) + (B * C))$
2. 運算子後移：
   • $(A + B) \implies (A \, B)+$
   • $((D * E) / F) \implies ((D \, E)* F)/$
   • $(A \, B)+ - ((D \, E)* F)/ \implies ((A \, B)+ (D \, E)* F)/)-$
   • $(B * C) \implies (B \, C)*$
   • $(((A \, B)+ (D \, E)* F)/)- + (B \, C)* \implies (((A \, B)+ (D \, E)* F)/)- (B \, C)*)+$
3. 去括號：
   $\text{AB+DE*F/-BC*+}$

算式二（對應選項 C、D）：$A+B*D*E/F+B*C$

1. 加括號：

核心觀念

本題考查雙向鏈結串列（Doubly Linked List）指標操作與串列反轉（List Reversal）演算法。

在雙向鏈結串列中，每個節點皆包含兩個指標：

• prev：指向前一個節點。
• next：指向後一個節點。

當我們遍歷串列，將每一個節點的 prev 與 next 指標相互交換（Swap），並在迴圈結束後將表頭指標（*head_ref）重新指向原串列的尾節點（Tail Node）時，即可完成雙向鏈結串列的原地（In-place）反轉。

解題方法

1. 程式碼邏輯分析與推導

分析 fun 函數的內部運作步驟：

void fun(struct node **head_ref)
{
    struct node *temp = NULL;
    struct node *current = *head_ref;
    while (current != NULL)
    {
        temp = current->prev;          // 步驟 1: 暫存原先的前驅指標 prev
        current->prev = current->next; // 步驟 2: 將 prev 改指向原先的後繼節點 next
        current->next = temp;          // 步驟 3: 將 next 改指向原先的前驅節點 temp
        current = current->prev;       // 步驟 4: 移動 current 至下一個待處理節點
    }
    if(temp != NULL)
        *head_ref = temp->prev;        // 步驟 5: 更新頭指標指向原串列的尾節點
}

• 關鍵推進邏輯（步驟 4）：
  執行 current = current->prev; 時，由於步驟 2 已將 current->prev 指向原先的 current->next，因此這一行實際上等同於讓 current 指向原串列中的下一個節點，從而順利向後遍歷整個串列。

• 頭指標更新邏輯（步驟 5）：
  當迴圈結束時（current == NULL），temp 會停在原串列倒數第二個節點。而在最後一次迭代中，原尾節點的 prev 已被改為 NULL，next 則改指向 temp。因此在反轉後的串列中，temp->prev 恰好指向原串列的尾節點（即反轉後的全新頭節點）。透過 *head_ref = temp->prev;，頭指標被正確更新。

由此可知，fun 函數的功能為：將傳入的雙向鏈結串列全域反轉（Reverse）。

2. 實例推導

核心觀念

本題考查**單向鏈結串列（Singly Linked List）的原地反轉（Iterative In-place Reversal）**以及 **C 語言指標的指標（Double Pointer / Pointer to Pointer）**應用。

1. 三指標迴圈控制：
   在迭代法反轉單向鏈結串列時，需要維持三個指標：

   • prev：記錄當前節點的前驅節點（反轉後的後繼節點）。
   • current：記錄當前正在處理的節點。
   • next：暫存當前節點原本的下一個節點，防止反轉指標時造成斷鏈（Memory Leak / Disconnection）。

2. 傳址呼叫（Call by Reference / Pass by Address）：
   函式參數宣告為 struct node** head_ref（雙重指標）。若要讓主呼叫端（Caller）的頭指標真正指向反轉後的新頭節點，必須透過解指標（Dereference）操作 *head_ref 來修改主呼叫端的頭指標內容。

解題方法

1. 演算法追蹤（Tracing）

假設輸入的鏈結串列為：$1 \to 2 \to 3 \to \text{NULL}$，指標 head_ref 指向儲存節點 $1$ 位址的指標。

• 初始狀態：
  • prev = NULL
  • current = *head_ref（指向節點 $1$）
• 迴圈過程 (while (current != NULL))：
  • 第 1 次迭代：
    • next = current->next（暫存節點 $2$）
    • current->next = prev（節點 $1$ 指向 $\text{NULL}$）
    • prev = current（prev 指向節點 $1$）
    • current = next（current 指向節點 $2$）
  • 第 2 次迭代：
    • next = current->next（暫存節點 $3$）
    • current->next = prev（節點 $2$ 指向節點 $1$）
    • prev = current（prev 指向節點 $2$）
    • current = next（current 指向節點 $3$）
  • 第 3 次迭代：
    • next = current->next（暫存 $\text{NULL}$）
    • current->next = prev（節點 $3$ 指向節點 $2$）
    • prev = current（prev 指向節點 $3$）

本題考查的核心觀念是遞迴函式在二元樹上的應用與分析，特別是理解遞迴的基底條件 (base cases) 和遞迴關係 (recursive relation) 如何共同決定函式的最終功能。透過追蹤函式在不同節點類型（空節點、葉節點、內部節點）上的行為，可以推斷其計算目的。

完整解題過程：

我們來逐步分析給定的函式 f：

int f(struct node *root)
{
    if (root == NULL)
        return 0; // 條件 1
    if (root->left == NULL && root->right == NULL)
        return 0; // 條件 2
    return 1 + f(root->left) + f(root->right); // 條件 3
}

1. 基底條件 (Base Case 1): if (root == NULL) return 0;
   當函式遇到一個空指標（即沒有節點）時，它會回傳 $0$。這表示空子樹對函式的計數沒有貢獻。

2. 基底條件 (Base Case 2): if (root->left == NULL && root->right == NULL) return 0;
   當函式遇到一個節點，且該節點的左子樹和右子樹都是空指標時，這表示該節點是一個葉節點 (leaf node)。對於葉節點，函式也回傳 $0$。這意味著葉節點本身不被計數。

3. 遞迴關係 (Recursive Relation): return 1 + f(root->left) + f(root->right);
   如果一個節點既不是空指標，也不是葉節點（即它至少有一個子節點），那麼它就是一個內部節點 (internal node)。對於這種節點，函式會回傳 $1$ 加上其左子樹和右子樹遞迴呼叫的結果之和。這個 $1$ 的回傳值表示該內部節點本身被計數了一次。

綜合分析：

核心觀念

本題考單一起點最短路徑。$d[i,j]$ 表示從節點 $i$ 到節點 $j$ 的最短路徑長度；路徑長度是沿途有向邊權重的總和。由於圖中有負權邊，可用 Bellman–Ford 的邊鬆弛觀念計算，不能只按邊權皆非負的情況處理。

解題方法

從節點 $0$ 出發，先比較到節點 $1$、$3$ 的路徑：

到節點 $3$ 有直接路徑 $0\to3$，長度為 $6$；也有 $0\to1\to3$，長度為 $7+(-2)=5$，因此

節點 $2$ 可由 $1\to2$ 到達，因此

節點 $4$ 可沿 $0\to1\to3\to4$ 到達，長度為 $7-2+2=7$；

核心觀念

1. 單源最短路徑問題（Single-Source Shortest Path, SSSP）：
   在給定帶權圖 $G = (V, E)$ 中，指定一源點（Source Node）$s = 0$，求源點到圖中其餘所有頂點 $v \in V$ 的最短距離 $d[s, v]$（題目簡寫為 $d[0, v]$）。
2. Dijkstra 演算法（Dijkstra's Algorithm）：
   適用於邊權重為非負數（$w(u, v) \ge 0$）的圖形。演算法採用貪婪策略（Greedy Strategy），每次從未存取的頂點集合中選取當前估計距離最小的頂點 $u$ 加入已確定集合 $S$，並對 $u$ 的鄰接邊進行鬆弛操作（Relaxation）。
3. 最短路徑數量統計（Shortest Path Counting）：
   在執行 Dijkstra 演算法時，可同時維護一陣列 $num[v]$ 記錄從源點 $0$ 到頂點 $v$ 的最短路徑總條數。其動態規劃遞迴關係式如下：
   • 若發現更短路徑（即 $d[u] + w(u, v) < d[v]$）：
     $d[v] = d[u] + w(u, v), \quad num[v] = num[u]$
   • 若發現等長的最短路徑（即 $d[u] + w(u, v) = d[v]$）：
     $num[v] = num[v] + num[u]$

解題方法

本題依據前題（第 11 題）給定之帶權圖 $G=(V, E)$（頂點集合 $V = \{0, 1, 2, \dots, 9\}$ 及其邊權重矩陣）進行計算。

以頂點 $0$ 為源點，初始化距離陣列 $d[0] = 0$，其餘 $d[v] = \infty$；路徑計數陣列 $num[0] = 1$，其餘 $num[v] = 0$。

執行 Dijkstra 演算法之鬆弛與路徑統計推導結果如下表所示：

核心觀念

本題考查**漸進符號（Asymptotic Notations）**的嚴格數學定義與代數運算性質，包含：

1. Big-$O$ 定義：$f(n) = O(g(n)) \iff \exists c > 0, n_0 > 0$，使得對所有 $n \ge n_0$，皆滿足 $0 \le f(n) \le c \cdot g(n)$。
2. Little-$o$ 定義：$f(n) = o(g(n)) \iff \lim_{n \to \infty} \frac{f(n)}{g(n)} = 0$。
3. Big-$\Theta$ 定義：$f(n) = \Theta(g(n)) \iff f(n) = O(g(n))$ 且 $f(n) = \Omega(g(n))$。
4. 對數與指數的漸進比較性質。

解題方法

驗證漸進分析敘述時，切入點分為兩類：

• 證明敘述正確：直接由定義出發，透過不等式變形找出符合條件的正常數 $c$ 與 $n_0$，或利用極限性質證明。
• 證明敘述錯誤：構造合法的反例函數（Counterexample），說明前提成立但結論不成立。

選項分析

(A) 正確

• 推導與證明：
  已知 $f(n) = O(g(n))$，代表存在常數 $c > 0$ 與 $n_0 \ge 1$，使得對所有 $n \ge n_0$，$0 \le f(n) \le c \cdot g(n)$。
  題目給定 $g(n) \ge 2$ 且 $f(n) \ge 1$，兩邊取底數為 $2$ 的對數（$\lg$）可得：
  $\lg f(n) \le \lg(c \cdot g(n)) = \lg c + \lg g(n)$
  因為 $g(n) \ge 2$，所以 $\lg g(n) \ge \lg 2 = 1$。
  • 若 $c \le 1$，則 $\lg c \le 0$，直接推得 $\lg f(n) \le \lg g(n)$。
  • 若 $c > 1$，則 $\lg c > 0$，可將常數項放大：$\lg c = \lg c \cdot 1 \le \lg c \cdot \lg g(n)$。
    此時：
    $\lg f(n) \le \lg c \cdot \lg g(n) + \lg g(n) = (1 + \lg c) \lg g(n)$
    令新常數 $c' = \max(1, 1 + \lg c) > 0$，則對所有 $n \ge n_0$，均滿足：
    $0 \le \lg f(n) \le c' \cdot \lg g(n)$
    故符合定義 $\lg f(n) = O(\lg g(n))$。

(B) 正確

• 推導與證明：
  已知 $f(n) = O(n)$，代表存在常數 $c > 0$ 與 $n_0 \ge 1$，使得對所有 $n \ge n_0$，$0 \le f(n) \le c \cdot n$。
  兩邊同乘以 $f(n)$（因 $f(n) \ge 0$）：
  $f(n) \times f(n) \le (c \cdot n) \times (c \cdot n) = c^2 \cdot n^2$
  令新常數 $c' = c^2 > 0$，對所有 $n \ge n_0$ 均滿足：

核心觀念

本題旨在考驗漸近複雜度（Asymptotic Complexity）分析與遞迴關係式（Recurrence Relation）的求解。主要涵蓋以下核心工具與定理：

1. 主定理（Master Theorem）：適用於型如 $T(n) = a T(n/b) + f(n)$ 的分治型遞迴式，根據 $f(n)$ 與 $n^{\log_b a}$ 的成長速率比較分為三種 Case：
   • Case 1：若 $f(n) = O(n^{\log_b a - \epsilon})$（其中 $\epsilon > 0$），則 $T(n) = \Theta(n^{\log_b a})$。
   • Case 2：若 $f(n) = \Theta(n^{\log_b a} \lg^k n)$（其中 $k \ge 0$），則 $T(n) = \Theta(n^{\log_b a} \lg^{k+1} n)$。
   • Case 3：若 $f(n) = \Omega(n^{\log_b a + \epsilon})$（其中 $\epsilon > 0$）且滿足正則條件（Regularity Condition）$a f(n/b) \le c f(n)$（$c < 1$），則 $T(n) = \Theta(f(n))$。
2. 差分法（Substitution / Subtracting equations）：對於含有累加項（$\sum$）的全歷史遞迴式，可利用 $t(n) - t(n-1)$ 消去累加項，化簡為一階線性遞迴關係式。
3. 級數夾擠與積分逼近法（Integral Approximation）：對於無法直接套用主定理的非分治遞迴式（如 $a(n) = a(n-1) + g(n)$），可展開為 $\sum g(k)$，並利用定積分或上下界夾擠判定漸近階數。

解題方法

針對題目給定之 5 個遞迴關係式，分別進行推導：

1. 函數 $t(n) = n + \sum_{k=1}^{n-1} [t(k) + t(n-k)]$

注意累加項中 $t(k) + t(n-k)$ 當 $k$ 從 $1$ 到 $n-1$ 時，兩項總和完全對稱：
$\sum_{k=1}^{n-1} [t(k) + t(n-k)] = 2 \sum_{k=1}^{n-1} t(k)$
因此遞迴式可寫為：
$t(n) = n + 2 \sum_{k=1}^{n-1} t(k)$
同理，將 $n$ 以 $n-1$ 代入可得：
$t(n-1) = (n-1) + 2 \sum_{k=1}^{n-2} t(k)$
兩式相減：
$t(n) - t(n-1) = 1 + 2 t(n-1) \implies t(n) = 3 t(n-1) + 1$
解此一階線性遞迴關係式：
$t(n) = 3^1 t(n-1) + 1 = 3^2 t(n-2) + 3 + 1 = \dots = 3^{n-2} t(2) + \sum_{i=0}^{n-3} 3^i = \Theta(3^n)$

2. 函數 $g(n) = g(n/2) + \sqrt{n}$

符合主定理形式，參數為 $a = 1, b = 2, f(n) = \sqrt{n} = n^{1/2}$：

• 計算臨界指數：$n^{\log_b a} = n^{\log_2 1} = n^0 = 1$。
• 比較成長階數：$f(n) = n^{1/2} = \Omega(n^{0 + 1/2})$，符合 Case 3 條件（取 $\epsilon = 0.5$）。
• 檢驗正則條件：$a f(n/b) = 1 \cdot \sqrt{n/2} = \frac{1}{\sqrt{2}} \sqrt{n} \le c \sqrt{n}$，取 $c = \frac{1}{\sqrt{2}} < 1$ 成立。
• 由主定理 Case 3 可得：$g(n) = \Theta(f(n)) = \Theta(\sqrt{n})$。

3. 函數 $f(n) = 2 f(n/4) + \sqrt{n}$

符合主定理形式，參數為 $a = 2, b = 4, f(n) = \sqrt{n} = n^{1/2}$：

• 計算臨界指數：$n^{\log_b a} = n^{\log_4 2} = n^{1/2} = \sqrt{n}$。
• 比較成長階數：$f(n) = \Theta(n^{\log_4 2}) = \Theta(\sqrt{n})$，符合 Case 2 條件（$k = 0$）。
• 由主定理 Case 2 可得：$f(n) = \Theta(n^{\log_4 2} \lg n) = \Theta(\sqrt{n} \lg n)$。

4. 函數 $h(n) = 5 h(n/2) + (n \lg n)^2$

核心觀念

本題考查圖形理論（Graph Theory）中**最小生成樹（Minimum Spanning Tree, MST）**的核心定理與性質，包含：

1. 割性質（Cut Property）：對圖形 $G=(V, E)$ 的任意切割 $(S, V \setminus S)$，若邊 $e$ 是跨越該切割的所有邊中權重嚴格最小者（unique lightest cross edge），則邊 $e$ 必定包含於 $G$ 的每一個 MST 中。
2. 迴路性質（Cycle Property）：對圖形 $G=(V, E)$ 中的任意簡單迴路 $C$，若邊 $e$ 是該迴路上權重嚴格最大者（unique heaviest edge），則邊 $e$ 絕不可能包含於 $G$ 的任何 MST 中。
3. 橋／割邊（Bridge / Cut Edge）：若移除某邊會導致圖形不連通，則該邊稱為橋。生成樹為了維持全圖連通性，必須包含圖形中的所有橋，不論其權重大小。
4. 最短路徑與 MST 的差異：單源最短路徑（Shortest Path）關注的是特定兩點間的路徑累積權重和，而 MST 關注的是全圖連通的總邊權重和，兩者的最佳化目標不同。

解題方法

針對此類觀念導向的選擇題，切入點如下：

1. 定理驗證：若選項敘述符合 MST 的標準定理（如 Cut Property 或 Cycle Property），則直接給出嚴謹的邏輯推導。
2. 反例建構（Counterexample）：若選項敘述並非通用定理，則嘗試建構最小規模的反例圖形（如少數頂點與邊的簡單權重圖），只要舉出一個反例即可判定該選項錯誤。

選項分析

(A) 錯誤

• 題目敘述：若 $|E| \ge |V| - 1$ 且存在唯一的最重邊，則該邊不可能屬於 $G$ 的任何 MST。
• 錯誤原因：若圖形 $G$ 本身為一棵樹（即 $|E| = |V| - 1$），則 $G$ 的生成樹即為其本身（唯一的生成樹）。此時，圖中所有的邊（包含該唯一的最重邊）都是連通圖形不可或缺的「橋（Bridge）」，因此該最重邊必定包含於 $G$ 的 MST 中。
• 反例：設 $G$ 為包含 3 個頂點與 2 條邊的路徑圖 $A - B - C$，邊權重分別為 $w(A,B) = 1$、$w(B,C) = 2$。邊 $(B,C)$ 是唯一的最重邊，但為了連通所有頂點，$G$ 唯一的 MST 必須包含 $(B,C)$。

(B) 正確

• 題目敘述：若 $G$ 包含一個迴路且該迴路上有唯一的最重邊 $e$，則 $e$ 不可能屬於 $G$ 的任何 MST。
• 敘述分析：此即為標準的 Cycle Property（迴路性質）。
• 證明：採用反證法（Proof by Contradiction）。假設存在一個包含邊 $e$ 的 MST 記為 $T$。若將 $e$ 自 $T$ 中移除，$T$ 會分裂成兩個連通元件 $T_1$ 與 $T_2$。因為 $e$ 原本屬於迴路 $C$，則迴路 $C$ 上必存在另一條邊 $e' \neq e$ 同樣跨越 $T_1$ 與 $T_2$。根據題意，$e$ 是迴路 $C$ 上唯一的最重邊，故 $w(e') < w(e)$。此時若構造新生成樹 $T' = T \setminus \{e\} \cup \{e'\}$，其總權重為 $w(T') = w(T) - w(e) + w(e') < w(T)$，這與 $T$ 為最小生成樹的假設矛盾。故 $e$ 絕不可能屬於任何 MST。

(C) 正確

• 題目敘述：若 $G$ 中權重最小的邊是唯一的，則它必定包含於 $G$ 的每一個 MST 中。
• 敘述分析：此即為標準 Cut Property（割性質） 的特例。
• 證明：設 $e = (u, v)$ 為全圖中嚴格最小的邊（即對任意 $e' \neq e$ 皆有 $w(e) < w(e')$）。考慮將頂點集 $V$ 切割為 $S = \{u\}$ 與 $V \setminus S$。

核心觀念

本題考查核心資料結構與演算法中「排序演算法（Sorting Algorithms）」的設計範式、時間複雜度分析及理論下界限制：

1. 分治法（Divide-and-Conquer Paradigm）：
   • 合併排序（Merge Sort）與快速排序（Quick Sort）均建構於分治原則：將大問題分割（Divide）為小問題、遞迴解決（Conquer）後進行合併或劃分（Combine）。
2. 經典排序演算法之時間複雜度：
   • Merge Sort：最佳 $O(n \log n)$、平均 $O(n \log n)$、最壞 $O(n \log n)$。
   • Heap Sort：最佳 $O(n \log n)$、平均 $O(n \log n)$、最壞 $O(n \log n)$。
   • Quick Sort：最佳 $O(n \log n)$、平均 $O(n \log n)$、最壞 $O(n^2)$。
   • Insertion Sort：最佳 $O(n)$（輸入近乎已排序時）、平均 $O(n^2)$、最壞 $O(n^2)$。
3. 排序演算法之理論下界（Lower Bound）：
   • 比較型排序（Comparison-based Sorting）：利用決策樹（Decision Tree）模型推導，在最壞情況下所需比較次數的下界為 $\Omega(n \log n)$。
   • 非比較型排序（Non-comparison Sorting）：如計數排序（Counting Sort）、基數排序（Radix Sort）與桶排序（Bucket Sort），突破比較限制，在特定條件下可達到線性時間複雜度 $O(n)$。

解題方法

本題為研究所入學考試常見之複選敘述判斷題，目標為選出**敘述錯誤（incorrect）**的選項。切入步驟如下：

1. 檢查各演算法的設計範式，確認 Merge Sort 與 Quick Sort 是否同屬分治法。
2. 分析資料在近乎已排序（Nearly Sorted）狀態下的演算法效能表現。
3. 查核各演算法於最壞情況（Worst-case）與期望/平均情況（Expected/Average-case）的時間複雜度 Big-$O$ 階次。
4. 釐清比較型排序的 $\Omega(n \log n)$ 下界與非比較型排序線性時間 $O(n)$ 之適用前提。

選項分析

• (A) 正確：Merge Sort 與 Quick Sort 皆基於**分治法（Divide and Conquer）**設計。Merge Sort 先對半分割再遞迴排序並合併；Quick Sort 則先選取基準值（Pivot）進行劃分（Partition），使左側不小於/不大於右側後遞迴排序。兩者本質皆屬於分治演算法。

• (B) 錯誤：當大部分數字已在正確位置（Nearly Sorted）時，傳統 Quick Sort（若固定選擇第一個或最後一個元素作為 Pivot）每次劃分會極度不對稱（切為 $0$ 與 $n-1$），導致遞迴樹深度退化為 $O(n)$，時

核心觀念

本題考查**雜湊表（Hash Table）在開放定址法（Open Addressing）**下的碰撞解決策略——偽隨機探查（Pseudo-Random Probing / Random Probing）。

1. 基本雜湊函數（Primary Hash Function）：
   $H(k) = k \bmod 7$
   將鍵值 $k$ 映射至雜湊表大小 $m = 7$ 的索引範圍 $\{0, 1, 2, 3, 4, 5, 6\}$ 中。

2. 偽隨機探查策略（Random Probing Strategy）：
   當發生碰撞（Collision）時，依據題目給定的偽隨機遞迴式 $i = (i + 5) \bmod 7$ 計算下一個探查位置。即當位址 $p$ 發生碰撞時，下一次探查的目標位址為：
   $p_{\text{next}} = (p + 5) \bmod 7$
   由於步長 $5$ 與表長 $7$ 互質（$\gcd(5, 7) = 1$），該探查序列能夠無重複地遍歷整個雜湊表的所有槽位（Slots）。

解題方法

建立大小為 $7$ 的雜湊表，初始狀態各槽位皆為空（Empty）：

• [0]: 空, [1]: 空, [2]: 空, [3]: 空, [4]: 空, [5]: 空, [6]: 空

依序由左至右插入鍵值 15, 11, 25, 16, 9, 8, 12：

1. 插入 $15$：

   • 初次位址：$H(15) = 15 \bmod 7 = 1$。
   • 位置 $1$ 為空，直接存入。
   • 狀態：[1] = 15

2. 插入 $11$：

   • 初次位址：$H(11) = 11 \bmod 7 = 4$。
   • 位置 $4$ 為空，直接存入。
   • 狀態：[1] = 15, [4] = 11

3. 插入 $25$：

   • 初次位址：$H(25) = 25 \bmod 7 = 4$。
   • 位置 $4$ 已被 $11$ 佔用（碰撞）。
   • 第 $1$ 次探查位址：$(4 + 5) \bmod 7 = 2$。
   • 位置 $2$ 為空，存入。
   • 狀態：[1] = 15, [2] = 25, [4] = 11

4. 插入 $16$：

   • 初次位址：$H(16) = 16 \bmod 7 = 2$。
   • 位置 $2$ 已被 $25$ 佔用（碰撞）。
   • 第 $1$ 次探查位址：$(2 + 5) \bmod 7 = 0$。
   • 位置 $0$ 為空，存入。
   • 狀態：[0] = 16, [1] = 15, [2] = 25, [4] = 11

5. 插入 $9$：

   • 初次位址：$H(9) = 9 \bmod 7 = 2$。
   • 位置 $2$ 已被 $25$ 佔用（碰撞）。
   • 第 $1$ 次探查位址：$(2 + 5) \bmod 7 = 0$，位置 $0$ 已被 $16$ 佔用（碰撞）。
   • 第 $2$ 次探查位址：$(0 + 5) \bmod 7 = 5$。
   • 位置 $5$ 為空，存入。
   • 狀態：[0] = 16, [1] = 15, [2] = 25, [4] = 11, [5] = 9

核心觀念

• 矩陣鏈乘積問題（Matrix Chain Multiplication Problem）：給定一連串矩陣 $M_1, M_2, \dots, M_n$，求將它們依序相乘時所需的最少純量乘法（Scalar Multiplications）次數。
• 動態規劃（Dynamic Programming, DP）：矩陣相乘具備結合律，不同的加括號方式（Parenthesization）計算次數差異極大。由於具有最佳子結構（Optimal Substructure）與重疊子問題（Overlapping Subproblems）的特性，若採用單純的分治法會導致重複計算大量的子問題，因此本題屬於經典的動態規劃問題。
• 純量乘法次數計算公式：若矩陣 $A$ 維度為 $p \times q$，矩陣 $B$ 維度為 $q \times r$，則兩矩陣相乘 $A \times B$ 需要花費 $p \cdot q \cdot r$ 次純量乘法，相乘後產生的矩陣維度為 $p \times r$。
• DP 遞迴轉移方程式：設 $m[i, j]$ 表示將第 $i$ 個矩陣至第 $j$ 個矩陣相乘所需的最少純量乘法次數，則轉移方程式為：
  $m[i, j] = \begin{cases} 0 & \text{if } i = j \\ \min_{i \le k < j} \{ m[i, k] + m[k+1, j] + p_{i-1} \cdot p_k \cdot p_j \} & \text{if } i < j \end{cases}$
  其中 $p_{i-1} \times p_i$ 為第 $i$ 個矩陣的維度。

解題方法

本題給定 4 個矩陣：

• $Q$（即 $M_1$）：維度 $13 \times 12 \implies (p_0, p_1) = (13, 12)$
• $R$（即 $M_2$）：維度 $12 \times 30 \implies (p_1, p_2) = (12, 30)$
• $S$（即 $M_3$）：維度 $30 \times 15 \implies (p_2, p_3) = (30, 15)$
• $T$（即 $M_4$）：維度 $15 \times 18 \implies (p_3, p_4) = (15, 18)$

維度序列為 $p = [p_0, p_1, p_2, p_3, p_4] = [13, 12, 30, 15, 18]$。採用由底向上（Bottom-up）動態規劃法計算 DP 表格 $m[i, j]$：

1. 矩陣鏈長度 $l = 1$（Base Cases）

$m[1,1] = m[2,2] = m[3,3] = m[4,4] = 0$

2. 矩陣鏈長度 $l = 2$（相鄰兩矩陣相乘）

• $m[1, 2]$（計算 $QR$）：
  $m[1, 2] = p_0 \cdot p_1 \cdot p_2 = 13 \times 12 \times 30 = 4680$
• $m[2, 3]$（計算 $RS$）：
  $m[2, 3] = p_1 \cdot p_2 \cdot p_3 = 12 \times 30 \times 15 = 5400$
• $m[3, 4]$（計算 $ST$）：
  $m[3, 4] = p_2 \cdot p_3 \cdot p_4 = 30 \times 15 \times 18 = 8100$

3. 矩陣鏈長度 $l = 3$（三個矩陣相乘）

• 計算 $m[1, 3]$（$QRS$）：

  • 切割點 $k = 1$（形式為 $Q(RS)$）：
    $m[1,1] + m[2,3] + p_0 p_1 p_3 = 0 + 5400 + 13 \times 12 \times 15 = 5400 + 2340 = 7740$
  • 切割點 $k = 2$（形式為 $(QR)S$）：
    $m[1,2] + m[3,3] + p_0 p_2 p_3 = 4680 + 0 + 13 \times 30 \times 15 = 4680 + 5850 = 10530$
  • 取最小值：$m[1, 3] = 7740$，最優加括號為 $Q(RS)$。

• 計算 $m[2, 4]$（$RST$）：

  • 切割點 $k = 2$（形式為 $R(ST)$）：
    $m[2,2] + m[3,4] + p_1 p_2 p_4 = 0 + 8100 + 12 \times 30 \times 18 = 8100 + 6480 = 14580$
  • 切割點 $k = 3$（形式為 $(RS)T$）：
    $m[2,3] + m[4,4] + p_1 p_3 p_4 = 5400 + 0 + 12 \times 15 \times 18 = 5400 + 3240 = 8640$

核心觀念

本題考查**霍夫曼編碼（Huffman Coding）與貪婪演算法（Greedy Algorithm）**的核心原理及應用：

1. 最佳前綴碼（Optimum Prefix Code）：任何字元編碼皆非其他字元編碼的前綴，確保解碼過程無歧義，且能達到最短的平均編碼長度。
2. 霍夫曼演算法（Huffman Algorithm）：一種基於貪婪策略（Greedy Strategy）建構最佳前綴碼二元樹的方法。每次從當前森林中選擇權重（頻率）最小的兩個節點進行合併，重複此步驟直到形成單一根節點的霍夫曼樹。
3. 編碼長度與樹深：字元在霍夫曼樹中的葉節點深度（Depth）即為該字元的編碼長度 $L(x)$。加權路徑長（Weighted Path Length, WPL）公式為：
   $WPL = \sum (f_x \times L(x))$
   其中 $f_x$ 為字元 $x$ 的頻率，$L(x)$ 為字元 $x$ 的編碼長度。