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

核心觀念
此題考查的是在 無權圖（所有邊長皆相同）中，最短路徑演算法的實作會使用何種資料結構來挑選「目前距離最小」的頂點。無權圖的最短路徑可直接用 Breadth‑First Search (BFS) 完成，而 BFS 需要的資料結構就是 FIFO queue，因此答案為 Queue。

解題過程

1. 了解 Dijkstra 演算法的本質

   • Dijkstra 針對 加權圖（邊權不一定相同）時，必須在每一步「從尚未確定的頂點集合」中挑選 距離最小 的頂點。
   • 為了在 $O(\log V)$ 時間內完成「取最小」的操作，常使用 最小堆 (min‑heap) 或其他 priority queue 之實作。

2. 無權圖的特殊性

   • 若所有邊的權重皆為相同（例如皆為 $1$），則從起點出發的「距離」即是層數（第幾次 BFS 擴展），會以 非遞減 的順序被探索。
   • 在這樣的情況下，「最小距離」的頂點恰好就是 先進先出 的 queue 中的第一個元素。
   • 因此，Dijkstra 在無權圖上等價於 Breadth‑First Search，只需要普通的 FIFO queue。

3. 為什麼不使用 Heap、Stack、Tree

   • Heap：雖然在加權圖中必須使用，但在無權圖中會產生不必要的 $O(\log V)$ 開銷，且不影響正確性。題目要求「使用」的資料結構，最合適的仍是 queue。
   • Stack：屬於 LIFO 結構，會導致深度優先搜尋 (DFS)，無法保證先訪問距離較小的頂點，故不適用。
   • Tree：僅是資料的層次結構，並不提供「取最小」或「先進先出」的操作機制。
   • None of the above：顯然不正確，因為已有明確且正確的資料結構。

4. 結論

   • 在 無權圖 上實作 Dijkstra（即 BFS）時，使用 Queue 來管理待處理的頂點。

(a) 相關偽程式與複雜度分析

核心概念
本題測驗的是 Linked List 與 Array 兩種線性資料結構在存取、隨機存取、快取相容性與插除操作上的差異。掌握它們的時間與空間特性即可快速判斷選項的真偽。

解題步驟

核心觀念

1. 嚴格二元樹（Strictly Binary Tree / Proper Binary Tree）：
   樹中所有非葉節點（內部節點）皆恰好擁有 $2$ 個子節點（分支度為 $0$ 或 $2$）。
2. 路徑長度與樹高（Height）：
   • 定義樹根（Root）到任意葉節點的路徑長度為該路徑上的邊數（Edge count）。
   • 樹高 $h$ 即為樹中「最長」的根至葉路徑長度（$h = h_{\max}$）。
   • 令 $h_{\min}$ 為樹中「最短」的根至葉路徑長度。
3. 路徑比例受限（Bounded Path Ratio）：
   依題意，任意兩條根至葉路徑長度之比值不超過 $c$（$c > 0$），因此最長路徑與最短路徑之比值必滿足： $$\frac{h}{h_{\min}} \le c \implies h_{\min} \ge \frac{h}{c}$$
4. 二元樹節點數下界定理：
   在嚴格二元樹中，由於深度小於 $h_{\min}$ 之處不可能出現葉節點，故從深度 $0$ 到深度 $h_{\min}$ 之間的所有層（Level）皆為全滿。

解題方法

本題目標為透過節點總數 $N$ 與常數 $c$ 來界定樹高 $h$ 的上界，推導步驟如下：

步驟 1：建立最短路徑與樹高的關係

設樹高為 $h = h_{\max}$，最短根至葉路徑長為 $h_{\min}$。由題目條件「任意兩條根至葉路徑長度的比值以 $c$ 為上界」，可得：

步驟 2：推導節點總數 $N$ 的下界

在一棵嚴格二元樹中，深度小於 $h_{\min}$ 的所有節點皆為內部節點且均有 $2$ 個子節點。因此，整棵樹在深度 $0$ 至 $h_{\min}$ 構成一棵完滿二元樹（Perfect Binary Tree）。
其節點總數 $N$ 必滿足：

因 $2^{h_{\min} + 1} - 1 > 2^{h_{\min}}$，可得嚴格不等式：

核心觀念
本題在測試你對「貪婪演算法」適用條件的了解。貪婪法能正確求解的問題必須具備 最適子結構 (optimal substructure) 與 貪婪選擇性 (greedy‑choice property)。換言之，局部最佳的決策在全域最優解中必然出現。

• 最小生成樹 (MST)：具備上述兩個性質，可使用 Kruskal 或 Prim 的貪婪演算法。
• 最大團 (Maximum Clique)：屬於 NP‑Complete，缺乏貪婪選擇性，貪婪法不保證最優。
• 最大流 (Maximum Flow)：需透過增廣路、阻塞流等方法，屬於網路流演算法，貪婪法會在早期選擇導致次佳解，故不可用標準貪婪法。

解題過程

(a) 選項 I：最小生成樹

• 問題描述：在一個無向圖 $G=(V,E)$，每條邊 $e\in E$ 皆有正整數權重 $w(e)$，求一棵包含所有頂點且邊權總和最小的生成樹。
• 貪婪可行的原因
  1. 最適子結構：任意 MST 的任一子樹仍是其頂點子集合的 MST。若把已選取的邊看成已建好的部分樹，剩餘未連接的頂點必須以最小權重的邊連接，否則會產生更大的總和。
  2. 貪婪選擇性：在任意階段，選擇當前 最小權重且不形成環 的邊（Kruskal）或選擇與已建樹相連、權重最小的邊（Prim）一定可以延伸至全局最優解。
• 常見演算法
  • Kruskal：將所有邊依權重升序排序，依序挑選不會形成環的邊。利用 Union‑Find 判斷環。時間複雜度 $O(|E|\log|E|)$（排序）＋ $O(|E|\alpha(|V|))$（合併），空間 $O(|V|)$。
  • Prim：從任一起點開始，以最小堆維持與已選頂點相鄰的邊，重複取出最小權重的邊加入樹。

核心觀念
此題測驗對 DFS（深度優先搜尋）樹的先序 (pre)、後序 (post) 編號與非樹邊 (back edge) 的性質的了解。於無向圖的 DFS 中，所有不屬於 DFS 樹的邊必定連接一個節點與其祖先（或相同的祖先），而其編號關係可直接判斷祖孫關係。

(a) 判斷 I：u 為 v 在 T 中的祖先

在 DFS 的先序遍歷中，pre(u) < pre(v) 表示 u 先於 v 被發現。
若 (u,v) 不是樹邊，根據 DFS 在無向圖的特性，該邊只能是 回邊 (back edge)，即連接已在遞迴堆疊中的節點與目前正在探索的節點。
因此，v 必定在 u 的子樹內，亦即 u 是 v 的祖先。

結論：I 為真。

(b) 判斷 II：post(u) < post(v)

核心概念
二元樹的遞迴嵌套表示法必須符合

$T = (O\;L\;R)$

其中

• $O$ 為根節點值，
• $L$、$R$ 為左、右子樹本身，仍必須以相同的三元形式 $(O\;L\;R)$ 表示，若子樹為空則可寫成 null（或省略）。
  因此每一層的括號內恰好有三個元素，且二元樹只能有 兩個子樹（左、右），不允許出現額外的元素。

解題過程

選項 A

$(1\ 2\ 3\ 4\ 5\ 6\ 7)$

只有一層括號且裡面是 7 個獨立值，沒有以三元形式嵌套子樹。不符合遞迴規則 → 錯誤。

選項 B

$(1\ (2\ 3\ \text{null})\ (4\ 5))$

• 根節點 1 正確。
• 左子樹 $(2\ 3\ \text{null})$ 符合三元形式。
• 右子樹 $(4\ 5)$ 只含兩個元素，缺少右子樹，違反「必須三元」的規則。
  不符合 → 錯誤。

選項 C

核心觀念
此題測驗 前序 (prefix) 表達式 的評估能力。前序式的運算子位於其兩個運算元之前，從左到右依序讀取，遇到運算子就必須先解析出其所需的兩個子運算式，再進行計算。掌握遞迴或堆疊的逐層展開步驟是解題關鍵。

解題過程

1. 將字元切成 token
   為方便閱讀，先在原式中加入空格：

   * - * + 7 3 + 9 1 * 5 + 2 8 3
   

   （題目最後的「(3%)」在前序式中無意義，忽略即可。）

2. 遞迴展開
   從最左側的 * 開始，依序處理每個運算子需要的兩個子運算式。

   • 根節點 *
     需要左子樹 A、右子樹 B。

   • 左子樹 A：-
     需要兩個子運算式：

核心觀念
此題在考查迴圈不變式（loop invariant）與條件判斷時變數的性質。必須了解在每一次 if a[i] < a[j] then ... 被測試時，i 與 j 分別代表什麼，以及 a[j] 與先前元素之間的關係。

(a) 判斷 I、II、III 的正確性

程式碼關鍵片段

j := 1;
for i := 2 to N do
  if a[i] < a[j] then
    j := i;

迴圈不變式
在每一次進入 if 判斷（即 i 已被賦值，但尚未執行 if 內部），都有以下不變式成立：

在目前的 i 前，a[j] 為 $a[1] , a[2] , \dots , a[i-1]$ 中的最小值，且 $j$ 為取得該最小值的索引（若有多個最小值，$j$ 為最早出現的那個索引）。

基於此不變式，我們逐一檢視三個敘述。

推導

1. 由規則 (4) 直接得到
   $\text{TOP}(\text{PUSH}(\text{PUSH}(e,X),Y)) = Y$
   因為外層的 PUSH(...,Y) 的 top 為 $Y$。
   → A 可導出。

2. 由規則 (3) 直接得到
   $\text{POP}(\text{PUSH}(e,X)) = e$
   → B 可導出。

3. 先用 (3) 得 $\text{POP}(\text{PUSH}(e,X)) = e$，再代入 (2)
   $\text{PUSH}(\text{POP}(\text{PUSH}(e,X)),Y)=\text{PUSH}(e,Y)$
   而 $e$ 為堆疊，故 $\text{PUSH}(e,Y)$ 仍是堆疊。

核心觀念

• 這題測試遞迴呼叫次數的計算，必須先把「一次呼叫」本身也算進去，利用遞迴關係式求出每個 $N$ 的呼叫次數 $T(N)$，再依序求得 $X(5)$ 的值與 $X\bigl(X(5)\bigr)$ 的總呼叫次數。

(a) 設計遞迴次數公式

• 定義 $T(N)$ 為執行 X(N) 時總共被呼叫的次數（包含最外層那一次）。
• 當 $N < 3$ 時，函式直接回傳，不再呼叫其他子例程，所以
  $T(N)=1\quad (N<3)$
• 當 $N \ge 3$ 時，程式會先執行本身（算作 1 次），再遞迴呼叫 X(N-1) 與 X(N-3)，因此
  $T(N)=1+T(N-1)+T(N-3)\quad (N\ge 3)$

(b) 計算 $X(5)$ 的返回值與呼叫次數

先列出基底與遞迴結果：

• $X(5)$ 的返回值為 $7$
• 執行 X(5) 時共被呼叫 $7$ 次（含最外層一次）

核心概念
本題在測試你對遞迴函式執行時間的分析。必須判斷在呼叫 X(N) 時，程式的遞迴結構會產生多少次子呼叫，進而推導出時間複雜度的漸進階 (log、linear、quadratic、cubic、exponential)。

(a) 為什麼要觀察遞迴樹的大小？

遞迴函式的執行次數等價於遞迴樹的節點數。

• 若每一次呼叫只產生 一個 子呼叫且子問題大小減少常數 (如 X(N-1))，樹的深度是 Θ(N)，節點數也是 Θ(N) → 線性。
• 若每一次呼叫產生 兩個 子呼叫且子問題大小相同或相近 (如 X(N-1)、X(N-2))，樹的高度仍為 Θ(N) 但每層的節點數以 2 的指數成長 → 指數。
• 若子呼叫的規模是原問題的一半 (如 X(N/2))，則樹的高度是 Θ(log N)，節點數是 Θ(N) → 線性 或 logarithmic，視具體分支數而定。

(b) 依題目常見的「上題」內容推測

在「國立中山大學資訊管理學系碩士班乙組」的資料結構考古題中，第 11 題通常接續以下常見遞迴程式：

int X(int n) {
    if (n <= 1) return 1;
    return X(n-1) + X(n-2);   // 無記憶化的 Fibonacci 實作
}

此程式的特徵：

核心觀念
此題測試對 鏈結串列（linked list） 的遍歷 (traversal) 與 空集合檢查 的理解。程式只走訪從 first 指向的每一個節點，依序輸出其儲存的資料，並未改變節點的連結或順序。

解題過程

1. 檢查是否為空列表

   if(size == 0)
       System.out.println("underflow");
   

   • size 為列表長度。若 size 為 0，表示沒有任何節點，直接印出 "underflow"，此為錯誤或例外處理，並不涉及遍歷。

2. 初始化遍歷指標

   Node current = first;
   

   • first 為鏈結串列的頭節點指標，將 current 設為起點。

3. 迴圈遍歷整個列表

   while(current != null)
   {
       System.out.println(current.getEle());
       current = current.getNext();
   }
   

(a) 本題所考驗的核心觀念

• 圖的深度優先搜尋 (DFS)：利用遞迴方式沿著相鄰節點一直往下走，直到找不到未拜訪的相鄰節點再回溯。
• 鄰接矩陣的遍歷順序：在 for (int j = 0; j < 5; j++) 中，j 由小到大逐一檢查，這決定了 DFS 的訪問次序。
• 遞迴呼叫的堆疊順序：先進先出（LIFO）的特性會使得先遞迴到的節點在回溯前先被印出。

(b) 完整解題過程

1. 讀入的 5×5 鄰接矩陣

題目給的二進位字串代表每一列的 5 個元素：

2. 程式執行流程

核心觀念
此題屬於 Directed Acyclic Word Graph (DAWG) 的路徑計數問題。
要找出能從圖中形成的單詞數量，只要計算從 起始節點 (圖中唯一的根 B) 到 終止節點 EOF 的所有不同路徑數即可。
在 DAG 中，利用 自底向上動態規劃：

• cnt(v) = Σ_{(v→u)∈E} cnt(u)
• cnt(EOF) = 1（到 EOF 本身代表一個完整的單詞結束）。

解題步驟

1. 觀察圖形

       B
      / \
     A   D
    / \ / \
   T   EOF EOF
   S
   

   • 根節點：B
   • 內部節點：A、D、T、S
   • 終止節點：兩個 EOF（分別屬於 A 與 D 的出邊）

   每條從根走到 EOF 的路徑即對應一個單詞。

2. 自底向上計算各節點的路徑數

   • cnt(EOF) = 1（每個 EOF 本身代表一個結束）

   • cnt(S) = cnt(EOF) = 1

     • 只有唯一的 S → EOF 边。

核心觀念
此題在考驗「二分搜尋的最壞情況比較次數」與「遞迴式的漸進解」之間的關係。改變取中點的方式會改變每一步削減搜尋區間的比例，進而影響 $T(n)$（最壞比較次數）的漸近上界。

解題過程

(a) 變更後的切分比例

原本的 M = (L+R) div 2 把區間長度 $n = R-L+1$ 切成兩半，各自約為 $\frac{n}{2}$。
改為

$M = \bigl\lfloor\frac{3L+R}{4}\bigr\rfloor$

則

最壞情況會走向較大的那一側，也就是右子區間 $\frac{3n}{4}$。

(b) 建立最壞情況遞迴式

令 $T(n)$ 為在長度為 $n$ 的已排序陣列中搜尋的最壞比較次數。根據上面的切分：

（左側的 $\frac{n}{4}$ 只會在更佳情況出現，故在「最壞」分析中不需要考慮。）

(c) 解遞迴式的漸進上界

遞迴式 $T(n)=T\!\left(\frac{3}{4}n\right)+1$ 可直接套用主定理（Master Theorem）或利用對數變換：

核心觀念

本題要分辨「迴圈執行次數」與「每次呼叫的成本」，並把建構 Grid 的成本也算進總時間。若各部分時間為 $T_1(n),T_2(n)$，總時間由較大的漸近項主導。

題目未提供 Grid 的類別定義；以下依本題常見設定分析：new Grid(n) 為 $\Theta(n)$，flip() 為 $\Theta(n^2)$，smash(r,c) 為 $\Theta(1)$，reverse(r) 為 $\Theta(r)$。

解題方法

(a) 建構花 $\Theta(n)$。flip() 處理整個 $n \times n$ 網格，花 $\Theta(n^2)$，因此總時間為 $\Theta(n^2)$。

(b) 迴圈從 $-10000$ 到 $10000$，共執行 $20001$ 次，次數與 $n$ 無關。每次 smash(1,1) 花 $\Theta(1)$，迴圈總成本仍為 $\Theta(1)$；加上建構成本，總時間為 $\Theta(n)$。

(c) r 依序取 $1,2,4,8,\ldots$，小於 $n$。每次 reverse(r) 花 $\Theta(r)$，所以總成本為等比級數：

核心觀念

本題考查演算法的最壞情況時間複雜度與漸近成長率比較。最壞情況表示：對所有輸入大小為 $n$ 的輸入，取演算法所需步驟數的最大值，再觀察 $n$ 增大時，步驟數如何成長。

依照漸近成長率，選項中的複雜度由慢到快排列為：

成長率越慢，輸入規模變大時，執行時間通常增加得越少。

解題方法

比較各選項的成長速度即可。$O(1)$ 表示執行步驟數不隨輸入大小 $n$ 增加，是這些選項中成長最慢的複雜度，因此代表執行最快的情況。

選項分析

• A. $O(n\log n)$：錯誤。 執行時間會隨輸入大小增加，成長速度快於 $O(n)$、$O(\log n)$ 與 $O(1)$。
• **B. $O(\log n)$：錯誤。

核心觀念

本題考查單向鏈結串列各項操作的最壞情況時間複雜度。以下依一般假設：串列只持有指向首節點的指標，沒有尾指標。

單向鏈結串列的每個節點只記錄下一個節點的位置。從首節點出發，可以沿著 next 指標向後走；若要定位尾端或特定值，最壞情況下必須逐節點走訪。設串列有 $n$ 個節點：

• 固定次數的指標操作：$O(1)$。
• 最多走訪整條串列：$O(n)$。

解題方法

逐項判斷每種操作是否必須從首節點開始走訪。只有在首端插入時，不必搜尋節點：建立新節點，讓它指向原首節點，再更新首指標即可，所需步驟固定，因此是 $O(1)$。

選項分析

• A. Searching for an item in the list：$O(n)$，錯誤。
  目標值可能不存在，也可能位於尾端；最壞情況下必須檢查全部 $n$ 個節點。

• B. Inserting an item at the beginning of the list：$O(1)$，正確。
  新節點直接接到原首節點之前，再將首指標改為新節點。不需走訪串列，時間與 $n$ 無關。

核心觀念

時間複雜度取決於程式執行次數如何隨輸入規模 $n$ 增長。每次迴圈執行的 total += i 都是常數時間操作，因此只要計算迴圈執行幾次，就能判斷時間複雜度。

解題方法

假設 $n \ge 0$。迴圈從 $i=0$ 開始，每次增加 $1$，直到 $i=n$ 時仍會執行。因此，迴圈總共執行：

次。每次執行耗時為常數，總時間可寫成：

其中 $c$ 為常數。忽略常數倍與低階項後，時間複雜度為 $\Theta(n)$，也就是 $O(n)$。程式只使用 i 與 total 等固定數量的變數，空間複雜度為 $O(1)$。

選項分析

核心觀念

前序走訪順序是「根節點、左子樹、右子樹」；中序走訪順序是「左子樹、根節點、右子樹」；後序走訪順序是「左子樹、右子樹、根節點」。

前序的第一個節點是整棵樹的根。利用中序序列找到根的位置，就能分出左右子樹，再依此前序與中序的規則重建子樹。

解題方法

前序序列第一個節點是 $10$。中序序列中，$10$ 左側的節點屬於左子樹，右側的節點屬於右子樹：

• 左子樹的中序序列：$1, 2, 3, 5, 7, 9$
• 右子樹的中序序列：$11, 15, 18$

左子樹的前序序列為 $5, 1, 3, 2, 7, 9$，所以左子樹根節點是 $5$。依中序序列可再分出：

• $5$ 的左子樹中序序列：$1, 2, 3$
• $5$ 的右子樹中序序列：$7, 9$

左側再以節點 $1$ 為根。由前序與中序序列可知，$1$ 的右子樹根為 $3$，而 $3$ 的左子節點為 $2$。因此，$5$ 的左子樹後序為 $2, 3, 1$。

$5$ 的右子樹由 $7$ 為根，且 $9$ 是 $7$ 的右子節點，後序為 $9, 7$。所以以 $5$ 為根的左子樹，後序序列為：

核心觀念

二元搜尋樹（BST）插入新值時，從根節點開始比較：新值較小就往左子樹，較大就往右子樹；搜尋時也依照同一規則逐節點往下找。

搜尋所需的比較次數，等於從根節點到目標節點的路徑上，實際比較過的節點數。找到目標值時，與目標節點的相等比較也計入次數。

解題方法

依題目給定順序插入數字。搜尋 $6$ 時，只需追蹤與 $6$ 相關的比較方向：

1. 從根節點 $11$ 開始：$6<11$，往左。
2. 到節點 $5$：$6>5$，往右。
3. 到節點 $6$：找到目標。

搜尋路徑為 $11\rightarrow5\rightarrow6$，共比較 $3$ 次。

選項分析

核心觀念

前序表示式（prefix expression）會將運算子放在運算元之前。對二元運算式而言，最外層的運算子會成為前序表示式的第一個字元。

解題方法

原式為 $(3+5)*(8-1)$。括號中的加法與減法各自先形成一個子運算式，兩者再由最外層的乘法相乘。因此，最外層運算子是 $*$。

完整前序表示式為：

第一個字元是 $*$。

選項分析

核心觀念

Min heap（最小堆積）是一種完全二元樹，且每個父節點的值都小於或等於子節點。因此，根節點必定是目前最小值。

以陣列表示堆積時，刪除根節點的步驟如下：

1. 將最後一個節點移到根節點。
2. 刪除原本的最後一個節點。
3. 從根節點開始向下調整，每次與較小的子節點交換，直到符合堆積性質。

解題方法

依序插入 $1$ 到 $10$。因為每個新插入的值都大於既有父節點，插入後不需要向上調整，堆積陣列為：

接著逐次刪除根節點：

• 第 1 次刪除： 移入最後一個值 $10$，再向下調整，得到
  $[2,4,3,8,5,6,7,10,9]$，根節點為 $2$。
• 第 2 次刪除： 移入最後一個值 $9$，再向下調整，得到
  $[3,4,6,8,5,9,7,10]$，根節點為 $3$。

核心觀念

最小生成樹會在連通所有頂點的前提下，選取總權重最小的邊。判斷某邊是否必定不在最小生成樹中，可用環路性質：若某個環路中有一條邊的權重嚴格大於其餘邊，該邊不會被選入最小生成樹。

解題方法

觀察 $A$、$B$、$G$ 形成的環路：

其中 $A\!-\!G$ 是環路上權重最大的邊。連接 $A$ 與 $G$ 時，可改走 $A\!-\!B\!-\!G$，且兩邊權重分別為 $1$、$4$，因此 $A\!-\!G$ 不會被選入最小生成樹。

選項分析

核心觀念

最小生成樹（Minimum Spanning Tree, MST）是在連通、無向且帶權的圖中，連接所有頂點、沒有環，並使總權重最小的生成樹。若圖有 $n$ 個頂點，生成樹會恰有 $n-1$ 條邊。

本題使用 Kruskal 演算法：依邊權重由小到大檢查，每次加入不會形成環的邊，直到選滿 $n-1$ 條。

解題方法

依題目列出的邊，從權重最小的邊開始選：

• 權重 $1$：選 $C\text{–}E$、$E\text{–}J$、$K\text{–}G$。
• 權重 $2$：選 $D\text{–}I$、$I\text{–}J$、$E\text{–}A$。這些邊都能連接不同的連通部分，不會形成環。
• 權重 $3$：選 $A\text{–}G$，連接兩個部分；再選 $G\text{–}B$，將 $B$ 接入。$C\text{–}I$ 會形成環，因此不選。

核心觀念

強連通分量是極大的頂點集合；集合中任兩個頂點都能彼此到達。判斷時可依鄰接矩陣逐列讀出有向邊，再找出能形成互相到達關係的頂點群。

解題方法

依矩陣可讀出以下關鍵邊：

• $B\to D$、$D\to B$，且 $E$ 與 $B、D$ 互有路徑，因此 $\{B,D,E\}$ 是一個強連通分量。
• $C\to F\to G\to H\to C$ 形成有向環，因此 $\{C,F,G,H\}$ 是一個強連通分量。
• $A$ 沒有出邊，無法與其他頂點互相到達，所以 $\{A\}$ 獨立成分。
• $J\to I\to F$，但從 $I$ 或 $J$ 沒有路徑返回，因此 $\{I\}$、$\{J\}$ 各自是單獨分量。

核心觀念

廣度優先搜尋（BFS）使用佇列，依照距離起點的邊數由近到遠拜訪節點。處理某節點時，依鄰接串列順序檢查相鄰節點；尚未拜訪的節點會加入佇列。這題要找的是 BFS 拜訪順序中的最後一個節點。

解題方法

從 $A$ 開始，依題目列出的鄰接串列順序操作。節點在加入佇列時標記為已拜訪，避免之後重複加入。

核心觀念

以陣列表示二元堆積時，索引 $i$ 的左右子節點索引分別為 $2i+1$、$2i+2$。建立最大堆積的標準作法是由最後一個非葉節點開始，依序向前執行向下調整（sift-down），讓每個節點都不小於其子節點。

本題有 $11$ 個元素，最後一個非葉節點的索引為：

解題方法

從索引 $4$ 開始，依序處理索引 $4,3,2,1,0$：

核心觀念

紅黑樹插入新節點時，先依二元搜尋樹的規則插入，並將新節點染成紅色。若因此出現「紅節點的紅色父節點」，就依父節點、叔叔節點與祖父節點的位置關係進行重新著色或旋轉，維持紅黑樹性質。根節點最後必須為黑色。

本題使用標準紅黑樹插入規則；空節點視為黑色。

解題方法

依序插入 $6,10,3,20,1,7,16,17,15,22$，只需在插入後違反紅黑樹性質時調整。

1. 插入 $6$：成為黑色根節點。

2. 插入 $10,3$：兩者成為 $6$ 的右、左子節點，皆為紅色。

3. 插入 $20$：父節點 $10$ 與叔叔節點 $3$ 都是紅色，因此將 $10,3$ 染黑，祖父節點 $6$ 暫染紅；因 $6$ 是根，再將根染回黑色。

4. 插入 $1,7,16$：各自的父節點皆為黑色，不需調整。

5. 插入 $17$：它是 $16$ 的右子節點，$16$ 是祖父節點 $20$ 的左子節點，屬於內側情況。先對 $16$ 左旋，再對 $20$ 右旋，並重新著色，得到以 $17$ 為根的子樹：

       17黑
      /    \
    16紅   20紅
   

6. 插入 $15$：成為 $16$ 的左子節點。父節點 $16$ 與叔叔節點 $20$ 都是紅色，因此將 $16,20$ 染黑，將祖父節點 $17$ 染紅。由於 $17$ 的父節點 $10$ 是黑色，調整到此結束。