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

核心觀念

本題考查 C 語言中：

1. 陣列總大小的計算。
2. sizeof 運算子的意義。
3. float 所占用的記憶體空間。

宣告如下：

float array[5];

代表 array 是一個含有 5 個 float 元素的陣列。因此：

$$\text{sizeof(array)} = 5 \times \text{sizeof(float)}$$

一般考試與常見系統環境中，sizeof(float) = 4 bytes，所以：

$$\text{sizeof(array)} = 5 \times 4 = 20\text{ bytes}$$

解題方法

sizeof(array) 計算的是整個陣列的大小，不是陣列元素個數。

float array[5];
printf("%d", sizeof(array));

計算步驟為：

$$\begin{aligned} \text{元素個數} &= 5 \\ \text{每個元素大小} &= 4\text{ bytes} \\ \text{陣列總大小} &= 5 \times 4 = 20\text{ bytes} \end{aligned}$$

因此題目預期的輸出為：

20

sizeof 的結果是位元組數，不是元素數量。

選項分析

• (A) 5：錯誤。
  5 是陣列的元素個數，並非整個陣列所占的位元組數。

核心觀念

本題考查單向鏈結串列在尾端插入節點的指標更新方式。

鏈結串列節點可表示為：

struct node {
    int data;
    struct node *link;
};

其中：

• link 指向下一個節點。
• IPtr 指向目前串列的最後一個節點。
• 目前最後一個節點的 link 應為 NULL。
• nPtr 指向要加入的新節點。

插入前的結構為：

$$\text{前一節點} \longrightarrow IPtr \longrightarrow NULL$$

插入後應變成：

$$\text{前一節點} \longrightarrow IPtr \longrightarrow nPtr \longrightarrow NULL$$

因此必須完成兩件事：

1. 將原本最後節點的 link 指向新節點。
2. 將 IPtr 更新為新節點，使其繼續代表最後節點。

解題方法

依照插入前後的鏈結關係，正確指標操作為：

IPtr->link = nPtr;
IPtr = nPtr;

第一行把原本最後節點連到新節點；第二行將尾端指標移到新節點。

嚴格而言，新節點成為最後節點後，其 link 應為 NULL：

nPtr->link = NULL;

若配置新節點時已經將 link 初始化為 NULL，則題目選項中的兩行程式碼已足以完成尾端插入。

選項分析

(A) IPtr = nPtr; nPtr->link = IPtr;

第一行先將 IPtr 改為 nPtr，原本最後節點的位址便不再能透過 IPtr 存取。

第二行等同於：

nPtr->link = nPtr;

核心觀念

Associative array（關聯陣列）是由「鍵（key）—值（value）」所組成的集合，也稱為 map 或 dictionary。每個鍵通常對應一個值，常見操作包括：

• 依鍵查詢值：Lookup
• 新增鍵值配對：Insert 或 Put
• 修改既有鍵所對應的值：Re-assign 或 Update
• 刪除鍵值配對：Delete

關聯陣列是以「鍵」作為操作依據，沒有堆疊的頂端，也不以先進後出（LIFO）為基本結構。

解題方法

逐一檢查各選項是否符合關聯陣列的基本操作：

1. 若操作是針對指定的 key，通常屬於關聯陣列操作。
2. 若操作依賴「頂端（top）」並具有堆疊的先進後出特性，則屬於 stack 的操作，不是關聯陣列的通用操作。

因此，尋找描述「加入集合頂端」的選項即可判斷答案。

選項分析

(A) Push：將新值加入集合頂端

錯誤。Push 是堆疊（stack）的典型操作，意義是將元素加入堆疊頂端，並配合 Pop 實現先進後出。

關聯陣列新增資料時，必須指定鍵，例如：

$$A[\text{studentID}] = \text{studentName}$$

它關心的是「值要綁定到哪一個 key」，而不是加入集合的頂端。關聯陣列也不必然具有 top 的概念，因此 Push 不是其通用操作。

(B) Lookup：尋找與指定 key 綁定的值

正確。查詢是關聯陣列的核心操作。例如：

核心觀念

雜湊函數（hash function）是將鍵值 $k$ 映射至雜湊表索引的函數：

$$h(k)\in\{0,1,\ldots,m-1\}$$

其中 $m$ 為雜湊表大小。

良好的雜湊函數通常具備以下特性：

1. 確定性（deterministic）：相同輸入必須產生相同輸出。
2. 均勻分布（uniform distribution）：將鍵值平均分散至各索引位置。
3. 低碰撞率（low collision rate）：盡量避免不同鍵值映射至相同位置。
4. 計算快速：雜湊函數應能快速計算，避免增加查找成本。

碰撞（collision）是指不同鍵值 $k_1\ne k_2$ 卻滿足：

$$h(k_1)=h(k_2)$$

解題方法

本題詢問「不屬於良好雜湊函數的特性」。逐一比對選項與上述定義即可。

判斷關鍵是：雜湊函數必須是確定性的，因此同一個輸入每次都應得到相同的雜湊值。若相同輸入產生不同結果，後續查找時便無法確定資料所在的位置。

選項分析

(A) able to avoid collisions

這是良好雜湊函數應具備的特性。實務上雜湊函數應盡量降低碰撞發生的機率。

嚴格而言，當鍵值範圍大於雜湊表大小時，依據鴿籠原理，不可能保證完全沒有碰撞。因此此選項的「avoid」應理解為「盡量避免、降低碰撞」，而非絕對保證零碰撞。

核心觀念

AVL tree 是一種「自我平衡的二元搜尋樹」（self-balancing binary search tree），必須同時符合：

1. 左子樹所有鍵值小於根節點。
2. 右子樹所有鍵值大於根節點。
3. 每個節點的左右子樹高度差至多為 $1$。

平衡因子定義為：

$$BF(v)=h(\text{left subtree})-h(\text{right subtree})$$

AVL tree 必須滿足：

$$|BF(v)|\leq 1$$

插入或刪除節點後，若某節點的平衡因子變成 $2$ 或 $-2$，就必須透過旋轉恢復平衡。常見旋轉包括 LL、RR、LR、RL 四種情況。

解題方法

本題直接對照 AVL tree 的定義與基本性質：

• 是否為二元搜尋樹？
• 左右子樹高度差的正確上限是多少？
• 是否利用旋轉維持平衡？
• 搜尋與走訪方式是否沿用二元搜尋樹？

題幹未說明是否將「at most 2」視為 AVL 平衡條件的精確上限；依一般考試命題意旨，應將它理解為「AVL tree 允許左右子樹高度差達到 $2$」，此說法違反標準定義。

選項分析

(A) 正確

AVL tree 是二元搜尋樹的特例，因此仍具備二元搜尋樹的排序性質：

• 左子樹鍵值小於節點鍵值。
• 右子樹鍵值大於節點鍵值。

所以此敘述正確。

(B) 錯誤

AVL tree 要求每個節點左右子樹高度差至多為 $1$，不是 $2$。

例如某節點的左右子樹高度分別為 $3$ 與 $1$，則：

核心觀念

本題考查「哪些演算法屬於 quicksort 的變形」。標準 quicksort 的核心流程為：

1. 選定樞紐值（pivot）。
2. 以分割（partition）將資料分成較小、相等、較大的部分。
3. 對各部分遞迴排序。

其平均時間複雜度為

$$T(n)=2T(n/2)+\Theta(n)=\Theta(n\log n)$$

若每次分割都極度不平衡，則為

$$T(n)=T(n-1)+\Theta(n)=\Theta(n^2)$$

quicksort 的變形可以改變儲存方式、鍵值處理方式或分割策略，但仍保留遞迴分割的基本精神。

解題方法

逐一判斷各選項是否仍以 quicksort 的「分割與遞迴」為主要架構：

• 若只是改變外部儲存方式，仍可屬於 quicksort 變形。
• 若以數字位數或字元進行遞迴分割，也可屬於 radix quicksort。
• 若改用間隔序列進行插入排序，則屬於另一種獨立的排序法。

選項分析

(A) Shell quicksort

此名稱不是一般資料結構教材中常見的 quicksort 變形。常見的正式名稱是 Shell sort，其核心是：

• 選定遞減的間隔序列 $h$。
• 對相距 $h$ 的元素分組。
• 對各組執行插入排序。
• 逐步縮小 $h$，最後以 $h=1$ 完成排序。

Shell sort 不選擇 pivot，也不進行 quicksort 式的 partition，因此它是獨立的排序演算法，而非 quicksort 的常見變形。

(B) External quicksort

概念說明

• Dijkstra：單源最短路，權重需非負。
• Floyd‑Warshall：全源最短路，適用任意權重（含負但無負環）。
• Viterbi：在隱馬可夫模型中，以對數機率求最大路徑，屬「最長」或「最大」路徑問題，並非傳統的最短路問題。

核心觀念

本題比較陣列（array）與鏈結串列（linked list）的記憶體配置、存取方式及結構特性：

• 陣列通常將元素儲存在連續記憶體空間。
• 陣列可透過索引直接存取，隨機存取時間為 $O(1)$。
• 鏈結串列由多個節點組成，每個節點包含資料部分與指向下一節點的連結。
• 鏈結串列的節點不要求配置在連續記憶體空間。

解題方法

判斷每個選項是否符合陣列與鏈結串列的基本定義。關鍵區分如下：

陣列第 $i$ 個元素的位置可由基底位址直接計算：

$$\text{Address}(A[i])=\text{Base}+(i-\text{LowerBound})\times \text{ElementSize}$$

因此陣列能以索引直接存取，時間複雜度為 $O(1)$。

鏈結串列則必須從首節點開始，沿著連結逐一尋找目標節點；若要存取第 $i$ 個節點，通常需要 $O(i)$，最壞情況為 $O(n)$。

選項分析

(A) Arrays are dense and static data structure.

正確。傳統陣列屬於密集（dense）資料結構，元素通常依序存放於連續記憶體位置；陣列大小通常在建立時決定，屬於靜態（static）資料結構。

雖然實務上有 dynamic array，可在容量不足時重新配置空間，但資料結構基本定義中的 array 通常指固定大小的陣列。

(B) Arrays are usually more efficient to access than linked lists.

核心觀念

本題比較兩種字串索引結構：

• 雜湊表（hash table）：利用雜湊函數將鍵值映射到陣列索引，平均查找、插入與刪除時間通常為 $O(1)$；若雜湊鍵本身是長度為 $L$ 的字串，計算雜湊值至少需要處理字串內容，因此實際成本通常為 $O(L)$。
• Trie（字典樹、前綴樹）：依照字串的字元逐層建立樹。長度為 $L$ 的字串，其查找與插入時間通常為 $O(L)$，且不同字串的共同前綴可以共用節點。

Trie 的主要優點是：

1. 不會發生雜湊碰撞。
2. 適合前綴查詢，例如找出所有以 comp 開頭的字串。
3. 字串越長、共同前綴越多時，共用前綴的優勢越明顯。

Trie 的主要缺點是需要為節點配置子節點指標或子節點表，記憶體消耗通常很大。

---

解題方法

判斷每個敘述是否符合 Trie 與雜湊表的定義及典型特性，特別檢查：

1. Trie 的結構定義是否正確。
2. 插入與查找的時間複雜度。
3. 長字串與共同前綴對效能的影響。
4. 兩者的記憶體使用方式。

其中，若敘述聲稱 Trie 一定或通常比雜湊表節省記憶體，便要特別注意，因為 Trie 需要額外儲存大量節點及子節點連結。

---

選項分析

(A) Tries are ordered prefix trees used to store strings.

正確。

Trie 是一種依照字串前綴組織資料的樹狀結構。每一條從根節點到某個終止節點的路徑，代表一個字串；共用前綴的字串會共用相同的前段路徑。

例如儲存 cat 與 car 時，兩者會共用 c → a，只在最後一個字元分岔。因此 Trie 確實是用來儲存字串的前綴樹，也可視為依字元順序排列的樹狀索引。

---

(B) Tries are usually faster on average at insertion than full hash tables.

正確。

Trie 插入長度為 $L$ 的字串時，只需沿著字串的 $L$ 個字元逐層查找或建立節點，時間複雜度為：

$$T_{\text{trie insert}} = O(L)$$

雜湊表插入字串時，必須先計算雜湊值。對長度為 $L$ 的字串，雜湊值的計算通常也需要掃描字串，因此成本約為：

$$T_{\text{hash}} = O(L)$$

核心觀念

本題考查圖形（graph）的常見表示法。圖形可表示為：

$$G=(V,E)$$

其中 $V$ 是頂點集合，$E$ 是邊集合。常見的圖形表示方式包括：

• Adjacency list：鄰接串列
• Adjacency matrix：鄰接矩陣
• Incidence matrix／list：關聯矩陣／關聯串列

判斷選項是否為圖形表示法，重點在於該資料結構是否用來描述「頂點與邊之間的連接關係」。

解題方法

逐一檢查各選項的用途：

1. 是否記錄頂點與頂點之間的相鄰關係。
2. 是否記錄頂點與邊之間的關聯關係。
3. 若用途是分類模型的結果統計，而非圖形結構，則不是圖形表示法。

因此，選項中若資料結構與圖形的頂點、邊連接關係無關，即為答案。

選項分析

(A) Adjacency list

鄰接串列為每個頂點建立一個串列，記錄與該頂點直接相連的其他頂點。

例如，若無向圖中有邊 $(u,v)$，則：

• $v$ 會出現在 $u$ 的鄰接串列中；
• $u$ 會出現在 $v$ 的鄰接串列中。

若圖形有 $|V|$ 個頂點與 $|E|$ 條邊，鄰接串列的空間複雜度通常為：

$$O(|V|+|E|)$$

它特別適合稀疏圖，因此是圖形的常見表示法。本選項正確描述圖形表示方式。

(B) Adjacency matrix

鄰接矩陣使用一個 $|V|\times |V|$ 的矩陣表示頂點間是否相鄰。令矩陣為 $A$，則：

$$A_{ij}= \begin{cases} 1, & \text{若頂點 } i \text{ 與 } j \text{ 之間有邊}\\ 0, & \text{否則} \end{cases}$$

加權圖則可在 $A_{ij}$ 中儲存邊的權重。

鄰接矩陣的空間複雜度為：

$$O(|V|^2)$$

核心觀念

本題考查圖論中幾種圖形的基本定義。設圖為 $G=(V,E)$，其中 $V$ 為頂點集合，$E$ 為邊集合。判斷時必須區分：

• 二分圖（bipartite graph）
• 稀疏圖（sparse graph）
• 對偶圖（dual graph）
• 圓圖（circular graph）
• 完全圖（complete graph）

解題方法

逐一比對各選項與標準定義即可。題目問「TRUE」，只要找出完全符合定義的選項；若選項把某種圖的定義偷換成另一種圖，便可判定錯誤。

選項分析

(A) 正確

二分圖是指頂點集合可以分割為兩個互斥且各自獨立的集合 $U$ 與 $V$，滿足：

$$U\cap V=\varnothing,\qquad U\cup V=V(G)$$

其中「獨立集合」表示同一集合內的任意兩個頂點之間沒有邊。因此，二分圖的每一條邊都必須連接 $U$ 中的頂點與 $V$ 中的頂點：

$$\forall (u,v)\in E,\quad u\in U,\ v\in V$$

選項 (A) 的敘述正好符合二分圖定義，因此正確。

補充：二分圖不要求 $U$ 與 $V$ 之間的每一對頂點都有邊；若每個 $u\in U$ 都與每個 $v\in V$ 相連，才是完全二分圖 $K_{|U|,|V|}$。

(B) 錯誤

稀疏圖是指邊數相對較少的圖，通常可概念性表示為：

$$|E|\ll |V|^2$$

核心觀念

本題比較兩種重複執行方式：

• 迭代（iteration）：利用 for、while 等迴圈，透過變數更新持續執行。
• 遞迴（recursion）：函式直接或間接呼叫自己，將原問題轉換成規模更小的同類問題。

正確的遞迴通常包含兩部分：

1. 基底條件（base case）：停止遞迴。
2. 遞迴條件（recursive case）：將問題化為較小的子問題。

遞迴每呼叫一次函式，通常都會在呼叫堆疊（call stack）中建立新的執行環境，因此會有額外的函式呼叫成本與堆疊空間需求。

---

解題方法

判斷每個選項是否符合迭代與遞迴的基本特性，特別注意「執行資源」與「執行速度」的比較：

• 遞迴通常需要額外的呼叫堆疊。
• 迭代通常不需為每一層建立函式呼叫框架。
• 兩者若缺乏有效的終止條件，都可能無限執行。

因此，宣稱「遞迴比等價的函式呼叫消耗更少資源」的選項，與一般遞迴執行模型不符。

---

選項分析

(A) 正確

遞迴常將一個較大的問題拆成數個規模較小、結構相同的子問題，待子問題求解後，再將結果合併或累積。

例如階乘：

$$n! = n \times (n-1)!$$

並以

$$0! = 1$$

作為基底條件。此時每次遞迴都將問題規模由 $n$ 降為 $n-1$，最後將各層結果乘回來。

遞迴不一定都需要明確的「合併」動作，但「拆成較小子問題並取得結果」是遞迴解題的典型概念，因此本選項正確。

---

(B) 錯誤

遞迴通常會消耗較多執行資源，而不是較少。每次遞迴呼叫通常需要：

• 儲存參數與區域變數；
• 儲存返回位址；
• 建立新的 stack frame；
• 執行函式呼叫與返回的額外處理。

例如計算階乘：

factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)

核心觀念

本題考查四種演算法的基本特性，重點在於區分「區域最佳解」與「全域最佳解」。

若目標函數為 $f(x)$，鄰近解集合為 $N(x)$：

• 區域最佳解（local optimum）：在鄰近解中沒有更好的解，例如最大化問題滿足
  $f(x^*)\geq f(y),\quad \forall y\in N(x^*)$
• 全域最佳解（global optimum）：在所有可行解中都是最佳解，例如最大化問題滿足
  $f(x^*)\geq f(y),\quad \forall y\in S$
  其中 $S$ 為全部可行解。

區域最佳解不一定是全域最佳解。Hill climbing 特別容易停在區域最佳解，因此不能一般性保證取得全域最佳解。

解題方法

逐一判斷各演算法的「保證程度」：

1. Greedy 每一步選擇當下看來最好的方案，屬於區域性選擇。
2. Brute-force 枚舉所有候選解，再比較其結果；若搜尋空間有限且評估正確，能保證找到最佳解。
3. Backtracking 透過逐步嘗試與違反條件即回溯，常用於限制滿足問題。
4. Hill climbing 只接受能改善目前解的鄰近狀態，可能被較差的區域最佳解困住。

因此，聲稱 Hill climbing 必定收斂到全域最大值是錯誤的。

選項分析

(A) Greedy algorithms are able to find local optimal solutions.

正確。Greedy algorithm 每一步都選擇目前階段看來最有利的選項，也就是當下的區域最佳選擇。

不過，Greedy 的局部選擇不代表最後一定得到全域最佳解。只有在問題具備適當的 greedy-choice property 與 optimal substructure 時，Greedy 才能保證全域最佳解。本選項只說能找到區域最佳解，敘述成立。

(B) Brute-force algorithms are guaranteed to find the best solution.

正確。Brute-force algorithm 會系統性枚舉所有可能候選解，計算每個候選解的結果，最後選出最佳者。若可行解集合為有限集合 $S$，則可透過

核心觀念

Merge sort（合併排序）具有以下特性：

1. 採用分治法，將陣列分成兩半，遞迴排序後再合併。
2. 合併兩個已排序序列時，每次比較兩序列目前最前面的元素，選出較小者放入結果序列。
3. 若相等時優先取左側序列元素，便能維持相同鍵值元素的原有相對順序，因此是穩定排序。
4. 時間複雜度為：

$$T(n)=2T\left(\frac{n}{2}\right)+\Theta(n)$$

其中 $\Theta(n)$ 是合併階段的成本，因此：

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

最壞情況自然也是 $O(n\log n)$。

解題方法

判斷各選項是否符合 merge sort 的定義與性質。特別注意「每次從未排序陣列中找出最小值，放到陣列前端」是另一種排序法的典型描述。

選項分析

(A) 錯誤

此敘述描述的是 selection sort（選擇排序）：

• 在未排序區域中尋找最小元素；
• 將該元素放到目前應排列的位置；
• 重複此程序，直到整個陣列排序完成。

Merge sort 不會在整個未排序陣列中逐次尋找全域最小值。它先將陣列切分成較小區段，分別排序後，再於合併階段比較兩個已排序子序列的目前元素。因此，(A) 並非 merge sort 的特性。

核心觀念

本題考查程式執行時的「子程序呼叫堆疊」（call stack）與堆疊的後進先出（LIFO, Last In First Out）特性。

當一個子程序被呼叫時，系統會建立一筆啟動記錄（activation record），通常包含：

• 參數
• 區域變數
• 返回位址
• 暫存器或執行狀態

子程序結束時，必須先返回「最近一次呼叫它的地方」。因此，子程序的呼叫與返回順序正好相反。

例如：

$$\text{main} \rightarrow A \rightarrow B$$

執行 $B$ 時，活躍中的子程序可視為：

$$[\text{main}, A, B]$$

$B$ 必須先結束並返回，接著才是 $A$，最後才回到 $\text{main}$。這正是堆疊的 LIFO 行為。

解題方法

判斷關鍵在於「active subroutines」代表目前已被呼叫、但尚未完成的巢狀子程序。

• 呼叫子程序：將新的啟動記錄 push 至堆疊頂端。
• 子程序返回：將最上層的啟動記錄 pop 出來。
• 最新呼叫的子程序最先返回。

因此，最適合儲存活躍子程序資訊的資料結構是堆疊。

選項分析

(A) Stack：正確

核心觀念

二元搜尋法（binary search）適用於「已排序」的資料。每次比較中間元素後，便能排除一半不可能的搜尋範圍。

若資料筆數為 $n$，經過 $k$ 次搜尋後，剩餘範圍約為：

$$\frac{n}{2^k}$$

當剩餘範圍縮小至 $1$ 筆時：

$$\frac{n}{2^k}\leq 1 \Rightarrow 2^k\geq n \Rightarrow k\geq \log_2 n$$

因此，最壞情況下需要進行 $O(\log n)$ 次比較。

解題方法

標準二元搜尋法每一輪都執行以下工作：

1. 取得中間元素。
2. 將搜尋值與中間元素比較。
3. 保留左半部或右半部繼續搜尋。

取得中間元素與一次比較皆視為 $O(1)$，而搜尋範圍每次縮小為原來的一半，因此其時間複雜度可表示為：

$$T(n)=T\left(\frac{n}{2}\right)+O(1)$$

展開後：

$$T(n)=T\left(\frac{n}{2^k}\right)+kO(1)$$

當 $\frac{n}{2^k}=1$ 時，$k=\log_2 n$，所以：

核心觀念

二元搜尋樹（Binary Search Tree, BST）搜尋時，每次比較目標值與目前節點：

• 相等：找到元素。
• 目標值較小：往左子樹搜尋。
• 目標值較大：往右子樹搜尋。

因此，所需比較次數等於搜尋路徑上所訪問的節點數。平衡二元搜尋樹的左右子樹高度大致相同，搜尋高度為：

$$O(\log_2 n)$$

其中 $n$ 為節點數。

解題方法

以根節點為第 $1$ 層，具有 $h$ 層的二元樹最多包含：

$$1+2+4+\cdots+2^{h-1}=2^h-1$$

本題有 $n=2000$ 個元素：

$$2^{10}-1=1023<2000$$ $$2^{11}-1=2047\geq 2000$$

所以，2000 個元素的平衡 BST 需要約 $11$ 層。搜尋最深層元素時，會逐層比較，共需：

$$11\text{ 次比較}$$

也可直接計算：

$$\left\lceil\log_2(2000+1)\right\rceil = \left\lceil\log_2 2001\right\rceil = 11$$

因此正確選項為 (B) 11。

核心觀念

鄰接矩陣（adjacency matrix）以矩陣的「列」與「欄」分別代表圖中的頂點。若圖有 $n$ 個頂點，鄰接矩陣的大小為：

$$n \times n$$

其中第 $i$ 列、第 $j$ 欄的元素，表示頂點 $v_i$ 與 $v_j$ 之間是否存在邊。

解題方法

本題有 $10$ 個頂點，因此鄰接矩陣具有 $10$ 列與 $10$ 欄：

$$10 \times 10 = 100$$

所以矩陣共有 $100$ 個元素／儲存格。

即使是無向圖，矩陣內容會呈現對稱性；即使不允許自我迴路，對角線位置仍然存在，只是通常填入 $0$。因此儲存格數量仍是 $10^2$。

選項分析

• (A) 10：錯誤。
  $10$ 是頂點數量，不是鄰接矩陣的元素數量。

核心觀念

本題考查：

• C 語言字元陣列以 '\0' 作為字串結尾。
• 陣列參數 char str[] 傳入函式後，實際上會視為字元指標。
• ++str 只會讓目前函式中的指標移到下一個字元，不會修改陣列內容。
• 遞迴呼叫後才執行 printf，屬於「回溯階段」輸出，因此會得到反向順序。

解題方法

函式的關鍵流程如下：

void fun1(char str[]) {
    char c = str[0];

    if (c != '\0') {
        fun1(++str);
        printf("%c", c);
    }
}

假設輸入字串為 "CAT"：

1. 第一次呼叫：c = 'C'，遞迴處理 "AT"。
2. 第二次呼叫：c = 'A'，遞迴處理 "T"。
3. 第三次呼叫：c = 'T'，遞迴處理空字串。
4. 此時 str[0] == '\0'，遞迴停止。
5. 開始返回上一層，依序執行 printf：

$$T \rightarrow A \rightarrow C$$

因此輸出為：

TAC

++str 改變的是每一層函式中的區域指標位置，並未交換或改寫字元陣列中的內容，所以原陣列仍為：

核心觀念

本題考查演算法的最壞情況時間複雜度與漸近成長率。

當輸入規模為 $n$ 時，時間複雜度主要比較當 $n$ 很大時，執行時間的成長速度：

$$O(\log n) < O(n) < O(n\log n) < O(n^2)$$

成長率越慢，代表在最壞情況下，輸入規模增加時所需的運算量增加得越少，演算法效率越高。

其中：

• $O(\log n)$：對數成長
• $O(n)$：線性成長
• $O(n\log n)$：線性乘以對數成長
• $O(n^2)$：平方成長

解題方法

比較各選項在 $n$ 趨近於無限大時的成長速度即可。

可利用相鄰複雜度的比值判斷：

$$\lim_{n\to\infty}\frac{\log n}{n}=0$$

因此，$\log n$ 的成長速度比 $n$ 慢。

同理：

$$\lim_{n\to\infty}\frac{n}{n\log n}=0$$

表示 $n$ 的成長速度比 $n\log n$ 慢；且

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

表示 $n\log n$ 的成長速度比 $n^2$ 慢。

所以最慢、效率最高的成長率是：

$$O(\log n)$$

選項分析

核心觀念

本題考查中序表示法（infix）轉後序表示法（postfix）。

• 中序表示法：運算子位於兩個運算元之間，例如 $5+3$。
• 後序表示法：運算子放在兩個運算元之後，例如 $5\ 3\ +$，可寫成 $53+$。
• 後序表示法不需要括號，運算順序由運算子的排列位置直接決定。

本題的運算優先順序為：

$$\text{括號} > \text{乘法} > \text{加法}$$

因此原式可依運算優先順序寫成：

$$(5+3)\times 7+1\times 5 = \bigl((5+3)\times 7\bigr)+(1\times 5)$$

解題方法

將每個子運算先轉成後序形式，再依原本的運算結構組合。

1. 括號內的 $5+3$：

$$5+3 \longrightarrow 53+$$

2. 將結果乘以 $7$：

$$(5+3)\times 7 \longrightarrow 53+7*$$

3. 右側的 $1\times 5$：

$$1\times 5 \longrightarrow 15*$$

4. 最後將左右兩部分相加：

$$\bigl((5+3)\times 7\bigr)+(1\times 5) \longrightarrow 53+7*15*+$$

所以後序表示式為：

$$\boxed{53+7*15*+}$$

選項分析

核心觀念

此題考查堆疊（stack）的後進先出原則（LIFO, Last In First Out）。

• push(x)：將資料 $x$ 放入堆疊頂端。
• pop()：移除並取出堆疊頂端資料。
• 每次 pop() 只能移除目前最上方的元素。

解題方法

以下以「堆疊底部 $\rightarrow$ 堆疊頂端」表示資料順序：

操作	動作	堆疊內容
push("A")	放入 A	A
push("C")	放入 C	A、C
push("B")	放入 B	A、C、B
pop()	移除頂端 B	A、C
push("F")	放入 F	A、C、F
pop()	移除頂端 F	A、C
push("K")	放入 K	A、C、K
push("J")	放入 J	A、C、K、J
pop()	移除頂端 J	A、C、K

核心觀念

本題比較各種資料結構執行「插入」的最差時間複雜度。令目前資料筆數為 $n$，應以漸進成長率比較：

$$\Theta(1)、\Theta(\log n)、\Theta(n)$$

本題未指定具體實作與插入位置，依一般考試標準假設：Stack 與 Queue 分別維護頂端、尾端指標；Singly linked list 的插入位置可能在任意處，需先走訪尋找插入點。

解題方法

• Stack：插入即 push，直接放在堆疊頂端，只需更新頂端指標，因此

  $$T_{\text{stack}}=\Theta(1)$$

• Queue：插入即 enqueue，直接接在隊尾，維護 rear 指標即可，因此

  $$T_{\text{queue}}=\Theta(1)$$

• Binary heap：新元素先放到最後一個位置，再向上調整以維持 heap 性質。二元堆的高度為

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

  最差情況下，新元素一路上移至根節點，最多比較、交換 $\Theta(\log n)$ 次，因此

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

• Singly linked list：若要插入第 $k$ 個位置，必須從 head 逐節點走訪以找到前一個節點。找到位置後，重新連接指標只需 $\Theta(1)$，但走訪成本為

  $$T_{\text{list}}(k)=\Theta(k)+\Theta(1)$$

核心觀念

本題考查迴圈變數以倍數成長時的時間複雜度。每次迭代後：

i = i * 2;

因此 $i$ 的值依序為：

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

迴圈執行的條件是 $i\le n$，所以最後一次執行需滿足：

$$2^k\le n$$

兩邊取以 $2$ 為底的對數：

$$k\le \log_2 n$$

故迴圈執行次數為：

$$\lfloor \log_2 n\rfloor+1=\Theta(\log n)$$

依一般資料結構考題的固定字長模型，乘法、加法與比較皆視為常數時間，因此整體時間複雜度為 $\Theta(\log n)$，空間複雜度為 $\Theta(1)$。

解題方法

關鍵程式碼為：

for(int i = 1; i <= n; i = i * 2) {
    total += i;
}

令第 $t$ 次迭代開始時的 $i=2^t$。由於迴圈從 $i=1=2^0$ 開始，所有符合條件的 $t$ 為：

$$0\le t\le \lfloor\log_2 n\rfloor$$

所以執行次數是：

$$\lfloor\log_2 n\rfloor+1$$

每次迭代只進行固定次數的加法、乘法與比較，故：

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

total 的累加值雖然是等比級數：

核心觀念

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

• 左子樹所有鍵值小於根節點。
• 右子樹所有鍵值大於根節點。
• 前序走訪順序為：根 → 左子樹 → 右子樹。
• 中序走訪順序為：左子樹 → 根 → 右子樹。
• 後序走訪順序為：左子樹 → 右子樹 → 根。

由於 BST 的中序走訪必定呈現遞增排列，本題可利用前序走訪找根，再利用中序走訪切分左右子樹。

解題方法

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

中序走訪為：

$$1\quad 2\quad 3\quad \boxed{5}\quad 7\quad 9\quad 10\quad 12$$

因此：

• $5$ 左側的 $1,2,3$ 屬於左子樹。
• $5$ 右側的 $7,9,10,12$ 屬於右子樹。

左子樹的前序序列為 $3,1,2$，所以左子樹根為 $3$。其中序序列為 $1,2,3$：

• $3$ 的左子樹為 $1,2$。
• $3$ 沒有右子樹。
• $1$ 的右子節點為 $2$。

左子樹結構為：

    3
   /
  1
   \
    2

其後序走訪為：

$$2\quad 1\quad 3$$

右子樹的前序序列為 $10,9,7,12$，所以右子樹根為 $10$。其中序序列為 $7,9,10,12$：

• $10$ 的左子樹為 $7,9$。
• $10$ 的右子樹為 $12$。
• 左子樹根為 $9$，且 $9$ 的左子節點為 $7$。

右子樹結構為：

      10
     /  \
    9    12
   /
  7

其後序走訪為：

$$7\quad 9\quad 12\quad 10$$

整棵樹為：

本題考查二元搜尋樹 (Binary Search Tree, BST) 的插入操作和前序遍歷 (pre-order traversal)。

首先，我們需要根據圖示構建原始的二元搜尋樹。
圖示中的節點及其關係：

• 根節點是 25。
• 25 的左子節點是 18。
• 25 的右子節點是 50。
• 18 的左子節點是 10。
• 18 的右子節點是 20。
• 10 的左子節點是 15 (注意：在 BST 中，左子節點應小於父節點，這裡 15 > 10，圖示可能不是標準 BST，但我們按照圖示結構來處理，並在插入時遵循 BST 規則)。
• 20 的左子節點是 23 (注意：23 > 20)。
• 50 的左子節點是 40。
• 50 的右子節點是 52。
• 40 的左子節點是 38。

重要提示： 題目要求的是「二元搜尋樹」，插入操作必須遵循 BST 的規則：左子節點 < 父節點，右子節點 > 父節點。圖示中的一些節點可能不符合 BST 規則（例如 10 的左子節點 15，20 的左子節點 23）。在插入新節點時，我們必須嚴格按照 BST 規則進行。

讓我們忽略圖示中可能存在的錯誤，並根據圖示的結構作為「初始狀態」，然後插入 12。
初始 BST 結構（基於圖示的節點和層級）：
25
/
18 50
/ \ /
10 20 40 52
/ / /
15 23 38

現在，我們需要插入節點 12。
插入 12 的過程（遵循 BST 規則）：

• 從根節點 25 開始。12 < 25，向左走。
• 到 18。12 < 18，向左走。
• 到 10。12 > 10，向右走。
• 到 15。12 < 15，向左走。
• 15 的左子節點是空的。將 12 插入到 15 的左子節點。

插入 12 後的 BST 結構：
25
/
18 50
/ \ /
10 20 40 52
/ / /
15 23 38
/
12

現在，我們需要計算這個新樹的前序遍歷 (Root, Left, Right)。
從根節點 25 開始：

1. 訪問根節點 25。輸出 25。
2. 訪問左子樹 (根 18)。
   1. 訪問根節點 18。輸出 18。
   2. 訪問左子樹 (根 10)。
      1. 訪問根節點 10。輸出 10。
      2. 訪問左子樹 (根 15)。
         1. 訪問根節點 15。輸出 15。
         2. 訪問左子樹 (根 12)。
            1. 訪問根節點 12。輸出 12。
            2. 訪問左子樹 (空)。
            3. 訪問右子樹 (空)。
         3. 訪問右子樹 (空)。
      3. 訪問右子樹 (根 20)。
         1. 訪問根節點 20。輸出 20。
         2. 訪問左子樹 (根 23)。

本題考查 Kruskal 演算法求最小生成樹 (Minimum Spanning Tree, MST)。Kruskal 演算法的步驟如下：

1. 將圖中的所有邊按權重從小到大排序。
2. 初始化一個空的最小生成樹。
3. 依次考慮排序後的邊。對於每一條邊，如果將它加入 MST 不會形成環，則將該邊加入 MST。
4. 重複步驟 3，直到 MST 包含 $V-1$ 條邊（其中 $V$ 是頂點數量）。

首先，我們需要識別圖中的所有邊及其權重，並將它們按權重排序。
圖中的頂點為 A, B, C, D, E, F, G。
邊及其權重：

• AB: 1
• BC: 1
• CG: 2
• CD: 4
• DE: 2
• EG: 4
• EF: 3
• AD: 4
• BE: 1
• BF: 5
• AC: 2

按權重排序：
權重 1: AB, BC, BE
權重 2: CG, DE, AC
權重 3: EF
權重 4: CD, EG, AD
權重 5: BF

我們需要找到第 5 條加入 MST 的邊。頂點數量 V = 7。MST 需要 V-1 = 6 條邊。

現在，我們按照排序的邊，依次加入 MST，並檢查是否形成環。我們使用 Disjoint Set Union (DSU) 來判斷是否形成環。

步驟：
初始時，每個頂點都在自己的集合中：{A}, {B}, {C}, {D}, {E}, {F}, {G}。

1. 權重 1 的邊：

• AB (1): A 和 B 不在同一集合。加入 AB。 MST 邊數: 1。 集合: {A, B}, {C}, {D}, {E}, {F}, {G}
• BC (1): B 和 C 不在同一集合。加入 BC。 MST 邊數: 2。 集合: {A, B, C}, {D}, {E}, {F}, {G}
• BE (1): B 和 E 不在同一集合。加入 BE。 MST 邊數: 3。

核心觀念

Prefix expression（前置表示式）的規則是：

• 運算子位於運算元之前。
• 二元運算子後面必須接兩個運算元或子表示式。
• 本題共有五個二元運算子：$+$、$+$、$*$、$-$、$*$、$/$? Let's count: string operators + at 1, + at 3, * at 4, - at 7, * at 9, / at 11 = 6 operators; operands 7. Binary expression result. Need state six binary operators. Good.
• 不需要依照一般中置表示式的優先順序判斷，而是依照前置結構由左至右建立巢狀子表示式。

解題方法

原式為：

$$+5+*79-8*2/93$$

依照前置表示式的結構分組：

$$+\left(5,\ +\left(*\left(7,9\right),\ -\left(8,\ *\left(2,\ /\left(9,3\right)\right)\right)\right)\right)$$

因此可寫成較容易閱讀的形式：

$$5+\left[(7\times 9)+\left(8-\left(2\times \frac{9}{3}\right)\right)\right]$$

由內而外計算：

$$\frac{9}{3}=3$$

核心觀念

二元搜尋樹（Binary Search Tree, BST）必須符合：

• 任一節點左子樹的鍵值小於該節點。
• 任一節點右子樹的鍵值大於該節點。

若依照題目給定順序逐一插入：

$1,4,5,10,11,3,2,8,12$

第一個插入的數字會成為根節點。後續數字只會依大小關係放入左子樹或右子樹，不會改變根節點。

解題方法

依序插入時：

1. 第一個數字 $1$ 沒有既有節點，因此成為根。
2. $4>1$，放在 $1$ 的右側。
3. $5>1$ 且 $5>4$，繼續放在右側。
4. $10,11$ 依相同規則接在右側。
5. $3>1$ 但 $3<4$，放入 $4$ 的左側。
6. $2>1$、$2<4$、$2<3$，放入 $3$ 的左側。
7. $8>1$、$8>4$、$8>5$，但 $8<10$，放入 $10$ 的左側。
8. $12$ 大於目前路徑上的 $1,4,5,10,11$，放入 $11$ 的右側。

核心觀念

二元樹的中序走訪順序是「左子樹 → 根節點 → 右子樹」。若某個節點沒有左子樹，就先走訪該節點，再依序走訪它的右子樹。

解題方法

依圖從左子樹開始走訪：

• 節點 2 的中序順序為：1、2、4。
• 節點 9 的中序順序為：1、2、4、9、11、12。
• 接著走訪根節點 15，再走訪右子樹。

完整中序順序為：

$$1,\ 2,\ 4,\ 9,\ 11,\ 12,\ 15,\ 16,\ 17,\ 20$$

核心觀念

本題考查「插入順序如何影響二元搜尋樹（Binary Search Tree, BST）的形狀」。

一般 BST 的性質為：

• 左子樹所有鍵值小於根節點。
• 右子樹所有鍵值大於根節點。
• 插入時依序比較，且不進行旋轉或自動平衡。

搜尋時間取決於樹高 $h$：

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

若根節點深度為 $0$，最深節點深度為 $h$，則最壞情況需要比較：

$$h+1$$

個節點。

對於 $n=7$ 個節點，二元樹高度至少為：

$$h\geq \left\lceil \log_2(n+1)\right\rceil-1 =\left\lceil \log_2 8\right\rceil-1=2$$

因此，具有最短最壞搜尋時間的樹，應形成高度為 $2$ 的完美平衡樹。

---

解題方法

依照各選項的順序逐一插入，觀察所形成的 BST 高度。高度越小，最壞情況搜尋時間越短。

---

選項分析

(A) $1,2,3,4,5,6,7$

每次插入的新元素都比目前節點大，因此全部沿右側延伸：

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6
           \
            7

樹高為：

$$h=6$$

最壞情況需要比較 $7$ 個節點，搜尋時間為 $\Theta(7)$。

因此，(A) 形成右斜樹，錯誤。

---

(B) $1,7,2,6,3,5,4$

依序插入後：

核心觀念

Min heap（最小堆積）必須同時符合：

1. 結構為完全二元樹。
2. 每個父節點的值都小於或等於其子節點：

$$\text{parent} \leq \text{child}$$

陣列通常依照二元樹的 level-order 儲存。若採用 0-based index，索引為 $i$ 的節點，其子節點索引為：

$$2i+1,\quad 2i+2$$

因此只需檢查所有非葉節點是否都小於或等於子節點。

解題方法

逐一將各陣列視為完全二元樹，檢查父子節點關係。只要找到一組父節點大於子節點，即可判定不是 min heap。

選項分析

(A) [1,2,3,4,5,6,7,8,9,10]

其父子關係為：

• $1$ 的子節點為 $2,3$
• $2$ 的子節點為 $4,5$
• $3$ 的子節點為 $6,7$
• $4$ 的子節點為 $8,9$
• $5$ 的子節點為 $10$

所有關係皆符合：

$$1\leq2,3;\quad 2\leq4,5;\quad 3\leq6,7;\quad 4\leq8,9;\quad 5\leq10$$

本題考查鄰接矩陣 (adjacency matrix) 與圖的連通分量 (connected components)。
一個無向圖的連通分量是指圖中一個極大的子圖，使得該子圖中的任意兩個頂點之間都存在路徑，並且該子圖與圖中其他頂點之間沒有邊相連。

我們需要檢查每個鄰接矩陣所表示的無向圖，看它有多少個連通分量。
對於無向圖，鄰接矩陣是對稱的。如果 $M[i][j] = 1$，則 $M[j][i] = 1$。

檢查每個選項：

選項 (A):

  1 2 3 4
1 0 1 0 0  (1-2)
2 1 0 0 1  (2-1, 2-4)
3 0 0 0 1  (3-4)
4 0 1 1 0  (4-2, 4-3)

邊：(1,2), (2,4), (3,4)。
頂點 1 連接到 2。
頂點 2 連接到 1 和 4。
頂點 3 連接到 4。
頂點 4 連接到 2 和 3。
從 1 可以到達 2，從 2 可以到達 4，從 4 可以到達 3。所以 1, 2, 3, 4 都在同一個連通分量中。
這個圖只有 1 個連通分量。

選項 (B):

  1 2 3 4
1 0 1 1 1  (1-2, 1-3, 1-4)
2 1 0 0 0  (2-1)
3 1 0 0 0  (3-1)
4 1 0 0 0  (4-1)

邊：(1,2), (1,3), (1,4)。

核心觀念

有向圖的 adjacency list（鄰接串列）是依照「邊的起點」逐一列出它能直接到達的頂點。若圖中有邊 $u\to v$，就在頂點 $u$ 的串列中列入 $v$；方向相反的邊不能互相代替。

解題方法

原卷圖中可讀出有向邊為 $1\to2$、$2\to3$、$2\to5$、$3\to1$、$3\to2$、$3\to4$、$5\to1$、$5\to4$。其中 $2$ 與 $3$ 之間有兩個方向相反的箭頭，因此兩者的串列都要列入對方。

依各頂點的出邊整理：

1 -> 2
2 -> 3 5
3 -> 1 2 4
4 ->
5 -> 1 4

選項分析

核心觀念

本題考查各種排序法在「已經由小到大排列」資料上的時間複雜度，尤其是：

• Insertion Sort 的最佳情況。
• Selection Sort 不受輸入排列影響的特性。
• Merge Sort 的固定分治結構。
• Quicksort 選取樞紐（pivot）不當時的最壞情況。

令資料筆數為 $n=100000$。常見複雜度如下：

排序法	本題資料的時間複雜度
Insertion Sort	$\Theta(n)$
Selection Sort	$\Theta(n^2)$
Merge Sort	$\Theta(n\log n)$
Quicksort	依 pivot 選法而定

題目未指定 Quicksort 的 pivot 選取規則。以下採研究所考試最常見的教科書假設：每次選取子陣列的第一個或最後一個元素作為 pivot。

解題方法

(A) Quicksort

原陣列已經是：

$$[1,2,3,\ldots,100000]$$

若每次選取第一個元素 $1$ 作為 pivot，因為它是目前子陣列的最小值，分割後會形成：

• 左側：空集合
• 右側：其餘 $n-1$ 個元素

下一層又對 $n-1$ 個元素形成同樣的不平衡分割，因此遞迴式為：

$$T(n)=T(n-1)+\Theta(n)$$

展開後：

$$T(n)=\Theta(n)+\Theta(n-1)+\cdots+\Theta(2)$$

而

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

所以：

$$T(n)=\Theta(n^2)$$

本題 $n=100000$，分割比較次數約為：

$$\frac{100000\times 99999}{2}=4,999,950,000$$

因此 Quicksort 在此情況會退化成最壞情況。

(B) Insertion Sort

Insertion Sort 會將每個新元素插入前方已排序的區段。

由於陣列已經排序完成，每次取出的元素都大於前一個元素，不需要向前搬移資料。每個元素只需進行一次邊界判斷，因此總次數約為：

$$n-1=99999$$

時間複雜度為：

$$\Theta(n)$$

這是 Insertion Sort 的最佳情況，執行速度很快。

(C) Selection Sort

Selection Sort 每一回合都必須掃描剩餘區段，尋找最小值。即使資料已經排序，仍不能省略這些搜尋。

比較次數為：

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

代入 $n=100000$：

$$\frac{100000\times99999}{2} =4,999,950,000$$

因此：

核心觀念

Insertion sort（插入排序）將陣列分成：

• 左側：已排序區間
• 右側：尚未處理區間

每次從右側取出一個元素，向左比較；若前一個元素較大，就交換兩者，直到該元素位於正確位置。

本題要求由小到大排序，因此交換條件為：

$$A[j-1] > A[j]$$

原始陣列為：

$$[1,3,6,10,7,50,5]$$

解題方法

依照插入排序的相鄰交換流程，逐步處理陣列。

第 1 次交換

處理元素 $7$ 時：

$$[1,3,6,10,7,50,5]$$

因為 $10>7$，交換 $10$ 與 $7$：

$$[1,3,6,7,10,50,5]$$

因此第 1 次交換的兩個數字是 $10,7$。

第 2 次交換

接著處理元素 $5$。此時陣列為：

$$[1,3,6,7,10,50,5]$$

先比較最右側相鄰元素 $50$ 與 $5$：

$$50>5$$

因此第 2 次交換為：

核心觀念

穩定排序（stable sorting）指的是：若兩筆資料的排序鍵值相同，排序後仍維持它們在原始資料中的先後順序。穩定性描述的是排序結果對相同鍵值資料的相對次序，與執行速度或每次移動的距離無關。

解題方法

原卷第 37 題詢問穩定排序的定義；四個選項分別談到不同輸入大小下的效能、相等項目的原始順序、實作方式，以及每輪移動距離。判斷時，直接比對哪個選項描述了相同鍵值資料的相對順序是否保留。

例如，原始資料中有兩筆鍵值同為 5 的資料，先出現的是甲、後出現的是乙。穩定排序後，甲仍須排在乙前面；若兩者次序顛倒，該排序便不穩定。

選項分析

核心觀念

本題考查最小堆積的刪除操作，以及節點「高度」的定義。刪除最小值時，先移除根節點，再將最後一個節點移到根部，接著沿著較小的子節點向下調整，直到恢復最小堆積性質。

節點的高度是該節點到其子樹中最遠葉節點的邊數；因此葉節點高度為 $0$，其父節點高度為 $1$。這和「深度」不同：深度是從根節點往下計算。

解題方法

圖中的最小堆積由上而下、由左而右排列為 $20,25,31,50,40,51,39,300,200,75,55,100,101,70$；其中 $39$ 有一個子節點 $70$。依序刪除根節點並向下調整：

1. 刪除 $20$，以最後的 $70$ 補到根部，再依序與較小子節點交換，得到
   $[25,40,31,50,55,51,39,300,200,75,70,100,101]$。
2. 刪除 $25$，以 $101$ 補到根部並向下調整，得到
   $[31,40,39,50,55,51,101,300,200,75,70,100]$。
3. 刪除 $31$，以 $100$ 補到根部並向下調整，得到
   $[39,40,51,50,55,100,101,300,200,75,70]$。
4. 刪除 $39$，以 $70$ 補到根部並向下調整，得到
   $[40,50,51,70,55,100,101,300,200,75]$。
5. 刪除 $40$，以 $75$ 補到根部並向下調整，得到

核心觀念

最小生成樹（MST）是在連通圖中，以最小總權重連接所有頂點的生成樹。用 Kruskal 演算法時，依權重由小到大選邊；若同一權重有多條邊都能連接不同的連通分量，選擇方式可能造成多棵 MST。

解題方法

圖中權重為 $1$ 的邊是 $AD、DC、CE、BI、FG、GE$。選入這些邊後，形成三個連通分量：$\{A,C,D,E,F,G\}$、$\{B,I\}$，以及孤立頂點 $\{H\}$。

權重為 $2$ 的邊中，$DE、CF$ 都在同一連通分量內，加入會形成環；$AB、BC、IF$ 則都能連接 $\{A,C,D,E,F,G\}$ 與 $\{B,I\}$。要合併這兩個分量，三條邊任選一條即可，因此有 $3$ 種選法。

核心觀念

AVL 樹是高度平衡的二元搜尋樹：每個節點左右子樹的高度差至多為 $1$。若要在高度固定時讓節點數最少，根節點的一側子樹必須達到高度 $h-1$，另一側子樹則可達到高度 $h-2$，同時仍符合 AVL 平衡條件。

以下採常見的「高度以層數計算」慣例，令高度 $1$ 表示只有根節點。設 $M(h)$ 為高度 $h$ 的 AVL 樹最少節點數，則：

$$M(1)=1,\qquad M(2)=2$$ $$M(h)=1+M(h-1)+M(h-2)\quad(h\geq 3)$$

解題方法

依遞迴式逐步計算：

$$\begin{aligned} M(3)&=1+2+1=4\\ M(4)&=1+4+2=7\\ M(5)&=1+7+4=12\\ M(6)&=1+12+7=20\\ M(7)&=1+20+12=33\\ M(8)&=1+33+20=54\\ M(9)&=1+54+33=88\\ M(10)&=1+88+54=143 \end{aligned}$$

因此，高度為 $10$ 層的 AVL 樹最少需要 $143$ 個節點。