113 年 國立成功大學會計學研究所乙組《資料結構》

核心觀念

在資料結構中，樹（tree）是一個：

• 連通（connected）的無向圖；
• 不含任何環（cycle）的圖。

若一棵樹有 $n$ 個頂點，則其邊數必定為：

這是樹的基本定理。

解題方法

可由逐步加入頂點的方式理解：

1. 最初只有 $1$ 個頂點時，不需要任何邊，因此邊數為 $0=1-1$。
2. 每加入一個新頂點，為了維持連通性，必須以 $1$ 條邊將它連接到原本的樹。
3. 每個新增頂點只增加 $1$ 條邊，且不能增加多餘的邊，否則會形成環。

因此，從 $1$ 個頂點增加到 $n$ 個頂點時，共增加 $n-1$ 條邊，所以：

選項分析

核心觀念

本題考查 Bubble Sort（泡沫排序法）的時間複雜度。

泡沫排序會反覆比較相鄰元素，若順序錯誤便交換。對 $n$ 個數字排序時，最多需要進行約 $n$ 個回合：

• 第 1 回合最多比較 $n-1$ 次
• 第 2 回合最多比較 $n-2$ 次
• $\cdots$
• 最後一回合最多比較 $1$ 次

因此，總比較次數為：

展開後為：

在漸進分析中，只保留成長最快的項次，因此：

解題方法

判斷排序演算法的時間複雜度時，觀察其主要的重複操作即可。

Bubble Sort 需要在多個回合中，逐一比較相鄰元素。每個回合的比較次數逐漸減少，但總和仍然是二次函數：

所以 Bubble Sort 的一般時間複雜度為：

補充而言：

• 最壞情況：$O(n^2)$
• 平均情況：$O(n^2)$
• 若採用「沒有發生交換便提前結束」的最佳化版本，最佳情況可為 $O(n)$

核心觀念

本題考查運算式的三種表示法：

• 中序表示法（infix）：運算子位於兩個運算元之間，例如 $4+5$。
• 前序表示法（prefix）：運算子位於運算元之前，例如 $+45$。
• 後序表示法（postfix）：運算子位於運算元之後，例如 $45+$。

後序運算式通常使用堆疊（stack）解析：由左至右讀取，遇到運算元便推入堆疊；遇到運算子便取出最上方的兩個運算元，組合成子運算式。

解題方法

題目給出的後序表示式為：

$45+67*+$

依序解析：

1. 讀取 $4$、$5$，兩者都是運算元。

2. 讀取 $+$，組合為：

   $4+5$

3. 讀取 $6$、$7$。

4. 讀取 $*$，組合為：

   $6*7$

5. 最後讀取 $+$，將前面兩個子運算式相加：

   $(4+5)+(6*7)$

因此其中序表示式為：

$(4+5)+(6*7)$

將此式改寫為前序表示法：

• 最外層運算子為 $+$。
• 左子運算式 $4+5$ 的前序為 $+45$。
• 右子運算式 $6*7$ 的前序為 $*67$。

所以前序表示式為：

$++45*67$

選項分析

• (A) $++45*67$：正確

  其結構為：

  $+(+(4,5),*(6,7))$

  對應的中序表示式是：

在二元最小堆的陣列表示中，父節點 $i$ 必須滿足

$A[i]\le A[2i]\quad\text{且}\quad A[i]\le A[2i+1]$

（若子節點不存在則無須比較）。依序檢查四個選項的每一個父子對：

核心觀念

函式呼叫具有「後進先出」（Last In, First Out, LIFO）的特性，因此使用 Stack（堆疊） 管理函式呼叫。

當函式 $f$ 呼叫函式 $g$ 時：

1. 將 $f$ 的執行狀態、區域變數與返回位址暫存在堆疊中。
2. 執行 $g$。
3. $g$ 結束後，取出最近一次暫存的 $f$ 狀態並返回繼續執行。

若呼叫順序為

則堆疊內容依序為：

$h$ 最先結束並被移除，接著是 $g$，最後是 $f$，符合 LIFO 原則。

解題方法

題目問哪一種資料結構可用來追蹤函式呼叫。判斷關鍵在於：函式呼叫與返回的順序是否符合「最後呼叫的函式最先返回」。

函式呼叫時執行 push，函式返回時執行 pop，因此應使用 Stack。

選項分析

• (A) Queue

此題考查演算法設計的概念，描述「在每一步都只挑選當前看似最佳的選擇，而不考慮所有可能的步驟序列」的演算法類型。

• 貪婪法 (Greedy algorithm)：於每一步決策時，僅根據目前的局部資訊選取當前最有利的決策，期望累積成全局最佳解。不會回溯或列舉所有可能的步驟組合。

核心觀念

本題考查演算法的表示方式與程式實作之間的關係。

演算法通常可分為三個層次：

1. 自然語言描述：以日常語言說明解題步驟，容易理解，但可能產生語意模糊。
2. 虛擬碼（pseudocode）：使用接近程式語言的結構描述演算法，但不受特定程式語言語法限制。
3. 程式語言實作：將演算法轉換成 C、C++、Java、Python 等語言可以執行的程式。

因此，虛擬碼正好扮演自然語言與程式實作之間的中介角色。

解題方法

題幹的關鍵語句是：

provides an intermediate step between a natural language description of the algorithm and an implementation

意思是「在演算法的自然語言描述與程式語言實作之間提供中間步驟」。

符合此定義的名詞是 pseudocode。虛擬碼通常具有以下特徵：

• 使用 IF、WHILE、FOR 等結構表達流程。
• 著重演算法邏輯，不要求符合特定程式語言的完整語法。
• 可在實作前協助設計、檢查與溝通演算法。
• 轉換成實際程式時，通常只需補上特定語言的語法與資料型態細節。

例如，以二分搜尋為例：

自然語言描述：

反覆比較中間元素，若目標值較小，就繼續搜尋左半部；若較大，就搜尋右半部。

虛擬碼描述：

核心觀念

Huffman coding 是一種「由下而上」建立的最佳前綴碼：

1. 每次挑選頻率最小的兩個節點合併。
2. 合併後的新節點，其頻率為兩者之和。
3. 重複合併，直到形成一棵二元樹。
4. 從根節點走到符號，沿途以左分支記為 $0$、右分支記為 $1$。

本題採用頻率較小者置於左側、記為 $0$ 的標準畫法。

解題方法

依頻率由小到大排列：

依序合併兩個最小頻率：

1. 合併 $A$ 與 $B$：

2. 此時最小的兩個節點為 $C$ 與 $D$，合併：

3. 合併 $0.18$ 與 $E$：

4. 合併 $0.27$ 與 $F$：

5. 最後合併 $0.38$ 與 $0.62$：

樹狀結構可表示為：

核心觀念

AVL tree 是一種高度平衡的二元搜尋樹。對於樹中的每一個節點，皆須滿足：

其中：

• $h_L$：左子樹高度
• $h_R$：右子樹高度

因此，任一節點的左右子樹高度差最多為 $1$。此差值稱為該節點的 balance factor：

AVL tree 要求每個節點的 balance factor 必須為 $-1$、$0$ 或 $1$。

解題方法

題目問：

AVL trees work only when all nodes' right and left subtrees differ in heights by at most ____.

關鍵字是 differ in heights by at most，意思是「高度最多相差多少」。

依照 AVL tree 的定義：

所以左右子樹高度差最多為 $1$，正確選項為 (B)。

核心觀念

雜湊（hashing）是利用雜湊函數 $h(k)$，將鍵值 $k$ 對應到雜湊表中的儲存位置：

當兩個不同的鍵值 $k_1$ 與 $k_2$ 經過雜湊函數後，得到相同的儲存格位置時：

此情況稱為「碰撞」（collision）。題目中的 “same cell” 正是指兩個鍵值被映射到雜湊表中的同一個位置。

解題方法

判斷關鍵在於辨認雜湊的專有術語：

1. 題目描述兩個鍵值。
2. 兩者被雜湊函數映射到相同的儲存格。
3. 不同鍵值共用同一個雜湊位置，即符合碰撞的定義。

因此，正確術語是 collision。

碰撞發生後，通常需透過鏈結法（chaining）或開放定址法（open addressing）處理，才能讓不同鍵值同時儲存在雜湊表中。

選項分析

核心觀念

Binary search algorithm（二分搜尋法）是一種在「已排序」資料中尋找特定元素的搜尋演算法。其核心思想是：每次比較搜尋區間的中間元素，依比較結果排除一半不可能的資料，將搜尋範圍縮小為原來的一半。

二分搜尋法必須建立在資料已依遞增或遞減順序排列的前提下。若資料未排序，無法根據大小關係排除一半元素，便不能直接使用此方法。

以遞增排列的陣列為例，搜尋值為 $x$，目前搜尋範圍為索引 $low$ 到 $high$，中間位置為

比較 $A[mid]$ 與 $x$：

• 若 $A[mid]=x$，表示找到目標。
• 若 $A[mid]<x$，目標只可能出現在右半部，因此令 $low=mid+1$。
• 若 $A[mid]>x$，目標只可能出現在左半部，因此令 $high=mid-1$。

每次比較都會捨棄約一半的候選資料。

解題方法

可採用「逐步縮小搜尋區間」的方式說明 Binary search algorithm。

假設有一個遞增陣列：

欲搜尋 $x=42$。

初始搜尋範圍為索引 $0$ 到 $8$：

1. 中間索引為

   $$mid=\left\lfloor\frac{0+8}{2}\right\rfloor=4$$

   $A[4]=25$。因為 $25<42$，所以索引 $0$ 到 $4$ 的元素不可能是答案，搜尋範圍縮小為索引 $5$ 到 $8$。

2. 中間索引為

   $$mid=\left\lfloor\frac{5+8}{2}\right\rfloor=6$$

   $A[6]=42$，因此找到目標。

若搜尋值為 $20$，搜尋過程如下：

• 中間值 $25$ 大於 $20$，保留左半部。
• 中間值 $12$ 小於 $20$，保留右半部。
• 中間值 $17$ 小於 $20$，保留右半部。
• 中間值 $25$ 大於 $20$，搜尋範圍變成空集合，表示 $20$ 不存在於陣列中。

迭代式虛擬碼

BinarySearch(A, n, x):
    low ← 0
    high ← n - 1

    while low ≤ high:
        mid ← low + floor((high - low) / 2)

        if A[mid] = x:
            return mid
        else if A[mid] < x:
            low ← mid + 1
        else:
            high ← mid - 1

    return NOT_FOUND

其中使用

可避免直接計算 $low+high$ 時發生整數溢位。

遞迴式概念

二分搜尋也可以用遞迴方式表示：

完全圖 (Complete graph)

• 定義：在無向單純圖中，若任意兩個不同頂點間皆有唯一邊相連，則此圖稱為完全圖。
• 記號：$K_n$ 表示含 $n$ 個頂點的完全圖。
• 邊數：$|E(K_n)| = \binom{n}{2} = \dfrac{n(n-1)}{2}$。

核心觀念

Splay tree（伸展樹）是一種自我調整的二元搜尋樹。它保持二元搜尋樹的排序性質，但不額外儲存平衡因子或高度資訊；每次搜尋、插入或刪除某個節點後，都會透過旋轉將該節點伸展至根節點。

二元搜尋樹的基本性質為：

• 左子樹所有鍵值小於目前節點。
• 右子樹所有鍵值大於目前節點。
• 伸展操作只改變樹的形狀，不破壞上述排序性質。

伸展樹的核心特色是：

最近被存取的節點會被移至根部，因此具有時間區域性（locality）：近期常被使用的資料，之後再次存取時通常會更快。

伸展操作（Splay Operation）

設要伸展的節點為 $x$，其父節點為 $p$，祖父節點為 $g$。根據 $x$、$p$、$g$ 的相對位置，伸展操作分為三種情況。

1. Zig：$x$ 的父節點就是根

此時只需對 $p$ 與 $x$ 做一次旋轉。

右旋

當 $x$ 是 $p$ 的左子節點時：

左旋

當 $x$ 是 $p$ 的右子節點時，做對稱的左旋，使 $x$ 成為根。

Zig 的成本為 $O(1)$。

2. Zig-Zig：同方向的兩層關係

當 $x$ 與 $p$ 的方向相同時，稱為 Zig-Zig。

左左情況（Left-Left）

若：

• $x$ 是 $p$ 的左子節點；
• $p$ 是 $g$ 的左子節點；

先對 $g$ 做右旋，再對 $p$ 做右旋：

右右情況（Right-Right）

若：

• $x$ 是 $p$ 的右子節點；
• $p$ 是 $g$ 的右子節點；

先對 $g$ 做左旋，再對 $p$ 做左旋，使 $x$ 向上移動兩層。

Zig-Zig 的兩次旋轉方向相同。

3. Zig-Zag：相反方向的兩層關係

當 $x$ 與 $p$ 的方向相反時，稱為 Zig-Zag。

左右情況（Left-Right）

若：

• $x$ 是 $p$ 的右子節點；
• $p$ 是 $g$ 的左子節點；

先對 $p$ 做左旋，再對 $g$ 做右旋。

右左情況（Right-Left）

若：

• $x$ 是 $p$ 的左子節點；
• $p$ 是 $g$ 的右子節點；

先對 $p$ 做右旋，再對 $g$ 做左旋。

Zig-Zag 的兩次旋轉方向相反。

搜尋、插入與刪除

搜尋

搜尋流程與一般二元搜尋樹相同：

1. 從根節點開始比較鍵值。
2. 目標值較小則往左子樹搜尋，較大則往右子樹搜尋。
3. 找到目標節點後，將該節點伸展至根。
4. 若搜尋失敗，通常將最後被訪問的節點伸展至根。

核心觀念

**Divide and conquer algorithm（分治演算法）**是一種將大型問題拆解、遞迴處理，再合併結果的演算法設計方法。其核心流程為：

1. Divide（分割）：將原問題拆成數個規模較小的子問題。
2. Conquer（解決）：以遞迴方式解決各個子問題；當子問題小到可直接處理時，使用基本情況（base case）求解。
3. Combine（合併）：將各子問題的解合併，形成原問題的完整解答。

設原問題規模為 $n$，每次分成 $a$ 個規模約為 $n/b$ 的子問題，分割與合併成本為 $f(n)$，其時間複雜度通常可表示為：

其中：

• $a$：子問題的數量；
• $n/b$：每個子問題的規模；
• $f(n)$：分割與合併所需的時間。

解題方法

判斷一個演算法是否屬於分治法，可依序檢查以下三點：

1. 是否將問題拆成較小子問題

分治法必須把原問題轉換成規模較小、結構相似的子問題。這些子問題通常與原問題具有相同的形式，因此適合使用遞迴處理。

2. 子問題是否可以獨立求解

各子問題通常彼此獨立，一個子問題的解不會直接依賴另一個子問題的中間結果。子問題解完後，再統一進行合併。

3. 是否存在合併步驟

分治法不只是「把問題分開」；還必須將子問題的解組合成原問題的解。例如合併排序先分別排序左右兩半，最後再將兩個已排序的序列合併。

代表例子：合併排序

合併排序（Merge Sort）是最典型的分治演算法。

分割

將長度為 $n$ 的陣列分成左右兩半：

解決

遞迴地將左右兩半排序，直到子陣列只剩一個元素。單一元素本身已經是排序完成的序列，因此是基本情況。

合併

將兩個已排序的子陣列，以雙指標方式逐一比較元素，合併成一個完整的已排序陣列。每一層合併所有元素的總成本為 $O(n)$。

因此其遞迴式為：

由主定理（Master Theorem）：

合併排序的額外空間複雜度通常為：

其他常見分治演算法

二分搜尋

二分搜尋（Binary Search）每次將已排序資料的搜尋範圍縮小一半，只遞迴處理其中一邊：

核心觀念

$d$-Heap（$d$ 元堆積）是二元堆積（binary heap）的推廣：每個內部節點最多擁有 $d$ 個子節點，並且同時滿足：

1. 堆積序性（heap-order property）

   • Min $d$-Heap：父節點鍵值 $\leq$ 所有子節點鍵值。
   • Max $d$-Heap：父節點鍵值 $\geq$ 所有子節點鍵值。

2. 近似完整樹結構

   • 除最後一層外，其餘各層皆填滿。
   • 最後一層的節點由左至右排列。

因此，$d$-Heap 仍可使用陣列儲存，不需要額外儲存指標。

陣列表示法

以 0-based index 儲存 $d$-Heap 時，若節點位於索引 $i$：

• 父節點索引：

• 子節點索引範圍：

其中超出陣列範圍的索引代表不存在的子節點。

若採用 1-based index，則：

• 父節點：

• 子節點：

考試中最常使用 0-based index，因此必須先確認題目所採用的索引方式。

高度與節點數

$d$-Heap 的每個內部節點最多有 $d$ 個子節點，因此高度比二元堆積低。含有 $n$ 個節點的 $d$-Heap 高度為：

在漸進表示法中：

當 $d=2$ 時，$d$-Heap 即為一般的 binary heap。

基本操作與複雜度

插入（Insert）

新元素先放入陣列最後，使完整樹結構維持不變。接著將該元素與父節點比較：

• Min $d$-Heap 中，若子節點小於父節點，便向上交換。
• Max $d$-Heap 中，若子節點大於父節點，便向上交換。

最多交換 $h$ 次，因此時間複雜度為：

取出根節點（Extract-Min / Extract-Max）

根節點是最小值或最大值。移除根節點後，將最後一個元素移到根部，再向下調整：

• Min $d$-Heap 必須在最多 $d$ 個子節點中找出最小者。
• Max $d$-Heap 必須在最多 $d$ 個子節點中找出最大者。

每一層需比較最多 $d$ 個子節點，共有 $O(\log_d n)$ 層，因此時間複雜度為：

核心觀念

AVL tree 是一種自我平衡的二元搜尋樹，對每個節點皆須滿足：

其中平衡因子必須符合：

若插入後某節點的平衡因子為 $2$ 或 $-2$，就必須透過旋轉恢復平衡。

本題依序插入：

並求：

1. 最終 AVL tree。
2. Breadth-first search（廣度優先搜尋，BFS）順序。
3. Internal nodes（內部節點）。

解題方法與插入過程

第一次插入：3

3

插入 2

  3
 /
2

節點 3 的平衡因子為 $1$，仍符合 AVL 條件。

插入 1

    3
   /
  2
 /
1

節點 3 的平衡因子為 $2$，形成 LL case，因此在節點 3 進行右旋：

    3              2
   /              / \
  2      →       1   3
 /
1

目前樹為：

  2
 / \
1   3

插入 4

4 大於 2、大於 3，因此插入為 3 的右子節點：

  2
 / \
1   3
     \
      4

所有節點仍保持平衡。

插入 5

5 大於 2、大於 3、大於 4，因此插入為 4 的右子節點：

  2
 / \
1   3
     \
      4
       \
        5

節點 3 的平衡因子為 $-2$，形成 RR case，在節點 3 左旋：

    3                4
     \              / \
      4     →      3   5
       \
        5

因此整棵樹變為：

    2
   / \
  1   4
     / \
    3   5

插入 6

6 大於 2、大於 4、大於 5，因此插入為 5 的右子節點：

    2
   / \
  1   4
     / \
    3   5
         \
          6

此時節點 2 的平衡因子為 $-2$，形成 RR case，在節點 2 左旋：

請提供題目所提到的圖形（或圖形的文字描述），才能針對第 3 題的 3 個小問給予完整解說與最終答案。

核心觀念

Shellsort（希爾排序）是插入排序的改良版，先使用較大的增量（increment）將元素分組排序，再逐步縮小增量，最後使用增量 $1$ 做完整的插入排序。

本題給定增量集合：

標準執行順序是由大到小：

增量為 $h$ 時，會將索引相差 $h$ 的元素視為同一組，對每一組執行插入排序。

解題方法

原始序列為：

以下採用陣列索引 $0$ 至 $8$。

第一次：增量 $h=7$

相差 $7$ 的元素分組如下：

• 索引 $(0,7)$：$9,2 \rightarrow 2,9$
• 索引 $(1,8)$：$8,1 \rightarrow 1,8$
• 索引 $(2)$、$(3)$、$(4)$、$(5)$、$(6)$：單獨成組，不變

因此序列變為：

第二次：增量 $h=3$

此時依索引分成以下三組：

第 $0$ 組：索引 $0,3,6$

原內容為：

插入排序後：

第 $1$ 組：索引 $1,4,7$

原內容為：

已經排序完成，維持：

第 $2$ 組：索引 $2,5,8$

原內容為：

插入排序後：

將三組結果放回原索引位置：

第三次：增量 $h=1$

核心觀念

• 簡單有向圖（simple directed graph）沒有自迴圈，也沒有重複的有向邊。
• 節點的入度是指向該節點的有向邊數。
• 深度優先搜尋（DFS）沿著尚未造訪的相鄰節點深入，回溯後再搜尋其他分支；搜尋時第一次走到各節點的邊，構成 DFS spanning tree。

解題方法

(1) 圖中沒有自迴圈，也沒有重複的有向邊，因此是簡單有向圖。

(2) 指向 $B$ 的邊只有 $A\to B$，所以 $B$ 的入度為 $1$。

(3) 題目未指定 DFS 起點與鄰接節點的搜尋順序，因此 DFS spanning tree 不唯一。以下採用 $A$ 為起點，並依節點字母順序搜尋：