114 年 國立中山大學資訊管理學系碩士班乙組《資料結構》

核心觀念

Queue（佇列）遵守「先進先出」原則（FIFO, First In First Out）：

• enqueue：從隊尾加入元素。
• dequeue：從隊首取出元素。
• 元素的取出順序與加入順序相同。

解題方法

依序加入 $B、C、A、D、E$ 後，佇列由隊首至隊尾為：

$$B \rightarrow C \rightarrow A \rightarrow D \rightarrow E$$

出隊順序如下：

1. 第 1 次出隊：取出 $B$
2. 第 2 次出隊：取出 $C$

因此，第 2 次從佇列取出的元素是 $C$。

選項分析

核心觀念

本題比較各種排序法的「額外空間複雜度」（auxiliary space complexity），也就是除了原始輸入資料外，演算法執行時額外使用的陣列、暫存區與遞迴堆疊空間。

在一般陣列排序的標準分析中：

• In-place 排序通常只需 $\Theta(1)$ 額外空間。
• 使用額外暫存陣列合併資料時，通常需要 $\Theta(n)$ 額外空間。
• 遞迴呼叫本身會使用遞迴堆疊，常見為 $\Theta(\log n)$ 或最壞 $\Theta(n)$。

Merge Sort 在合併階段需要額外的暫存陣列，因此其額外空間通常為

$$\Theta(n)+\Theta(\log n)=\Theta(n)$$

解題方法

判斷每個選項是否需要建立與輸入規模 $n$ 同級的額外資料結構：

1. 若只在原陣列內交換元素，通常為 $\Theta(1)$。
2. 若有遞迴但沒有大型暫存陣列，通常為 $\Theta(\log n)$。
3. 若合併或複製時建立大小為 $n$ 的暫存陣列，則為 $\Theta(n)$。

因此，標準陣列實作下，Merge Sort 的額外空間最大。

選項分析

A. Quicksort

Quicksort 通常採用 in-place partition，在原陣列內重新排列元素，不需要大小為 $n$ 的暫存陣列。

其主要額外空間來自遞迴堆疊：

• 平均情況：約 $\Theta(\log n)$。
• 最壞情況：若每次 pivot 都造成極度不平衡的切割，遞迴深度可能為 $\Theta(n)$。

不過在一般考題的標準比較中，Quicksort 通常以平均遞迴堆疊空間 $\Theta(\log n)$ 評估；即使採用最佳化遞迴，也能控制堆疊空間。因此不是本題預期答案。

B. Selection Sort

Selection Sort 每一回合尋找剩餘元素中的最小值，再與目前位置交換，整個過程直接在原陣列內進行。

額外空間為

$$\Theta(1)$$

核心觀念

二元搜尋樹（BST）的中序走訪順序是：先走訪左子樹，再走訪根節點，最後走訪右子樹。依照 BST 的大小關係，這樣走訪會依序得到由小到大的節點值。

解題方法

依圖中的樹，從左子樹開始做中序走訪：

• 根節點 $50$ 的左子樹以 $30$ 為根。走訪 $30$ 的左子樹時，先走訪 $20$ 的左子節點 $3$，再走訪 $20$，接著走訪 $20$ 的右子節點 $25$，最後回到 $30$。
• 接著走訪 $30$ 的右子樹：$39$ 的左子節點是 $31$，因此順序為 $31、39$。
• 左子樹完成後走訪根節點 $50$。
• 最後走訪右子樹：先走訪 $60$ 的左子節點 $51$，再走訪 $60$，最後走訪右子節點 $65$。

完整順序為：

$$3,\ 20,\ 25,\ 30,\ 31,\ 39,\ 50,\ 51,\ 60,\ 65$$

選項分析

核心觀念

本題考查巢狀迴圈的時間複雜度，以及：

• 變數每次乘以 $2$，迴圈次數為對數級：$\Theta(\log N)$。
• 變數每次減少 $1$，迴圈次數為線性級：$\Theta(N)$。
• 巢狀迴圈的總執行次數，通常為外層次數乘以內層次數。

解題方法

關鍵程式碼如下：

for (int i = 1; i <= N; i = i * 2) {
    for (int j = N; j > 0; j--) {
        aggregate += i + j;
    }
}

外層迴圈中，$i$ 的取值依序為：

$$1,2,4,8,\ldots,2^k$$

當 $2^k \leq N$ 時仍會執行，因此外層迴圈次數為：

$$\left\lfloor \log_2 N \right\rfloor+1=\Theta(\log N)$$

內層迴圈中，$j$ 從 $N$ 遞減至 $1$，共執行 $N$ 次，因此：

$$\text{內層迴圈次數}=\Theta(N)$$

每次執行 aggregate += i + j 都是常數時間 $O(1)$。由於內外層迴圈為巢狀關係，總時間為：

$$T(N)=\Theta(\log N)\times\Theta(N) =\Theta(N\log N)$$

因此其時間複雜度可寫為：

$$O(N\log N)$$

核心觀念

強連通分量（strongly connected component, SCC）是有向圖中的一組頂點，其中任意兩個頂點都能彼此到達。判斷時要確認兩個方向都存在路徑；只有單向可達不算在同一個強連通分量。

解題方法

由圖中的 adjacency list 可讀出相關有向邊：

• $A\to C$、$A\to H$
• $B\to A$
• $C\to B$、$C\to D$
• $D\to C$、$D\to A$
• $E\to F$、$F\to E$
• $G\to D$、$G\to I$
• $H\to I$

頂點 $A,B,C,D$ 彼此可達。例如：

$$A\to C\to B\to A$$

而 $C\to D$，且 $D\to C$、$D\to A$，所以 $D$ 也能到達這個環中的其他頂點。故最大的強連通分量是 $\{A,B,C,D\}$，共有 4 個頂點。

紅黑樹插入步驟概覽

插入序列	主要調整	目前根節點
5	5 為根，染黑	5
7	7 為 5 的右子，保持紅	5
20	7、20 為連紅；利用「重新著色」把 5、7 變黑、紅 → 再把 5 重新染黑	5
31	31 為 20 的右子，形成「直線」紅紅 → 左旋 7，交換顏色，根仍 5	5
6	6 為 7 的左子，引發「叔叔為紅」→ 重新著色，20 變紅	5

核心觀念

二元搜尋樹（Binary Search Tree, BST）具有以下性質：

• 每個節點的左子樹所有鍵值都小於該節點。
• 每個節點的右子樹所有鍵值都大於該節點。
• 前序走訪（pre-order）：根節點 $\rightarrow$ 左子樹 $\rightarrow$ 右子樹。
• 中序走訪（in-order）：左子樹 $\rightarrow$ 根節點 $\rightarrow$ 右子樹。
• 後序走訪（post-order）：左子樹 $\rightarrow$ 右子樹 $\rightarrow$ 根節點。

BST 的中序走訪必定呈現遞增排序，因此可利用前序與中序走訪還原樹的結構。

解題方法

前序走訪的第一個元素必為整棵樹的根節點，因此根節點為 $10$。

中序走訪中，$10$ 左側為左子樹，右側為右子樹：

• 左子樹：$1,2,3,5,6,7,8$
• 右子樹：$12,15,16,20$

因此前序走訪可分成：

• 左子樹：$5,3,2,1,7,6,8$
• 右子樹：$20,15,12,16$

繼續還原左子樹：

• 根為 $5$
• $5$ 的左子樹由 $1,2,3$ 組成，根為 $3$
• $3$ 的左子樹由 $1,2$ 組成，根為 $2$，而 $2$ 的左子節點為 $1$
• $5$ 的右子樹由 $6,7,8$ 組成，根為 $7$，左右子節點分別為 $6$、$8$

右子樹則為：

先根據運算子優先權與結合性設定堆疊流程：

1. 讀入 5 → 輸出 5
2. 讀入 + → 推入堆疊 +
3. 讀入 ( → 推入堆疊 (
4. 讀入 7 → 輸出 7
5. 讀入 - → 推入堆疊 -（在 ( 之上）
6. 讀入 2 → 輸出 2
7. 讀入 ) → 依序彈出堆疊至 (，輸出 -，彈除 (
8. 讀入 * → * 優先權高於堆疊頂 +，直接推入 *
9. 讀入 2 → 輸出 2

核心觀念

最小生成樹（MST）是在連通且無向的加權圖中，選出能連接所有頂點、且不形成迴圈的邊，使總權重最小。若圖有 $n$ 個頂點，生成樹必須恰有 $n-1$ 條邊。

本題有 14 個頂點，因此最小生成樹須選 13 條邊。可用 Kruskal 演算法：依權重由小到大選邊；若加入某邊會形成迴圈，就略過。

解題方法

依圖中邊的權重排序，逐步選取不形成迴圈的邊：

權重	選取的邊	小計
1	$BF,\ NE,\ CD$	3
2	$MG,\ GB,\ GH,\ AI$	8
3	$IH,\ HK$	6
4	$FE,\ FL,\ IJ$	12
6	$ED$	6

此題考驗對廣度優先搜尋 (Breadth-First Search, BFS) 演算法的理解，以及如何追蹤 BFS 遍歷過程中節點的訪問順序。

廣度優先搜尋 (BFS)：
BFS 是一種圖遍歷演算法，它從起始節點開始，然後一層一層地訪問節點。它使用一個佇列 (queue) 來儲存待訪問的節點。

1. 將起始節點加入佇列，並標記為已訪問。
2. 當佇列不為空時：
   • 從佇列頭部取出一個節點。
   • 處理該節點（在此題中，我們只需要知道訪問順序）。
   • 將該節點所有未訪問過的鄰居節點加入佇列，並標記為已訪問。

圖示分析：
題目給出了一個無向圖，並要求從節點 A 開始進行 BFS，找出選項中哪個節點是最後被訪問到的。

BFS 模擬：
起始節點：A

1. 初始化：

   • 佇列 (Queue): [A]
   • 已訪問 (Visited): {A}
   • 訪問順序 (Traversal Order): [A]

2. 處理 A：

   • 從佇列取出 A。
   • A 的鄰居是 B, F, H (根據圖示)。
   • 將 B, F, H 加入佇列，並標記為已訪問。
   • 佇列: [B, F, H]
   • 已訪問: {A, B, F, H}
   • 訪問順序: [A, B, F, H]

3. 處理 B：

   • 從佇列取出 B。
   • B 的鄰居是 A, C, F。A 和 F 已訪問。
   • 將 C 加入佇列，並標記為已訪問。
   • 佇列: [F, H, C]
   • 已訪問: {A, B, F, H, C}
   • 訪問順序: [A, B, F, H, C]

4. 處理 F：

   • 從佇列取出 F。
   • F 的鄰居是 B, E, G。B 已訪問。
   • 將 E, G 加入佇列，並標記為已訪問。
   • 佇列: [H, C, E, G]
   • 已訪問: {A, B, F, H, C, E, G}
   • 訪問順序: [A, B, F, H, C, E, G]

5. 處理 H：

   • 從佇列取出 H。
   • H 的鄰居是 A, G, I, N。A, G 已訪問。
   • 將 I, N 加入佇列，並標記為已訪問。
   • 佇列: [C, E, G, I, N]
   • 已訪問: {A, B, F, H, C, E, G, I, N}
   • 訪問順序: [A, B, F, H, C, E, G, I, N]

6. 處理 C：

   • 從佇列取出 C。
   • C 的鄰居是 B, D, L。B 已訪問。
   • 將 D, L 加入佇列，並標記為已訪問。
   • 佇列: [E, G, I, N, D, L]
   • 已訪問: {A, B, F, H, C, E, G, I, N, D, L}
   • 訪問順序: [A, B, F, H, C, E, G, I, N, D, L]

7. 處理 E：

   • 從佇列取出 E。
   • E 的鄰居是 F, M。F 已訪問。
   • 將 M 加入佇列，並標記為已訪問。

插入順序依次構成的二元搜尋樹（BST）如下（只列出關鍵節點與方向）：

• 10 為根
• 22 為 10 的右子
• 18 為 22 的左子
• 1 為 10 的左子
• 5 為 1 的右子、3 為 5 的左子、7 為 5 的右子
• 20 為 18 的右子、12 為 20 的左子、11 為 12 的左子、15 為 12 的右子

先以 0 起始索引視為完全二元樹，建構 max‑heap 時從最後一個非葉節點 $i=\lfloor n/2\rfloor-1=3$ 逆向 sift‑down：

1. $i=3$: 子節點 $7\;(1)$、$8\;(15)$ → 交換 $6\leftrightarrow15$
   → $[8,11,2,15,10,7,3,1,6]$

2. $i=2$: 子節點 $5\;(7)$、$6\;(3)$ → 交換 $2\leftrightarrow7$
   → $[8,11,7,15,10,2,3,1,6]$

3. $i=1$: 子節點 $3\;(15)$、$4\;(10)$ → 交換 $11\leftrightarrow15$
   → $[8,15,7,11,10,2,3,1,6]$

核心觀念

連通分量是圖中「彼此有路徑相連，且不能再加入其他頂點」的最大頂點集合。每個孤立頂點也各自構成一個連通分量。

依圖中的鄰接矩陣，頂點為 $A$ 至 $J$，矩陣對稱，代表這是無向圖。

解題方法

從矩陣中找出值為 $1$ 的位置，可讀出邊：

• $A$ 與 $E、J$ 相連，因此形成 $\{A,E,J\}$。
• $B$ 與 $G、I$ 相連，且 $G$ 與 $I$ 相連，因此形成 $\{B,G,I\}$。
• $F$ 與 $H$ 相連，因此形成 $\{F,H\}$。
• $C$ 沒有連到其他頂點，是孤立頂點。
• $D$ 沒有連到其他頂點，也是孤立頂點。

所以共有五個連通分量：

核心觀念

本題考查高度平衡二元搜尋樹（height-balanced binary search tree）的搜尋時間與樹高性質。

對任一節點，若左右子樹高度差不超過 $1$，則稱其符合高度平衡條件。此類樹的關鍵性質為：

$$h=\Theta(\log n)$$

其中 $h$ 為樹高，$n$ 為節點數。

二元搜尋樹搜尋一個鍵值時，從根節點開始，每次依比較結果往左子樹或右子樹前進，因此搜尋時間與搜尋路徑長度有關，最多不超過樹高。

---

解題方法

逐項判斷四個敘述：

1. 先利用高度平衡樹的定理判斷樹高是否為對數級。
2. 再由搜尋路徑長度與樹高的關係，判斷最壞與平均情況。
3. 最佳情況須特別注意：若搜尋值位於根節點，只需比較一次，並非一定要走完整棵樹高。

高度平衡樹的最少節點數可用遞迴表示：

$$N(h)=N(h-1)+N(h-2)+1$$

其成長速度與 Fibonacci 數列相近，因此：

$$N(h)=\Theta(\varphi^h)$$

取對數可得：

$$h=\Theta(\log n)$$

---

選項敘述判斷

I. Worst-case search time is logarithmic in the number of nodes.

正確。

最壞情況下，搜尋路徑可能從根走到最深葉節點，所需時間為：

$$T_{\text{worst}}=\Theta(h)$$

由於高度平衡樹的高度為 $\Theta(\log n)$，因此：

$$T_{\text{worst}}=\Theta(\log n)$$

---

II. Average-case search time is logarithmic in the number of nodes.

正確。

在一般假設下，各節點被搜尋的機率相近，平均搜尋時間與平均深度相關。高度平衡樹的整體高度為 $\Theta(\log n)$，其平均深度也維持在對數級，因此：

核心觀念

本題考「反覆縮小輸入規模的遞迴式」與漸近界。對任意 $n\ge 2$，令 $N=\lfloor n/2\rfloor$，題目給的兩種情況都可寫成：

$$f(n)=f\!\left(\left\lfloor\frac n2\right\rfloor\right) +\log\left\lfloor\frac n2\right\rfloor$$

每次遞迴會將輸入約減半，因此遞迴層數是 $\Theta(\log n)$。但每層增加的代價也會隨輸入大小改變，不能只看層數；必須把各層代價加總。

解題方法

從 $n$ 開始反覆取一半並向下取整，遞迴每層所加的項依序為：

$$\log\left\lfloor\frac n2\right\rfloor,\quad \log\left\lfloor\frac n4\right\rfloor,\quad \log\left\lfloor\frac n8\right\rfloor,\quad \ldots$$

當輸入縮小至 $1$ 時，$f(1)=0$，因此：

$$f(n)=\sum_{j=1}^{\lfloor\log_2 n\rfloor} \log\left\lfloor\frac{n}{2^j}\right\rfloor$$

上界方面，總共有 $O(\log n)$ 項，每一項至多為 $\log n$，所以：

$$f(n)=O((\log n)^2)$$

核心觀念

本題考的是前代法（forward substitution）：求解 $Lx=b$ 時，因為 $L$ 是下三角矩陣，可以從第一列開始，逐列利用已求出的變數，更新目前列的右側常數。

「單位下三角矩陣」表示 $L[i,i]=1$，且對角線上方的元素為 $0$。因此第 $i$ 列方程式為：

$$x[i]+\sum_{j=1}^{i-1}L[i,j]x[j]=b[i]$$

移項後可寫成：

$$x[i]=b[i]-\sum_{j=1}^{i-1}L[i,j]x[j]$$

解題方法

依原卷圖，第 16 題給定先將每個 $x[i]$ 設為 $b[i]$，再依序令 $i=2,\ldots,n$、$j=1,\ldots,i-1$。因此，每次內層迴圈都要從目前的 $x[i]$ 扣除 $L[i,j]x[j]$；已完成的 $x[j]$ 是前面列求得的值。

逐項更新的式子是：

$$x[i]\leftarrow x[i]-L[i,j]x[j]$$

這正是選項 (A)。

選項分析

核心觀念

堆疊（Stack）遵守後進先出（LIFO）：最後放入的元素會最先取出。令 $S$ 表示原堆疊，$e$ 表示元素，則：

• $Push(S,e)$：將 $e$ 放到堆疊頂端。
• $Pop(S)$：移除堆疊頂端元素。
• $Top(S)$：取得堆疊頂端元素，但不移除。
• $IsEmpty(S)$：判斷堆疊是否為空。

只要執行 $Push(S,e)$，結果堆疊就至少含有 $e$，因此不會是空堆疊。

解題方法

逐一依照堆疊操作定義代入。特別注意，$Push$ 後的新元素位於頂端；連續 $Push$ 會使後加入的元素在前一個元素上方。接著按照 LIFO 順序判斷 $Pop$ 與 $Top$ 的結果。

選項分析

(A) $IsEmpty(Push(Stack, Elem))=true$：錯誤。
執行 $Push$ 後，堆疊至少含有 $Elem$，所以它不是空堆疊：

$$IsEmpty(Push(Stack, Elem))=false$$

核心觀念

二分搜尋每次檢查目前區間的中間位置 $M$，再把搜尋範圍縮小到左半部或右半部。若目前區間長度為 $n$，下一層的區間長度至多為 $\lfloor n/2\rfloor$，因此搜尋層數為 $O(\log N)$。

題目中的邊界條件也很重要：當 $M=L$ 或 $M=R$ 時，搜尋區間已無法再依條件往該側縮小；若此時仍未找到 $x$，便以失敗結束。

解題方法

每往下一層，區間大小至多減半。經過 $k$ 層後，區間大小至多為 $N/2^k$。當區間縮小至空或單一位置時，搜尋便會結束，所以層數至多與 $\log_2 N$ 成正比。

每一層只需進行固定次數的比較，例如先比較 $x=a[M]$，再判斷 $x<a[M]$ 或 $x>a[M]$。因此，成功與失敗搜尋的比較次數都不超過 $O(\log N)$。

判斷 III 則需比較不同缺值的搜尋路徑。搜尋樹各葉節點深度不一定相同，兩個缺值可能在不同層數才到達失敗條件。

選項分析

I 正確。 若 $x$ 存在，每次搜尋最多將區間縮小至原來的一半。搜尋層數為 $O(\log N)$，每層比較次數為常數，因此成功搜尋最多需要 $O(\log N)$ 次比較。

核心觀念

這題考查圖形走訪中的「已訪問標記」。每個節點有兩個指標，形成一張有向圖；圖中可能有環，也可能有多條路徑通往同一節點。計算可到達的節點數時，每個節點只能計算一次。

正確做法是在第一次到達節點時，先檢查標記，再立刻設為已訪問，最後才遞迴走訪兩個指標。這樣遇到環或重複路徑時，遞迴會在已訪問的節點停止。

解題方法

若節點 $a$ 已標記，表示它先前已被計數，因此直接回傳 $0$。若尚未標記，就先將 $a$ 標記，再走訪 $a\to p$ 與 $a\to q$，並把本節點算入總數：

int nodecount(struct test *a)
{
    if (a->mark) return 0;
    a->mark = 1;
    return nodecount(a->p) + nodecount(a->q) + 1;
}

核心觀念

二元樹的三種走訪順序為：

• 前序：根、左子樹、右子樹。
• 中序：左子樹、根、右子樹。
• 後序：左子樹、右子樹、根。

本題要分別對 Tree1、Tree2 套用選項指定的走訪方式，再比較節點名稱的順序是否完全相同。

解題方法

圖中 Tree1 的根為 A；A 的左右子節點為 B、C。B 的右子節點為 D；D 的左右子節點為 E、F；E 的左右子節點為 G、H，且 H 的右子節點為 I、I 的右子節點為 J。Tree2 的根為 G，右子節點為 F；F 的左右子節點為 E、C；E 的左子節點為 I，I 的左右子節點為 J、H；C 的左右子節點為 D、A，且 D 的右子節點為 B。

先算 Tree1 的後序。依序走訪左子樹、右子樹、根：

$$\text{Tree1 後序： } G,\ J,\ I,\ H,\ E,\ F,\ D,\ B,\ C,\ A$$

再算 Tree2 的中序。依序走訪左子樹、根、右子樹：

$$\text{Tree2 中序： } G,\ J,\ I,\ H,\ E,\ F,\ D,\ B,\ C,\ A$$

核心觀念

題目考的是排序演算法的執行時間會不會隨輸入資料的初始排列改變。比較時要看演算法執行了多少次比較與資料移動，而不能只看排序後的結果。

選擇排序每一趟都掃描尚未排序的部分，找出其中最小元素；無論資料原本如何排列，掃描範圍都相同。因此，它的比較次數固定為：

$$(n-1)+(n-2)+\cdots+1=\frac{n(n-1)}{2}$$

執行時間為 $\Theta(n^2)$，且比較次數不受輸入初始順序影響。

解題方法

判斷各演算法的執行過程是否會因資料排列而改變：

• 若比較或掃描次數會隨輸入順序改變，執行時間便較依賴初始排列。
• 若演算法固定執行相同的比較流程，時間便較不受初始排列影響。

選擇排序每一趟都檢查完整的未排序區段，總比較次數固定。因此，在選項中，它的執行時間最不依賴初始排列。

選項分析

(A) Insertion sort：錯誤。
插入排序的執行時間會受到初始順序影響。輸入已排序時，每個元素只需少量比較，最佳情況為 $\Theta(n)$；輸入反向排序時，元素需大量移動，最差情況為 $\Theta(n^2)$。

核心觀念

本題考的是圖論問題的計算複雜度：判斷問題能否在輸入大小的多項式時間內求解。無向圖 $G$ 有頂點與邊；「簡單環」是不重複經過頂點（起點與終點相同除外）的環；「生成樹」是包含所有頂點的樹；「團」則是彼此兩兩相鄰的頂點集合。

解題方法

依原卷第 22 題，題目給的是一般無向圖 $G$，詢問哪一種問題已知可在多項式時間內求解；沒有指定頂點或邊的數量，也沒有提供一張特定圖要計算。逐項辨認這些問題的複雜度：最短環可用廣度優先搜尋求解；最長簡單環與最大團是 NP-hard 問題；列出所有生成樹則可能需要輸出指數多棵樹。

選項分析

• (A) Finding a shortest cycle in $G$：正確。 對每條邊 $e=(u,v)$，暫時移除 $e$，再用廣度優先搜尋找 $u$ 到 $v$ 的最短路徑。若找到長度為 $d$ 的路徑，加回 $e$ 就得到長度為 $d+1$ 的環。取所有邊所形成環中的最小值，即為最短環。每條邊執行一次廣度優先搜尋，時間複雜度為 $O(|E|(|V|+|E|))$，是多項式時間。若圖中沒有環，則沒有最短環可回報。

核心觀念

本題比較三種資料結構中，找出並刪除「第 7 大元素」的最壞情況時間。判斷時要看結構提供的排序資訊，以及刪除指定元素後需要移動或調整多少資料。

第 7 大是固定名次。固定名次對時間複雜度很重要：即使資料結構無法直接依名次查找，若只需從最大值往前走固定 6 個元素，這段操作仍是常數時間。

解題方法

原卷第 23 題列出三種結構：min-heap、遞增排序陣列、平衡二元搜尋樹；題目問最壞情況下，找出並移除第 7 大元素是否可在 $O(\log n)$ 內完成。

逐一看「找到」與「移除」的成本：

• **I. Min-heap：**只保證父節點不大於子節點，沒有左右子樹或兄弟節點之間的完整大小次序。最大值所在位置不固定，找到第 7 大可能須檢查線性數量的節點，因此最壞情況是 $O(n)$。無法保證 $O(\log n)$。
• **II. 遞增排序陣列：**第 7 大位於從陣列尾端往前數第 7 個位置，可直接定位。刪除時只須將它後方的 6 個較大元素往前移，因此查找與移除合計為 $O(1)$，符合 $O(\log n)$ 上界。

核心觀念

雙向鏈結串列的每個節點有兩個連結：

• Fwd 指向後方相鄰節點。
• Bwd 指向前方相鄰節點。

刪除中間節點時，必須讓它的前一個節點與後一個節點直接相連。設：

• $P = X\uparrow.Bwd$，即 $X$ 的前一個節點。
• $N = X\uparrow.Fwd$，即 $X$ 的後一個節點。

刪除 $X$ 後，應滿足：

$$P\uparrow.Fwd = N,\qquad N\uparrow.Bwd = P$$

解題方法

將題目中的兩個指標更新式分別對照上述條件：

1. 從 $P$ 向前走，應直接到 $N$：
   X↑.Bwd↑.Fwd := X↑.Fwd
2. 從 $N$ 向後走，應直接回到 $P$：
   X↑.Fwd↑.Bwd := X↑.Bwd

因此，正確更新方式是：

X↑.Bwd↑.Fwd := X↑.Fwd
X↑.Fwd↑.Bwd := X↑.Bwd

這兩個更新都需要執行，才能維持串列的前向與後向連結一致。

選項分析

• (A) 正確。 第一行將 $X$ 的前一個節點之 Fwd 改指向 $X$ 的後一個節點；第二行將 $X$ 的後一個節點之 Bwd 改指向 $X$ 的前一個節點。

核心觀念

FindColor(n) 會從節點 $n$ 開始往父節點尋找：遇到第一個具有 Color 屬性的節點，就回傳該節點的顏色。因此，沒有標示顏色的節點會繼承其最近的有色祖先之顏色。

解題方法

圖中根節點標示為藍色；左子樹的上方節點標示為紅色，其右子節點標示為藍色，左側下方葉節點標示為綠色。右子樹中，根的右子節點未標色，其右子節點標示為紅色。

逐一判斷各節點回傳的顏色：

節點位置	FindColor 回傳
左子樹的紅色節點	紅
紅色節點的左子節點（未標色）	紅
紅色節點的右子節點（藍色）	藍
左側未標色節點的左葉（綠色）	綠
左側未標色節點的右葉（未標色）	紅
根的右子節點（未標色）	藍
根右子節點的左葉（藍色）	藍

核心觀念

獨立集是任兩個節點都不相鄰的節點集合。極大獨立集除了本身是獨立集外，還必須無法再加入任何一個圖中的其他節點而維持獨立。

解題方法

依圖可讀出節點為 $a,b,c,d,e,f,g$，邊為 $ab,bc,ae,ce,ef,ad,df,cg,fg$。先檢查各選項中的節點是否彼此不相鄰，再檢查是否有未選節點能加入。

選項分析

• (A) $\{a,e\}$：錯。 $a$ 與 $e$ 由邊 $ae$ 相連，因此不是獨立集。
• (B) $\{a,g\}$：對。 $a$ 與 $g$ 不相鄰，所以是獨立集。未選的 $b,d,e$ 都與 $a$ 相鄰，$c,f$ 都與 $g$ 相鄰；

核心觀念

這題考二元樹的遞迴定義與數學歸納法。每個內部節點恰有兩個子節點，因此若 $T$ 不是葉節點：

$$n(T)=n(T_L)+n(T_R)+1$$

而樹高為：

$$h(T)=\max(h(T_L),h(T_R))+1$$

解題關鍵是利用：

$$h(T_L)+h(T_R)-\min(h(T_L),h(T_R)) =\max(h(T_L),h(T_R))$$

解題方法

以樹的結構做歸納，證明：

$$F(T)=n(T)-h(T)$$

基底情形： 若 $T$ 是葉節點，題目定義 $F(T)=0$、$n(T)=0$、$h(T)=0$，所以：

$$F(T)=0=n(T)-h(T)$$

歸納步驟： 假設左右子樹都符合 $F(T)=n(T)-h(T)$。對非葉節點 $T$：

$$\begin{aligned} F(T) &=F(T_L)+F(T_R)+\min(h(T_L),h(T_R))\\ &=n(T_L)-h(T_L)+n(T_R)-h(T_R)+\min(h(T_L),h(T_R))\\ &=n(T_L)+n(T_R)-\max(h(T_L),h(T_R))\\ &=n(T)-h(T) \end{aligned}$$

核心觀念

連通分量是圖中彼此可達的最大節點集合。對有 $n$ 個節點的圖，若加入一條連接兩個不同連通分量的邊，連通分量數會減少 $1$；若邊兩端已在同一分量，連通分量數不變。

本題有 $10$ 個節點、$6$ 條邊，且沒有自我迴圈、任兩節點間至多一條邊。題目要找連通分量數的最大值 $M$ 與最小值 $m$。

解題方法

原卷第 28 題給定無向圖有 $10$ 個節點、$6$ 條邊，並限制沒有自我迴圈、每對節點間至多一條邊；選項 C 為 $M=7,\ m=4$。

先求最小連通分量數。每條邊最多只能讓連通分量數減少 $1$，所以從 $10$ 個分量出發，使用 $6$ 條邊後至少還有

$$m \ge 10-6=4$$

這個下界可以達成：讓 $7$ 個節點形成一棵樹，使用 $6$ 條邊，另外 $3$ 個節點各自孤立，總共正好有 $4$ 個連通分量。因此 $m=4$。

再求最大連通分量數。把邊集中在最少節點上，能讓其餘節點保留為孤立節點。任意 $3$ 個節點之間最多只有 $\binom{3}{2}=3$ 條邊；要放下 $6$ 條不同的邊，至少需要 $4$ 個節點。用這 $4$ 個節點組成完全圖 $K_4$，恰有 $6$ 條邊，其他 $6$ 個節點孤立，連通分量數為

$$M=1+6=7$$