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

核心觀念

本題考查各種排序法的：

• 最佳、最壞時間複雜度
• 是否為原地排序（in-place）
• Heapify 與 Build-Heap 的時間複雜度
• Big-O 與 Big-Omega 的意義

常見結論如下：

排序法／操作	最佳情況	最壞情況	是否原地
Bubble Sort（具提前停止最佳化）	$\Theta(n)$	$O(n^2)$	是
Quick Sort	$O(n\log n)$	$O(n^2)$	是
Heap Sort	$O(n\log n)$	$O(n\log n)$	是
MAX-HEAPIFY	—	$O(\log n)$	—
BUILD-MAX-HEAP	—	$O(n)$	—

其中，$O(g(n))$ 表示漸近上界，$\Omega(g(n))$ 表示漸近下界，$\Theta(g(n))$ 表示同時具有上下界。

解題方法

逐一檢查每個敘述是否符合上述定義與定理：

1. 判斷 Bubble Sort 最佳情況的實際執行成本。
2. 判斷 Quick Sort 的額外空間需求與分割方式。
3. 使用 Quick Sort 最壞情況的遞迴式。
4. 區分單一節點的 HEAPIFY 與整體建堆 BUILD-HEAP。
5. 判斷 Heap Sort 是否需要額外陣列。

選項分析

(A) The best case time complexity of Bubble Sort is $\Omega(n)$

正確。

在已排序的輸入上，若 Bubble Sort 使用「本輪沒有交換就提前停止」的最佳化版本，只需掃描一次陣列，確認沒有逆序相鄰元素：

$$T(n)=cn+d$$

因此最佳情況為：

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

由於 $\Theta(n)$ 必然也是 $\Omega(n)$，所以「最佳情況時間複雜度是 $\Omega(n)$」成立。

補充而言，若實作未使用提前停止最佳化，最佳情況會是 $\Theta(n^2)$；即使如此，$\Theta(n^2)$ 仍然屬於 $\Omega(n)$。因此依照一般漸近分析，選項仍為正確。

(B) Quick Sort sorts in place

正確。

Quick Sort 的 partition 通常直接在原陣列內交換元素，不需建立與輸入陣列同樣大小的額外陣列，因此屬於原地排序。

其主要額外空間來自遞迴呼叫堆疊：

• 平衡分割時：約為 $O(\log n)$
• 最壞分割時：約為 $O(n)$

雖然遞迴堆疊可能達到 $O(n)$，Quick Sort 仍被歸類為 in-place sorting，因為它不需要 $O(n)$ 的額外資料陣列來存放元素。

(C) The worst case time complexity of Quick Sort is $O(n^2)$

正確。

核心觀念

本題考查二元樹的定義、層數上下界，以及節點度數與葉節點數之間的關係。

• 二元樹是樹的特例，每個節點最多有兩棵子樹。
• 若二元樹有 $n$ 個節點，其最少層數來自每層盡可能擁有最多節點。
• 其最多層數出現在退化成單鏈的情況。
• 對非空二元樹，設度數為 $0,1,2$ 的節點數分別為 $n_0,n_1,n_2$，則有
  $n_0=n_2+1.$

---

解題方法

逐一檢查各選項：

1. 依據二元樹與一般樹的定義判斷。
2. 依據二元樹每個節點最多兩個子樹的限制判斷。
3. 使用 $h$ 層二元樹的最大節點數公式
   $2^h-1.$
4. 以最不平衡的退化二元樹判斷最大層數。
5. 以邊數公式推導葉節點數與度數為 $2$ 的節點數關係。

---

選項分析

(A) 錯誤

二元樹的定義允許空二元樹；但是一般所稱的樹通常要求至少有一個根節點，因此空二元樹不被視為一棵樹。

所以「二元樹總是樹」不成立，尤其在二元樹為空時不成立。

---

(B) 正確

二元樹的定義就是每個節點最多有兩個子樹，因此任一節點的 degree 必須滿足

$\text{degree}\leq 2.$

故此敘述正確。

---

(C) 正確

若二元樹有 $h$ 層，最多可容納的節點數為

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

要容納 $8$ 個節點，需滿足

$2^h-1\geq 8,$

因此

$2^h\geq 9.$

由於

$2^3-1=7<8,\qquad 2^4-1=15\geq 8,$

核心觀念

本題考查無向圖、完全圖、連通圖與生成樹的基本定義及公式：

• 無向簡單圖的邊連接兩個不同頂點，且同一條邊不重複。
• $n$ 個頂點的完全圖記為 $K_n$，任兩個不同頂點之間都有一條邊。
• 連通圖中任兩個頂點之間都存在路徑。
• 生成樹包含原圖的所有頂點，且是一棵樹。因此，$n$ 個頂點的生成樹有 $n-1$ 條邊。

---

解題方法

逐一檢查各選項是否符合無向簡單圖的定義與相關定理，特別注意：

1. 無向邊不分方向，因此兩個頂點形成的邊只能計算一次。
2. 樹的頂點數與邊數關係為「邊數 = 頂點數 − 1」。
3. 完全圖是邊數最多的簡單圖，且在通常定義下必為連通圖。

---

選項分析

(A) 錯誤

對於 $n$ 個頂點的無向簡單圖，每條邊由兩個不同頂點組成。

若先選取兩個頂點，排列數為：

$$n(n-1)$$

但無向邊 $(u,v)$ 與 $(v,u)$ 是同一條邊，因此每條邊被計算兩次，必須除以 $2$：

$$|E|_{\max}=\frac{n(n-1)}{2}=\binom{n}{2}$$

因此最大邊數是 $\frac{n(n-1)}{2}$，不是 $n(n-1)$。後者是有向圖計算邊數時的排列數。

---

(B) 錯誤

連通圖只需保證所有頂點彼此可達，其最少邊數為：

$$n-1$$

例如一棵含有 $n$ 個頂點的樹就是連通圖，但只有 $n-1$ 條邊。因此「至少有 $n$ 條邊」並不成立。

正確敘述應為：

核心觀念

本題考查三柱漢諾塔（Tower of Hanoi）的遞迴結構與時間複雜度。

要將 $n$ 個大小不同的盤子從起始柱移到目標柱，必須遵守：

1. 每次只能移動一個盤子。
2. 大盤子不能放在小盤子上面。
3. 可使用第三根柱子作為輔助。

令 $T(n)$ 表示移動 $n$ 個盤子所需的最少移動次數。

解題方法

移動最大的第 $n$ 個盤子之前，必須先將上面的 $n-1$ 個盤子移到輔助柱，所需移動次數為 $T(n-1)$。

接著移動最大的盤子一次，所需次數為 $1$。

最後再將 $n-1$ 個盤子從輔助柱移到目標柱，所需次數仍為 $T(n-1)$。

因此遞迴式為：

$$T(n)=2T(n-1)+1$$

初始條件為：

$$T(0)=0$$

展開遞迴式：

$$\begin{aligned} T(n) &=2T(n-1)+1\\ &=2\left(2T(n-2)+1\right)+1\\ &=2^2T(n-2)+2+1\\ &=\cdots\\ &=2^nT(0)+(2^{n-1}+2^{n-2}+\cdots+2+1)\\ &=2^n-1 \end{aligned}$$

所以最少移動次數為：

$$T(n)=2^n-1$$

核心觀念

堆疊（stack）遵循後進先出（LIFO, Last In First Out）原則：

• push(X)：將元素 $X$ 放入堆疊頂端。
• pop()：移除並回傳堆疊頂端元素。
• 題目要求由 Front 到 Rear 列出內容；此處將 Front 視為堆疊頂端，也就是 pop() 操作的一端。

解題方法

依序執行每個操作，記錄堆疊內容。表中由左至右皆表示 Front（頂端）到 Rear（底端）。

操作	執行結果	堆疊內容（Front → Rear）
push(A)	放入 $A$	$A$
push(B)	放入 $B$，位於 $A$ 前方	$B, A$
pop()	移除頂端 $B$	$A$
push(C)	放入 $C$	$C, A$

核心觀念

本題考查樹的高度、節點度數上限，以及等比級數求和。

• 每個節點最多有 $K$ 個子節點。
• 樹的高度 $L$ 定義為根節點到最深葉節點的邊數，因此共有 $L+1$ 層。
• 要使節點總數最大，根節點至第 $L-1$ 層的每個節點都必須恰好擁有 $K$ 個子節點。

解題方法

各層最多節點數如下：

• 第 $0$ 層：$1=K^0$
• 第 $1$ 層：$K=K^1$
• 第 $2$ 層：$K^2$
• $\cdots$
• 第 $L$ 層：$K^L$

因此最大節點總數為：

$$N_{\max}=1+K+K^2+\cdots+K^L$$

這是首項為 $1$、公比為 $K$ 的等比級數。當 $K>1$ 時：

$$N_{\max} =\frac{K^{L+1}-1}{K-1}$$

因此，最大節點數為：

$$\boxed{\frac{K^{L+1}-1}{K-1}}$$

(A) 中序轉後序

1. 設「輸出」空列，「運算子堆疊」空堆疊。
2. 依左至右掃描中序式每個字元，依下表處理

token	動作
operand (A‑H)	直接加入輸出
'('	推入堆疊
')'	逐一彈出堆疊至遇到 '('，彈出的運算子加入輸出，丟棄 '('
operator (+ – * /)	彈出堆疊中 優先度 ≥ 當前運算子（左結合）並加入輸出，然後推入當前運算子

3. 掃描完畢後，將堆疊中剩餘運算子全部彈出加入輸出。

執行過程（堆疊以最上層在右）

token	輸出	堆疊
A	A
*	A	*
B	A B	*
–	A B *	–
C	A B * C	–
+	A B * C –	+
(	A B * C –	+ (
D	A B * C – D	+ (
+	A B * C – D	+ ( +
E	A B * C – D E	+ ( +
)	A B * C – D E +	+
*	A B * C – D E +	+ *
F	A B * C – D E + F	+ *
+	A B * C – D E + F *	+

核心觀念

本題考查雜湊表的碰撞處理：

• 表格大小為 $m=7$，索引為 $0,1,\ldots,6$。
• 每個 bucket 容量為 $1$，因此一個位置只能存放一個元素。
• 採用 open addressing 時，發生碰撞後必須依照探測公式尋找下一個空位置。
• 線性探測公式：

$$p_i(x)=(h(x)+i)\bmod 7,\qquad i=0,1,2,\ldots$$

• Double hashing 公式：

$$p_i(x)=\bigl(h_1(x)+i\cdot h_2(x)\bigr)\bmod 7$$

其中本題為：

$$h_1(x)=x\bmod 7,\qquad h_2(x)=\left\lfloor\frac{x}{7}\right\rfloor+1$$

計算出的探測位置已經連續探測 $7$ 個位置仍無空位時，才算 overflow。

---

解題方法

依照鍵值給定的順序：

$$15,\ 17,\ 8,\ 23,\ 3,\ 5$$

每插入一個鍵值，就先計算其初始位置；若該位置已被占用，再依指定的探測方法逐一尋找空位，並記錄每一步的表格狀態。

---

(A) $h(x)=x\bmod 7$，線性探測

1. 插入 $15$

$$h(15)=15\bmod 7=1$$

位置 $1$ 為空，直接放入。

索引	0	1	2	3	4	5	6
內容	—	15	—	—	—	—	—

---

2. 插入 $17$

$$h(17)=17\bmod 7=3$$

位置 $3$ 為空，放入位置 $3$。

索引	0	1	2	3	4	5	6
內容	—	15	—	17	—	—	—

---

3. 插入 $8$

$$h(8)=8\bmod 7=1$$

位置 $1$ 已有 $15$，線性探測下一格：

$$(1+1)\bmod 7=2$$

位置 $2$ 為空，將 $8$ 放入位置 $2$。

索引	0	1	2	3	4	5	6
內容	—	15	8	17	—	—	—

---

4. 插入 $23$

$$h(23)=23\bmod 7=2$$

探測過程：

• 位置 $2$：已有 $8$
• 位置 $3$：已有 $17$
• 位置 $4$：為空

因此將 $23$ 放入位置 $4$。

索引	0	1	2	3	4	5	6
內容	—	15	8	17	23	—	—

---

5. 插入 $3$

$$h(3)=3\bmod 7=3$$

探測過程：

• 位置 $3$：已有 $17$
• 位置 $4$：已有 $23$
• 位置 $5$：為空

因此將 $3$ 放入位置 $5$。

索引	0	1	2	3	4	5	6
內容	—	15	8	17	23	3	—

---

6. 插入 $5$

$$h(5)=5\bmod 7=5$$

探測過程：

• 位置 $5$：已有 $3$
• 位置 $6$：為空

因此將 $5$ 放入位置 $6$。

索引	0	1	2	3	4	5	6
內容	—	15	8	17	23	3	5

(A) 結果

所有鍵值皆成功插入，沒有 overflow。

$$\boxed{[\,-,\ 15,\ 8,\ 17,\ 23,\ 3,\ 5\,]}$$

---

(B) Double hashing

本題使用：

$$h_1(x)=x\bmod 7$$ $$h_2(x)=\left\lfloor\frac{x}{7}\right\rfloor+1$$

探測公式為：

$$p_i(x)=\bigl(h_1(x)+i\cdot h_2(x)\bigr)\bmod 7$$

---

1. 插入 $15$

$$h_1(15)=1,\qquad h_2(15)=\left\lfloor\frac{15}{7}\right\rfloor+1=3$$

初始位置為：

$$p_0(15)=1$$

位置 $1$ 為空，放入 $15$。

核心觀念

本題要求計算有向加權圖中任意兩點間的最短距離，適合使用 Floyd–Warshall 全點對最短路徑演算法。

圖中的有向邊如下：

• $A\to B=5,\ A\to C=2$
• $B\to C=-4,\ B\to D=2,\ B\to E=3$
• $C\to F=2$
• $D\to A=-1,\ D\to G=1$
• $E\to D=-5,\ E\to F=4,\ E\to G=3$
• $F\to G=3$

Floyd–Warshall 的遞迴公式為：

$$D^{(k)}[i][j] = \min\left( D^{(k-1)}[i][j], D^{(k-1)}[i][k]+D^{(k-1)}[k][j] \right)$$

其中 $D^{(k)}[i][j]$ 表示允許經過前 $k$ 個節點作為中繼點時，從 $i$ 到 $j$ 的最短距離。

節點順序採用：

$$A,\ B,\ C,\ D,\ E,\ F,\ G$$

---

解題方法

以 $\infty$ 表示目前沒有路徑。初始矩陣 $D^{(0)}$ 只填入直接邊：

$$\begin{array}{c|rrrrrrr} & A&B&C&D&E&F&G\\ \hline A&0&5&2&\infty&\infty&\infty&\infty\\ B&\infty&0&-4&2&3&\infty&\infty\\ C&\infty&\infty&0&\infty&\infty&2&\infty\\ D&-1&\infty&\infty&0&\infty&\infty&1\\ E&\infty&\infty&\infty&-5&0&4&3\\ F&\infty&\infty&\infty&\infty&\infty&0&3\\ G&\infty&\infty&\infty&\infty&\infty&\infty&0 \end{array}$$

經過 $A$ 作為中繼點

可改善：

$$D\to B=-1+5=4$$ $$D\to C=-1+2=1$$

經過 $B$ 作為中繼點

可改善：

$$A\to C=\min(2,5-4)=1$$ $$A\to D=5+2=7$$ $$A\to E=5+3=8$$ $$D\to C=\min(1,4-4)=0$$ $$D\to E=4+3=7$$

經過 $C$ 作為中繼點

因為 $C\to F=2$，可得：

$$A\to F=1+2=3$$ $$B\to F=-4+2=-2$$ $$D\to F=0+2=2$$

再利用 $F\to G=3$：

$$A\to G=3+3=6$$ $$B\to G=-2+3=1$$ $$D\to G=2+3=5$$

經過 $D$ 作為中繼點

利用 $D\to A=-1$，可得：

$$B\to A=2-1=1$$

利用 $D\to E=7$，可得：

$$B\to E=2+7=9$$

其餘路徑沒有比目前結果更短。

核心觀念

DTW（動態時間扭曲）要在所有符合起點、終點與步長限制的路徑中，找出累積局部成本最低的一條路徑。每一步可由上方、左方或左上方的格子前進，因此可以用動態規劃逐格計算最小累積成本。

本題的局部成本為

$$c(x_i,y_j)=\sqrt{(x_i-y_j)^2}=|x_i-y_j|$$

令 $D(i,j)$ 表示從 $(1,1)$ 到 $(i,j)$ 的最小累積成本，則遞迴式為

$$D(i,j)=c(x_i,y_j)+\min\{D(i-1,j),D(i,j-1),D(i-1,j-1)\}$$

其中上方、左方、左上方分別對應步長 $(1,0)$、$(0,1)$、$(1,1)$。第一列與第一行只能沿著邊界前進，需依序累加成本。

解題方法

$x=[1,2,4,1]$，$y=[1,5,4,2]$。先計算每對元素的局部成本，得到成本矩陣：

$$\begin{array}{c|cccc} & y_1=1 & y_2=5 & y_3=4 & y_4=2\\ \hline x_1=1 & 0 & 4 & 3 & 1\\ x_2=2 & 1 & 3 & 2 & 0\\ x_3=4 & 3 & 1 & 0 & 2\\ x_4=1 & 0 & 4 & 3 & 1 \end{array}$$

從左上角開始填入累積成本表。第一列和第一行只能沿邊界累加，例如 $D(1,2)=0+4=4$，$D(2,1)=0+1=1$。其餘格子使用遞迴式，例如：

$$D(2,2)=3+\min\{D(1,2),D(2,1),D(1,1)\} =3+\min\{4,1,0\}=3$$