113 年 國立成功大學電腦與通信工程研究所丁組《資料結構》

核心觀念

強連通分量（strongly connected component）是有向圖中一個極大的強連通頂點集合。集合內任兩個頂點都必須能互相到達；「極大」表示無法再加入其他頂點而仍保持強連通。

解題方法

依圖中的箭頭，頂點 $1$ 與 $2$ 互相可達，$2$ 與 $3$ 互相可達，$3$ 與 $5$ 互相可達。因此，頂點 $1,2,3,5$ 彼此都能沿著有向路徑互相到達，構成同一個強連通分量。

核心觀念

本題考查 Dijkstra 演算法在不同圖形表示法與最小值選取資料結構下的時間複雜度。

Dijkstra 演算法每次會：

1. 從尚未確定最短距離的頂點中，找出距離最小者。
2. 以該頂點更新相鄰頂點的暫定距離。

當圖以 adjacency matrix（鄰接矩陣）表示時，每一個頂點都必須逐一檢查，因此標準實作的時間複雜度為：

$$O(n^2)$$

其中 $n$ 為頂點數。

---

解題方法

1. 找出距離最小的頂點

在每一輪中，需從尚未選取的頂點中找出目前距離最小者。

若使用陣列儲存距離，必須掃描最多 $n$ 個頂點：

$$O(n)$$

Dijkstra 最多執行 $n$ 輪，因此找最小距離的總成本為：

$$n \times O(n)=O(n^2)$$

2. 進行距離更新

使用 adjacency matrix 時，選定一個頂點後，必須掃描該頂點在鄰接矩陣中的整列，以檢查它與所有頂點的連線關係。

每輪最多檢查 $n$ 個頂點：

$$O(n)$$

共執行 $n$ 輪，因此更新距離的總成本也是：

$$n \times O(n)=O(n^2)$$

3. 合併總複雜度

總時間複雜度為：

$$O(n^2)+O(n^2)=O(n^2)$$

因此，使用 adjacency matrix 的標準 Dijkstra 實作，其時間複雜度不是 $O(n\log n)$。

---

為何會出現 $O(n\log n)$

$O(n\log n)$ 通常是使用 adjacency list（鄰接串列）搭配 binary heap（一般二元堆積）時的簡化描述。

較完整的複雜度為：

$$O((n+m)\log n)$$

其中 $m$ 為邊數。

核心觀念

題目考查漸進複雜度的 $\Theta$ 定義。

函數 $f(n)$ 為 $\Theta(g(n))$，必須同時滿足：

$$\exists c_1,c_2>0,\ \exists n_0>0,\quad 0\le c_1g(n)\le f(n)\le c_2g(n), \quad \forall n\ge n_0$$

也就是：

• $f(n)$ 至少與 $g(n)$ 同階：$f(n)=\Omega(g(n))$
• $f(n)$ 至多與 $g(n)$ 同階：$f(n)=O(g(n))$

因此，$\Theta$ 是上下界同時成立，而不是只有下界。

解題方法

題目給出的條件為：

$$\exists c>0,\ \exists n_0>0,\quad f(n)>c\,g(n),\quad \forall n\ge n_0$$

這只表示 $f(n)$ 最低成長速度不小於 $g(n)$，對應於：

$$f(n)=\Omega(g(n))$$

但題目沒有要求存在另一個正數常數 $C$，使得：

$$f(n)\le Cg(n)$$

因此，無法保證 $f(n)=O(g(n))$，自然也無法保證 $f(n)=\Theta(g(n))$。

反例說明

令：

$$f(n)=n^2,\qquad g(n)=n$$

當 $n\ge 2$ 時：

$$f(n)=n^2>n=g(n)$$

所以題目所給的條件成立，可取 $c=1$、$n_0=2$。

但是：

核心觀念

本題考查插入排序（insertion sort）在不同輸入排列下的時間複雜度。

若插入排序採用「由小到大」排序，演算法會將目前元素與前方已排序區段比較，並將較大的元素向右移動，直到找到適當位置。

• 遞增排列：每個元素都已在正確位置，幾乎不需移動。
• 遞減排列：每次取出的元素都必須移到已排序區段的最前方，移動與比較次數最多。

解題方法

假設陣列共有 $n$ 個元素，且使用由小到大的插入排序。

在第 $i$ 回合，需將第 $i$ 個元素插入前方長度為 $i$ 的已排序區段。

遞增排列

例如：

$$1,2,3,4,5$$

每次插入的元素都大於前一個元素，只需進行少量比較，不需大量搬移：

$$T_{\text{best}}(n)=\Theta(n)$$

因此，遞增排列是插入排序的最佳情況，而不是最差情況。

遞減排列

例如：

$$5,4,3,2,1$$

處理過程如下：

• 插入 $4$：需移動 $5$，共約 $1$ 次
• 插入 $3$：需移動 $5,4$，共約 $2$ 次
• 插入 $2$：需移動 $5,4,3$，共約 $3$ 次
• 插入 $1$：需移動 $5,4,3,2$，共約 $4$ 次

總移動次數為：

核心觀念

1. 基數排序法（Radix Sort）原理：
   Radix Sort 是一種非比較型排序演算法（Non-comparison Sort），專門用於處理多鍵值（Multiple Keys）或多位數資料的排序。其核心運作依鍵值處理順序可分為兩種策略：

   • LSD（Least Significant Digit first）：由最低有效鍵（次要鍵）往最高有效鍵依序進行排序。每一回合必須使用穩定排序（Stable Sort）（如 Counting Sort 或 Bucket Sort）進行分配與收集（Distribution & Collection）。
   • MSD（Most Significant Digit first）：由最高有效鍵（主要鍵）開始分堆（Piles/Buckets），隨後必須對各子堆遞迴處理次高鍵（Next Significant Key），而非在所有回合重複處理最高有效鍵。

2. 時間複雜度公式：
   若待排序資料有 $n$ 筆、鍵值個數（或位數）為 $d$、各鍵值的基數（Radix，即取值範圍）為 $r$，則 Radix Sort 的時間複雜度為：
   $O(d \cdot (n + r))$
   只有在鍵值數量 $d$ 為常數且基數 $r = O(n)$ 或 $r = O(1)$ 時，時間複雜度才可簡化為線性時間 $O(n)$。

---

題目解析

本題為是非判斷題，原文敘述拆解為以下三個部分進行檢視：

1. 前半句敘述：Radix sort algorithm can be used to sort multiple keys.

   • 正確。Radix Sort 最早的應用即為多欄位排序（如撲克牌的花色與大小、年/月/日等多鍵值排序）。

2. 後半句複雜度敘述：Its time complexity in O(n)...

   • 不完全正確。其時間複雜度一般表示為 $O(d(n + r))$，省略 $d$ 與 $r$ 的條件直接斷言為 $O(n)$ 缺乏前提假設。

3. 後半句成因敘述：...since it will allocate the most significant key into multiple piles in every iteration.

   • 錯誤。此理由在演算法邏輯上完全錯誤：
     • 若採用 MSD：僅在第 1 個回合（Iteration）依據「最高有效鍵（Most Significant Key）」進行分堆；

核心觀念

Kruskal 演算法用於求加權無向連通圖的最小生成樹（Minimum Spanning Tree, MST）。其主要步驟為：

1. 將所有邊依權重由小到大排序。
2. 依序選取邊。
3. 若加入該邊不會形成 cycle，便加入目前的解。
4. 直到選出 $|V|-1$ 條邊為止。

Kruskal 演算法在執行過程中維持的是一個「森林」（forest），不是從頭到尾都維持單一棵樹。

森林是由一棵或多棵互不相連的樹所組成。Kruskal 一開始將每個頂點視為獨立的一棵樹：

$$F_0=\{\{v_1\},\{v_2\},\ldots,\{v_n\}\}$$

因此一開始通常有 $|V|$ 棵樹，而不是一棵樹。隨著選入連接不同樹的邊，森林中的樹逐漸合併，最後才形成一棵最小生成樹。

解題方法

判斷此敘述的關鍵，是區分「樹」與「森林」：

• 樹（tree）：連通且不含 cycle 的圖。
• 森林（forest）：不含 cycle，但不一定連通的圖。

Kruskal 每次加入邊時，會使用 Union-Find 判斷該邊兩端是否已在同一個連通元件中：

• 若在同一棵樹中，加入後會形成 cycle，因此捨棄。
• 若分屬不同的樹，加入後不會形成 cycle，因此接受，並將兩棵樹合併。

例如有四個頂點 $A,B,C,D$，一開始的狀態為：

$$\{A\},\{B\},\{C\},\{D\}$$

此時共有四棵樹，構成一個森林。若選入邊 $(A,B)$，狀態變為：

$$\{A,B\},\{C\},\{D\}$$

若再選入邊 $(B,C)$，狀態變為：

核心觀念

繼承（inheritance）可用來表達 ADT（抽象資料型別）之間的子型別（subtype）關係。

若類別 $B$ 繼承類別 $A$，表示：

• $B$ 擁有 $A$ 所提供的操作與特性；
• $B$ 可以在符合條件下被視為 $A$ 使用；
• $B$ 是較特殊、較具體的型別；
• $A$ 是較一般、較抽象的型別。

因此可表示為：

$$B \subseteq A$$

此處的「$\subseteq$」表示 $B$ 的物件可被視為 $A$ 的物件使用，並非單純指資料集合的包含。

解題方法

判斷繼承關係時，可套用「is-a」測試：

若 $B$ 繼承 $A$，則 $B$ is-a $A$。

例如：

• Stack 繼承 List：Stack 是一種 List；
• GraduateStudent 繼承 Student：研究生是一種學生；
• Circle 繼承 Shape：圓形是一種形狀。

在上述關係中，子型別通常比父型別更具體。因此：

$$B \text{ 是 } A \text{ 的子型別}$$

等價於：

核心觀念

在 C 語言中，若 x、y 是指向結構的指標，*x 和 *y 分別代表兩個指標所指向的結構。執行 *x = *y 會把 y 所指結構的欄位值複製到 x 所指的結構；這不會改變指標 x 本身指向的位置。

解題方法

圖 (a) 中，x、y 分別指向不同的結構。若執行 *x = *y，應將 y 所指結構的內容複製到 x 所指結構，兩個指標仍各自指向原位置。

核心觀念

AOV（Activity-on-Vertex）網路以頂點表示活動，以有向邊表示活動間的先後關係。若有邊 $u \to v$，表示活動 $u$ 必須先於活動 $v$ 完成。

AOV 網路必須是有向無環圖（DAG），其先後關係需符合：

1. 不可自反（irreflexive）：不存在 $v \to v$，活動不能先於自己。
2. 具傳遞性（transitive）：若 $u$ 先於 $v$，且 $v$ 先於 $w$，則 $u$ 先於 $w$。
3. 不可形成有向迴圈：否則會產生互相等待，無法安排活動順序。

因此，完整的 precedence relation 通常可由圖的傳遞閉包求得。

解題方法

題目敘述指出圖所對應的網路「不是 irreflexive」，表示該關係違反不可自反條件，至少可能存在某個頂點 $v$ 使得：

$$(v,v)\in R$$

也就是存在自迴圈：

$$v\to v$$

這代表活動 $v$ 必須先於自己完成，邏輯上不成立。此圖也不是合法的 AOV 網路，無法進行有效的拓樸排序，因此不能據此建立合理的活動 precedence relation。

更一般地，若圖中存在有向迴圈：

核心觀念

這題考查 $k$ 元樹的子節點指標表示法與「未使用欄位」的計算。

• 每個節點固定配置 $k$ 個欄位，用來記錄最多 $k$ 個子節點。
• $n$ 個節點的樹恰有 $n-1$ 條邊。
• 每條邊對應一個實際使用的子節點欄位，其餘欄位皆為空欄位。

解題方法

總欄位數為：

$$nk$$

因為樹中有 $n$ 個節點，所以實際存在的子節點連結數，也就是邊數為：

$$n-1$$

因此浪費的欄位數為：

$$nk-(n-1) = nk-n+1 = n(k-1)+1$$

題目敘述為 $n(k-1)$，少計了 $1$ 個欄位。這個額外的 $1$ 來自樹的根節點：整棵樹只有 $n-1$ 條邊，而不是 $n$ 條邊。

選項分析

本題雖未列出傳統選擇題選項，但題幹本身是一個是非敘述：

本題在考驗對循環佇列 (Circular Queue) 的實作細節，包括 front 和 rear 指標的位置，以及判斷佇列空或滿的條件。

循環佇列的結構：
循環佇列通常使用一個固定大小的陣列來實作。為了區分「空」和「滿」兩種狀態（因為在某些情況下，當 front 和 rear 指向相同位置時，可能表示空或滿），我們通常需要額外的機制。常見的方法有：

1. 保留一個空位：陣列大小設為 $N+1$，但只允許使用 $N$ 個元素。當 (rear + 1) % (N+1) == front 時，佇列為滿。
2. 使用一個計數器：維護一個變數 count 來記錄佇列中的元素數量。count == 0 表示空，count == N 表示滿。
3. 使用旗標：用一個額外的布林變數來標記最後一次操作是插入還是刪除。

題目給出的陣列大小是 16，索引從 0 到 15。
陣列中已有的元素是：C, D, E, F, G, A, B。
觀察這些元素的順序，它們似乎是按照插入的順序排列在陣列中，並發生了環繞。
C -> D -> E -> F -> G -> A -> B

假設這是循環佇列的當前狀態，且這些是佇列中的所有元素。
根據循環佇列的特性，front 指標指向佇列的第一個元素，rear 指標指向佇列的最後一個元素。

從陣列的填充情況來看：

• C 在索引 0。
• D 在索引 1。
• ...
• G 在索引 4。
• A 在索引 13。
• B 在索引 14。

這表示，佇列中的元素是從索引 0 開始，然後環繞到索引 13、14。
因此：

• front 指標應該指向 C，即 front = 0。
• rear 指標應該指向 B，即 rear = 14。

判斷佇列空或滿的機制：
這裡我們需要根據 front 和 rear 的位置，以及陣列的大小來判斷。
假設陣列大小為 MAX_SIZE = 16。

1. 判斷佇列為空 (Empty)：
   在許多實作中，當 front == rear 時，佇列可能為空或為滿。
   為了區分，我們通常會採用以下規則：

   • 方法一 (保留一個空位)：如果我們保留一個空位，則當 (rear + 1) % MAX_SIZE == front 時，佇列為滿。當 front == rear 時，佇列為空。
   • 方法二 (使用計數器)：如果我們有一個 count 變數，則當 count == 0 時，佇列為空。

   在題目給定的陣列狀態下，front = 0，rear = 14。
   front != rear。
   如果我們採用方法一，rear + 1 = 15。15 % 16 = 15。
   front = 0。
   因為 15 != 0，所以不是滿。
   如果我們採用方法二，需要知道當前的元素數量。從陣列看，元素是 C, D, E, F, G, A, B，共 7 個元素。如果 count = 7，則不是空。

   最常見的判斷空的方法是：front == rear (在某些實作中，需要配合其他條件或指標設置)。
   但是，考慮到題目給出的圖示，front 和 rear 顯然不相等。
   如果我們要判斷「空」，通常是在佇列中沒有任何元素的時候。

   一個更通用的判斷空的方法是：當 front 指向的位置是無效的，或者 front 沒有指向任何有效的元素時。
   在這種情況下，如果佇列是空的，front 和 rear 可能都指向同一個初始位置（例如 -1 或 0，取決於初始化的方式）。

   另一種常見的判斷空的方法：當 front 指向的位置是陣列中不存在的元素，或者 front 指向的位置是下一個要插入的位置（這比較少見）。

   最標準的判斷空的方法是：當 front 指向的位置是沒有被元素佔據的。
   如果我們假設 front 和 rear 都始終指向陣列中的有效元素（或下一個可插入位置），則：

   • 空：通常發生在初始化後，或所有元素都被刪除後。此時 front 和 rear 可能相等（例如，都指向陣列的開頭），或者 front 指向 rear 的下一個位置。
   • 滿：當 rear 的下一個位置（循環後）就是 front 時。

   基於題目給定的陣列狀態，我們無法直接判斷「空」的狀態，因為目前佇列中有元素。
   但我們可以描述判斷空的方法：

   • 如果使用計數器 count，則 count == 0 表示空。
   • 如果沒有計數器，且 front 和 rear 都指向陣列中的有效元素，那麼通常需要額外的邏輯。一個常見的設定是：當 front 和 rear 指向同一個位置時，表示空。但這會與滿的狀態混淆。
   • 如果我們採用「保留一個空位」的策略，則當 front == rear 時，表示空。

2. 判斷佇列為滿 (Full)：

   • 方法一 (保留一個空位)：當 (rear + 1) % MAX_SIZE == front 時，佇列為滿。
     在這個例子中，front = 0, rear = 14, MAX_SIZE = 16。
     (14 + 1) % 16 = 15 % 16 = 15。
     front = 0。
     由於 15 != 0，所以根據這個陣列狀態，佇列不是滿的。
   • 方法二 (使用計數器)：當 count == MAX_SIZE 時，佇列為滿。
     在這個例子中，count = 7 (C, D, E, F, G, A, B)。
     由於 7 != 16，所以佇列不是滿的。

給定陣列狀態下的 front 和 rear 位置：
從圖示看，元素 C, D, E, F, G 似乎是連續的，從索引 0 到 4。
而 A, B 則出現在索引 13, 14。
這表明，在插入 A 和 B 之前，佇列可能包含 C, D, E, F, G。
然後，在某個時刻，front 指向 0 (C)，rear 指向 4 (G)。
接著，在環繞的情況下，插入 A 和 B。
如果佇列滿了，rear 會移動到 front-1 的位置。

核心觀念

本題考查中序表示式（infix expression）轉後序表示式（postfix expression），需掌握：

• 運算元直接輸出。

• 運算子依優先順序決定輸出時機。

• 括號只用來控制運算順序，轉換完成後不輸出。

• 本題運算優先順序為：

  $\% \;>\; * , /$

  同一層級的乘法、除法與取餘運算皆採由左至右結合。

原式可視為：

$\frac{(A\%B)*(C-D)}{E+F}$

解題方法

採用「先依運算順序建立運算樹，再以後序走訪輸出」的方法。

1. 轉換左側子表示式 $(A\%B)$

先處理 $A\%B$：

• 先輸出 $A$
• 再輸出 $B$
• 最後輸出運算子 $\%$

因此：

$A\%B \rightarrow AB\%$

2. 轉換左側子表示式 $(C-D)$

先輸出 $C$，再輸出 $D$，最後輸出減法運算子：

$C-D \rightarrow CD-$

3. 處理兩個子表示式的乘法

原式中的左側分子為：

$(A\%B)*(C-D)$

兩個子表示式分別轉為 $AB\%$ 與 $CD-$ 後，最後補上乘法運算子 $*$：

$AB\% \; CD- \; *$

即：

核心觀念

Floyd–Warshall 演算法利用動態規劃，逐步增加允許出現在路徑中間的頂點集合，以同時求出所有頂點對之間的最短路徑。

定義 $A^k(i,j)$ 為：

從頂點 $v_i$ 到頂點 $v_j$，且所有中間頂點只能取自 $\{v_1,v_2,\ldots,v_k\}$ 時的最短距離。

其中，起點 $v_i$ 與終點 $v_j$ 不算「中間頂點」。

---

解題方法與遞迴公式

考慮 $A^k(i,j)$ 的最短路徑。這條路徑對頂點 $v_k$ 有兩種情況。

情況一：最短路徑不經過 $v_k$

此時允許的中間頂點雖然增加到 $\{v_1,\ldots,v_k\}$，但實際最短路徑仍不使用 $v_k$，因此距離為：

$$A^{k-1}(i,j)$$

情況二：最短路徑經過 $v_k$

若最短路徑經過 $v_k$，可拆成兩段：

$$v_i \longrightarrow v_k \quad\text{以及}\quad v_k \longrightarrow v_j$$

兩段路徑的中間頂點都只能取自 $\{v_1,\ldots,v_{k-1}\}$，因此距離為：

$$A^{k-1}(i,k)+A^{k-1}(k,j)$$

取兩種情況中的較小值，得到 Floyd–Warshall 的遞迴關係：

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

---

初始條件

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

$$A^0(i,j)= \begin{cases} 0, & i=j,\\ w(i,j), & \text{若 }v_i\text{ 與 }v_j\text{ 有直接邊},\\ \infty, & \text{若沒有直接邊}. \end{cases}$$

其中 $w(i,j)$ 表示從 $v_i$ 到 $v_j$ 的直接邊權重。

完成 $k=1,2,\ldots,n$ 的更新後，所有頂點對的最短距離為：

$$A^n(i,j)$$

---

關鍵程式碼

使用距離矩陣 $D$ 儲存目前結果：

核心觀念

本題考查有向圖的兩種表示法：

1. Adjacency Matrix（鄰接矩陣）
2. Inversed Adjacency List（反向鄰接串列）

圖的頂點為 $V=\{0,1,2\}$，有向邊為：

$$E=\{(0,1),(0,2),(1,0),(1,2),(2,0),(2,1)\}$$

有向邊 $(u,v)$ 表示由頂點 $u$ 指向頂點 $v$。

---

解題方法

一、鄰接矩陣

鄰接矩陣 $A$ 的定義為：

$$A[i][j]= \begin{cases} 1, & \text{若存在有向邊 }(i,j)\\ 0, & \text{若不存在有向邊 }(i,j) \end{cases}$$

以列表示出發頂點、欄表示抵達頂點：

• 第 $0$ 列：有 $(0,1)$、$(0,2)$，因此為 $[0,1,1]$
• 第 $1$ 列：有 $(1,0)$、$(1,2)$，因此為 $[1,0,1]$
• 第 $2$ 列：有 $(2,0)$、$(2,1)$，因此為 $[1,1,0]$

因此鄰接矩陣為：

$$A= \begin{bmatrix} 0 & 1 & 1\\ 1 & 0 & 1\\ 1 & 1 & 0 \end{bmatrix}$$

對角線皆為 $0$，表示沒有自我迴圈，例如 $(0,0)$、$(1,1)$、$(2,2)$ 均不存在。

---

二、反向鄰接串列

反向鄰接串列記錄「哪些頂點可以直接抵達目前頂點」，也就是每個頂點的入邊來源。

對每個頂點逐一整理：

• 頂點 $0$ 的入邊為 $(1,0)$、$(2,0)$，所以反向串列為 $1\to2$

核心觀念

本題考查無向連通圖中的：

• DFS spanning tree（深度優先搜尋生成樹）
• articulation point（關節點／割點）
• biconnected component（雙連通分量）

若頂點 $v$ 被移除後，圖的連通分量數量增加，則稱 $v$ 為關節點。形式化表示為：

$$G-v \text{ 不連通}$$

在 DFS 樹中，根節點是否為關節點有一項特殊判定規則：

DFS 樹的根節點若擁有至少兩個子節點，則根節點必為關節點。

這與一般非根節點的判定條件不同；非根節點通常需要搭配 low value 判斷。

---

解題方法

設 DFS 樹的根節點為 $r$，且 $r$ 有兩個以上的子節點：

$$c_1,c_2,\ldots,c_k,\qquad k\ge 2$$

每個子節點 $c_i$ 都代表一個 DFS 子樹，記為 $T_i$。

在無向圖的 DFS 中，不同 DFS 子樹 $T_i$ 與 $T_j$ 之間不會存在連接它們的邊。原因如下：

假設 $T_i$ 與 $T_j$ 之間存在一條邊，且 $i\ne j$。當 DFS 從 $r$ 進入其中一個子樹，例如 $T_i$ 時，DFS 會沿著這條邊進入 $T_j$，因此 $T_j$ 就會被納入 $T_i$ 的 DFS 子樹中，不可能另外成為根節點 $r$ 的另一個子樹。

因此，根節點 $r$ 是連接各個 DFS 子樹的唯一樞紐：

$$T_i \longleftrightarrow r \longleftrightarrow T_j$$

當移除根節點 $r$ 後，各個子樹之間失去連接：

$$G-r=T_1\cup T_2\cup\cdots\cup T_k$$

且 $k\ge 2$，所以 $G-r$ 至少包含兩個彼此不連通的部分。也就是說：

$$G-r \text{ 不連通}$$

核心觀念

Min Heap（最小堆積）是一棵完全二元樹，且每個節點皆滿足：

$$\text{父節點值} \leq \text{子節點值}$$

陣列採用索引 $0$ 空置，因此：

• 根節點位於索引 $1$
• 索引為 $i$ 的節點，其父節點為 $\left\lfloor i/2 \right\rfloor$
• 左子節點為 $2i$
• 右子節點為 $2i+1$

題目未明確指定建堆方法，以下依照通常的「依資料順序逐筆插入 Min Heap」處理。

解題方法

每筆資料先放入堆積陣列的下一個空位置，再與父節點比較。若新節點小於父節點，便向上交換，直到符合 Min Heap 性質。

初始時索引 $0$ 保留空白。

1. 插入 $7$

$$[\,\_,7\,]$$

2. 插入 $3$

$3$ 位於索引 $2$，父節點為索引 $1$ 的 $7$。因為 $3<7$，交換：

$$[\,\_,3,7\,]$$

3. 插入 $17$

$17$ 位於索引 $3$，父節點為 $3$，不需交換：

$$[\,\_,3,7,17\,]$$

4. 插入 $10$

$10$ 位於索引 $4$，父節點為索引 $2$ 的 $7$。因為 $10>7$，不需交換：

$$[\,\_,3,7,17,10\,]$$

5. 插入 $4$

核心觀念

二元樹中的每個節點，其子節點數可能為：

• $0$：葉節點，數量為 $n_0$
• $1$：具有一個子節點，數量設為 $n_1$
• $2$：具有兩個子節點，數量為 $n_2$

題目要求建立葉節點數 $n_0$ 與度為 $2$ 的節點數 $n_2$ 之間的關係。

非空樹具有以下基本性質：

1. 若樹共有 $n$ 個節點，則邊數為 $n-1$。
2. 每個節點的子節點數總和，等於樹的邊數。

解題方法與推導

樹的總節點數為

$$n=n_0+n_1+n_2$$

由於每個度為 $1$ 的節點貢獻 $1$ 條由父節點連出的邊，每個度為 $2$ 的節點貢獻 $2$ 條邊，葉節點不貢獻邊，因此樹的邊數為

$$n_1+2n_2$$

另一方面，非空樹的邊數等於節點數減一，因此

本題在考驗對雜湊表 (Hash Table) 的處理，包括雜湊函數、開放定址法 (Open Addressing)、二次探測法 (Quadratic Probing) 以及雜湊函數的應用。

雜湊表資訊：

• Keys (鍵): 62, 104, 67, 22, 77
• 雜湊表大小 (m): 7
• 雜湊函數: $F(x) = x \pmod{7}$
• 開放定址法 (Open Addressing)
• 二次探測法 (Quadratic Probing)：$h(k, n) = (h_0(k) + n^2) \pmod m$，其中 $h_0(k) = F(k)$。
  • 題目中給的公式是 $i = (F(x) + n^2) \pmod m$，這裡的 $i$ 是探測的索引，而 $F(x)$ 是初始雜湊值。
  • 所以，探測序列是：
    • 第一次嘗試 (n=0): $(F(x) + 0^2) \pmod m = F(x) \pmod m$
    • 第二次嘗試 (n=1): $(F(x) + 1^2) \pmod m$
    • 第三次嘗試 (n=2): $(F(x) + 2^2) \pmod m$
    • 第四次嘗試 (n=3): $(F(x) + 3^2) \pmod m$
    • 依此類推。

插入過程：
雜湊表大小 $m=7$，索引為 0, 1, 2, 3, 4, 5, 6。
初始狀態：所有槽都是空的 _。
[_, _, _, _, _, _, _]

1. 插入 62：

   • $F(62) = 62 \pmod 7 = 6$。
   • 索引 6 是空的。
   • 雜湊表：[_, _, _, _, _, _, 62]

2. 插入 104：

   • $F(104) = 104 \pmod 7$。
     $104 = 14 \times 7 + 6$。所以 $104 \pmod 7 = 6$。
   • 索引 6 已經被 62 佔用。發生碰撞。
   • 使用二次探測法：
     • $n=0$: $(6 + 0^2) \pmod 7 = 6$ (已佔用)

本題在考驗對 Augumented Binary Search Tree (增強式二元搜尋樹) 的理解，特別是如何利用額外資訊來快速查找第 k 小的元素，以及在給定的樹結構中進行查找的步驟。

增強式二元搜尋樹 (Augmented BST)：
為了能夠快速查找第 $k$ 小的元素（按大小順序排序），我們可以在 BST 的每個節點中額外儲存其子樹的大小（或節點數）。
通常，每個節點會儲存：

1. 節點的值。
2. 指向左子節點的指標。
3. 指向右子節點的指標。
4. 子樹的大小 (subtree size)：表示以該節點為根的子樹中包含的總節點數（包括該節點本身）。

查找第 $k$ 小元素：
假設我們要在 BST 中查找第 $k$ 小的元素。
從根節點開始：

1. 計算左子樹的大小 (left_subtree_size)。如果左子節點存在，則 left_subtree_size 是左子節點儲存的子樹大小。如果左子節點不存在，則 left_subtree_size = 0。
2. 令 rank = left_subtree_size + 1。這個 rank 表示當前節點在整個 BST 中（如果從根開始查找）的排名。
3. 比較：
   • 如果 $k == rank$，則當前節點就是我們要找的第 $k$ 小元素。
   • 如果 $k < rank$，則第 $k$ 小的元素一定在左子樹中。我們繼續在左子樹中查找第 $k$ 小的元素。
   • 如果 $k > rank$，則第 $k$ 小的元素一定在右子樹中。我們需要查找右子樹中的第 $(k - rank)$ 小的元素（因為我們已經排除了左子樹的 rank 個元素）。

給定的 BST 結構：
根節點是 8。
左子樹：

• 根: 3
  • 左子節點: 2 (葉節點)
  • 右子節點: 6
    • 左子節點: 4 (葉節點)
    • 右子節點: 10 (葉節點)
      右子樹：
• 根: 12
  • 左子節點: (無)
  • 右子節點: 14
    • 左子節點: 13 (葉節點)
    • 右子節點: (無)

計算每個節點的子樹大小 (Subtree Size)：
我們從葉節點開始向上計算。

• 葉節點 (大小為 1)：2, 4, 10, 13。
• 節點 6：左子節點 4 (大小 1)，右子節點 10 (大小 1)。總大小 = 1 (自身) + 1 + 1 = 3。
• 節點 3：左子節點 2 (大小 1)，右子節點 6 (大小 3)。總大小 = 1 (自身) + 1 + 3 = 5。
• 節點 14：左子節點 13 (大小 1)。總大小 = 1 (自身) + 1 = 2。
• 節點 12：左子節點 (無, 大小 0)，右子節點 14 (大小 2)。總大小 = 1 (自身) + 0 + 2 = 3。
• 節點 8 (根)：左子節點 3 (大小 5)，右子節點 12 (大小 3)。總大小 = 1 (自身) + 5 + 3 = 9。

更新後的 BST 結構 (節點值, 子樹大小)：

• 2: (2, 1)
• 4: (4, 1)
• 10: (10, 1)
• 13: (13, 1)
• 6: (6, 3)
• 3: (3, 5)
• 14: (14, 2)
• 12: (12, 3)
• 8: (8, 9)

查找第 4 小的元素：
題目要求查找「4-th smallest values in the right tree」。
這裡的「right tree」可能指：

1. 以根節點 8 的右子節點 12 為根的子樹。
2. 或者，指的是在整個 BST 中，根據查找第 4 小元素過程中，我們進入右子樹的步驟。

根據上下文，「find the 4-th smallest values in the right tree」更可能指以節點 12 為根的子樹。
讓我們首先在這個子樹中查找第 4 小的元素。
這個子樹包含的節點是：12, 13, 14。
它們按大小排序是：13, 14, 12。
這個子樹的節點數是 3。
所以，在這個子樹中，不可能找到第 4 小的元素。

重新解讀題目：
「Please show the number of comparisons before we can find the 4-th smallest values in the right tree」
這裡的「right tree」很可能指的是在查找第 4 小元素過程中，我們進入的右子樹。

讓我們在整個 BST 中查找第 4 小的元素，並記錄過程。
目標：查找第 4 小的元素 ($k=4$)。
起始節點：根節點 8。

步驟 1：節點 8

• 左子樹大小 (節點 3 的大小)：5。
• rank = left_subtree_size + 1 = 5 + 1 = 6。
• 我們需要找第 4 小的元素 ($k=4$)。
• 因為 $k=4 < rank=6$，所以第 4 小的元素在左子樹中。
• 比較 1：比較 $k$ 和 rank (4 vs 6)。
• 繼續在左子樹（以 3 為根）中查找第 4 小的元素。

步驟 2：節點 3

• 左子樹大小 (節點 2 的大小)：1。
• rank = left_subtree_size + 1 = 1 + 1 = 2。
• 我們需要找第 4 小的元素 ($k=4$)。
• 因為 $k=4 > rank=2$，所以第 4 小的元素在右子樹中。
• 我們需要查找右子樹（以 6 為根）中的第 $(k - rank) = (4 - 2) = 2$ 小的元素。
• 比較 2：比較 $k$ 和 rank (4 vs 2)。
• 進入右子樹（以 6 為根），查找第 2 小的元素。

步驟 3：節點 6

• 左子樹大小 (節點 4 的大小)：1。
• rank = left_subtree_size + 1 = 1 + 1 = 2。
• 我們需要找第 2 小的元素 ($k=2$)。
• 因為 $k=2 == rank=2$，所以當前節點 6 就是我們要找的第 2 小的元素 (在這個子問題範圍內)。
• 比較 3：比較 $k$ 和 rank (2 vs 2)。
• 找到第 2 小的元素是 6。

結果：
在整個 BST 中，第 4 小的元素是 6。
查找過程中，我們進行了 3 次比較。

題目問題的解讀：
「Please show the number of comparisons before we can find the 4-th smallest values in the right tree」
這個問題可以有兩種解釋：

1. 解釋 A：在整個 BST 中查找第 4 小的元素。在查找過程中，我們進入了哪個「右子樹」？

   • 從節點 8 進入左子樹。
   • 從節點 3 進入右子樹（以 6 為根）。
   • 在節點 6 找到答案。
     在這個過程中，我們進入的「右子樹」是以 6 為根的子樹。
     在這個子樹中，我們進行了多少比較？
     在這個子樹 (節點 6, 4, 10) 中，查找第 2 小的元素（因為 $k=4$, $rank=2$, $k-rank=2$）。
   • 節點 6：左子樹大小 1 (節點 4)。$rank = 1+1=2$。
   • $k=2$, $rank=2$。相等。
   • 比較 1 次。找到節點 6。
     如果「right tree」指的是以 6 為根的子樹，那麼比較次數是 1。

2. 解釋 B：在整個 BST 中查找第 4 小的元素，總共做了多少次比較？
   我們做了 3 次比較（8 vs 6, 4 vs 2, 2 vs 2）。

3. 解釋 C：題目可能問的是，如果我們只考慮以 12 為根的右子樹，以及這個子樹中的元素 (12, 13, 14)，要找到第 4 小的元素，需要多少比較？
   如前所述，這個子樹只有 3 個節點，不可能找到第 4 小的。這個解釋不太可能。

最合理的解釋：
題目要求：
a) 查找第 4 小的元素。
b) 顯示「number of comparisons」
c) 顯示「in the right tree」

這句話「in the right tree」比較模糊。
它可能是指：

• 在整個查找過程中，我們第一次進入右子樹時，該子樹的根是什麼？
• 在這個右子樹中，我們進行了多少次比較？

核心觀念

動態規劃（Dynamic Programming, DP）適用於能將原問題拆成較小子問題，並利用子問題結果建構原問題答案的最佳化問題。通常需要具備兩項特性：

1. 最佳子結構（optimal substructure）：原問題的最佳解，可以由其子問題的最佳解組合而成。換言之，若要得到整體最佳解，相關子問題的解也必須是最佳的。
2. 重疊子問題（overlapping subproblems）：遞迴拆解問題時，會重複遇到相同的子問題。將子問題答案記錄並重複使用，可以避免重複計算。

解題方法

核心觀念

本題考查動態規劃與最優子結構。令 $d(v)$ 表示從起點 $S$ 到節點 $v$ 的最低成本，$\operatorname{cost}(u,v)$ 表示經過邊 $(u,v)$ 的成本。每個節點的最低成本，取決於它能到達的前驅節點之最低成本。

解題方法

圖（b）的座標軸為 $X$ 向右、$Y$ 向上，起點 $S=(0,0)$，目標 $T=(m,n)$。單調路徑只能向右或向上前進，因此內部節點 $g=(x,y)$ 的候選前驅是左側的 $g_1=(x-1,y)$ 與下側的 $g_2=(x,y-1)$；底邊與左邊界各只有一個可用前驅。

先沿底邊及左邊界累積成本：

$$d(x,0)=d(x-1,0)+\operatorname{cost}\big((x-1,0),(x,0)\big)$$ $$d(0,y)=d(0,y-1)+\operatorname{cost}\big((0,y-1),(0,y)\big)$$

對內部節點，分別計算從左側與下側前進的成本，選擇較小者，並記錄對應前驅：

$$d(x,y)=\min\left\{ d(g_1)+\operatorname{cost}(g_1,g),\ d(g_2)+\operatorname{cost}(g_2,g) \right\}$$

填入答案

1. $d(G_1)+\operatorname{cost}(G_1,G)$
2. $d(g_1)+\operatorname{cost}(g_1,g)<d(g_2)+\operatorname{cost}(g_2,g)$
3. $d(g_1)+\operatorname{cost}(g_1,g)$
4. $g_1$
5. $d(g_2)+\operatorname{cost}(g_2,g)$

若兩側成本相同，任選一側作為前驅皆可；上述條件在相同時會走 else，記錄 $g_2$。

偽程式碼