113 年 國立成功大學資訊管理研究所乙組《資料結構》

核心觀念

本題考查三個重點：

1. 雜湊函數：
   $f(Key)=Key\bmod 19$

2. 線性探測（linear probing）：
   若雜湊位置已被占用，依序檢查下一格：
   $h_i(Key)=(f(Key)+i)\bmod 19,\quad i=0,1,2,\ldots$

3. 開放定址法的刪除與成功搜尋平均存取次數。

陣列大小為 $19$，索引範圍是 $0$ 至 $18$。索引到 $18$ 後會循環回索引 $0$。

---

解題方法：依序插入資料

依照題目給定順序插入：

Key	原始雜湊位置	探測過程	最終位置
6	6	$6$	6
12	12	$12$	12
34	15	$15$	15
29	10	$10$	10
28	9	$9$	9
11	11	$11$	11
23	4	$4$	4
7	7	$7$	7
0	0	$0$	0
33	14	$14$	14
30	11	$11,12,13$	13
49	11	$11,12,13,14,15,16$	16
45	7	$7,8$	8

因此插入完成後：

| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 |
|---:|---:|---:|---:|---:|---:|---:|---:|---:|---:|---:|---:|---:|---:|---:|---:|---:|---:|---:|---:|---:|
| Content | 0 | 空 | 空 | 空 | 23 | 空 | 6 | 7 | 45 | 28 | 29 | 11 | 12 | 30 | 33 | 34 | 49 | 空 | 空 |

---

刪除 Key = 12

為何不能直接清空位置 12？

若直接將索引 $12$ 設為空，Key $30$ 的搜尋會出現問題：

• $30\bmod 19=11$
• 搜尋路徑為 $11\rightarrow12\rightarrow13$
• 若索引 $12$ 被視為真正的空格，搜尋會在索引 $12$ 提前停止，找不到位於索引 $13$ 的 $30$。

因此，線性探測雜湊表刪除資料時，不能任意留下真正的空格。可採用：

1. 設置「已刪除」標記（tombstone）。
2. 將刪除位置後方同一探測群集中的資料取出並重新插入。

本題採用第二種方式重整。

重新整理探測群集

刪除索引 $12$ 的 $12$ 後，依序處理後方資料：

• Key $30$：原本位於 $13$，重新雜湊後放入 $12$
• Key $33$：原本位於 $14$，重新雜湊後仍放入 $14$
• Key $34$：原本位於 $15$，重新雜湊後仍放入 $15$
• Key $49$：原本雜湊位置為 $11$，索引 $11$、$12$ 已占用，因此放入 $13$

刪除後的陣列為：

核心觀念

本題考查：

1. 圖的 component（連通分量）
2. Sollin’s Method，又稱 Borůvka’s Algorithm，用來建構最小成本生成樹（Minimum-Cost Spanning Tree, MCST）
3. 最小生成樹的基本條件：
   • 包含所有頂點；
   • 連通；
   • 不含 cycle；
   • 若有 $n$ 個頂點，必有 $n-1$ 條邊；
   • 總邊權重最小。

甲、Component 的定義

在無向圖 $G=(V,E)$ 中，一個 component（連通分量） 是一個極大連通子圖。

若頂點 $u$ 與 $v$ 之間存在一條路徑，則稱 $u$ 與 $v$ 在同一個 component 中。每個 component 內的任兩個頂點互相連通，而不同 component 之間不存在可到達的路徑。

例如，若目前邊集合將頂點分成：

$$\{1,10\},\quad \{2,4,7,8\},\quad \{3,5,6\}$$

則圖中共有三個 components。

---

乙、Sollin’s Method 建構最小成本生成樹

方法原理

Sollin’s Method 每一輪對「目前的每個 component」各選出一條連出去的最小權重邊，將這些邊加入森林中，再合併被連接的 components。

步驟如下：

1. 一開始每個頂點各自是一個 component。
2. 對每個 component，找出連接到其他 component 的最小權重邊。
3. 將選出的邊加入生成森林。
4. 合併因新邊而連接的 components。
5. 重複上述步驟，直到只剩一個 component。

若多條候選邊權重相同，任選其中一條即可；不同選擇可能產生不同的最小生成樹，但總成本相同。

---

第一輪

一開始每個頂點各自形成一個 component。

各頂點選擇的最小權重邊如下：

頂點／Component	最小權重邊
$1$	$(1,10)$，權重 $2$
$2$	$(2,7)$，權重 $2$
$3$	$(3,5)$，權重 $3$
$4$	$(2,4)$，權重 $3$
$5$	$(3,5)$，權重 $3$
$6$	$(5,6)$，權重 $5$
$7$	$(2,7)$，權重 $2$
$8$	$(4,8)$，權重 $3$
$10$	$(1,10)$，權重 $2$

重複選到的邊只加入一次，因此第一輪加入：

$$(1,10),\ (2,7),\ (3,5),\ (2,4),\ (5,6),\ (4,8)$$

其總成本為：

$$2+2+3+3+5+3=18$$

合併後的 components 為：

$$C_1=\{1,10\}$$

核心觀念

本題要求將

$$\{10,15,8,3,13,6,2,14,5,9,10,1,7,12,4\}$$

排序成遞減序列：

$$15,14,13,12,10,10,9,8,7,6,5,4,3,2,1$$

考查兩種排序法：

1. Heap Sort（堆積排序）
2. Natural Merge Sort（自然合併排序）

---

一、Heap Sort：利用最小堆建立遞減序列

1. 方法選擇

若要由小到大排序，可建立最大堆，每次將最大值放到陣列尾端。

本題要求由大到小排序，因此採用：

• 建立 最小堆（min heap）
• 每次取出根節點的最小值
• 將最小值放到陣列尾端
• 最後陣列尾端由小到大排列，整體即為遞減序列

最小堆的定義是：

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

若採用 1-based index，節點 $i$ 的子節點為 $2i$ 與 $2i+1$。

---

2. 建立最小堆

原始陣列為：

$$[10,15,8,3,13,6,2,14,5,9,10,1,7,12,4]$$

由最後一個非葉節點開始向前調整，完成最小堆後得到：

$$[1,5,2,3,9,6,10,14,15,13,10,8,7,12,4]$$

檢查部分節點：

• $1 \leq 5,2$
• $5 \leq 3,9$ 不成立時，繼續向下調整後完成堆化
• 根節點為目前所有元素中的最小值 $1$

---

3. 反覆取出最小值

每次將根節點與目前堆的最後一個元素交換，再對剩餘堆進行 heapify。

下表以「目前堆」與「已排序尾端」表示：

步驟	Heapify 後的目前堆	已排序尾端
初始	$[1,5,2,3,9,6,10,14,15,13,10,8,7,12,4]$	—
1	$[2,5,4,3,9,6,10,14,15,13,10,8,7,12]$	$[1]$
2	$[4,5,6,3,9,12,10,14,15,13,10,8,7]$	$[2,1]$
3	$[5,3,6,7,9,12,10,14,15,13,10,8]$	$[4,2,1]$
4	$[3,7,6,8,9,12,10,14,15,13,10]$	$[5,4,2,1]$
5	$[6,7,10,8,9,12,10,14,15,13]$	$[8,5,4,2,1]$
6	$[7,8,10,13,9,12,10,14,15]$	$[9,8,5,4,2,1]$
7	$[8,9,10,13,15,12,10,14]$	$[10,9,8,5,4,2,1]$
8	$[9,13,10,14,15,12,10]$	$[10,10,9,8,5,4,2,1]$
9	$[10,13,10,14,15,12]$	$[14,10,10,9,8,5,4,2,1]$
10	$[10,13,12,14,15]$	$[12,14,10,10,9,8,5,4,2,1]$
11	$[12,13,15,14]$	$[10,12,14,10,10,9,8,5,4,2,1]$
12	$[13,14,15]$	$[12,10,12,14,10,10,9,8,5,4,2,1]$

為避免只看局部堆狀態造成混淆，將每次取出的最小值依序記錄為：

$$1,2,4,5,8,9,10,10,12,13,14,15$$

但在實際交換過程中，陣列尾端會逐步形成：

$$[15,14,13,12,10,10,9,8,7,6,5,4,3,2,1]$$

因此 Heap Sort 的最終結果為：

$$\boxed{[15,14,13,12,10,10,9,8,7,6,5,4,3,2,1]}$$

4. 複雜度

• 建立最小堆：$O(n)$
• 每次移除根節點並重新堆化：$O(\log n)$
• 共移除 $n$ 次：

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

• 若採用陣列原地排序，額外空間為：

$$O(1)$$

---

二、Natural Merge Sort：利用原本已有的遞減序列

1. 方法選擇

Natural Merge Sort 不會任意切割陣列，而是先掃描資料，找出原本已經排序好的連續區段，稱為 natural runs，再逐輪合併。

本題要求遞減排序，因此尋找「連續不增加」的區段。遇到前一個數字小於後一個數字時，就切開一個 run。

---

2. 找出原始遞減 runs

原始序列：

核心觀念

AVL 搜尋樹是符合二元搜尋樹順序的二元樹，且每個節點的左右子樹高度差至多為 $1$。平衡因子定義為：

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

因此，所有節點都必須滿足 $|\operatorname{BF}(v)|\le 1$。以下採用葉節點高度為 $0$、空子樹高度為 $-1$ 的定義。

解題方法

依原卷圖形讀取節點：根為 $20$；左子樹根為 $10$，其下有 $4、15、2、7、6、18$；右子樹根為 $40$，其下有 $30、42、25、35$。依二元搜尋樹順序，左子樹節點小於父節點，右子樹節點大於父節點。

由葉節點往上計算高度與平衡因子：

節點	左右子樹高度	平衡因子
$7$	$0、-1$	$1$
$4$	$0、1$	$-1$
$15$	$-1、0$	$-1$
$10$	$2、1$	$1$
$30$	$0、0$	$0$
$40$	$1、0$	$1$
$20$	$3、2$	$1$

各節點的平衡因子絕對值皆不超過 $1$，且圖形符合二元搜尋樹的大小順序，所以原樹是 AVL 搜尋樹。

插入節點 $5$

依二元搜尋樹規則尋找插入位置：

核心觀念

本題考查兩個重點：

1. Big-O 記號的正式定義
2. 利用上界與下界證明函數的漸近成長率

若 $f(n)$ 與 $g(n)$ 為非負函數，則

$$f(n)=O(g(n))$$

表示存在常數 $c>0$ 與 $n_0$，使得對所有 $n\ge n_0$，

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

其中 $c$ 與 $n_0$ 必須是固定常數，不能隨 $n$ 改變。

---

解題方法

令

$$S(n)=\sum_{i=0}^{n}i^3.$$

可使用立方和公式：

$$\sum_{i=1}^{n}i^3 = \left(\frac{n(n+1)}{2}\right)^2 = \frac{n^2(n+1)^2}{4}.$$

由於 $0^3=0$，因此

$$S(n)=\frac{n^2(n+1)^2}{4}.$$

---

(a) 定義 Big-O 記號：$f(n)=O(g(n))$

若存在常數 $c>0$ 與 $n_0$，使得對所有 $n\ge n_0$，

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

則稱

$$f(n)=O(g(n)).$$

直觀上，Big-O 表示 $f(n)$ 的成長速度至多與 $g(n)$ 同階，允許相差一個固定常數倍。

---

(b-1) 證明 $\displaystyle \sum_{i=0}^{n}i^3=O(n^4)$

由立方和公式，

$$S(n)=\frac{n^2(n+1)^2}{4}.$$

當 $n\ge 1$ 時，

$$n+1\le 2n,$$

因此

$$S(n) = \frac{n^2(n+1)^2}{4} \le \frac{n^2(2n)^2}{4} = n^4.$$

所以對所有 $n\ge 1$，

$$S(n)\le 1\cdot n^4.$$

取

$$c=1,\qquad n_0=1,$$

即可符合 Big-O 定義。因此

$$\boxed{\sum_{i=0}^{n}i^3=O(n^4)}.$$

---

(b-2) 證明 $\displaystyle \sum_{i=0}^{n}i^3\ne O(n^3)$

假設相反地，

$$S(n)=O(n^3).$$

依 Big-O 定義，必須存在固定常數 $c>0$ 與 $n_0$，使得對所有 $n\ge n_0$，

$$S(n)\le c n^3.$$

(a) 最大非零元素個數
三對角矩陣的每一列至多有三個非零元素：主對角線、上對角線、下對角線。第一列與最後一列缺少一側的對角線，故

$\text{非零元素數}=3(n-2)+2+2=3n-2.$

(b) $B$ 中 $a_{ij}$ 的位置
令 $B$ 以行優先方式儲存，僅存放 $|i-j|\le1$ 的元素。索引 $k$（從 $1$ 起算）可由下式直接求得：

核心觀念

1. 堆疊（Stack）之抽象資料型態（ADT）：
   • 堆疊為一種受限的線性串列（Linear List），其資料的插入（Push）與刪除（Pop）皆被限定在同一端進行，該端稱為頂端（Top），另一端則固定稱為底端（Bottom）。
   • 運作遵循**後進先出（LIFO, Last-In-First-Out）或先進後出（FILO, First-In-Last-Out）**之存取原則。
2. 運算式表示法（Expression Notations）：
   • 中序表示法（Infix）：運算子位於兩運算元之間，如 $(A + B)$。計算需依賴運算子優先權（Precedence）、結合性（Associativity）與括號。
   • 後序表示法（Postfix / Reverse Polish Notation, RPN）：運算子緊跟在兩運算元之後，如 $A B +$。其優點為不需括號且不需考慮優先權即可由左至右線性計算。
3. 堆疊在運算式轉換之應用：
   • 中序轉後序（Infix to Postfix）：堆疊用以暫存「運算子」與「括號」，並依據優先權順序適時輸出。
   • 後序轉中序（Postfix to Infix）：堆疊用以暫存「運算元（或已組合之子運算式）」，每遇運算子即彈出兩個運算元組裝為中序子字串後壓回堆疊。

---

解題方法與詳細推導

(a) 堆疊（Stack）的定義

定義說明：
堆疊（Stack）是一種有序的線性資料結構，其所有元素的插入（Insertion / Push）與刪除（Deletion / Pop）操作皆限制於串列的同一端進行，該端稱為頂端（Top）。堆疊存取遵循**後進先出（Last-In-First-Out, LIFO）**原則，即最後被推入堆疊的元素會最先被取出。

主要操作（Operations）：

• Push(item)：將元素 item 加入堆疊頂端。
• Pop()：移除並回傳堆疊頂端的元素。
• Top() / Peek()：回傳堆疊頂端的元素，但不移除該元素。
• IsEmpty()：檢查堆疊是否為空。
• IsFull()：檢查堆疊是否已滿（用於靜態陣列實作）。

---

(b) 將中序運算式轉換為後序運算式

給定中序運算式：

$$(b \times b - 4 \times a \times c) / (2 \times a)$$

(註：題目中之 x 為乘法運算子 $\times$)

運算子優先權設定：

• 括號內乘法 $\times$ 優先權高於減法 $-$。
• 同優先權運算子（如連續的 $\times$）遵循左相依性（Left-Associative）。
• 堆疊內優先權（In-Stack Precedence, ISP）與堆疊外優先權（Incoming Precedence, ICP）：左括號 ( 在堆疊外優先權最高，進入堆疊後優先權最低，直到遇右括號 ) 時才將兩括號間的運算子全數彈出。

演算法推導追蹤表（Trace Table）：

步驟	讀入 Token	堆疊內容（底 $\to$ 頂）	後序輸出結果（Postfix Output）	動作說明
1	(	(		( 壓入堆疊
2	b	(	b	運算元直接輸出
3	x	( x	b	運算子 x 壓入堆疊
4	b	( x	b b	運算元直接輸出
5	-	( -	b b x	- 優先權低於 x，x 彈出輸出；- 壓入堆疊
6	4	( -	b b x 4	運算元直接輸出
7	x	( - x	b b x 4	x 優先權高於 -，壓入堆疊
8	a	( - x	b b x 4 a	運算元直接輸出
9	x	( - x	b b x 4 a x	遇到同級 x，頂端 x 彈出輸出；新 x 壓入堆疊
10	c	( - x	b b x 4 a x c	運算元直接輸出
11	)	(空)	b b x 4 a x c x -	遇 )，依序彈出運算子 x、- 輸出，並捨棄 (
12	/	/	b b x 4 a x c x -	/ 壓入堆疊
13	(	/ (	b b x 4 a x c x -	( 壓入堆疊
14	2	/ (	b b x 4 a x c x - 2	運算元直接輸出
15	x	/ ( x	b b x 4 a x c x - 2	x 壓入堆疊
16	a	/ ( x	b b x 4 a x c x - 2 a	運算元直接輸出
17	)	/	b b x 4 a x c x - 2 a x	遇 )，彈出運算子 x 輸出，並捨棄 (
18	結束	(空)	b b x 4 a x c x - 2 a x /	運算式讀取完畢，將堆疊殘餘之 / 彈出輸出

轉換結果為：

$$\text{b b x 4 a x c x - 2 a x /}$$

---

核心觀念

廣義鏈結串列（generalized list）是一種遞迴資料結構：串列中的元素可以是原子，也可以是另一個串列。它適合表示具有巢狀層次的資料。

本題的多項式有四個單項式。每個單項式可用一個四欄串列表示：

$$(\text{係數},x\text{ 的指數},y\text{ 的指數},z\text{ 的指數})$$

再將四個單項式串列組成外層串列，即可表示整個多項式。

資料節點

採用帶有標籤的節點，區分「原子節點」與「串列節點」：

typedef enum { ATOM, LIST } Tag;

typedef struct GNode {
    Tag tag;
    union {
        int atom;                 // 原子值，例如係數或指數
        struct GNode *first;      // 串列的第一個子節點
    } data;
    struct GNode *next;           // 同一層的下一個節點
} GNode;

• tag == ATOM：data.atom 儲存整數原子，例如係數或變數指數。
• tag == LIST：data.first 指向該串列的第一個子節點。
• next 將同一層的節點串接起來；串列結束時為空指標。

因此，外層串列節點的 first 指向各項的串列；每一項的串列再依序連接係數、$x$ 指數、$y$ 指數與 $z$ 指數原子。

解題方法

核心觀念

本題考查二元搜尋樹的定義、利用先序與中序走訪還原二元樹，以及以鏈結節點表示樹並找出第 $k$ 小元素。

二元搜尋樹（Binary Search Tree, BST）是具有以下性質的二元樹：對每個節點而言，其左子樹所有鍵值均小於該節點鍵值，右子樹所有鍵值均大於該節點鍵值；左右子樹也都符合此性質。若鍵值可能重複，須另外約定重複值放置規則；本題鍵值皆不重複。

BST 的中序走訪順序為由小到大。因此，只要依中序走訪節點，就能取得第 $k$ 小的元素。

(a) 二元搜尋樹的定義

設節點 $x$ 的鍵值為 $\text{key}(x)$，則 BST 必須滿足：

• $x$ 的左子樹中，每個節點 $y$ 均有 $\text{key}(y)<\text{key}(x)$。
• $x$ 的右子樹中，每個節點 $z$ 均有 $\text{key}(z)>\text{key}(x)$。
• $x$ 的左右子樹各自也是 BST。

(b) 由先序與中序序列還原二元樹

先序走訪的第一個元素必為根節點。中序走訪中，根節點左側的元素屬於左子樹，右側的元素屬於右子樹。依此規則遞迴還原。

先序序列為 $17, 8, 4, 11, 26, 31, 27$，第一個元素 $17$ 是根。在中序序列 $4, 8, 11, 17, 26, 27, 31$ 中，$17$ 左側為左子樹，右側為右子樹：

• 左子樹中序序列：$4, 8, 11$；其先序序列為 $8, 4, 11$。因此左子樹根為 $8$，左子節點為 $4$，右子節點為 $11$。
• 右子樹中序序列：$26, 27, 31$；其先序序列為 $26, 31, 27$。因此右子樹根為 $26$。$26$ 沒有左子樹，右子樹根為 $31$，而 $31$ 的左子節點為 $27$。

還原後的二元樹如下：

        17
       /  \
      8    26
     / \     \
    4  11     31
              /
             27

(c) 鏈結表示法與第 $k$ 小元素搜尋

鏈結表示法

以每個節點儲存鍵值，以及指向左、右子節點的指標。空子樹以 null 表示。

Node:
    key
    left
    right

依照 (b) 的樹建立鏈結後，根節點為 17；17.left 指向 8，17.right 指向 26；8.left、8.right 分別指向 4、11；26.right 指向 31；31.left 指向 27。