113 年 國立成功大學工程科學系碩士班乙組《資料結構》

核心觀念

• 結構化程式設計（Structured Programming） 與 Böhm-Jacopini 定理：1966 年由 Corrado Böhm 與 Giuseppe Jacopini 提出「結構化程式定理」（Structured Program Theorem），證明任何可計算的演算法（Computable Algorithm），皆可僅憑三種基本的控制結構（Control Structures / Programming Structures）組合實現，無需使用 goto 等無條件跳躍指令。
• 三種基本程式結構：
  1. 順序結構（Sequence Structure）
  2. 選擇結構 / 條件結構（Selection / Decision Structure）
  3. 重複結構 / 迴圈結構（Repetition / Iteration Structure）
• 控制流程特性：三大結構皆嚴格遵循「單一入口、單一出口（Single-Entry, Single-Exit）」原則，確保程式碼結構清晰、易於追蹤與維護。

---

解題方法

本題為配分 15 分的簡答觀念題，切入點應清晰說明三大基本結構的定義、執行流程、程式範例與時間複雜度分析。

1. 順序結構 (Sequence Structure)

• 定義：程式碼按照撰寫的實體順序，由上至下、由前至後依序執行，每一道指令執行完畢後自動進入下一道指令。
• 控制流程：指令 A $\rightarrow$ 指令 B $\rightarrow$ 指令 C。中間無任何分支或跳躍。
• 程式碼範例（C 語言）：

  int a = 5;       // 步驟 1：變數初始化
  int b = 10;      // 步驟 2：變數初始化
  int sum = a + b; // 步驟 3：算術運算
  

• 時間複雜度：包含固定的 $k$ 個順序指令區塊，時間複雜度為 $\mathcal{O}(1)$。

2. 選擇結構 (Selection / Decision Structure)

• 定義：根據特定條件式（Boolean Expression）評估為真（True）或假（False），決定程式執行流程走向不同的分支路徑。
• 控制流程：在決策點進行路徑分流（如 if-else、switch-case）。
• 程式碼範例（C 語言）：

  if (score >= 60) {
      printf("Pass\n");    // 條件成立（True）執行的分支
  } else {
      printf("Fail\n");    // 條件不成立（False）執行的分支
  }
  

• 時間複雜度：取決於各分支中耗時最大者。若 True 分支時間複雜度為 $\mathcal{O}(f(n))$，False 分支為 $\mathcal{O}(g(n))$，則整體時間複雜度為 $\mathcal{O}(\max(f(n), g(n)))$。

3. 重複結構 (Repetition / Iteration Structure)

核心觀念

本題考查**一般樹（General Tree）的結構特性、節點數 $N$ 與樹高（Height, $h$）**之間的極限關係。關鍵定義說明如下：

1. 一般樹（General Tree）的定義：與二元樹（Binary Tree）不同，一般樹對節點的分支度（Degree）完全沒有限制，單一節點可擁有任意數量的子節點（Degree 可為 $0$ 至 $N-1$ 的任意整數）。
2. 樹高（Height）的兩種學術定義：
   • 定義一：以邊數（Edges）計算（根節點高度計為 $0$）
     樹高 $h$ 定義為從根節點（Root）至最深葉節點（Leaf）的最長路徑邊數。
   • 定義二：以節點數（Nodes / Levels）計算（根節點高度計為 $1$）
     樹高 $h$ 定義為從根節點（Root）至最深葉節點（Leaf）的最長路徑節點數。

---

解題方法

設一般樹 $T_1$ 的總節點數為 $N = 101$。欲求樹高 $h$ 的所有可能解答，需透過極端樹型結構分析其最小高度 $h_{\min}$ 與最大高度 $h_{\max}$：

1. 最小樹高 $h_{\min}$（最扁平樹型 / 星狀樹 Star Tree）

當所有非根節點（$100$ 個節點）皆直接掛載於根節點下方時，樹型達到最扁平狀態（根節點的分支度為 $100$）：

• 若採「邊數定義」：最長路徑包含 $1$ 條邊，故最小樹高：
  $h_{\min} = 1$
• 若採「節點數定義」：最長路徑包含 $2$ 個節點（根節點與葉節點），故最小樹高：
  $h_{\min} = 2$

2. 最大樹高 $h_{\max}$（最傾斜樹型 / 鏈狀樹 Skewed Tree）

當每一個非葉節點均只有 $1$ 個子節點時，101 個節點會連成單一直線鏈狀結構：

• 若採「邊數定義」：$N$ 個節點組成的鏈狀樹包含 $N - 1$ 條邊，故最大樹高：
  $h_{\max} = 101 - 1 = 100$
• 若採「節點數定義」：最長路徑經過全部 101 個節點，故最大樹高：
  $h_{\max} = 101$

核心觀念

本題考查**完全二元樹（Complete Binary Tree）的結構特性與樹高（Height）**的數學推導證明。

1. 完全二元樹（Complete Binary Tree）之定義：
   高度為 $h$ 的二元樹，若其第 $1$ 層至第 $h-1$ 層皆填滿節點（即滿二元樹 Full Binary Tree 的狀態），且第 $h$ 層（最底層）的所有節點皆從最左側開始連續排列，則稱此樹為完全二元樹。
2. 樹高與節點數之關係：
   經典資料結構教科書對「樹高（Height）」的起算點有兩種常見定義：
   • 定義一（以邊數 Edge 計算）：單一根節點高度為 $0$，空樹高度為 $-1$。
   • 定義二（以層數 Level / 節點數 Node 計算）：單一根節點高度為 $1$，空樹高度為 $0$。

---

解題方法

設二元樹的總節點數為 $n = 101$。根據題目要求「若有多個答案，請全部寫出」，以下針對兩種主流樹高定義分別進行數學證明與計算：

情況一：以「路徑邊數（Edges）」定義樹高（根節點高度為 0）

• 證明推導：
  設樹高為 $h$（$h \ge 0$）。

  • 高度為 $h$ 的完全二元樹，其節點數最小值發生於「高度 $h-1$ 之滿二元樹再加上 $1$ 個第 $h$ 層的節點」：
    $n_{\min} = (2^h - 1) + 1 = 2^h$
  • 其節點數最大值發生於「高度為 $h$ 之滿二元樹」：
    $n_{\max} = 2^{h+1} - 1$
    因此，高度為 $h$ 的完全二元樹節點數 $n$ 必須滿足以下不等式：
    $2^h \le n \le 2^{h+1} - 1 < 2^{h+1}$
    不等式兩邊取以 $2$ 為底的對數 $\log_2$：
    $h \le \log_2 n < h + 1$
    由高斯取整函數（無條件捨去）可知高度 $h$ 的一般解公式為：
    $h = \lfloor \log_2 n \rfloor$

• 計算步驟：
  將 $n = 101$ 代入公式：
  $h = \lfloor \log_2 101 \rfloor$
  因為 $2^6 = 64 \le 101 < 128 = 2^7$，取對數可得 $6 \le \log_2 101 < 7$（$\log_2 101 \approx 6.658$）。
  故 $h = \lfloor 6.658 \rfloor = 6$。

---

情況二：以「層數／節點數（Levels / Nodes）」定義樹高（根節點高度為 1）

• 證明推導：
  設樹高（總層數）為 $h$（$h \ge 1$）。
  • 高度為 $h$ 的完全二元樹，其節點數最小值發生於「第 $1$ 至 $h-1$ 層皆填滿，且第 $h$ 層僅有 $1$ 個節點」：

核心觀念

AVL 樹是一種自我平衡的二元搜尋樹，必須同時符合：

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

定義節點的平衡因子為：

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

AVL 樹要求：

$$BF(v)\in\{-1,0,1\}$$

插入新值後，若某節點的平衡因子變成 $2$ 或 $-2$，就必須透過旋轉恢復平衡。常見情況如下：

• LL：對失衡節點做右旋。
• RR：對失衡節點做左旋。
• LR：先對失衡節點的左子節點左旋，再對失衡節點右旋。
• RL：先對失衡節點的右子節點右旋，再對失衡節點左旋。

---

解題方法

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

$$12,\ 1,\ 5,\ 3,\ 7,\ 6,\ 4,\ 16,\ 13$$

每次插入後，從新節點往根節點方向檢查平衡因子；若出現失衡，立即旋轉。

---

逐步插入結果

1. 插入 12

樹為單一節點：

12

---

2. 插入 1

$1<12$，因此插入至 $12$ 的左子樹。

  12
 /
1

各節點平衡，無須旋轉。

---

3. 插入 5

依二元搜尋樹規則：

• $5<12$，往左走。
• $5>1$，插入至 $1$ 的右子樹。

原本形成：

  12
  /
 1
  \
   5

此時節點 $12$ 的左子樹較高，且新增節點位於左子節點 $1$ 的右側，屬於 LR 型失衡。

先對 $1$ 左旋：

   12
   /
  5
 /
1

再對 $12$ 右旋：

   5
  / \
 1  12

---

4. 插入 3

依序比較：

• $3<5$，往左走。
• $3>1$，插入至 $1$ 的右子樹。

   5
  / \
 1  12
  \
   3

各節點平衡，無須旋轉。

---

5. 插入 7

依序比較：

• $7>5$，往右走。
• $7<12$，插入至 $12$ 的左子樹。

   5
  / \
 1   12
  \  /
   3 7

各節點平衡，無須旋轉。

---

6. 插入 6

依序比較：

• $6>5$，往右走。
• $6<12$，往左走。
• $6<7$，插入至 $7$ 的左子樹。

插入後：

    5
   / \
  1   12
   \  /
    3 7
      /
     6

節點 $12$ 的左子樹高度為 $2$，右子樹高度為 $0$，因此：

$$BF(12)=2$$

新增節點位於 $12$ 的左子樹之左側，屬於 LL 型失衡，對 $12$ 做右旋：

    5
   / \
  1   7
   \ / \
   3 6 12

---

7. 插入 4

依序比較：

• $4<5$，往左走。
• $4>1$，往右走。
• $4>3$，插入至 $3$ 的右子樹。

插入後暫為：

    5
   / \
  1   7
   \ / \
   3 6 12
    \
     4

節點 $1$ 的右子樹高度為 $2$，左子樹高度為 $0$：

$$BF(1)=-2$$

新增節點位於右子節點 $3$ 的右側，屬於 RR 型失衡，對 $1$ 做左旋：

核心觀念

AVL 樹是一種自我平衡的二元搜尋樹，必須同時符合：

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

定義節點的平衡因子為：

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

AVL 樹要求：

$$BF(v)\in\{-1,0,1\}$$

插入新值後，若某節點的平衡因子變成 $2$ 或 $-2$，就必須透過旋轉恢復平衡。常見情況如下：

• LL：對失衡節點做右旋。
• RR：對失衡節點做左旋。
• LR：先對失衡節點的左子節點左旋，再對失衡節點右旋。
• RL：先對失衡節點的右子節點右旋，再對失衡節點左旋。

---

解題方法

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

$$12,\ 1,\ 5,\ 3,\ 7,\ 6,\ 4,\ 16,\ 13$$

每次插入後，從新節點往根節點方向檢查平衡因子；若出現失衡，立即旋轉。

---

逐步插入結果

1. 插入 12

樹為單一節點：

12

---

2. 插入 1

$1<12$，因此插入至 $12$ 的左子樹。

  12
 /
1

各節點平衡，無須旋轉。

---

3. 插入 5

依二元搜尋樹規則：

• $5<12$，往左走。
• $5>1$，插入至 $1$ 的右子樹。

原本形成：

  12
  /
 1
  \
   5

此時節點 $12$ 的左子樹較高，且新增節點位於左子節點 $1$ 的右側，屬於 LR 型失衡。

先對 $1$ 左旋：

   12
   /
  5
 /
1

再對 $12$ 右旋：

   5
  / \
 1  12

---

4. 插入 3

依序比較：

• $3<5$，往左走。
• $3>1$，插入至 $1$ 的右子樹。

   5
  / \
 1  12
  \
   3

各節點平衡，無須旋轉。

---

5. 插入 7

依序比較：

• $7>5$，往右走。
• $7<12$，插入至 $12$ 的左子樹。

   5
  / \
 1   12
  \  /
   3 7

各節點平衡，無須旋轉。

---

6. 插入 6

依序比較：

• $6>5$，往右走。
• $6<12$，往左走。
• $6<7$，插入至 $7$ 的左子樹。

插入後：

    5
   / \
  1   12
   \  /
    3 7
      /
     6

節點 $12$ 的左子樹高度為 $2$，右子樹高度為 $0$，因此：

$$BF(12)=2$$

新增節點位於 $12$ 的左子樹之左側，屬於 LL 型失衡，對 $12$ 做右旋：

    5
   / \
  1   7
   \ / \
   3 6 12

---

7. 插入 4

依序比較：

• $4<5$，往左走。
• $4>1$，往右走。
• $4>3$，插入至 $3$ 的右子樹。

插入後暫為：

    5
   / \
  1   7
   \ / \
   3 6 12
    \
     4

節點 $1$ 的右子樹高度為 $2$，左子樹高度為 $0$：

$$BF(1)=-2$$

新增節點位於右子節點 $3$ 的右側，屬於 RR 型失衡，對 $1$ 做左旋：

核心觀念

本題考查 Bubble Sort（氣泡排序法） 的基本交換操作。

內層迴圈每次比較相鄰元素 a[j] 與 a[j+1]：

• 若前者大於後者，表示兩者順序錯誤，必須交換。
• 每完成一輪內層迴圈，未排序區間中最大的元素會逐步向右移動，固定在正確位置。
• 外層迴圈控制最多進行 len - 1 輪。

題目未特別指定排序方向，通常以 由小到大排序 為預設。

解題方法

由小到大排序時，正確順序應滿足：

$$a[j] \leq a[j+1]$$

因此，當

$$a[j] > a[j+1]$$

就必須交換兩個相鄰元素。交換時需使用 temp 暫存其中一個值，避免資料遺失。

填入的程式碼為：

if (a[j] > a[j+1]) {
    temp = a[j];
    a[j] = a[j+1];
    a[j+1] = temp;
}

完整程式如下：

void bubble_sort(int a[], int len){
    int i, j, temp;

    for (i=0; i<len-1; i++) {
        for (j=0; j<len-1-i; j++) {
            if (a[j] > a[j+1]) {
                temp = a[j];
                a[j] = a[j+1];
                a[j+1] = temp;
            }
        }
    }
}

正確性說明

假設目前正在進行第 $i$ 輪外層迴圈，內層迴圈處理的範圍為：

$$a[0], a[1], \ldots, a[len-1-i]$$

核心觀念

本題考查經典排序演算法中的**插入排序法（Insertion Sort）**之 C 語言實作與邊界條件控制。

1. 基本原理：插入排序法將陣列劃分為「已排序區域」與「未排序區域」。
   • 初始時，將第一個元素 $a[0]$ 視為長度為 1 的已排序區域。
   • 迴圈變數 $i$ 從 $1$ 遞增至 $\text{len} - 1$，每次取出未排序區域的第一個元素 $a[i]$ 存入暫存變數 $\text{key}$。
   • 在已排序區域 $a[0 \dots i-1]$ 中從右至左進行比對，將所有大於 $\text{key}$ 的元素依次向右移動一格，直到找到適當的插入位置後，將 $\text{key}$ 放入該位置。
2. 演算法特性：
   • 穩定性（Stability）：插入排序法為穩定排序（Stable Sort），比對條件必須使用嚴格大於（$>$），以確保相等元素的相對順序不改變。
   • 原地排序（In-place）：不需要額外開闢陣列空間。

---

解題方法

外部 for 迴圈已將未排序元素存入 key = a[i]，並設定比對起點 j = i。缺漏部分需實現已排序區間的元素的比較與搬移：

1. 建立內部比對迴圈：
   • 使用 while 迴圈向前檢查已排序區間的元素 $a[j-1]$。
   • 迴圈繼續執行的條件包含兩個關鍵邏輯：
     1. 陣列邊界檢查：$j > 0$，確保存取 $a[j-1]$ 時不會發生索引越界（Index Out of Bounds）。
     2. 數值比較：$a[j-1] > \text{key}$，代表前一個元素大於暫存值，需要向右挪動。
2. 元素向右位移：
   • 執行 a[j] = a[j-1];，將較大的元素覆蓋至右側位置。
   • 執行 j--;，將指標向左移動，準備比對下一個元素。
3. 完成插入：
   • 當 while 迴圈結束時，j 即為 key 的正確插入點，執行 a[j] = key;。

完整 C 語言實作程式碼如下：

void insertion_sort(int a[], int len) {
    int i, j, key;
    for (i = 1; i < len; i++) {
        j = i;
        key = a[i];
        
        /* 填空部分開始 */
        while (j > 0 && a[j - 1] > key) {
            a[j] = a[j - 1];
            j--;
        }
        a[j] = key;
        /* 填空部分結束 */
    }
}

---

選項分析

本題為程式填空題，針對填空區塊之邏輯判斷與語法邊界拆解說明如下：

• j > 0 判斷之必要性與順序：
  • 正確：必須擺放在 && 的左側。若 $key$ 為目前已排序區中最小的元素，$j$ 會一路遞減至 $0$。

核心觀念

拓樸排序是將有向圖的頂點排成線性順序，使每條邊 $u\to v$ 都滿足 $u$ 排在 $v$ 前面。只有有向無環圖（DAG）才存在拓樸排序。

解題方法

圖中頂點為 $A$ 至 $M$。關鍵箭線方向是 $F\to K$、$K\to J$、$J\to F$；其餘依圖可整理為 $C\to A,B$、$E\to A,D,F$、$A,B\to D$、$D\to G,H$、$G,H\to I$、$H\to J$、$I\to L$、$J\to L,M$。

三條關鍵邊形成有向環：

$$F\to K\to J\to F$$

若存在拓樸排序，就必須同時滿足 $F$ 在 $K$ 前、$K$ 在 $J$ 前、$J$ 在 $F$ 前，彼此矛盾。因此整張圖不存在拓樸排序。

用「每次取目前入度為 $0$ 的最小字母」執行 Kahn 演算法，可得到以下移除順序：

核心觀念

Prim 演算法從任一頂點開始，每一步選擇「已納入生成樹的頂點」連到「尚未納入頂點」的最小權重邊。這樣逐步擴張，可避免形成環；含 $n$ 個頂點的最小生成樹會有 $n-1$ 條邊。

圖中有 16 個頂點，因此最小生成樹應有 15 條邊。圖中央的交叉處沒有標示頂點，斜線交叉不代表新增頂點。

解題方法

以頂點 $A$ 為起點。每一步列出目前能連到樹外頂點的邊，選取其中權重最小者：

步驟	加入的邊	權重
起點	加入頂點 $A$	—
1	$A-B$	1
2	$A-I$	2
3	$I-H$	8
4	$H-P$	1
5	$H-G$	7
6	$I-J$	9
7	$J-K$	6
8	$G-F$	10
9	$F-E$	5
10	$E-M$	3
11	$M-L$	4
12	$L-D$	4

核心觀念

Prim 演算法從任一頂點開始，每一步選擇「已納入生成樹的頂點」連到「尚未納入頂點」的最小權重邊。這樣逐步擴張，可避免形成環；含 $n$ 個頂點的最小生成樹會有 $n-1$ 條邊。

圖中有 16 個頂點，因此最小生成樹應有 15 條邊。圖中央的交叉處沒有標示頂點，斜線交叉不代表新增頂點。

解題方法

以頂點 $A$ 為起點。每一步列出目前能連到樹外頂點的邊，選取其中權重最小者：

步驟	加入的邊	權重
起點	加入頂點 $A$	—
1	$A-B$	1
2	$A-I$	2
3	$I-H$	8
4	$H-P$	1
5	$H-G$	7
6	$I-J$	9
7	$J-K$	6
8	$G-F$	10
9	$F-E$	5
10	$E-M$	3
11	$M-L$	4
12	$L-D$	4