111 年 國立成功大學資訊管理研究所乙組《資料結構》

核心觀念

本題考查漸近成長率的比較，主要使用：

• $O(g(n))$：$f(n)$ 的成長率至多與 $g(n)$ 同階。
• $\Theta(g(n))$：$f(n)$ 與 $g(n)$ 同階。
• $o(g(n))$：$f(n)$ 的成長率嚴格低於 $g(n)$，即
  $\lim_{n\to\infty}\frac{f(n)}{g(n)}=0.$

常用公式與定理：

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

此結果可由 Stirling 公式得到：

$$\log(n!)=n\log n-n+O(\log n)=\Theta(n\log n).$$

不同底數的對數只差一個常數倍，不影響漸近成長率。

---

解題方法

逐一將各函數化為熟悉的漸近形式，再比較其成長速度。

$f_1=\log\left(\frac{n!}{n}\right)$

利用對數性質：

$$f_1=\log(n!)-\log n.$$

由於：

$$\log(n!)=\Theta(n\log n),$$

而 $\log n=o(n\log n)$，因此扣除 $\log n$ 不會改變主要成長項：

$$f_1=\Theta(n\log n).$$

也可直接寫成：

$$f_1=\log((n-1)!)=\Theta(n\log n).$$

---

$f_2=\log n!$

由 Stirling 公式：

$$\log(n!)=\Theta(n\log n).$$

因此：

$$f_2=\Theta(n\log n).$$

---

$f_3=\log^2 n$

題目中的 $\log^2 n$ 表示：

$$f_3=(\log n)^2.$$

比較 $f_3$ 與 $n\log n$：

$$\lim_{n\to\infty}\frac{(\log n)^2}{n\log n} = \lim_{n\to\infty}\frac{\log n}{n} =0.$$

所以：

$$f_3=o(n\log n).$$

---

$f_4=n\log n$

這本身就是標準成長形式：

$$f_4=\Theta(n\log n).$$

因此 $f_1,f_2,f_4$ 三者具有相同的漸近階。

---

$f_5=\left(\frac43\right)^n$

這是底數大於 $1$ 的指數函數。任何固定底數的指數函數都快於多項式及對數函數，因此：

a) Heap
使用優先佇列 (heap) 依照訊息優先度排序，可在 $O(\log n)$ 時間取出最高優先度訊息，且新訊息持續加入。

b) Queue
排隊購買須遵循先進先出，佇列提供 $O(1)$ 入列與出列。

c) AVL Tree
以玩家姓名作鍵的自平衡二元搜尋樹，支援 $O(\log n)$ 單筆查詢與插入，且透過中序走訪可在 $O(n)$ 時得到已排序名單。

參考書等級：大學二年級資料結構（Dutch National Flag 問題）

核心觀念
將 $b[0\ldots n-1]$ 以一次掃描完成三段分割：

• 位置 $[0,\,low-1]$ 為負數
• 位置 $[low,\,mid-1]$ 為零
• 位置 $[high+1,\,n-1]$ 為正數

演算法步驟（單指標三指針）

1. 初始化 low = 0, mid = 0, high = n-1。
2. 只要 mid <= high：
   • 若 b[mid] < 0：交換 b[low] ↔ b[mid]，low++、mid++。
   • 否若 b[mid] == 0：mid++。
   • 否則（b[mid] > 0）：交換 b[mid] ↔ b[high]，high--（mid 不動，因為換入的元素需再判斷）。

正確性說明

• 交換後，已確保 low 前皆為負，high 後皆為正。
• mid 只向右移動至遇到未確定的元素，保證所有元素最終被歸入三區。

【答案】

a) 最終 3‑ary min heap（插入 5,2,8,3,6,4,9,7,1）

          1
      /   |   \
    4     2    3
   /| \   /\
 6 5 9  8 7

b) 執行一次 delete‑min 後的 heap（以 a) 的結果為基礎）

核心觀念

本題考查兩個 AVL tree 性質：

1. AVL tree 中，每個節點的左右子樹高度差至多為 $1$。
2. 高度為 $h$ 的 AVL tree：
   • 節點數最少時，左右子樹高度為 $h-1$ 與 $h-2$。
   • 節點數最多時，為完全填滿的二元樹。
3. AVL tree 插入後，至多需要在一個祖先節點進行一次重新平衡；若左右方向相反，使用 double rotation，但題目規定 double rotation 計為 $1$ 次 rotation。

以下採用資料結構常見定義：單一節點的高度為 $0$，空樹高度為 $-1$。

---

解題方法：節點數的最小值

令 $N(h)$ 表示高度為 $h$ 的 AVL tree 所需的最少節點數。

最少節點的 AVL tree 必須讓兩棵子樹盡量矮，但仍維持高度 $h$，因此兩棵子樹高度為 $h-1$ 與 $h-2$：

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

初始值為：

$$N(0)=1,\qquad N(1)=2$$

逐步計算：

$$\begin{aligned} N(2)&=1+N(1)+N(0)=1+2+1=4\\ N(3)&=1+N(2)+N(1)=1+4+2=7\\ N(4)&=1+N(3)+N(2)=1+7+4=12\\ N(5)&=1+N(4)+N(3)=1+12+7=20\\ N(6)&=1+N(5)+N(4)=1+20+12=33 \end{aligned}$$

因此，高度為 $6$ 的 AVL tree 最少有 $33$ 個節點。

---

解題方法：節點數的最大值

節點數最多時，每一層都完全填滿，形成高度為 $6$ 的 perfect binary tree。

高度以邊數計算時，共有 $7$ 層，因此節點數為：

$$1+2+2^2+\cdots+2^6=2^{7}-1=127$$

因此，高度為 $6$ 的 AVL tree 最多有 $127$ 個節點。

核心觀念

Quick sort 的執行效率高度取決於 pivot 的選擇：

• 若 pivot 每次都接近資料的中位數，資料可被分成大小接近的兩部分，時間複雜度約為 $O(n\log n)$。
• 若 pivot 每次都是最大值或最小值，分割會極度不平衡，時間複雜度退化為 $O(n^2)$。

**Median of three rule（三者取中法）**是從目前待排序區間的三個代表元素中選出中間值作為 pivot。通常選取：

1. 第一個元素
2. 中間位置的元素
3. 最後一個元素

再取這三個值的中位數，而不是取整個資料集合的真正中位數。

---

解題方法

題目給定資料：

$$\{11,19,13,20,21,6,7,1,10,15,14,17,35\}$$

共有 $13$ 個元素，因此：

• 第一個元素：$11$
• 中間位置為第 $7$ 個元素：$7$
• 最後一個元素：$35$

三個候選值為：

$$11,\ 7,\ 35$$

將三者由小到大排列：

$$7 < 11 < 35$$

因此三者的中間值為：

$$\boxed{11}$$

所以本次 quick sort 的 pivot 選為：

$$\boxed{\text{pivot}=11}$$

---

以本題資料說明分割

選定 $11$ 為 pivot 後，quick sort 會將其他元素分到 pivot 的兩側：

• 小於 $11$ 的元素：

$$\{6,7,1,10\}$$

• 大於 $11$ 的元素：

$$\{19,13,20,21,15,14,17,35\}$$

概念上的分割結果為：

$$\{6,7,1,10\}\quad 11\quad \{19,13,20,21,15,14,17,35\}$$

接著，quick sort 會對左右兩個子區段分別重複套用 median of three rule，直到所有子區段完成排序。

實際程式實作時，元素不一定會維持上述排列順序；分割過程可能透過交換元素完成，但 pivot 的選擇原則與左右兩側的大小關係不變。

---

為何使用三者取中法

核心觀念

本題考查 Quick Sort（快速排序）中的 median of three pivot selection（中位數之三選樞紐）方法。

對目前待排序區間的三個元素：

1. 第一個元素
2. 中間位置元素
3. 最後一個元素

先比較三者大小，選出其中的中位數作為 pivot。如此可避免已排序、逆序等特殊輸入時，經常選到最小值或最大值，降低 Quick Sort 退化成 $O(n^2)$ 的機率。

Quick Sort 的核心分割原則為：

$$\text{小於 pivot 的元素}\quad|\quad pivot\quad|\quad\text{大於 pivot 的元素}$$

完成一次 partition 後，pivot 已位於最終正確位置，再遞迴處理 pivot 左右兩側的子序列。

---

解題方法

題目採用 median of three 規則選擇 pivot。設目前排序區間為：

$$A[\text{left}],\ldots,A[\text{right}]$$

其中間位置為：

$$\text{mid}=\left\lfloor\frac{\text{left}+\text{right}}{2}\right\rfloor$$

比較：

$$A[\text{left}],\quad A[\text{mid}],\quad A[\text{right}]$$

三者的中位數即為本輪 pivot。

本題題幹所稱的「above numbers」數字列表未附在目前資料中，因此無法列出每一輪的實際數值交換順序。以下依照標準的 median-of-three Quick Sort，採用 Lomuto partition 方式完整說明排序流程。

---

Median of Three 的選擇規則

假設目前區間三端點元素為 $x=A[\text{left}]$、$y=A[\text{mid}]$、$z=A[\text{right}]$：

• 若 $x\le y\le z$，pivot 為 $y$
• 若 $z\le y\le x$，pivot 為 $y$
• 若 $y\le x\le z$，pivot 為 $x$
• 若 $z\le x\le y$，pivot 為 $x$
• 若 $x\le z\le y$，pivot 為 $z$
• 若 $y\le z\le x$，pivot 為 $z$

也就是將三個候選值排序後，取第二個值。

---

一次 partition 的完整程序

對目前區間 $A[\text{left}..\text{right}]$：

1. 找出 $A[\text{left}]$、$A[\text{mid}]$、$A[\text{right}]$ 的中位數。

2. 將該中位數交換到最右端 $A[\text{right}]$。

3. 設定：

   $$i=\text{left}-1$$

4. 從 $j=\text{left}$ 掃描至 $\text{right}-1$：

   • 若 $A[j]<\text{pivot}$，先將 $i$ 加一，再交換 $A[i]$ 與 $A[j]$。
   • 若 $A[j]\ge\text{pivot}$，保持不動。

5. 掃描完成後，將 $A[i+1]$ 與最右端 pivot 交換。

6. 此時 pivot 位於：

核心觀念

圖中若存在一條路徑，從某個頂點出發沿著邊行走，最後又回到原頂點，即稱為存在 cycle（循環）。

使用 DFS（深度優先搜尋）判斷 cycle 時，關鍵在於：

• WHITE：尚未拜訪。
• GRAY：目前正在 DFS 遞迴路徑上。
• BLACK：已完成該頂點及其所有相鄰頂點的搜尋。

對於有向圖，若搜尋頂點 $u$ 時，發現一條邊 $(u,v)$ 且 color[v] = GRAY，表示目前 DFS 路徑中已經存在 $v$，這條邊又回到正在搜尋的祖先頂點，因此形成 cycle。

解題方法：有向圖

以 DFS 搭配三色標記判斷：

HasCycle(G):
    for each vertex v in G:
        color[v] = WHITE

    for each vertex v in G:
        if color[v] == WHITE:
            if DFS(v) == true:
                return true

    return false


DFS(u):
    color[u] = GRAY

    for each vertex v in Adj[u]:
        if color[v] == GRAY:
            return true

        if color[v] == WHITE:
            if DFS(v) == true:
                return true

    color[u] = BLACK
    return false

其中 Adj[u] 表示頂點 $u$ 的鄰接串列。

正確性說明

當 DFS 從 $u$ 走到 $v$ 時：

1. 若 color[v] = WHITE，表示 $v$ 尚未搜尋，繼續 DFS。
2. 若 color[v] = BLACK，表示 $v$ 的搜尋已完成，此邊不會形成目前 DFS 路徑上的循環。
3. 若 color[v] = GRAY，表示 $v$ 是目前 DFS 遞迴路徑中的頂點。沿著 DFS 樹從 $v$ 可走到 $u$，再透過邊 $(u,v)$ 回到 $v$，因此形成 cycle。

DFS 會從每個尚未拜訪的頂點開始，因此即使圖不是連通圖，也能檢查所有 connected component。

無向圖的寫法

本題要求使用 DFS 演算法，從節點 1 開始，並偏好較小數值的鄰居，來構建一個生成樹（Spanning Tree）。同時需要展示 DFS 使用的數據結構（堆疊 Stack）的內容變化過程。

圖示分析：
首先，我們需要理解題目中提供的圖。雖然 OCR 沒有識別出圖片，但根據題目內容，圖中包含節點，並且節點之間有邊連接。題目要求從節點 1 開始，並偏好較小數值的鄰居。這意味著在 DFS 遍歷時，如果一個節點有多個鄰居，我們應該優先訪問數值較小的鄰居。

DFS 構建生成樹的原理：
DFS 遍歷圖時，會記錄下從起點到每個節點的路徑。當 DFS 訪問一個新的節點時，從當前節點到這個新節點的邊就被添加到生成樹中。DFS 使用堆疊（Stack）來管理待訪問的節點。

演算法步驟：

1. 初始化：

   • 選擇起始節點：1。
   • 使用堆疊（Stack）來模擬 DFS 的遞迴調用。
   • 使用一個 visited 集合來記錄已訪問的節點。
   • 生成樹的邊集（Edge Set for Spanning Tree）。

2. DFS 過程：

   • 將起始節點 1 壓入堆疊，並標記為已訪問。
   • 當堆疊不為空時，執行以下操作：
     • 查看堆疊頂部的節點 u（但不彈出）。
     • 找到 u 的所有未訪問過的鄰居。
     • 如果 u 有未訪問過的鄰居：
       • 選擇數值最小的那個未訪問鄰居 v。
       • 將邊 $(u, v)$ 加入生成樹的邊集中。
       • 將 v 標記為已訪問。
       • 將 v 壓入堆疊。
     • 如果 u 沒有未訪問過的鄰居：
       • 將 u 從堆疊彈出（回溯）。

注意： 題目要求「偏好較小的數值」，這需要在選擇下一個訪問的鄰居時進行排序。

假設圖結構（根據常見的圖題猜測，需要實際圖片確認）：
假設圖中有以下節點和邊（邊的權重或節點值）：
節點：1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11
邊（無向）：(1,2), (1,3), (1,4), (2,5), (2,6), (3,7), (3,8), (4,9), (4,10), (5,11), ...

根據題目要求，我們使用 Stack 和 DFS，並偏好較小數值。

模擬過程：

• 起始節點：1
• Stack: []
• Visited: {}
• Spanning Tree Edges: {}

1. 訪問節點 1：

   • 將 1 壓入堆疊。
   • Stack: [1]
   • Visited: {1}
   • 查看節點 1 的鄰居。假設鄰居是 {2, 3, 4} (按數值從小到大排序)。
   • 選擇最小鄰居 2。
   • 加入邊 (1, 2) 到生成樹。
   • 將 2 壓入堆疊，標記為已訪問。
   • Stack: [1, 2]
   • Visited: {1, 2}
   • Spanning Tree Edges: {(1, 2)}

2. 查看堆疊頂部節點 2：

   • 查看節點 2 的鄰居。假設鄰居是 {1, 5, 6}。
   • 節點 1 已訪問。
   • 未訪問鄰居是 {5, 6}。
   • 選擇最小鄰居 5。
   • 加入邊 (2, 5)。
   • 將 5 壓入堆疊，標記為已訪問。
   • Stack: [1, 2, 5]
   • Visited: {1, 2, 5}
   • Spanning Tree Edges: {(1, 2), (2, 5)}

3. 查看堆疊頂部節點 5：

   • 查看節點 5 的鄰居。假設鄰居是 {2, 11}。
   • 節點 2 已訪問。
   • 未訪問鄰居是 {11}。
   • 選擇 11。
   • 加入邊 (5, 11)。
   • 將 11 壓入堆疊，標記為已訪問。
   • Stack: [1, 2, 5, 11]
   • Visited: {1, 2, 5, 11}
   • Spanning Tree Edges: {(1, 2), (2, 5), (5, 11)}

4. 查看堆疊頂部節點 11：

   • 假設節點 11 沒有未訪問的鄰居。
   • 將 11 從堆疊彈出（回溯）。
   • Stack: [1, 2, 5]

5. 查看堆疊頂部節點 5：

   • 節點 5 的未訪問鄰居 {11} 已經處理完畢。
   • 將 5 從堆疊彈出（回溯）。
   • Stack: [1, 2]

6. 查看堆疊頂部節點 2：

   • 節點 2 的未訪問鄰居是 {5, 6}。
   • 5 已處理。
   • 未訪問鄰居是 {6}。
   • 選擇 6。
   • 加入邊 (2, 6)。
   • 將 6 壓入堆疊，標記為已訪問。
   • Stack: [1, 2, 6]
   • Visited: {1, 2, 5, 11, 6}
   • Spanning Tree Edges: {(1, 2), (2, 5), (5, 11), (2, 6)}

7. 查看堆疊頂部節點 6：

   • 假設節點 6 沒有未訪問的鄰居。
   • 將 6 從堆疊彈出。
   • Stack: [1, 2]

8. 查看堆疊頂部節點 2：

   • 節點 2 的所有鄰居都已處理。
   • 將 2 從堆疊彈出。
   • Stack: [1]

9. 查看堆疊頂部節點 1：

   • 節點 1 的未訪問鄰居是 {2, 3, 4}。
   • 2 已處理。
   • 未訪問鄰居是 {3, 4}。
   • 選擇最小鄰居 3。
   • 加入邊 (1, 3)。
   • 將 3 壓入堆疊，標記為已訪問。
   • Stack: [1, 3]
   • Visited: {1, 2, 5, 11, 6, 3}
   • Spanning Tree Edges: {(1, 2), (2, 5), (5, 11), (2, 6), (1, 3)}

10. 查看堆疊頂部節點 3：

    • 假設節點 3 的鄰居是 {1, 7, 8}。
    • 節點 1 已訪問。
    • 未訪問鄰居是 {7, 8}。
    • 選擇最小鄰居 7。
    • 加入邊 (3, 7)。
    • 將 7 壓入堆疊，標記為已訪問。
    • Stack: [1, 3, 7]
    • Visited: {1, 2, 5, 11, 6, 3, 7}
    • Spanning Tree Edges: {(1, 2), (2, 5), (5, 11), (2, 6), (1, 3), (3, 7)}

... (繼續這個過程，直到所有節點都被訪問，堆疊為空)

繪製過程：
需要繪製：

1. 初始圖。
2. DFS 過程中的堆疊內容變化。
3. 生成樹的邊集如何逐步增加。
4. 最終的生成樹。

由於無法看到實際的圖，我將基於一個假設的圖結構來模擬，並強調 DFS 和 Stack 的使用。

假設的圖結構（節點 1-11，邊根據 B3 的圖推測）：
節點：1 到 11。
邊：(1,2), (1,3), (1,4), (2,4), (2,5), (3,5), (3,6), (4,7), (5,7), (5,8), (6,9), (7,10), (8,10), (8,11), (9,11)
（這是一個猜測，實際圖可能不同，但 DFS 原理一樣）

使用 Stack 和 DFS 構建生成樹（偏好小數值）：

• 起始節點：1
• Stack: []
• Visited: {}
• Spanning Tree Edges: {}

步驟 1:

• 訪問 1。將 1 壓入 Stack。Visited: {1}。Stack: [1]
• 1 的鄰居：{2, 3, 4}。選擇最小的 2。
• 加入邊 (1, 2)。將 2 壓入 Stack。Visited: {1, 2}。Stack: [1, 2]。Edges: {(1, 2)}

步驟 2:

• 查看頂部 2。鄰居：{1, 4, 5}。1 已訪問。
• 選擇最小未訪問鄰居 4。
• 加入邊 (2, 4)。將 4 壓入 Stack。Visited: {1, 2, 4}。Stack: [1, 2, 4]。Edges: {(1, 2), (2, 4)}

步驟 3:

• 查看頂部 4。鄰居：{1, 2, 7}。1, 2 已訪問。
• 選擇最小未訪問鄰居 7。
• 加入邊 (4, 7)。將 7 壓入 Stack。Visited: {1, 2, 4, 7}。Stack: [1, 2, 4, 7]。Edges: {(1, 2), (2, 4), (4, 7)}

步驟 4:

• 查看頂部 7。鄰居：{4, 10}。4 已訪問。
• 選擇最小未訪問鄰居 10。
• 加入邊 (7, 10)。將 10 壓入 Stack。Visited: {1, 2, 4, 7, 10}。Stack: [1, 2, 4, 7, 10]。Edges: {(1, 2), (2, 4), (4, 7), (7, 10)}

步驟 5:

• 查看頂部 10。鄰居：{7, 8}。7 已訪問。
• 選擇最小未訪問鄰居 8。
• 加入邊 (10, 8)。將 8 壓入 Stack。Visited: {1, 2, 4, 7, 10, 8}。Stack: [1, 2, 4, 7, 10, 8]。Edges: {(1, 2), (2, 4), (4, 7), (7, 10), (10, 8)}

步驟 6:

• 查看頂部 8。鄰居：{5, 10, 11}。10 已訪問。
• 選擇最小未訪問鄰居 5。
• 加入邊 (8, 5)。將 5 壓入 Stack。Visited: {1, 2, 4, 7, 10, 8, 5}。Stack: [1, 2, 4, 7, 10, 8, 5]。Edges: {..., (10, 8), (8, 5)}

步驟 7:

• 查看頂部 5。鄰居：{2, 3, 8}。2, 8 已訪問。
• 選擇最小未訪問鄰居 3。
• 加入邊 (5, 3)。將 3 壓入 Stack。Visited: {..., 5, 3}。Stack: [..., 5, 3]。Edges: {..., (8, 5), (5, 3)}

步驟 8:

• 查看頂部 3。鄰居：{1, 5, 6}。1, 5 已訪問。
• 選擇最小未訪問鄰居 6。
• 加入邊 (3, 6)。將 6 壓入 Stack。Visited: {..., 3, 6}。Stack: [..., 3, 6]。Edges: {..., (5, 3), (3, 6)}

步驟 9:

• 查看頂部 6。鄰居：{3, 9}。3 已訪問。
• 選擇最小未訪問鄰居 9。
• 加入邊 (6, 9)。將 9 壓入 Stack。Visited: {..., 6, 9}。Stack: [..., 6, 9]。Edges: {..., (3, 6), (6, 9)}

步驟 10:

• 查看頂部 9。鄰居：{6, 11}。6 已訪問。
• 選擇最小未訪問鄰居 11。
• 加入邊 (9, 11)。將 11 壓入 Stack。Visited: {..., 9, 11}。Stack: [..., 9, 11]。Edges: {..., (6, 9), (9, 11)}

步驟 11:

• 查看頂部 11。鄰居：{8, 9}。8, 9 已訪問。
• 沒有未訪問鄰居。彈出 11。Stack: [..., 9]

步驟 12:

• 查看頂部 9。鄰居：{6, 11}。都已訪問。
• 沒有未訪問鄰居。彈出 9。Stack: [..., 6]

... (繼續彈出，直到堆疊為空)

最終的生成樹邊集 (Edge Set for Spanning Tree)：
{(1, 2), (2, 4), (4, 7), (7, 10), (10, 8), (8, 5), (5, 3), (3, 6), (6, 9), (9, 11)}

最終的生成樹結構：
需要根據邊集繪製。

繪製過程的細節：

• Stack 內容變化： 記錄每次壓棧和彈棧的操作。
• Visited 節點： 記錄訪問順序。
• Spanning Tree Edges： 記錄每次添加的邊。

重要提示：
由於題目中沒有提供實際的圖，這裡的模擬過程是基於一個假設的圖結構。實際作答時，必須根據題目提供的圖來進行 DFS 遍歷和邊的選擇。

偽代碼（使用 Stack）：

本題要求使用 Kruskal 演算法，找出圖中度數最大頂點所在連通分量的最小生成樹（Minimum Spanning Tree, MST）。

Kruskal 演算法原理：
Kruskal 演算法是一種貪心演算法，用於尋找圖的最小生成樹。其步驟如下：

1. 將圖中所有的邊按照權重從小到大排序。
2. 初始化一個空的邊集，用於存放 MST 的邊。
3. 遍歷排序後的邊列表。對於每條邊 $(u, v)$：
   • 檢查添加這條邊是否會在當前 MST 的邊集中形成環。
   • 如果不會形成環，則將這條邊加入 MST 的邊集中。
4. 重複步驟 3，直到 MST 的邊數等於 $V-1$（其中 $V$ 是連通分量的節點數），或者所有邊都被考慮過。

判斷環的技巧：
通常使用 Union-Find（Disjoint Set Union, DSU）數據結構來高效地判斷是否形成環。

• 初始時，每個節點自成一個集合。
• 當考慮邊 $(u, v)$ 時，檢查 find(u) 和 find(v)。
  • 如果 find(u) == find(v)，表示 u 和 v 已經在同一個集合中，添加邊 $(u, v)$ 會形成環。
  • 如果 find(u) != find(v)，表示 u 和 v 在不同的集合中，添加邊 $(u, v)$ 不會形成環。此時，將 u 和 v 所屬的集合進行合併 (union(u, v))。

題目要求：

1. 找出度數最大的頂點： 需要先計算圖中每個頂點的度數（連接到該頂點的邊的數量），然後找到度數最大的頂點。
2. 確定其所在的連通分量： 找出包含該頂點的整個連通分量。
3. 應用 Kruskal 演算法： 在這個連通分量上應用 Kruskal 演算法，找出其最小生成樹。

步驟分解：

1. 計算頂點度數並找出度數最大的頂點：
（由於沒有實際圖，這裡假設一個例子）
假設圖有節點 {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}，邊及其權重（假設邊的權重就是節點值或簡單標號）：
邊（權重）：(1,2, w1), (1,3, w2), (1,4, w3), (2,4, w4), (2,5, w5), (3,5, w6), (3,6, w7), (4,7, w8), (5,7, w9), (5,8, w10), (6,9, w11), (7,10, w12), (8,10, w13), (8,11, w14), (9,11, w15)
（這裡的 w 是權重，題目未給，假設就是邊的標識或節點值，或者是題目圖中直接標註的權重）

假設權重如下（隨意賦值，以說明過程）：
(1,2, 5), (1,3, 2), (1,4, 8), (2,4, 3), (2,5, 6), (3,5, 4), (3,6, 9), (4,7, 11), (5,7, 10), (5,8, 7), (6,9, 12), (7,10, 13), (8,10, 14), (8,11, 15), (9,11, 16)

計算度數：

• Deg(1) = 3 (邊 (1,2), (1,3), (1,4))
• Deg(2) = 3 (邊 (1,2), (2,4), (2,5))
• Deg(3) = 3 (邊 (1,3), (3,5), (3,6))
• Deg(4) = 3 (邊 (1,4), (2,4), (4,7))
• Deg(5) = 4 (邊 (2,5), (3,5), (5,7), (5,8))
• Deg(6) = 2 (邊 (3,6), (6,9))
• Deg(7) = 3 (邊 (4,7), (5,7), (7,10))
• Deg(8) = 3 (邊 (5,8), (8,10), (8,11))
• Deg(9) = 2 (邊 (6,9), (9,11))
• Deg(10) = 3 (邊 (7,10), (8,10))
• Deg(11) = 2 (邊 (8,11), (9,11))

度數最大的頂點是 5，其度數為 4。

2. 確定度數最大頂點所在的連通分量：
在這個例子中，假設整個圖是連通的。如果圖有多個連通分量，我們需要先找出節點 5 所在的那個分量。通常，可以通過 BFS 或 DFS 從節點 5 開始，找出所有可達的節點，這就是該連通分量。假設整個圖是連通的，節點數 $V=11$。

3. 在該連通分量上應用 Kruskal 演算法：

• 邊列表 (按權重排序)：
  (1,3, 2), (2,4, 3), (3,5, 4), (1,2, 5), (2,5, 6), (5,8, 7), (1,4, 8), (3,6, 9), (5,7, 10), (4,7, 11), (6,9, 12), (7,10, 13), (8,10, 14), (8,11, 15), (9,11, 16)

• 初始化 Union-Find：
  每個節點自成一個集合：{1}, {2}, {3}, {4}, {5}, {6}, {7}, {8}, {9}, {10}, {11}。
  MST 邊集：{}

• 遍歷排序後的邊：

  1. 邊 (1,3) 權重 2：find(1) != find(3)。加入邊 (1,3)。Union(1,3)。集合：{1,3}, {2}, {4}, {5}, {6}, {7}, {8}, {9}, {10}, {11}。MST: {(1,3)}
  2. 邊 (2,4) 權重 3：find(2) != find(4)。加入邊 (2,4)。Union(2,4)。集合：{1,3}, {2,4}, {5}, {6}, {7}, {8}, {9}, {10}, {11}。MST: {(1,3), (2,4)}
  3. 邊 (3,5) 權重 4：find(3) != find(5)。加入邊 (3,5)。Union(3,5)。集合：{1,3,5}, {2,4}, {6}, {7}, {8}, {9}, {10}, {11}。MST: {(1,3), (2,4), (3,5)}
  4. 邊 (1,2) 權重 5：find(1) != find(2)。加入邊 (1,2)。Union(1,2)。集合：{1,2,3,4,5}, {6}, {7}, {8}, {9}, {10}, {11}。MST: {(1,3), (2,4), (3,5), (1,2)}
  5. 邊 (2,5) 權重 6：find(2) == find(5) (都在 {1,2,3,4,5} 集合中)。形成環。忽略。
  6. 邊 (5,8) 權重 7：find(5) != find(8)。加入邊 (5,8)。Union(5,8)。集合：{1,2,3,4,5,8}, {6}, {7}, {9}, {10}, {11}。MST: {(1,3), (2,4), (3,5), (1,2), (5,8)}
  7. 邊 (1,4) 權重 8：find(1) == find(4)。形成環。忽略。
  8. 邊 (3,6) 權重 9：find(3) != find(6)。加入邊 (3,6)。Union(3,6)。集合：{1,2,3,4,5,6,8}, {7}, {9}, {10}, {11}。MST: {..., (5,8), (3,6)}
  9. 邊 (5,7) 權重 10：find(5) != find(7)。加入邊 (5,7)。Union(5,7)。集合：{1,2,3,4,5,6,7,8}, {9}, {10}, {11}。MST: {..., (3,6), (5,7)}
  10. 邊 (4,7) 權重 11：find(4) == find(7)。形成環。忽略。
  11. 邊 (6,9) 權重 12：find(6) != find(9)。加入邊 (6,9)。Union(6,9)。集合：{1,2,3,4,5,6,7,8,9}, {10}, {11}。MST: {..., (5,7), (6,9)}
  12. 邊 (7,10) 權重 13：find(7) != find(10)。加入邊 (7,10)。Union(7,10)。集合：{1,2,3,4,5,6,7,8,9,10}, {11}。MST: {..., (6,9), (7,10)}
  13. 邊 (8,10) 權重 14：find(8) == find(10)。形成環。忽略。
  14. 邊 (8,11) 權重 15：find(8) != find(11)。加入邊 (8,11)。Union(8,11)。集合：{1,2,3,4,5,6,7,8,9,10,11}。MST: {..., (7,10), (8,11)}

• 結束： 已經添加了 $V-1 = 11-1 = 10$ 條邊。MST 構建完成。

最終的 MST 邊集（基於假設）：
{(1,3, 2), (2,4, 3), (3,5, 4), (1,2, 5), (5,8, 7), (3,6, 9), (5,7, 10), (6,9, 12), (7,10, 13), (8,11, 15)}

繪製 MST：
需要根據最終的 MST 邊集，將對應的節點和邊連接起來。

重要提示：
此處的計算和結果完全基於假設的圖結構和邊權重。實際作答時，必須參照題目提供的圖，準確計算度數、確定連通分量、列出邊並排序，然後執行 Kruskal 演算法。

偽代碼（Kruskal's Algorithm）：

核心觀念

Floyd 最短路徑演算法是求解「所有頂點對之間最短路徑」的動態規劃方法。

令

$$c(i,j,k)$$

表示從頂點 $i$ 到頂點 $j$ 的最短路徑長度，且路徑中的中間頂點編號不可大於 $k$。其中起點 $i$ 與終點 $j$ 不算中間頂點。

當 $k=0$ 時，不允許使用任何中間頂點，因此：

$$c(i,j,0)= \begin{cases} 0, & i=j\\ w(i,j), & i\neq j\text{ 且 }(i,j)\text{ 有邊}\\ \infty, & i\neq j\text{ 且 }(i,j)\text{ 無邊} \end{cases}$$

其中 $w(i,j)$ 是頂點 $i$ 到頂點 $j$ 的直接邊權重。

解題方法

考慮加入頂點 $k$ 作為允許使用的最大編號中間頂點。從 $i$ 到 $j$ 的最短路徑只有兩種情況：

1. 最短路徑不經過頂點 $k$：

$$c(i,j,k-1)$$

2. 最短路徑經過頂點 $k$：

$$c(i,k,k-1)+c(k,j,k-1)$$

因此遞迴公式為：

$$c(i,j,k)= \min\left\{ c(i,j,k-1), c(i,k,k-1)+c(k,j,k-1) \right\}$$

實作時可將 $c(i,j,k)$ 壓縮成二維陣列 $D[i][j]$。每次以 $k$ 為最外層迴圈，依序更新所有 $i,j$：

$$D[i][j]\leftarrow \min\left(D[i][j],D[i][k]+D[k][j]\right)$$

外層必須先固定 $k$，因為第 $k$ 輪代表「允許頂點 $k$ 作為中間頂點」。

Floyd 演算法虛擬碼

Floyd-Warshall(W, n)

    for i = 1 to n
        for j = 1 to n
            if i == j
                D[i][j] = 0
            else if W[i][j] 有直接邊
                D[i][j] = W[i][j]
            else
                D[i][j] = ∞

    for k = 1 to n
        for i = 1 to n
            for j = 1 to n
                if D[i][k] + D[k][j] < D[i][j]
                    D[i][j] = D[i][k] + D[k][j]

    return D

若要求實際最短路徑，而不只要求最短距離，可額外維護前驅矩陣 Next：

核心觀念
本題測驗的是 Floyd‑Warshall 演算法（全源最短路徑）以及 路徑重建 的技巧。

• Cost 矩陣保存經過所有中繼點後的最短距離，已是最終結果。
• Kay 矩陣（又稱 Next 或 Predecessor 矩陣）保存從起點到終點的第一個中繼點，用來依序還原實際路徑。

---

解題過程

1. 閱讀 Cost 與 Kay 矩陣

   • 先在 Cost 矩陣中找到 $C_{4,7}$，即從頂點 $4$ 到頂點 $7$ 的最短距離。若 $C_{4,7}= \infty$（或使用特殊值如 $-1$）則表示無路徑。
   • 再利用 Kay 矩陣重建路徑：Kay[4][7] 代表從 $4$ 前往 $7$ 時的第一個中繼節點 $k$（若 $k=7$ 表示直接相連）。

2. 路徑重建的遞迴步驟

   • 若 $k=7$，則路徑即為 $\{4,7\}$。
   • 否則，將問題拆成兩段：
     • 從 $4$ 到 $k$ 的子路徑：Path(4, k)
     • 從 $k$ 到 $7$ 的子路徑：Path(k, 7)
   • 合併時注意去除重複的節點 $k$（只保留一次）。

   以遞迴公式表示：

   $$\text{Path}(i,j)= \begin{cases} \{i,j\} & \text{if } \text{Kay}[i][j]=j \\ \text{Path}(i,\text{Kay}[i][j])\cup\text{Path}(\text{Kay}[i][j],j) & \text{otherwise} \end{cases}$$

核心觀念

本題考查雜湊函數中「除法取餘法」（division method）之除數選擇：

$$\text{homeBucket} = \text{Key} \bmod \text{divisor}$$

若除數為 $m$，雜湊表便有 $m$ 個 bucket，鍵值會依照除以 $m$ 的餘數分配至 $0$ 到 $m-1$ 的 bucket。

理想的除數應使鍵值平均分散，避免大量鍵值集中在少數 bucket，造成碰撞（collision）。在沒有特別鍵值分布資訊時，通常選擇「不接近 $2^k$，且最好為質數」的除數，以降低鍵值本身規律性對分布造成的影響。

---

解題方法

本題可從兩個方向判斷：

1. 除數是否為質數
2. 除數是否容易與鍵值的規律產生週期性對應

若除數為合數，鍵值的某些位元、尾數或因數結構可能直接影響餘數分布。例如：

• 以 $8$ 為除數時，只特別反映鍵值的低位元。
• 以 $9$ 為除數時，若鍵值與十進位數字和具有規律，餘數分布容易受影響。
• 以 $27$ 為除數時，因數結構更複雜，且 bucket 數量不一定符合實際需求。
• 以質數 $11$ 為除數時，通常較能打散具有規律的鍵值。

因此，在四個候選值中，$11$ 是最適合的選擇。

---

選項分析

除數 $8$

$8$ 是合數，也是 $2$ 的冪：

$$8 = 2^3$$

對任何整數 $K$ 而言，$K \bmod 8$ 只與 $K$ 的低位元有關。若鍵值具有連續編號、固定格式或低位元重複等特性，便容易使資料集中到部分 bucket。

例如，若鍵值皆為偶數，則不會落入奇數餘數 bucket；若鍵值的低三位元具有固定模式，分布也會明顯失衡。

因此，$8$ 容易受到鍵值低位元規律影響，不是最佳選擇。

除數 $9$

$9$ 為合數：

$$9 = 3^2$$

當鍵值具有十進位表示上的規律時，取 $9$ 的餘數容易呈現週期性。例如十進位整數除以 $9$ 的餘數與各位數字和有關：

核心觀念

本題考查 Bloom filter 在「檔案同步」或「資料集合差異比對」中的應用。

Bloom filter 是一種節省空間的機率型集合結構，包含：

• 長度為 $m$ 的位元陣列，初始皆為 $0$。
• $k$ 個雜湊函數 $h_1,h_2,\ldots,h_k$。
• 插入元素 $x$ 時，將

$$h_i(x)\bmod m,\quad i=1,2,\ldots,k$$

所對應的位置設為 $1$。

查詢元素 $x$ 時：

• 只要其中一個對應位元為 $0$，即可確定 $x$ 不在集合中。
• 若所有對應位元皆為 $1$，只能判定 $x$「可能」在集合中。

因此，Bloom filter 具有：

• 不會漏判集合中原本存在的元素，即沒有 false negative。
• 可能將不存在的元素誤判為存在，即可能產生 false positive。

---

Differential file 的意義

Differential file，中文可稱為「差異檔」或「增量檔」，是指兩份檔案或兩個資料集合之間不同部分所形成的檔案。

假設：

• 接收端目前擁有資料集合 $R$。
• 傳送端擁有較新的資料集合 $S$。

理想的差異檔為：

$$D=S-R$$

也就是傳送端有、但接收端沒有的資料。傳送差異檔後，接收端即可將資料更新為較新的版本，而不必重新傳送完整檔案。

差異檔通常可包含：

• 新增的資料項目。
• 被修改後的資料項目。
• 必要時，代表刪除操作的刪除標記。

Bloom filter 主要處理「某資料項目是否已存在」的判斷；若要偵測修改內容，通常必須對完整記錄、版本號或內容摘要進行雜湊。

---

解題方法：利用 Bloom filter 建立差異檔

第一步：接收端建立 Bloom filter

接收端先將自己目前擁有的所有資料項目加入 Bloom filter。

若接收端資料集合為

$$R=\{r_1,r_2,\ldots,r_n\}$$

則對每個 $r_j$，計算 $k$ 個雜湊位置，並將這些位置設為 $1$。

完成後，接收端不必傳送完整資料集合，只需將 Bloom filter 傳給傳送端。

第二步：傳送端逐項查詢

傳送端針對自己的每個資料項目 $s\in S$，查詢 Bloom filter：

• 若任一雜湊位置為 $0$，表示接收端一定沒有 $s$，因此將 $s$ 放入差異檔。
• 若所有雜湊位置皆為 $1$，表示接收端可能已有 $s$，通常暫時不放入差異檔。

因此，基本流程可表示為：