109 年 國立中山大學資訊管理學系碩士班乙組《資料結構》

插入順序依次為 7、3、11、9、13，得到的 AVL 樹：

      7
    /   \
   3    11
       /  \
      9   13

各節點高度 (leaf 為 1)：

• 3、9、13：1
• 11：$2$ (左、右子樹皆高 1)
• 7：$3$ (左子樹高 1，右子樹高 2)

插入 12
路徑：$7 \rightarrow 11 \rightarrow 13 \rightarrow$ 左子 → 成為 13 的左子。

更新後高度：

核心觀念

本題考查自平衡搜尋樹（Self-Balancing Search Trees）與多元平衡樹（Multi-way Balanced Trees）的樹高（Height / Depth）上界性質。

對於包含 $n$ 個節點的樹狀資料結構：

• 若最壞情況（Worst-case）下的樹高 $h$ 滿足 $h = O(\log n)$，則稱該樹具有對數高度（Logarithmic Height）或對數深度（Logarithmic Depth）。
• 常見的自平衡二元搜尋樹（如 AVL Tree、Red-Black Tree、AA Tree）與多路平衡樹（如 B-Tree 系列），皆透過特定的平衡機制（如旋轉、節點分裂與合併），保證在進行插入與刪除後，樹高始終維持在 $O(\log n)$。

---

解題方法

逐一檢視各樹種在含有 $n$ 個節點時，最壞情況下的樹高（Worst-case Height $h$）之數學推導與定義：

1. AVL Tree：
   定義任一節點的左右子樹高度差（平衡因子 Balance Factor）絕對值不大於 1。
   最壞情況下的最少節點數遞迴式為斐波那契數列型態：
   $N_h = N_{h-1} + N_{h-2} + 1 \implies h < 1.4404 \log_2(n+2) = O(\log n)$

2. Red-Black Tree（紅黑樹）：
   滿足紅黑性質（根與葉為黑、無連續紅節點、各路徑黑色節點數相同）。任一路徑上紅色節點數不超過黑色節點數，最長路徑至多為最短路徑的 2 倍。
   最壞高度滿足：
   $h \le 2 \log_2(n+1) = O(\log n)$

3. AA Tree（AA 樹）：
   由 Arne Andersson 提出，為紅黑樹的簡化變形。AA 樹規定紅色節點只能作為右子節點（等價於消除了紅黑樹中的左傾紅色連結）。此限制使實作旋轉（Skew 與 Split）更為簡潔，其高度依然維持紅黑樹的漸近界限：
   $h = O(\log n)$

4. B-tree of order 4（4 階 B 樹 / 2-3-4 樹）：
   屬於多元平衡搜尋樹，規定所有外部葉節點必須嚴格落在同一深度。每個節點最多有 4 個子節點、至少有 $\lceil 4/2 \rceil = 2$ 個子節點（根節點除外）。

核心觀念

有向無環圖（DAG）的加權最短路徑演算法，會依照拓樸順序處理頂點：每個頂點都在它所有前驅頂點處理完後，才會被宣告為已知並進行邊的鬆弛。這和依目前距離由小到大選頂點的標準加權最短路徑演算法不同。

解題方法

從圖中的箭頭可讀出，從 $V_4$ 出發可到達其餘所有頂點。相關邊包括 $V_4\to V_1$、$V_4\to V_3$、$V_4\to V_6$，以及 $V_1\to V_0$、$V_3\to V_0$、$V_0\to V_2$、$V_3\to V_2$、$V_3\to V_5$、$V_6\to V_5$、$V_5\to V_2$ 等。

圖中沒有由某頂點沿箭頭繞回自身的路徑，因此是有向無環圖。$V_2$ 沒有向外的邊，是唯一的匯點；而它的前驅 $V_0$、$V_3$、$V_5$ 都必須先處理。因此拓樸順序中，$V_2$ 必定最後處理，也就是最後被宣告為已知的頂點。

核心觀念

本題考標準加權最短路徑演算法，也就是 Dijkstra 演算法。每一步都從尚未確定的頂點中，選出目前暫定起點距離最小者，將它標記為「已知」，再用它的出邊更新其他頂點的暫定距離。

解題方法

由圖可讀出，從 $V_4$ 出發的相關有向邊為：$V_4\to V_3$ 權重 $2$、$V_4\to V_6$ 權重 $7$、$V_4\to V_1$ 權重 $10$；另有 $V_3\to V_0$ 權重 $1$、$V_3\to V_2$ 權重 $2$、$V_3\to V_5$ 權重 $8$、$V_3\to V_6$ 權重 $4$，以及 $V_6\to V_5$ 權重 $1$。

依序選出暫定距離最小的頂點：

已知頂點	暫定距離更新	下一個標記為已知的頂點
$V_4$	$d(V_3)=2,\ d(V_6)=7,\ d(V_1)=10$	$V_3$
$V_3$	$d(V_0)=2+1=3,\ d(V_2)=2+2=4,\ d(V_5)=2+8=10,\ d(V_6)=\min(7,2+4)=6$	$V_0$
$V_0$	經 $V_0$ 到 $V_2$ 的距離為 $3+4=7$，不優於目前的 $4$	$V_2$

核心觀念

中序走訪（in-order traversal）的規則是依序走訪「左子樹、根節點、右子樹」。每個子樹也按照相同規則遞迴處理。

解題方法

原圖中，A 是根節點，左子節點為 B、右子節點為 C；C 的左子節點為 D、右子節點為 E。依中序規則，先走訪 A 的左子樹 B，再走訪 A，接著走訪 C 的左子樹 D、C 本身，最後走訪 C 的右子樹 E。

因此，中序走訪結果為 BADCE，題目選項中沒有這個序列。

選項分析

• A. ABCDE：錯誤。 B 是 A 的左子節點，必須先於 A；此選項把 A 排在 B 前面。
• **B. ABDCE：錯誤。

核心觀念

後序走訪的順序是「左子樹、右子樹、根節點」。使用堆疊迭代時，節點會先入堆疊；等左右子樹都處理完，才彈出並輸出。某節點輸出後，便不再留在堆疊中。

解題方法

依圖中的樹，根節點為 $A$；$A$ 的左子節點是 $B$、右子節點是 $C$；而 $C$ 的左、右子節點分別是 $D$、$E$。

按照後序走訪逐步處理：

1. 先將 $A$、$B$ 放入堆疊。$B$ 是葉節點，先輸出 $B$ 並彈出，此時堆疊只剩 $A$。
2. 接著處理 $A$ 的右子樹，將 $C$ 放入堆疊，再將 $D$ 放入堆疊。
3. $D$ 是葉節點，輸出 $D$ 並彈出。此時堆疊中仍有 $A$ 和 $C$。

因此，$D$ 輸出時，堆疊上仍有 $A$、$C$。

核心觀念

本題考查各種排序演算法的「最壞情況時間複雜度」。設待排序資料筆數為 $n$，比較各演算法在最不利輸入下的漸進複雜度：

• $O(n^2)$：平方級
• $O(n\log n)$：線性對數級

當 $n$ 增大時，$n\log n$ 的成長速度低於 $n^2$，因此具有 $O(n\log n)$ 最壞情況複雜度的演算法較佳。

此外，基於比較的排序演算法具有下界：

$$\Omega(n\log n)$$

Merge sort 能達到此下界，因此其最壞情況複雜度為 $\Theta(n\log n)$。

解題方法

逐一判斷各選項的最壞情況複雜度：

• Selection sort：$\Theta(n^2)$
• Merge sort：$\Theta(n\log n)$
• Bubble sort：$\Theta(n^2)$
• Insertion sort：$\Theta(n^2)$
• Quick sort：$\Theta(n^2)$

比較成長率：

$$n\log n < n^2$$

所以最壞情況時間複雜度最低的是 Merge sort。

選項分析

A. Selection sort

Selection sort 每一回合從尚未排序的部分尋找最小值。比較次數為：

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

即使輸入資料原本已排序，仍須完成尋找最小值的掃描，因此最壞情況為 $\Theta(n^2)$。此選項錯誤。

B. Merge sort

Merge sort 先將資料分成兩半，遞迴排序後再合併：

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

其中：

• $2T(n/2)$：分別排序兩個子問題
• $\Theta(n)$：合併兩個已排序序列

由遞迴式可得：

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

核心觀念

完全二元樹（complete binary tree）的特性是：

• 除了最底層外，其餘層皆填滿。
• 最底層的節點由左至右排列。
• 標準定義中，樹高（height）是根節點到最深葉節點的「邊數」，根節點高度為 $0$。

對於含有 $n$ 個節點的完全二元樹，其高度為：

$$h=\lfloor \log_2 n \rfloor$$

其中 $h$ 是最深節點所在的深度。

解題方法

題目給定：

$$n=16384=2^{14}$$

因此：

$$h=\lfloor \log_2 16384 \rfloor =\lfloor 14 \rfloor =14$$

也可以從節點排列理解：

• 深度 $0$ 到深度 $13$ 的節點數為

$$1+2+2^2+\cdots+2^{13}=2^{14}-1=16383$$

• 題目共有 $16384$ 個節點，因此還有 $1$ 個節點位於深度 $14$。
• 根節點到該節點的路徑包含 $14$ 條邊，所以樹高為 $14$。

選項分析

核心觀念

本題考查二元搜尋樹與堆積的結構限制：

• Binary search tree（BST）：左子樹所有鍵值必須小於節點鍵值，右子樹所有鍵值必須大於節點鍵值。
• Max heap：每個父節點鍵值必須大於或等於子節點，即
  $\text{parent} \geq \text{child}$
• Min heap：每個父節點鍵值必須小於或等於子節點，即
  $\text{parent} \leq \text{child}$

解題方法

題目給定父節點鍵值為 $8$，左子節點鍵值為 $10$，直接比較父子節點關係：

$8<10$

再分別套用三種資料結構的規則即可。

選項分析

• A. Binary search tree

  BST 要求左子節點的鍵值小於父節點：

  $10<8$

  此條件不成立，因此不可能是 Binary search tree。

• B. Max heap

  Max heap 要求父節點鍵值大於或等於子節點：

  $8\geq 10$

核心觀念

Quadratic probing（二次探測）用於雜湊碰撞處理。第一次嘗試原始雜湊位置，之後依序加入平方偏移量：

$$\operatorname{Index}_i=(h(K)+i^2)\bmod m,\qquad i=0,1,2,\ldots$$

其中：

• $K$：鍵值
• $h(K)$：原始雜湊位置
• $m$：雜湊表大小
• $i^2$：二次探測的偏移量

本題的雜湊表大小為 $100$。

解題方法

先計算鍵值 $4592$ 的原始雜湊位置：

$$h(4592)=4592\bmod 100=92$$

因此，二次探測的嘗試順序為：

$$\begin{aligned} i=0 &: (92+0^2)\bmod100=92\\ i=1 &: (92+1^2)\bmod100=93\\ i=2 &: (92+2^2)\bmod100=96\\ i=3 &: (92+3^2)\bmod100=101\bmod100=1 \end{aligned}$$

前 3 個位置 $92、93、96$ 已被占用，因此下一個嘗試的位置是 $1$。

核心觀念

本題考查陣列實作堆疊時，採用 array doubling 動態擴充容量後，單次 push 的最壞時間複雜度。

若目前陣列已滿，將容量由 $N$ 擴充為 $2N$，必須：

1. 配置容量為 $2N$ 的新陣列。
2. 將原本 $N$ 個元素逐一複製到新陣列。
3. 將新元素放入堆疊頂端。

其中複製 $N$ 個元素需要 $\Theta(N)$ 時間，因此該次 push 的最壞成本為：

$$\Theta(N)=O(N)$$

解題方法

當陣列尚有空間時，push 只需將元素放入下一個位置，成本為 $O(1)$。

但題目問的是「單次操作的最壞情況」。最壞情況發生在陣列已滿時：

$$\text{原容量}=N \quad\longrightarrow\quad \text{新容量}=2N$$

搬移原有元素的成本為：

$$N \times O(1)=O(N)$$

再加上配置新陣列與插入新元素的成本，總成本仍由複製操作主導：

$$O(N)+O(1)=O(N)$$

因此，單次 push 的最壞時間複雜度是 $O(N)$。

選項分析

核心觀念

使用 header node 的鏈結串列中，header 通常指向一個不存放實際資料的標頭節點。真正的資料節點從 header->next 開始：

• 空串列：header->next == NULL
• 恰有一個資料節點：header->next != NULL，且該節點的 next == NULL
• 有兩個以上資料節點：header->next->next != NULL

恰有一個資料節點時，串列結構如下：

$$\text{header} \rightarrow \text{第一個資料節點} \rightarrow NULL$$

因此判斷條件為：

$$\text{header} \neq NULL \land \text{header->next} \neq NULL \land \text{header->next->next} = NULL$$

解題方法

先排除標頭節點本身，再觀察實際資料節點：

1. header != NULL：確認標頭節點存在。
2. header->next != NULL：確認至少有一個資料節點。
3. header->next->next == NULL：確認第一個資料節點後面沒有其他資料節點。

三個條件同時成立時，代表串列中恰好只有一個資料節點。

選項分析

• A. header != NULL

核心觀念

Huffman coding tree 是用來建立最佳前綴碼（prefix code）的二元樹，目標是最小化加權外部路徑長度：

$$\text{WPL}=\sum_{i=1}^{n} f_i d_i$$

其中 $f_i$ 是第 $i$ 個符號的出現頻率，$d_i$ 是該符號所在葉節點的深度。

標準 Huffman tree 具有以下特徵：

1. 每個資料符號都放在葉節點。
2. 每個內部節點恰有兩個子節點，因此不存在只有一個子節點的節點。
3. 樹不必平衡，形狀會依符號頻率而定。

解題方法

逐一判斷 Huffman tree 的樹結構特性即可。Huffman 演算法每次取出頻率最小的兩個節點合併，形成一個具有兩個子樹的內部節點。因此，最終樹的資料項目位於葉節點，內部節點則負責表示合併後的權重。

Huffman tree 的主要最佳化目標是降低 WPL，而不是維持樹的平衡。頻率越高的符號通常越接近根節點，頻率越低的符號可能位於較深的位置。

選項分析

• A. All items are stored at the leaves

  正確。Huffman coding 是前綴碼，編碼對應到根節點至葉節點的路徑；資料符號必須放在葉節點，內部節點只代表子樹頻率的總和。

核心觀念

本題考查巢狀迴圈的執行次數與漸近複雜度。關鍵在於：

• k 迴圈的範圍會隨著 i、j 改變。
• 迴圈上下界皆包含，因此從 i 到 j 共執行 $j-i+1$ 次。
• 第 6～7 行的迴圈是在第 1～4 行之後執行，不會影響 statement 4 的執行次數。

解題方法

相關程式碼為：

for (int i = 0; i < n; i++)
    for (int j = i; j <= n; j++)
        for (int k = i; k <= j; k++)
            sum++;

固定 $i$ 與 $j$ 時，statement 4 的執行次數為：

$$j-i+1$$

因此總執行次數為：

$$T(n)=\sum_{i=0}^{n-1}\sum_{j=i}^{n}(j-i+1)$$

固定 $i$，令 $r=j-i$，則 $r$ 會從 $0$ 到 $n-i$：

$$\sum_{j=i}^{n}(j-i+1) =\sum_{r=0}^{n-i}(r+1) =\frac{(n-i+1)(n-i+2)}{2}$$

所以：

$$T(n)=\sum_{i=0}^{n-1}\frac{(n-i+1)(n-i+2)}{2}$$

令 $m=n-i$，則 $m$ 從 $n$ 遞減至

題目所對應的程式片段

1  for (int i = 0; i < n; i++)
2      for (int j = i; j <= n; j++)
3          for (int k = i; k <= j; k++)
4              sum++;

5  for (int p = 0; p < n*n; p++)
6      for (int q = 0; q < p; q++)
7          sum--;

第 15 題的 statement 7 是 sum--;，完整題面可見於官方試題第 3 頁：國立中山大學 109 學年度資料結構試題 PDF。

核心觀念

本題考查巢狀迴圈的執行次數分析，尤其要注意內層迴圈的上限會隨外層變數 $p$ 改變。

Big-O 表示成長的上界；若能求出精確次數並得到 $\Theta(N^4)$，即可判定其屬於 $O(N^4)$。

解題方法

令 $N=n$。statement 7 位於第二組巢狀迴圈中：

for (int p = 0; p < N*N; p++)
    for (int q = 0; q < p; q++)
        sum--;

外層變數 $p$ 的取值為

$$p=0,1,2,\ldots,N^2-1$$

固定某一個 $p$ 時，內層變數 $q$ 的取值為

$$q=0,1,2,\ldots,p-1$$

因此 statement 7 對固定的 $p$ 會執行 $p$ 次。總執行次數為

核心觀念

本題考查：

1. 質數判斷的基本定理。
2. 迴圈執行次數的估算。
3. 最壞情況時間複雜度。

若 $n$ 是合成數，必定存在一個因數不大於 $\sqrt{n}$。因此，只需測試 $3$ 到 $\sqrt{n}$ 的奇數因數，即可判斷 $n$ 是否為質數。

---

解題方法

程式的主要迴圈為：

for (int i = 3; i <= squareRoot(n); i += 2)
    if (n % i == 0)
        return false;

迴圈變數依序取：

$$3,5,7,\ldots,\lfloor\sqrt{n}\rfloor$$

只檢查奇數，因此執行次數約為：

$$\frac{\sqrt{n}}{2}$$

忽略常數因子後：

$$T(n)=\Theta(\sqrt{n})$$

也就是：

$$T(n)=O(n^{1/2})$$

最壞情況發生在 $n$ 為奇質數時，因為必須測試所有可能的奇數因數直到 $\sqrt{n}$，迴圈才結束。即使輸入是合成數，只要最小因數較大，也會執行相當多次。

前面的判斷：

if (n == 2 || n == 3)
    return true;

if (n % 2 == 0)
    return false;

都只需固定次數的運算，屬於 $O(1)$，不影響整體最壞情況複雜度。

---

選項分析

• A. $O(1)$：錯誤

核心觀念

遞迴（recursion）是函式在執行過程中再次呼叫自身。每次函式呼叫都必須保存一組執行資訊，稱為 activation record（啟動記錄），內容通常包括：

• 返回位址
• 傳入參數
• 區域變數
• 暫存的執行狀態

這些記錄由系統放在呼叫堆疊（call stack）中管理。Stack 的特性是後進先出（LIFO），正好符合遞迴函式的返回順序：最後呼叫的函式，必須最先完成並返回。

解題方法

假設函式 f(n) 會遞迴呼叫 f(n-1)：

1. 呼叫 f(3)，將 f(3) 的執行資訊放入 Stack。
2. f(3) 呼叫 f(2)，再將 f(2) 放入 Stack。
3. f(2) 呼叫 f(1)，再將 f(1) 放入 Stack。
4. 遇到終止條件後，先完成 f(1)，將其啟動記錄移出 Stack。
5. 接著返回並完成 f(2)、f(3)。

堆疊內容的變化可表示為：

$$f(3) \rightarrow f(2) \rightarrow f(1)$$

返回時則按照：

$$f(1) \rightarrow f(2) \rightarrow f(3)$$

核心觀念

將運算式樹轉成後序式（postfix expression），使用「左子樹、右子樹、根節點」的後序走訪順序。運算元會先輸出，運算子則在其左右運算元之後輸出。

解題方法

圖中的根節點是乘號 *。它的左子樹以加號 + 為根，左右子節點分別是 a、b；右子樹以減號 - 為根，左右子節點分別是 c、d。

依後序走訪：

1. 左子樹輸出：a b +
2. 右子樹輸出：c d -
3. 最後輸出根節點：*

因此後序式為 a b + c d - *，即選項 C 的 ab+cd-*。

選項分析

核心觀念

本題考查中序式（infix expression）與後序式（postfix expression）的轉換，以及運算子的優先順序與結合方向。

• 乘法 * 的優先權高於加法 + 與減法 -。
• 加法與減法優先權相同，採由左至右結合。
• 後序式不使用括號，運算子會放在其兩個運算元之後。

例如：

$$a+b*c=a+(b*c)$$

其後序式為：

$$a\ b\ c\ *\ +$$

解題方法

可使用堆疊逐一讀取後序式：

1. 遇到運算元便放入堆疊。
2. 遇到運算子便取出堆疊最上方的兩個運算元。
3. 先取出的作為右運算元，後取出的作為左運算元。
4. 計算結果再放回堆疊。

其中 a b c * + 的處理為：

• 讀入 a、b、c。
• 遇到 *：取出 b、c，形成 $b*c$。
• 遇到 +：取出 a、$b*c$，形成 $a+(b*c)$。

因此：

$$a\ b\ c\ *\ + \equiv a+(b*c)$$

選項分析

A. $a+b-c$ 與 $a\ b\ c\ -\ +$

由於加、減法同級且由左至右結合：

$$a+b-c=(a+b)-c$$

正確後序式應為：

$$a\ b\ +\ c\ -$$

選項中的 $a\ b\ c\ -\ +$ 代表：

$$a+(b-c)$$

與原中序式不相同，因此錯誤。

核心觀念

本題考查二元搜尋樹（Binary Search Tree, BST）的插入規則與節點深度。

• 小於目前節點的鍵值，插入左子樹。
• 大於目前節點的鍵值，插入右子樹。
• 節點深度（depth）是該節點到根節點所經過的邊數。
• 最深節點是深度最大的節點；深度相同時，屬於並列最深。

解題方法

依序插入 $3,6,5,2,4,7,1$：

1. $3$ 成為根節點。
2. $6>3$，插入 $3$ 的右子節點。
3. $5>3$ 且 $5<6$，插入 $6$ 的左子節點。
4. $2<3$，插入 $3$ 的左子節點。
5. $4>3$、$4<6$、$4<5$，插入 $5$ 的左子節點。
6. $7>3$ 且 $7>6$，插入 $6$ 的右子節點。
7. $1<3$ 且 $1<2$，插入 $2$ 的左子節點。

形成的二元搜尋樹如下：

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

各節點深度為：

$$\operatorname{depth}(3)=0$$ $$\operatorname{depth}(2)=\operatorname{depth}(6)=1$$

核心觀念

最小生成樹是在連通、無向、帶權圖中，選出能連接所有頂點且不形成迴圈的邊，使總權重最小。若圖有 $n$ 個頂點，生成樹必須恰有 $n-1$ 條邊。

解題方法

使用 Kruskal 演算法：將邊依權重由小到大排列，逐一加入不會形成迴圈的邊，直到選滿 $7-1=6$ 條。

依圖中邊權重排序後，選取過程如下：

權重	邊	處理
1	$V_0V_3$	加入
2	$V_0V_1$	加入
3	$V_1V_3$	略過，會形成迴圈
4	$V_0V_2$	加入
5	$V_3V_6$	加入
6	$V_3V_4$	加入

核心觀念

二元搜尋樹（Binary Search Tree, BST）只要求：

• 左子樹所有鍵值小於根節點；
• 右子樹所有鍵值大於根節點；
• 每個子樹本身也符合上述規則。

一般 BST 沒有平衡限制，因此可能退化成一條鏈。

若樹高以「根到最深葉節點的邊數」計算，$N$ 個節點的最大高度為：

$$h_{\max}=N-1$$

若以「層數」計算，最大高度則為 $N$。兩種定義都屬於 $\Theta(N)$，而非 $\Theta(\log N)$。

解題方法

為使 BST 高度最大，讓每個節點都只有一個子節點。例如依遞增順序插入：

$$1,2,3,\ldots,N$$

會形成完全向右的退化樹：

$$1 \rightarrow 2 \rightarrow 3 \rightarrow \cdots \rightarrow N$$

從根節點 $1$ 到最深節點 $N$ 共經過 $N-1$ 條邊，因此：

$$h_{\max}=N-1\approx N$$

所以最大高度是線性成長，不是對數成長。

選項分析

核心觀念

雙端佇列（double-ended queue, deque）允許在「前端」與「後端」進行操作，標準操作及其時間複雜度如下：

• 前端插入：$O(1)$
• 後端插入：$O(1)$
• 取得前端元素：$O(1)$
• 取得後端元素：$O(1)$
• 刪除前端元素：$O(1)$
• 刪除後端元素：$O(1)$

deque 的核心限制是：只能保證兩端操作有效率，並不會依照元素大小排序，也不會自動維護最小值位置。

解題方法

判斷每個選項是否屬於 deque 的標準端點操作：

1. 若操作只涉及前端或後端，通常可在常數時間完成。
2. 若要找出最小元素，必須檢查 deque 中的元素，因為最小值可能位於任意位置。
3. 對含有 $n$ 個元素的 deque，尋找最小值需要逐一比較，時間複雜度為

$$O(n)$$

因此，「取得並刪除最小元素」並非標準 deque 能保證在常數時間完成的操作。

選項分析

A. Insertion at the front or rear item

正確。deque 支援前端與後端插入。

以雙向鏈結串列實作時，只需調整前端或後端指標；以循環陣列實作時，也能透過索引移動完成。因此兩種操作皆可達到

$$O(1)$$

B. Access of the front or rear item

正確。deque 通常維護 front 與 rear 指標，取得兩端元素時可直接存取，不需走訪其他元素，時間複雜度為

$$O(1)$$

核心觀念

Huffman 演算法用於建立最佳前綴碼（optimal prefix code），常應用於資料壓縮。每個字元依出現頻率 $f_i$ 指派不同長度的二元編碼，目標是使加權平均編碼長度最小：

$$L=\sum_{i=1}^{n} f_i l_i$$

其中：

• $f_i$：第 $i$ 個字元的出現頻率或機率
• $l_i$：該字元的編碼長度
• $L$：整體加權編碼長度

Huffman 演算法的核心規則是：每次選出目前頻率最小的兩個節點合併，將合併後的頻率重新放回集合，重複此步驟直到形成完整的二元樹。

這種「每一步都選擇當下最有利選項」的策略，正是 Greedy algorithm（貪心演算法）的特徵。

解題方法

判斷演算法類型時，觀察 Huffman 的決策方式：

1. 將每個字元視為一個節點，權重為其出現頻率。
2. 找出權重最小的兩個節點。
3. 將兩者合併成新節點，新節點權重為兩者權重之和。
4. 將新節點加入集合，繼續選取目前權重最小的兩個節點。
5. 持續合併，直到只剩一個根節點。

例如頻率為 $2,3,7,9$：

• 合併 $2$ 與 $3$，得到 $5$
• 此時集合為 $5,7,9$，合併 $5$ 與 $7$，得到 $12$
• 此時集合為 $9,12$，合併成根節點 $21$

每一步都直接選擇當下頻率最小的兩個節點，沒有列舉所有樹形，也沒有嘗試不同路徑後回溯。因此 Huffman 演算法屬於貪心法。

Huffman 演算法之所以能得到最佳結果，是因為它具有：

• 貪心選擇性質：當下合併兩個最小頻率節點，不會破壞最佳解。
• 最佳子結構：合併後的較小問題，其最佳解可以組成原問題的最佳解。

實作上通常使用最小堆積（min-heap）維護節點，因此時間複雜度為：

$$O(n\log n)$$

空間複雜度為：

$$O(n)$$

選項分析

核心觀念

• Full binary tree（滿二元樹）：每個節點的子節點數量必為 $0$ 或 $2$，不允許只有一個子節點。
• Complete binary tree（完全二元樹）：除了最底層外，其餘層皆填滿；最底層的節點必須由左至右排列。
• Max heap（最大堆積）：除了符合完全二元樹結構外，每個父節點的鍵值皆大於或等於子節點。
• Stack（堆疊）：遵循後進先出（LIFO, Last-In First-Out）。
• Binary search tree（BST，二元搜尋樹）：左子樹所有鍵值小於根節點，右子樹所有鍵值大於根節點。搜尋效率取決於樹高。
• Linked list（鏈結串列）：是一種資料儲存結構，本身不規定資料存取必須遵循 LIFO 或 FIFO。

解題方法

本題為複選題，逐一將各選項與上述定義及時間複雜度比較。

最大堆積的高度為

$$h=\lfloor \log_2 N \rfloor$$

因此，只要操作最多沿著樹高移動，其時間複雜度就是 $O(\log N)$。

選項分析

A. A full binary tree is a complete binary tree, and vice versa

錯誤。

滿二元樹與完全二元樹的定義不同，兩者不互相等價。

• 滿二元樹要求每個節點必須有 $0$ 或 $2$ 個子節點。
• 完全二元樹要求節點依層、由左至右填入，並不禁止某個節點只有一個子節點。

例如，根節點有左子節點、沒有右子節點的樹，可以是完全二元樹，但不是滿二元樹。

反過來，某些滿二元樹的形狀也不符合完全二元樹由左至右填滿的規則，因此兩者不能互相推導。

B. When using a max heap to implement a priority queue, the time complexity of both the push and pop operations are O(log N)

正確。

使用最大堆積實作優先佇列時：

• Push（插入）：新元素先放在陣列最後，再依序與父節點比較並向上調整（up-heap）。最多移動樹高 $h$ 層，因此為

  $O(h)=O(\log N)$