111 年 國立陽明交通大學資訊工程學系碩士班《資料結構與演算法》

核心觀念

AVL 樹是具有高度平衡條件的二元搜尋樹。定義節點的平衡因子為

$$BF(v)=h(v_{\text{左子樹}})-h(v_{\text{右子樹}})$$

每個節點都必須滿足 $|BF(v)|\leq 1$。插入新節點時，先依二元搜尋樹規則找到位置，再由插入處往根節點回溯，對第一個失衡節點進行旋轉。

本題也考查三個關係：祖先位於根至該節點的路徑上；葉節點沒有子節點；兄弟節點具有同一個父節點。

解題方法

原圖的根為 $45$，左子樹為 $22$，其左右子節點是 $7、31$，且 $31$ 的右子節點為 $39$。右子樹為 $73$，其左右子節點是 $58、79$，而 $58$ 的右子節點為 $65$。

依大小比較，插入 $61$ 的搜尋路徑為

$$45\rightarrow73\rightarrow58\rightarrow65$$

因為 $58<61<65$，所以 $61$ 插入為 $65$ 的左子節點。此時相關子樹為：

    58
      \
       65
      /
     61

由下往上檢查，$65$ 的平衡因子為 $+1$，仍符合 AVL 條件；$58$ 的平衡因子為 $-2$，是第一個失衡節點。插入位置位於 $58$ 的右子樹之左側，因此屬於 RL（右－左）型，需要兩次旋轉：

1. 對 $65$ 右旋，讓 $61$ 成為 $58$ 的右子節點，$65$ 成為 $61$ 的右子節點。
2. 對 $58$ 左旋，讓 $61$ 成為這棵子樹的根，左右子節點分別為 $58、65$。

核心觀念

AVL 樹是具有平衡條件的二元搜尋樹。定義節點 $v$ 的平衡因子為

$$BF(v)=h(v_{\text{左}})-h(v_{\text{右}}),$$

其中空樹高度為 $0$、葉節點高度為 $1$。每個節點都必須滿足 $|BF(v)|\leq 1$。

插入或刪除節點後，須沿著修改位置往根節點檢查，透過旋轉恢復平衡。旋轉同時必須維持「左子樹的鍵值小於節點，右子樹的鍵值大於節點」的搜尋樹性質。

解題方法

原圖的根節點為 $45$；左子節點 $22$ 的左右子節點為 $7$、$31$，而 $31$ 的右子節點為 $39$。右子節點 $73$ 的左右子節點為 $58$、$79$，而 $58$ 的右子節點為 $65$。

1. 先插入 $61$，完成前一題的調整

依二元搜尋樹規則，插入路徑為

$$45\rightarrow 73\rightarrow 58\rightarrow 65.$$

因為 $58<61<65$，所以 $61$ 成為 $65$ 的左子節點。

此時 $65$ 的平衡因子為 $+1$，仍然平衡；往上遇到的第一個失衡節點是 $58$：

$$BF(58)=0-2=-2.$$

新增節點位於 $58$ 的「右子樹之左側」，屬於 RL 型失衡，依序進行：

1. 對 $65$ 右旋，使 $61$ 位於 $65$ 上方。
2. 對 $58$ 左旋，使 $61$ 成為這棵子樹的根。

調整後，$73$ 以下的結構為：

       73
      /  \
     61   79
    /  \
   58  65

因此，插入後 $73$ 的左子節點是 $61$，而 $61$ 的左右子節點分別為 $58$、$65$。

2. 刪除 $7$，恢復 AVL 平衡

$7$ 是葉節點，可以直接刪除。此時 $22$ 的左子樹為空，右子樹則是 $31$ 及其右子節點 $39$：

核心觀念

AVL 樹是一種自平衡二元搜尋樹。對每個節點，其左、右子樹高度差至多為 $1$。這項限制使 AVL 樹的高度維持在 $O(\log n)$，其中 $n$ 為節點數。

因此，搜尋或插入等沿樹高進行的操作需要 $O(\log n)$ 時間；走訪整棵樹則必須處理所有節點，時間為 $O(n)$。

解題方法

逐一判斷選項，區分兩種操作：

• 沿樹高走訪一條路徑：AVL 樹高度為 $O(\log n)$，例如搜尋與插入。
• 走訪整棵樹：每個節點都要處理一次，因此為 $O(n)$。

再比較 AVL 樹與 Red-Black 樹的平衡程度：兩者操作的漸進時間皆為 $O(\log n)$，但 AVL 樹的平衡限制較嚴格，查找路徑通常較短。

選項分析

(A) 錯誤。 AVL 樹本身就是二元搜尋樹，並額外維持左右子樹高度差至多為 $1$ 的平衡條件。

核心觀念

Kruskal 演算法將邊依權重由小到大排列，逐一加入不會形成環的邊，直到包含所有節點。含 $n$ 個節點的最小生成樹會有 $n-1$ 條邊。

解題方法

圖中有節點 $0$ 至 $8$，共 $9$ 個節點；相關邊及權重包括 $0$–$1:8$、$3$–$5:8$、$1$–$4:9$、$7$–$8:9$、$6$–$8:11$、$5$–$7:11$、$0$–$2:12$、$3$–$6:12$、$3$–$7:12$、$1$–$2:13$、$2$–$3:14$ 等。

由小到大選邊，若加入後會形成環便跳過：

• 權重 $8$：選 $0$–$1$、$3$–$5$。
• 權重 $9$：選 $1$–$4$、$7$–$8$。
• 權重 $11$：選 $6$–$8$、$5$–$7$。
• 權重 $12$：選 $0$–$2$；$3$–$6$、$3$–$7$ 都會形成環，跳過。
• 權重 $13$：$1$–$2$ 會形成環，跳過。
• 權重 $14$：選 $2$–$3$，此時所有節點連通。

核心觀念

圖中的偽程式先將來源點距離設為 $0$、其餘頂點設為無限大，再反覆從尚未處理的頂點中取出目前距離最小者，並用

$$\text{alt}=\text{dist}[u]+\text{dist\_between}(u,v)$$

更新鄰居 $v$ 的距離。這是 Dijkstra 最短路徑演算法的作法；它適用於邊權重皆非負的加權圖。

解題方法

題目中的關鍵操作是「取出 $Q$ 中距離最小的頂點」以及「放鬆該頂點的每條鄰邊」。若以線性掃描尋找最小值，每次取最小值需 $O(V)$，最多取出 $V$ 次，合計 $O(V^2)$；遍歷鄰邊另需 $O(E)$。因此總時間為 $O(V^2+E)$，對簡單圖而言 $E=O(V^2)$，可寫成 $O(V^2)$。

核心觀念

動態規劃（dynamic programming）的典型特徵是：把問題拆成較小的子問題，利用子問題的最佳解推導更大的問題，並儲存子問題結果以避免重複計算。常見形式是定義狀態，再寫出狀態轉移式。

貪婪法則是在每一步選擇當下看起來最好的方案，通常不會枚舉並保存一系列子問題的解。Kruskal 與 Dijkstra 都屬於貪婪演算法；最長共同子序列與 Floyd–Warshall 則使用動態規劃。

解題方法

逐一辨認各演算法的核心設計方式：若演算法以較小子問題的結果建立較大子問題的解，便是動態規劃；若依局部最佳選擇逐步完成，則屬於貪婪法。

最長共同子序列令 $L[i][j]$ 表示兩個字串前 $i$ 個與前 $j$ 個字元的最長共同子序列長度。若末字元相同，就接在較短前綴的解後面；若不同，就比較略去其中一方末字元的兩種情況：

$$L[i][j]= \begin{cases} L[i-1][j-1]+1, & X_i=Y_j,\\ \max(L[i-1][j],L[i][j-1]), & X_i\ne Y_j. \end{cases}$$

Floyd–Warshall 令 $D^{(k)}[i][j]$ 表示只允許頂點 $1,\ldots,k$ 作為中繼點時，從頂點 $i$ 到頂點 $j$ 的最短距離。加入頂點 $k$ 作為可能的中繼點後，最短距離取「不經過 $k$」與「經過 $k$」兩種路徑中較短者：

核心觀念

雜湊函數 $h(\text{key})=\text{key}\bmod m$ 會把鍵值映射到 $0$ 到 $m-1$ 的槽位。若新鍵映射到已被占用的槽位，就發生碰撞（collision）。

• 鏈結法（chaining）：同一槽位可以存放多個鍵值，通常以鏈結串列等方式連接。
• 線性探測（linear probing）：碰撞後依序檢查下一個槽位，槽位計算為 $(h(\text{key})+i)\bmod m$。
• 平方探測（quadratic probing）：碰撞後依平方數偏移探測；本題採標準公式 $(h(\text{key})+i^2)\bmod m$，其中 $i=0,1,2,\ldots$。

各選項使用的表格大小為 $m=7$。

解題方法

先計算每個鍵值的初始雜湊位置：

鍵值	計算	初始槽位
1	$1\bmod 7$	1
2	$2\bmod 7$	2
4	$4\bmod 7$	4
6	$6\bmod 7$	6
8	$8\bmod 7$	1
12	$12\bmod 7$	5
15	$15\bmod 7$	1

這些初始位置可直接判斷碰撞；遇到碰撞時，再依題目指定的處理方法模擬探測或存放。

選項分析

(A) 錯誤。
初始雜湊位置依序為 $1,2,4,6,1,5,1$。鍵值 $8$ 的初始位置是 $1$，與先前放入槽位 $1$ 的鍵值 $1$ 碰撞；鍵值 $15$ 的初始位置也是 $1$，該槽位已有鍵值，因此再發生一次碰撞。總共有兩次碰撞，不是一次。

(B) 正確。
鏈結法允許同一槽位存放多個鍵值。鍵值 $12$ 的位置為：

核心觀念

Dijkstra 演算法適用於邊權重皆非負的圖。從起點 $b$ 出發，每次選取尚未確定、暫定距離最小的節點 $u$，再沿著其向外的有向邊更新鄰點：

$$\operatorname{dist}(v)\leftarrow \min\left\{\operatorname{dist}(v),\operatorname{dist}(u)+w(u,v)\right\}.$$

本題須分清楚「最短路徑的總權重」與「最短路徑的邊數」；Dijkstra 最小化的是總權重，並非邊數。

解題方法

依原圖，雙向連線的權重分別為 $b\to c:2$、$c\to b:1$，$c\to e:1$、$e\to c:3$，以及 $f\to g:3$、$g\to f:1$。其餘有向邊為 $a\to d:2$、$a\to b:1$、$c\to a:9$、$b\to f:8$、$b\to g:6$、$c\to f:4$、$e\to g:8$、$e\to h:7$、$f\to h:6$、$h\to g:9$，其中底部權重 $9$ 的邊方向是 $h\to g$。

初始化 $\operatorname{dist}(b)=0$，其餘節點距離為 $\infty$，依序計算如下：

1. 確定 $b$，距離為 $0$：
   由 $b$ 的出邊得到

   $$\operatorname{dist}(c)=2,\qquad \operatorname{dist}(f)=8,\qquad \operatorname{dist}(g)=6.$$

2. 確定 $c$，距離為 $2$：
   經由 $c$ 更新

   $$\operatorname{dist}(e)=2+1=3,\qquad \operatorname{dist}(f)=\min\{8,2+4\}=6,\qquad \operatorname{dist}(a)=2+9=11.$$

   $c\to b$ 所得距離為 $2+1=3$，不優於 $b$ 原有的 $0$。

3. 確定 $e$，距離為 $3$：
   經由 $e\to h$ 得到

   $$\operatorname{dist}(h)=3+7=10.$$

   經由 $e\to g$ 的權重為 $3+8=11$，不優於 $g$ 原有的 $6$。

核心觀念

紅黑樹插入時，新節點一律先著成紅色，再依父節點、叔叔節點的顏色修正。修正方式包括重新著色與旋轉，並須維持紅黑樹的性質：

• 根節點為黑色。
• 紅色節點的子節點必為黑色。
• 從任一節點到其後代外部節點的每條路徑，黑色節點數相同。
• 外部節點（NIL）視為黑色。

含有 $n$ 個實際鍵值節點的二元樹，外部節點數為 $n+1$。

解題方法

依序插入 $5,2,7,3,4$，每次檢查是否有紅色父子相連，並記錄旋轉次數。

1. 插入 $5$：新節點成為根，根必須為黑色。

2. 插入 $2$、$7$：兩者均為紅色，分別成為 $5$ 的左右子節點，沒有紅色父子相連。

3. 插入 $3$：成為 $2$ 的右子節點。此時父節點 $2$ 與叔叔節點 $7$ 都是紅色，因此將 $2$、$7$ 改為黑色，將祖父節點 $5$ 暫改為紅色；根節點最後恢復為黑色。此步不需旋轉。

4. 插入 $4$：成為 $3$ 的右子節點。父節點 $3$ 是紅色，叔叔節點為黑色的 NIL。

核心觀念

本題考查圖形走訪與圖形基本定義：

• 廣度優先搜尋（BFS）以起點為中心，依照與起點的距離由近至遠走訪頂點，使用佇列保存待處理頂點。
• 強連通有向圖：對任意兩個頂點 $u$、$v$，都存在從 $u$ 到 $v$ 的有向路徑。
• 完全圖：每一對不同頂點之間都有邊相連。

解題方法

逐一比對選項中的敘述與標準定義。判斷 BFS 時，注意它是先走訪同一層的頂點，再進入下一層；判斷圖形定義時，確認頂點間路徑的方向，以及「完全」代表每一對不同頂點都有邊。

選項分析

核心觀念

本題考查漸近記號 $O$、$\Theta$ 的定義，以及比較多項式、階乘與指數函數成長速度的方法。

對非負函數 $f(n)$、$g(n)$，若存在常數 $c>0$ 與 $n_0$，使得所有 $n\ge n_0$ 都滿足

$$f(n)\le c\,g(n),$$

則 $f(n)=O(g(n))$。若存在常數 $c_1,c_2>0$ 與 $n_0$，使得所有 $n\ge n_0$ 都滿足

$$c_1g(n)\le f(n)\le c_2g(n),$$

則 $f(n)=\Theta(g(n))$。

判斷和式的漸近階時，可先找成長最快的項；但若要證明整個和式屬於某個 $O$ 類別，仍須確認其他各項也都能被該上界控制。多項式次方固定時，指數底數較大的函數成長較快；指數函數也會快於任何固定次方的多項式。

解題方法

逐項依定義比較。對 $O$，可將候選函數相除，檢查比值是否有界；對 $\Theta$，則需同時找出上界與下界。

選項分析

(A) $n!=O(n^n)$：正確。

對每個 $1\le k\le n$，都有 $k\le n$，因此

$$n!=1\cdot2\cdots n\le n\cdot n\cdots n=n^n.$$

取常數 $c=1$，便符合 $O$ 的定義，所以 $n!=O(n^n)$。

(B) $10n^3+10n^5+100n^2 2^n=O(n^2 2^n)$：正確。

分別比較左側各項與 $n^2 2^n$：

$$\frac{10n^3}{n^2 2^n}=\frac{10n}{2^n}\longrightarrow 0,$$ $$\frac{10n^5}{n^2 2^n}=\frac{10n^3}{2^n}\longrightarrow 0,$$

而

$$\frac{100n^2 2^n}{n^2 2^n}=100.$$

核心觀念

堆疊（stack）遵循「後進先出」（LIFO）：每次 push 都把新元素放到頂端，每次 pop 都移除頂端元素。題目以括號由左至右列出堆疊內容，並指定頂端是 $5$，因此列出的順序就是由頂端往底端。

原堆疊有 $5$ 個元素：$(5,4,7,9,0)$。依序 push 3、再 push 5 後，頂端至底端為 $(5,3,5,4,7,9,0)$，共有 $5+2=7$ 個元素。

解題方法

先依堆疊規則逐次更新頂端，再檢查每個選項的內容、元素數量與彈出結果。連續 pop 時，每次都移除當下的頂端元素。

選項分析

• (A) 錯誤。 依序推入 $3$、$5$ 後，頂端至底端應為 $(5,3,5,4,7,9,0)$。選項所列的 $(3,5,4,7,9,0)$ 不是正確的堆疊內容，且只有 $6$ 個元素。

核心觀念

本題考查堆疊（stack）與佇列（queue）的基本定義、陣列的元素型態，以及佇列元素數量與連結方式。

• 堆疊採用後進先出（LIFO）：最後加入的元素最先取出。
• 佇列採用先進先出（FIFO）：最早加入的元素最先取出。
• 堆疊與佇列都是抽象資料型態，可用陣列或鏈結串列實作。採用陣列時，陣列中的元素具有相同型態。
• 在有限記憶體的實作中，佇列當下存放的元素數量有限，必小於某個整數。

解題方法

逐項對照資料結構的定義與常見實作方式：確認堆疊和佇列是否能用鏈結串列實作，再區分兩者的取出順序；接著檢查陣列的型態限制、佇列元素數量是否有限，以及佇列是否規定元素要指向前驅。

選項分析

(A) 正確。
堆疊與佇列都能用鏈結串列實作。堆疊可在串列一端進行插入與刪除；佇列則可用 front 與 rear 指標，分別管理取出端與加入端。

核心觀念

本題考查鏈結串列的動態特性、合併排序，以及串列尾端指標對操作時間的影響。以下將「合併兩個鏈結串列」按一般串列串接理解：保留兩串列各自的節點順序，將第二串列接到第一串列尾端。

單向鏈結串列只有頭指標時，若要找到尾端，必須沿著 next 逐節點走訪。若另有尾指標，則可直接取得最後一個節點。

解題方法

逐項判斷操作是否需要走訪節點：

• 修改串列結構時，若必須先找到尾端，需走訪串列。
• 合併排序會分割串列並反覆合併子串列，整體時間為 $O(n\log n)$。
• 串接時，若沒有尾指標，要走訪第一個串列找到尾端；有尾指標時，可直接連接。

選項分析

(A) 錯誤。 鏈結串列是動態資料結構，可依需要配置或釋放節點；節點不必像陣列元素一樣連續存放。

(B) 錯誤。 使用合併排序對鏈結串列排序，遞迴分割的層數為 $O(\log n)$，每一層合併所有節點需 $O(n)$，因此最壞時間為

$$O(n\log n)$$

不是 $O(n^2)$。

核心觀念

雙向鏈結串列可在已知節點位置時，以 $O(1)$ 時間刪除節點；但若只給定值，必須先從串列中搜尋該值。兩條已排序串列可用雙指標合併，時間與總節點數成正比。

排序的複雜度取決於排序方法。對鏈結串列，可用合併排序達到 $O(n\log n)$；排序兩條串列合併後的全部元素，總數為 $2n$，因此時間為 $O(2n\log(2n))=O(n\log n)$。

解題方法

逐項判斷是否需要搜尋、是否能線性合併，以及題目宣稱的複雜度是否符合標準高效率做法。題目未指定排序法；以下以鏈結串列常用的合併排序作為排序方法，並以緊確的漸近複雜度判斷。

選項分析

(A) 正確。 要刪除具有指定值的節點，最壞情況下須搜尋整條長度為 $n$ 的串列，耗時 $O(n)$。找到節點後，更新前後節點的連結只需 $O(1)$，總時間仍為 $O(n)$。

(B) 正確。 若兩條串列已依相同方向排序，從兩個串列的首端開始比較，每次取出較小（或較大）的值並移動對應指標。每個節點至多被檢查、處理一次；

核心觀念

題目問的是「用哪一種資料結構來輔助排序隨機數」比較快。每個選項都要想成：把資料逐一放進該結構、最後依序取出，需要多少時間。

結構	排序方式	時間（隨機資料）
陣列	快速排序／合併排序	$O(n\log n)$
單向／雙向／環狀鏈結串列	逐一插入到正確位置（插入排序）	$O(n^2)$
二元搜尋樹	逐一插入後中序走訪（tree sort）	平均 $O(n\log n)$
堆疊、佇列	只能存取兩端，本身不提供排序能力	—

選項分析

• (A) 錯誤。 佇列與堆疊都只能在端點存取，兩者都不會讓排序變快，沒有誰比較快的道理。
• (B) 錯誤。 鏈結串列不能隨機存取，難以套用快速排序等高效率方法；用插入方式排序是 $O(n^2)$。

核心觀念

本題考查二元搜尋樹（BST）的節點表示方式，以及建立與搜尋的時間複雜度。以下以「將 $n$ 個鍵值逐一插入標準、未平衡的 BST」為前提。

BST 中，每個節點最多有左、右兩個子節點；若採用指標表示，每個節點需要兩個連結欄位。雙向鏈結串列節點也有兩個連結欄位，因此可將原本的前、後指標分別用作左、右子節點指標。

解題方法

設 BST 的高度為 $h$。搜尋或插入一個鍵值時，從根節點開始，依鍵值大小選擇左子樹或右子樹，最多走訪 $h$ 層，因此單次操作時間為 $O(h)$。

• 若樹大致平衡，$h=O(\log n)$，逐一插入 $n$ 個鍵值的總時間為 $O(n\log n)$。
• 若每次插入都使樹向單側延伸，$h=O(n)$。逐一插入時，各次操作成本依序可達 $1,2,\ldots,n$，總時間為

$$\sum_{i=1}^{n} O(i)=O(n^2)$$

• 單次搜尋在平均情況下，假設鍵值插入順序隨機且分布合理，樹高平均為 $O(\log n)$；最壞情況下樹高為 $O(n)$。

選項分析

核心觀念

二元搜尋樹（BST）的核心性質是：每個節點的鍵值都能依照大小關係，分布在根節點的左、右子樹中；而且左右子樹本身也必須是二元搜尋樹。

本題採用標準定義：每個節點有一個鍵值，且不同節點的鍵值互異。對任一節點而言：

• 左子樹中的鍵值都小於該節點的鍵值。
• 右子樹中的鍵值都大於該節點的鍵值。
• 左右子樹各自也符合二元搜尋樹的定義。

解題方法

逐項對照二元搜尋樹的定義，再檢查高度是否能由節點數一般性地界定為對數級。BST 的形狀會受插入順序影響；只有樹形夠平衡時，高度才是 $O(\log n)$，一般情況下不能保證如此。

選項分析

核心觀念

中序式轉成前序式或後序式時，先依照運算子優先順序與括號確定運算樹，再以不同順序走訪運算樹：

• 前序式：根節點、左子樹、右子樹。
• 後序式：左子樹、右子樹、根節點。
• 樹高取決於運算樹的形狀；最壞情況可能退化成單鏈。
• 每個運算元與運算子在前序式、後序式中各出現一次，因此輸出長度與中序式的 token 數量同階。

解題方法

原式為

$$(A+B)*D+E/(F+A*D)$$

依照括號與優先順序，其運算結構是：先算 $(A+B)$，再乘上 $D$；分母為 $F+(A*D)$；最後將兩部分相加。因此運算樹的根節點是 $+$，左子樹是 $(A+B)*D$，右子樹是 $E/(F+A*D)$。

以前序走訪得到：

$$+*+ABD/E+F*AD$$

以後序走訪得到：

$$AB+D*EFAD*+/+$$

選項分析

核心觀念

二元堆積（binary heap）是以陣列表示的完全二元樹，並滿足堆積順序性：

• 最小堆積：每個父節點的值小於或等於子節點，因此最小值在根節點。
• 最大堆積：每個父節點的值大於或等於子節點，因此最大值在根節點。

堆積的根節點位於陣列索引 $0$，直接讀取根節點需要 $O(1)$ 時間。若要移除根節點，才需將末端元素移至根部並向下調整，時間為 $O(\log n)$。

另外，將任意 $n$ 個元素建立成堆積，可使用自底向上的堆積化（heapify），時間為 $O(n)$，不必逐個插入而花費 $O(n\log n)$。

解題方法

逐一判斷各敘述涉及的操作：

1. 從堆積取得極值，先確認題目指的是讀取根節點，還是移除根節點。
2. 將資料排成有序串列，視為排序問題；在一般比較模型下，排序需要 $\Omega(n\log n)$ 時間。
3. 建立或轉換堆積，採用自底向上的堆積化，分析所有節點調整成本的總和。

選項分析

(A) 錯誤。 最小堆積的最小值位於根節點，直接讀取只需 $O(1)$，不是最壞情況 $O(n)$。若操作是移除最小值，則需調整堆積，時間為 $O(\log n)$，仍不是 $O(n)$。

(B) 正確。 最大堆積的最大值位於根節點，直接讀取根節點所需時間為 $O(1)$。

核心觀念

這題考遞迴式的漸近分析，可使用主定理（Master Theorem）。對於

$$T(n)=aT\left(\frac{n}{b}\right)+f(n)$$

比較 $f(n)$ 與 $n^{\log_b a}$ 的成長速度。本題中 $a=3$、$b=4$、$f(n)=n$。假設 $T(1)=\Theta(1)$，且 $n$ 可視為 $4$ 的次方。

解題方法

先計算遞迴部分的基準成長率：

$$n^{\log_b a}=n^{\log_4 3}$$

因為 $\log_4 3<1$，所以 $n^{\log_4 3}$ 的成長速度低於 $n$，即 $f(n)=n$ 多項式級地較大。

再檢查主定理第三種情況的規則性條件：

$$a f\left(\frac{n}{b}\right) =3\cdot\frac{n}{4} =\frac{3}{4}n$$

因此可取常數 $c=\frac{3}{4}<1$，使得 $a f(n/b)\le c f(n)$。符合主定理第三種情況，得到：

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

核心觀念

遞迴程式的時間複雜度可由「每次呼叫執行的工作量」與「遞迴呼叫次數」推導。若每次只做常數時間的工作，並依序呼叫規模減少 $1$ 的子問題，總時間通常與遞迴深度成正比。

解題方法

圖中的程式在 $n \le 1$ 時直接回傳；否則呼叫 sum(n-1)，再加上 $n$：

int sum(int n) {
    if (n <= 1)
        return 1;
    else
        return sum(n-1) + n;
}

每次呼叫只執行一次條件判斷、一次遞迴呼叫及一次加法，這些工作皆為常數時間。因此，對 $n>1$，時間遞迴式為

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

展開可得

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

核心觀念

插入排序每一輪取出一個待插入元素 key，再把已排序區段中應排在它後面的元素往右移，最後將 key 放入空出的位置。排序方向由 while 條件中的比較符號決定；排序是否穩定，則要看相等元素是否會改變原本的先後次序。

解題方法

圖中的程式從 $i=1$ 開始，令 $j=i-1$；第 9 行條件是 arr[j] <= key，符合條件時便把 arr[j] 往右移，最後將 key 放在 arr[j+1]。因此第 6 行應取出目前要插入的元素 arr[i]。由於比 key 小或相等的元素會被移到右邊，程式會將陣列排成遞減順序。

key = arr[i]
j = i - 1

while (j >= 0 && arr[j] <= key) {
    arr[j + 1] = arr[j]
    j = j - 1
}
arr[j + 1] = key

例如插入 key = 4 到已排序區段 [7, 5, 2]：7 和 5 都大於 4，不會移動；4 放在 5 後面，結果為 [7, 5, 4, 2]。這也驗證了排序方向是遞減。

核心觀念

最大堆（max-heap）是完全二元樹，且每個父節點都不小於子節點，因此根節點是目前最大的元素。執行一次 extract-max 時，移除根節點，把堆尾元素移到根部，再向下調整，使最大堆性質恢復。

題目寫明 $A[0]=94$，而給定陣列符合零起始索引的最大堆規則：$A[k]$ 的父節點索引是 $\lfloor (k-1)/2\rfloor$。題目所寫的 $\lfloor k/2\rfloor$ 與 $A[0]$ 為根節點不相容；若照該公式檢查，$A[2]=82$ 的父節點會是 $A[1]=23$，不符合最大堆性質。

解題方法

依符合給定陣列的零起始索引規則，連續執行 6 次移除最大值。每次移除根節點後，將堆尾元素移到根部，並依序與較大的子節點交換。

次數	移除的最大值	調整後的堆
1	94	$[82,23,17,11,19,2,3,4,9,15]$
2	82	$[23,19,17,11,15,2,3,4,9]$

核心觀念

本題考查固定選擇最後一個元素作為樞紐（pivot）的快速排序：

• 執行時間取決於各次分割的子陣列大小，以及每次 partition 掃描的成本。
• partition 的總呼叫次數是整棵遞迴樹的分割節點數。
• 遞迴深度是遞迴樹最長路徑的長度，不能直接等同總呼叫次數。

若每次分割都只排定一個元素，剩下 $n-1$ 個元素繼續排序，時間為 $\Theta(n^2)$；若每次分割大致平均，時間為 $\Theta(n\log n)$。

解題方法

圖中程式以 A[hi] 為 pivot，迴圈從 lo 掃描到 hi，包含 pivot 本身，比較條件為 A[k] <= pivot。partition 回傳位置 $p$ 後，遞迴處理 lo 到 $p-1$ 與 $p+1$ 到 hi，且只有至少含兩個元素的區間才呼叫 partition。

關鍵程式為：

pivot := A[hi]
i := lo - 1
for k := lo to hi do
    if A[k] <= pivot then
        i := i + 1
        swap A[i] with A[k]
return i

當 $k=\text{hi}$ 時，pivot 本身必定通過比較，因此被交換到最後的 $i$ 位置。這就是回傳的 pivot 位置，圖中不需要再補一次交換。

設目前子陣列有 $m$ 個元素，partition 掃描全部 $m$ 個元素，成本為 $\Theta(m)$。若左右分別有 $a$、$b$ 個元素，則

$$a+b=m-1,\qquad T(m)=T(a)+T(b)+\Theta(m).$$

因此，判斷各選項的關鍵是 pivot 的位置與遞迴樹形狀。

選項分析

(A) 正確：遞增排序時，時間為 $\Theta(n^2)$。

最後一個元素是最大值，所有元素都符合 A[k] <= pivot，所以回傳 $p=\text{hi}$。右側為空，左側有 $n-1$ 個元素，且仍維持遞增排序。

每次都產生大小為 $m-1$ 與 $0$ 的分割：

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

各次掃描的元素數為 $n,n-1,\ldots,2$，故

$$T(n)=\Theta\!\left(\sum_{m=2}^{n}m\right) =\Theta(n^2).$$

(B) 正確：遞減排序時，時間為 $\Theta(n^2)$。

第一次的 pivot 是最小值，只有 pivot 本身通過比較，因此被交換到最左端，回傳 $p=\text{lo}$。

交換後，原本最左端的最大值移到最後一個位置，成為下一次分割的 pivot。此時 pivot 又被排定在最右端。後續持續交替取到剩餘區間的最小值與最大值，每次都只有一側含 $m-1$ 個元素。

例如：

$$[5,4,3,2,1] \longrightarrow [1,4,3,2,5].$$

核心觀念

這題考查開放定址雜湊表的容量、雜湊搜尋，以及在未排序資料中尋找最大值或後繼元素的時間複雜度。

• 開放定址法將每個鍵直接存放在表格槽位中；$N$ 個槽位最多可存放 $N$ 個鍵。
• 若沒有可利用的排序資訊，掃描全部 $N$ 個鍵可以找到最大值，時間為 $O(N)$。
• 若先排序，再查找某鍵的後繼，總時間可控制在 $O(N\lg N)$。
• 若鍵集合固定，且雜湊函數能讓集合中的每個鍵映射到不同槽位，便可用完美雜湊達成最壞情況 $O(1)$ 查找。

解題方法

逐項判斷各操作是否有符合敘述的演算法或資料配置。

尋找最大鍵時，逐一檢查所有槽位並記錄目前最大值即可，需檢查 $N$ 個鍵。尋找後繼時，可先將鍵排序，再用排序結果定位給定鍵及其後一個鍵，排序成本為 $O(N\lg N)$，定位成本不會超過 $O(\lg N)$，因此總時間仍為 $O(N\lg N)$。

對於最壞情況 $O(1)$ 搜尋，固定鍵集合可使用完美雜湊函數，讓每個已儲存鍵直接映射至自己的槽位；搜尋時只需檢查該槽位。

選項分析

核心觀念

雜湊函數 $h(k)=k\bmod 5$ 以除以 $5$ 的餘數決定鍵值所在的槽位。採用鏈結法（chaining）時，雜湊到同一槽位的鍵值會串在該槽位的鏈結串列中，因此只要計算各鍵值的餘數並統計每個槽位的鍵數即可。

解題方法

逐一計算鍵值對 $5$ 取餘數：

鍵值 $k$	$h(k)=k\bmod 5$	槽位
$7$	$2$	$2$
$1$	$1$	$1$
$10$	$0$	$0$
$12$	$2$	$2$
$2$	$2$	$2$
$55$	$0$	$0$
$5$	$0$	$0$

整理各槽位的鍵值：

核心觀念

二元搜尋樹（BST）滿足：對任一節點，其左子樹的鍵值小於該節點，右子樹的鍵值大於該節點。搜尋、插入與刪除時，通常沿著樹的一條路徑往下操作，因此時間複雜度與樹高 $h$ 有關。

若樹高以邊數計算，根節點深度為 $0$；以節點層數計算只會相差常數，不影響以下漸近複雜度。

解題方法

逐項判斷選項所述複雜度或性質是否對所有二元搜尋樹都成立。特別留意：未平衡的 BST 高度可能達到 $n-1$，因此不能把高度複雜度直接視為常數時間。

選項分析

(A) 正確。 插入時從根節點開始，比較鍵值並沿左、右子樹往下走，直到找到適合插入的位置。最多走過樹高量級的路徑，因此時間複雜度為 $O(h)$。

(B) 正確。 刪除前需先沿樹搜尋目標節點，耗時 $O(h)$。若目標節點有兩個子節點，通常以右子樹中的最小節點或左子樹中的最大節點替代；尋找該替代節點也只需沿一條高度不超過 $h$ 的路徑。因此整體時間複雜度仍為 $O(h)$。

核心觀念

樹高是根節點到最深葉節點的最長路徑長度。以下以「邊數」計算；若改用節點數，各樹高度都只會多 $1$，不影響是否變高的判斷。

單旋轉會改變根節點附近的父子關係，因此要比較旋轉前後的最長路徑。題目問哪些樹「可能」變高，只要該樹存在一種合法的根節點旋轉，能讓高度增加即可。

解題方法

圖中五棵樹的根節點分別為：$(A)$ 的 $2$、$(B)$ 的 $3$、$(C)$ 的 $4$、$(D)$ 的 $3$、$(E)$ 的 $4$。對各樹檢查根節點可做的左旋或右旋，再比較旋轉前後的最長路徑。

選項分析

• (A) 正確。 原樹最長路徑為 $2 \to 4 \to 3$，樹高為 $2$。在根節點 $2$ 右旋後，根變成 $1$，路徑 $1 \to 2 \to 4 \to 3$ 長度為 $3$，樹高增加。
• (B) 正確。 原樹最長路徑為 $3 \to 2 \to 1$，樹高為 $2$。