109 年 國立成功大學電機工程學系碩士班已組《資料結構》

錯誤敘述與更正

• (C) $n^{10}+1.1^{n}=O(n^{10})$
  • $1.1^{n}$ 為指數函數，漸近上界超過任何多項式，故 $n^{10}+1.1^{n}= \Theta(1.1^{n})\not=O(n^{10})$。
  • 更正：$n^{10}+1.1^{n}=O(1.1^{n})$（亦可寫成 $\Omega(1.1^{n})$）。

核心觀念

本題考查遞迴與迭代的效率比較，以及 Fibonacci 數列的遞迴定義：

$$F_n=F_{n-1}+F_{n-2},\qquad F_0=F_1=1$$

直接依照數學定義撰寫的遞迴函式，會重複計算大量相同的子問題。例如計算 $F_5$ 時，$F_3$ 會在不同分支中被重複計算。

此外，$F_{500}$ 的數值非常大，已超過 C 語言一般整數型別的表示範圍，因此必須使用大數表示法，不能直接以 int、long 或 unsigned long long 儲存。

解題方法

應採用迭代法，由小到大依序計算：

$$F_0=1,\quad F_1=1$$

接著使用兩個變數保存前兩項：

$$F_2=F_1+F_0$$ $$F_3=F_2+F_1$$

一般而言，第 $i$ 次迭代計算：

$$F_i=F_{i-1}+F_{i-2}$$

計算完成後，最後一個變數即為 $F_{500}$。

若使用可儲存大數的陣列，關鍵程式架構如下：

核心觀念

完整二元樹以陣列儲存時，若採用 1 起始索引：

• 節點 $i$ 的左子節點為 $2i$
• 右子節點為 $2i+1$
• 最後一個非葉節點為 $\lfloor n/2 \rfloor$

最大堆積（max heap）須滿足：每個父節點值皆大於或等於其子節點值。

本題共有 $n=10$ 個元素，因此從第 $\lfloor 10/2 \rfloor=5$ 個節點開始，反向執行下沉調整（sift-down）。

解題方法

原始陣列為：

$$[10,\ 9,\ 20,\ 6,\ 15,\ 48,\ 14,\ 8,\ 90,\ 17]$$

調整第 5 個節點

第 5 個節點為 $15$，其子節點為第 10 個節點 $17$。

因為 $17>15$，交換兩者：

$$[10,\ 9,\ 20,\ 6,\ 17,\ 48,\ 14,\ 8,\ 90,\ 15]$$

調整第 4 個節點

第 4 個節點為 $6$，子節點為 $8$ 與 $90$，取較大者 $90$ 交換：

$$[10,\ 9,\ 20,\ 90,\ 17,\ 48,\ 14,\ 8,\ 6,\ 15]$$

調整第 3 個節點

第 3 個節點為 $20$，子節點為 $48$ 與 $14$，取較大者 $48$ 交換：

$$[10,\ 9,\ 48,\ 90,\ 17,\ 20,\ 14,\ 8,\ 6,\ 15]$$

調整第 2 個節點

第 2 個節點為 $9$，子節點為 $90$ 與 $17$，取較大者 $90$ 交換：

$$[10,\ 90,\ 48,\ 9,\ 17,\ 20,\ 14,\ 8,\ 6,\ 15]$$

核心觀念

本題考查兩個重點：

1. Quick sort 的最壞時間複雜度與 partition 後的子問題大小有關。
2. Sorting algorithm 的穩定性（stable sorting）。

若排序前有兩筆資料的排序鍵相同，穩定排序會保留它們原本的相對順序。

---

(a) Quick sort 最壞情況

解題方法

Quick sort 每次選定一個 pivot，將資料分成：

• pivot 左側：小於 pivot 的元素
• pivot
• pivot 右側：大於 pivot 的元素

理想情況是每次平均分割，遞迴式為：

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

因此時間複雜度為：

$$\Theta(n\log n)$$

最壞情況發生在每次 partition 都極度不平衡，使其中一個子陣列大小為 $0$，另一個大小為 $n-1$。此時：

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

展開可得：

$$\begin{aligned} T(n) &=T(n-1)+cn\\ &=T(n-2)+c(n-1)+cn\\ &=\cdots\\ &=T(1)+c(2+3+\cdots+n) \end{aligned}$$

而：

$$2+3+\cdots+n=\Theta(n^2)$$

所以：

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

造成最壞情況的條件

當每次選出的 pivot 都是目前子陣列中的最小值或最大值時，partition 會產生大小為 $0$ 與 $n-1$ 的兩個子問題。

典型例子如下：

• 資料已經遞增排列，而每次選第一個元素作為 pivot。
• 資料已經遞增排列，而每次選最後一個元素作為 pivot。
• 資料已經遞減排列，而 pivot 固定選在開頭或結尾。
• 資料排列方式使固定的 pivot 選擇規則每次都選到極端值。
• 即使資料不是已排序，只要 pivot 在每一層遞迴都接近最小值或最大值，也會產生相同結果。

例如資料為：

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

若每次選第一個元素 $1$ 作為 pivot，則每次分割結果為：

$$0 \quad\text{與}\quad 5$$

接著依序形成：

$$0+5,\quad 0+4,\quad 0+3,\quad \ldots$$

partition 每層仍需掃描目前的資料，因此總成本為：

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

【答案】

Quick sort 的最壞情況發生在每次 partition 都產生極度不平衡的分割，即一邊有 $0$ 個元素，另一邊有 $n-1$ 個元素。此時遞迴式為：

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

因此最壞時間複雜度為：

$$\boxed{\Theta(n^2)}$$

---

(b) 穩定的排序演算法

判斷原則

判斷穩定性時，觀察排序過程是否可能交換兩筆「排序鍵相同、但原始順序不同」的資料。

標準實作下：

核心觀念

本題考查最小成本生成樹（Minimum Spanning Tree, MST）的定義與性質：

• 生成樹必須包含所有頂點、無環且有 $|V|-1$ 條邊。
• 最小成本生成樹是所有生成樹中邊權總和最小者。
• MST 不一定唯一；只有在邊權皆相異等條件下，才能保證唯一。
• MST 上兩點間的路徑只保證屬於某棵最小生成樹，不保證是全圖中的最短路徑。
• 若刪除某條邊後，最小生成樹成本上升，表示原本所有最小生成樹都必須使用該邊。

解題方法

逐一檢驗各敘述，對錯誤敘述提供反例，對正確敘述利用生成樹集合的包含關係證明。

---

(a) Minimal cost spanning tree of $G$ is unique.

錯誤。

題目沒有給定所有邊的權重皆相異，因此最小生成樹不一定唯一。

例如，考慮三角形圖：

$$V=\{A,B,C\}$$

且三條邊權重皆為 $1$：

$$w(AB)=w(BC)=w(AC)=1$$

任取其中兩條邊即可形成生成樹，而且總成本皆為

$$1+1=2$$

因此共有三棵最小生成樹，並非唯一。

最小生成樹唯一的充分條件之一，是圖中所有邊的權重皆相異。

---

(b) The path from vertex $A$ to vertex $B$ on a minimal cost spanning tree of $G$ is a shortest path from $A$ to $B$.

錯誤。

MST 最小化的是「涵蓋所有頂點的總成本」，而最短路徑問題最小化的是「兩個指定頂點之間的路徑成本」。兩者的最佳化目標不同。

反例如下：

$$w(AB)=1,\qquad w(BC)=1,\qquad w(AC)=1.5$$

考慮以 $AB$ 與 $BC$ 組成的生成樹，其總成本為

$$1+1=2$$

而其他生成樹的成本為

$$1+1.5=2.5$$

所以 $AB$ 與 $BC$ 組成唯一的 MST。在這棵 MST 上，從 $A$ 到 $C$ 的路徑為

$$A\to B\to C$$

其成本為

$$1+1=2$$

(a) AVL 插入過程與旋轉

插入次序	變化說明	旋轉類型
27	成為根節點	–
49	49 為 27 的右子	–
17	17 為 27 的左子	–
20	20 為 17 的右子；平衡因子仍在 $[-1,1]$	–
61	61 為 49 的右子；仍平衡	–
23	23 為 20 的右子，導致節點 17 平衡因子 $-2$（右‑右） → 左旋於 17	左旋 (LL)
92	92 為 61 的右子，導致節點 49 平衡因子 $-2$（右‑右） → 左旋於 49	左旋 (LL)
33	33 為 49 的左子；仍平衡	–
77	77 為 92 的左子；仍平衡	–