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

核心觀念

題目考查資料結構的存取順序：

• First-Come First-Served（FCFS）：先到者先接受處理，亦即「先進先出」。
• Queue（佇列）：採用 FIFO（First-In First-Out），最早加入佇列的元素最早被取出。

因此，FCFS 作業通常使用佇列表示。新增元素由佇列尾端（rear）加入，處理元素則由佇列前端（front）取出。

其操作概念如下：

$$\text{enqueue：由尾端加入}$$ $$\text{dequeue：由前端移除}$$

這樣即可確保先抵達的工作先被服務。

解題方法

將題目的「first-come first-served」轉換成資料結構的存取規則：

1. 第一個抵達的工作必須第一個被處理。
2. 後抵達的工作必須排在前面工作之後。
3. 這正是「先進先出」FIFO 的特性。
4. 具備 FIFO 特性的資料結構為 Queue。

例如工作依序抵達：

$$A \rightarrow B \rightarrow C$$

處理順序也必須是：

$$A \rightarrow B \rightarrow C$$

此流程由 Queue 完成。

選項分析

A. Stack

核心觀念

本題考查「鏈結串列（linked list）插入元素的時間複雜度」。

在單向鏈結串列中，每個節點通常包含：

1. 資料欄位（data）
2. 指向下一個節點的指標（next）

原本的串列為：

$$3 \rightarrow 4 \rightarrow 12 \rightarrow 52 \rightarrow 62$$

若已知要將新節點 $16$ 插入在 $12$ 與 $52$ 之間，只需調整相關節點的指標，不需要搬移其他元素。

---

解題方法

設：

• 節點 $12$ 的指標為 p
• 新節點 $16$ 的指標為 newNode

插入前：

$$12 \rightarrow 52$$

插入後：

$$12 \rightarrow 16 \rightarrow 52$$

只需執行兩次指標連結：

newNode.next = p.next
p.next = newNode

每一次指標修改都只需固定時間，因此總執行時間為：

$$T(n)=c_1+c_2=O(1)$$

鏈結串列不需要像陣列一樣，將 $52$、$62$ 等後續元素逐一往後搬移，所以插入本身與串列長度 $n$ 無關。

因此正確答案為 B. $O(1)$。

核心觀念

本題考查中序運算式轉換為後序運算式（postfix expression）。

• 中序：運算子位於運算元中間，例如 $a+b$。
• 後序：運算子放在所有運算元之後，例如 $ab+$。
• 運算優先順序：
  1. 括號
  2. 乘法 *
  3. 加法 +
• 同一優先順序下，通常由左至右計算。

後序表示法不需要括號，因為運算順序已由運算子出現的位置確定。

解題方法

原式為：

$$a+b*c+(d*e+f)*g$$

先依照優先順序加上結構：

$$(a+(b*c))+((d*e+f)*g)$$

分別將各個子運算式轉為後序表示法。

第一部分：$a+b*c$

先處理乘法：

$$b*c \rightarrow bc*$$

再與 $a$ 相加：

$$a+(b*c) \rightarrow abc*+$$

第二部分：$(d*e+f)*g$

先處理括號內的 $d*e+f$：

$$d*e \rightarrow de*$$

再將結果與 $f$ 相加：

$$d*e+f \rightarrow de*f+$$

最後乘上 $g$：

$$(d*e+f)*g \rightarrow de*f+g*$$

合併兩大部分

原式是：

$$(a+b*c)+((d*e+f)*g)$$

兩部分分別為：

$$abc*+$$

與：

$$de*f+g*$$

最後執行最外層的加法，得到：

$$abc*+de*f+g*+$$

因此正確選項為 D。

選項分析

A. abc*de+*f+g*+

此選項在 abc* 後直接接上 de+，其運算順序相當於先處理：

$$d+e$$

但原式中 $d$ 與 $e$ 應先做乘法 $d*e$，正確片段應為：

$$de*$$

核心觀念

在樹（tree）中，若兩個以上節點具有相同的直接父節點，這些節點彼此稱為兄弟節點（siblings）。

例如：

      A
    / | \
   B  C  D

節點 $B$、$C$、$D$ 的直接父節點都是 $A$，因此 $B$、$C$、$D$ 彼此為兄弟節點。

解題方法

題幹指出：

nodes with the same parents

意思是「具有相同父節點的節點」。依照樹的基本術語定義，這些節點稱為 Siblings。

因此正確選項為 C。

選項分析

• A. Ancestors：錯誤

  Ancestors 指「祖先節點」。若從節點 $x$ 沿著父節點一路向上，途中經過的節點都是 $x$ 的祖先，例如父節點、祖父節點等，並非指具有相同父節點的節點。

核心觀念

Merge sort（合併排序）採用「分治法」：

1. 將 $n$ 個元素分成兩半。
2. 分別遞迴排序左右兩半。
3. 將兩個已排序的子序列合併。

每一層合併所有元素的總成本為 $O(n)$，而元素大約每次分半，因此遞迴深度為：

$$\log_2 n$$

所以 Merge sort 的時間複雜度為：

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

更精確地說，Merge sort 的最佳、平均與最壞情況時間複雜度皆為：

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

解題方法與推導

Merge sort 的遞迴式為：

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

其中：

• $2T(n/2)$：分別排序左右兩個子問題。
• $\Theta(n)$：合併兩個已排序序列，最多需要檢查並移動所有 $n$ 個元素。

依據 Master Theorem：

$$a=2,\qquad b=2,\qquad f(n)=\Theta(n)$$

且：

$$n^{\log_b a}=n^{\log_2 2}=n$$

因此：

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

所以其最壞情況執行時間為：

核心觀念

單變數多項式可表示為多個「係數—次方」項目的集合，例如：

$$P(x)=5x^4-3x^2+7$$

可拆成：

$$(5,4),\ (-3,2),\ (7,0)$$

其中每個項目記錄：

• 係數（coefficient）
• 指數（exponent）

資料結構只需能依序儲存這些多項式項目，便能進行多項式的走訪、加法與乘法。常見表示方式是陣列或鏈結串列；當多項式較稀疏時，鏈結串列尤其適合，因為不必儲存係數為零的項目。

解題方法

觀察各選項是否適合儲存任意數量的多項式項目，並支援依序走訪與項目運算。

以鏈結串列表示時，每個節點可包含：

$$(\text{coefficient},\ \text{exponent},\ \text{next})$$

例如：

$$5x^4-3x^2+7$$

可表示為：

$$(5,4)\rightarrow(-3,2)\rightarrow(7,0)$$

若節點按照指數遞減排列，多項式相加時，只需比較兩個串列目前節點的指數：

• 指數相同：係數相加。
• 指數較大者：先放入結果。
• 某一串列走訪完畢：接續另一串列剩餘項目。

因此，List 能自然表示多項式的項目集合，且具有彈性與良好的走訪能力。

選項分析

A. Queue

Queue 是佇列，遵循先進先出（FIFO）原則，主要操作是從尾端加入資料、從前端移除資料。

核心觀念

本題考查雜湊碰撞（hashing collision）的處理策略。

當兩個不同鍵值經由雜湊函數得到相同位置時，就會發生碰撞。常見處理方式分為：

1. 開放定址法（open addressing）
   所有資料都儲存在同一個雜湊表陣列中。發生碰撞時，依照探查規則尋找其他空槽位。

2. 分離鏈結法（separate chaining）
   雜湊表的每個位置通常是一條鏈結串列或其他動態集合。發生碰撞時，在該位置的鏈結串列中新增節點，存放新的資料。

因此，判斷關鍵在於：該策略是否需要在雜湊表外新增儲存節點。

---

解題方法

逐一判斷各策略處理碰撞時的儲存方式：

• 若碰撞後只是尋找雜湊表陣列中的另一個空槽位，屬於開放定址法，不需配置新細胞。
• 若碰撞後要在該位置的鏈結串列中加入新節點，就必須配置新的細胞。

分離鏈結法的基本結構可表示為：

$$H[i] \rightarrow \text{node}_1 \rightarrow \text{node}_2 \rightarrow \cdots$$

其中 $H[i]$ 是雜湊表第 $i$ 個位置。若多個鍵值都映射到 $i$，就必須新增節點接在該鏈結串列中。

---

選項分析

A. Linear probing

Linear probing（線性探查）是開放定址法的一種。當雜湊位置 $h(k)$ 發生碰撞時，依序檢查：

$$h(k),\ (h(k)+1)\bmod m,\ (h(k)+2)\bmod m,\ldots$$

其中 $m$ 是雜湊表大小。

資料會被放入原有陣列中的下一個空槽位，不需建立新的鏈結節點，因此不需要配置新的 cells。

本選項錯誤。

---

B. Separate chaining

Separate chaining（分離鏈結法）將每個雜湊位置視為一個鏈結串列的入口。

核心觀念

堆疊（Stack）遵循「後進先出」（Last In, First Out, LIFO）原則：

• push：將元素放入堆疊頂端。
• pop：移除堆疊頂端元素。
• 堆疊內容的表示順序為「由頂端到底端」。

初始堆疊由上到下為：

$$w,\ x,\ y,\ z$$

---

解題方法

先依序執行三次 pop：

1. 第一次 pop：移除頂端的 $w$
2. 第二次 pop：移除頂端的 $x$
3. 第三次 pop：移除頂端的 $y$

此時堆疊只剩下：

$$z$$

接著依序將 $a$、$b$ 推入堆疊：

1. push(a)：堆疊變為 $a,\ z$
2. push(b)：$b$ 會被放到最頂端，堆疊變為

$$b,\ a,\ z$$

因此最後由頂端到底端的內容為 $b,\ a,\ z$。

---

選項分析

核心觀念

Huffman codes（霍夫曼編碼）是一種建立最佳前綴碼（optimal prefix code）的方法，目標是在已知各符號出現頻率或機率的情況下，使平均編碼長度最小。

其基本原理是：

1. 每次選取出現頻率最低的兩個節點。
2. 將兩者合併成新的父節點，其頻率為兩者頻率之和。
3. 重複上述步驟，直到所有節點形成一棵二元樹。
4. 從根節點到各符號的路徑產生其二進位編碼。

由於每一步都選擇當下最有利的局部方案，並且這種選擇能導向整體最佳解，因此 Huffman codes 是 Greedy algorithm（貪婪演算法）的應用。

---

解題方法

判斷演算法類型時，可觀察 Huffman 演算法的核心決策：

• 每一回合選擇頻率最小的兩個符號。
• 將它們合併後，繼續處理剩餘節點。
• 已作出的合併決策不再回溯修改。

這正符合貪婪法的特徵：

在每個階段選擇目前看來最好的局部選擇，逐步建構全域最佳解。

Huffman 演算法具有貪婪選擇性質：頻率最低的兩個符號必須位於編碼樹最深層，且可作為同一個兄弟節點。先合併這兩個符號，再對縮小後的問題求解，便能得到最佳前綴碼。

實作時通常使用最小堆積（min-heap）保存各節點，因此每次能快速取出頻率最低的兩個節點。若共有 $n$ 個符號，建立 Huffman tree 的時間複雜度通常為：

$$O(n \log n)$$

---

選項分析

A. divide-and-conquer algorithm

錯誤。

Divide-and-conquer（分治法）通常包含三個步驟：

1. 將問題分割成數個較小的子問題。
2. 分別解決各子問題。
3. 合併子問題的結果。

核心觀念

本題考查最大堆積（max-heap）的定義與陣列表示法。

最大堆積是一棵完整二元樹，且每個節點的鍵值都不小於其子節點：

$$\text{parent} \geq \text{left child},\qquad \text{parent} \geq \text{right child}$$

若以陣列採「從 1 開始編號」表示堆積，則：

• 第 $i$ 個節點的父節點位置為

$$\left\lfloor \frac{i}{2} \right\rfloor$$

• 第 $i$ 個節點的左子節點位置為 $2i$
• 第 $i$ 個節點的右子節點位置為 $2i+1$

因此，只要逐一檢查每個父節點是否大於或等於其子節點，即可判斷是否為 max-heap。

---

解題方法

各選項的陣列結構皆為：

$$\begin{array}{c|ccccccc} \text{位置} & 1 & 2 & 3 & 4 & 5 & 6 & 7\\ \hline \text{節點} & 97 & 53 & 59 & 26 & 41 & 58 & 31 \end{array}$$

其樹狀關係為：

• 位置 $1$ 的 $97$ 為根節點，子節點為位置 $2$、$3$
• 位置 $2$ 的節點，子節點為位置 $4$、$5$
• 位置 $3$ 的節點，子節點為位置 $6$、$7$

只需檢查三組父子關係：

$$a_1 \geq a_2,\ a_3$$ $$a_2 \geq a_4,\ a_5$$ $$a_3 \geq a_6,\ a_7$$

---

選項分析

A. 97, 53, 59, 26, 41, 58, 31

樹狀關係如下：

核心觀念

本題考察漸近分析與 Big-O 表示法。判斷多項式或數列的成長率時，重點如下：

1. 忽略常數倍。
2. 忽略低階項。
3. 保留成長最快的主導項。

若函數同時具有上界與下界，通常可用較精確的 $\Theta$ 表示其緊確成長率；題目要求 Big-O，則寫出相同階數的最佳上界。

---

(1) $x^2+2x+1$

解題方法

原式包含三項：

$$x^2,\qquad 2x,\qquad 1$$

當 $x$ 趨近於無窮大時，$x^2$ 的成長速度高於 $x$ 與常數，因此主導項為 $x^2$。

也可直接計算比值：

$$\lim_{x\to\infty}\frac{x^2+2x+1}{x^2} = \lim_{x\to\infty} \left(1+\frac{2}{x}+\frac{1}{x^2}\right) =1$$

比值收斂至正的有限常數，表示兩者具有相同的漸近成長率。

因此：

$$x^2+2x+1=\Theta(x^2)$$

所以最佳 Big-O 為：

$$\boxed{O(x^2)}$$

---

(2) $x!$

解題方法

$x!$ 表示階乘：

$$x!=1\cdot2\cdot3\cdots x$$

它本身就是一個階乘成長函數，沒有可刪除的低階項或常數項。因此其緊確成長率為：

$$x!=\Theta(x!)$$

所以最佳 Big-O 為：

$$\boxed{O(x!)}$$

階乘的成長速度非常快。依據 Stirling 公式：

$$x!\sim \sqrt{2\pi x}\left(\frac{x}{e}\right)^x$$

核心觀念

本題考查 Big-O 時間複雜度的判定，以及多項式函數中「最高次項主導成長速度」的觀念。

對於

$$f(x)=x^2+2x+1$$

當 $x$ 持續增大時，$x^2$ 的成長速度高於 $2x$ 與常數 $1$，因此整體成長速度由 $x^2$ 主導。

Big-O 的正式定義為：若存在正常數 $c$ 與 $x_0$，使得對所有 $x\ge x_0$，

$$0\le f(x)\le c\cdot g(x)$$

則稱

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

---

解題方法

第一步：找出最高次項

原式為

$$x^2+2x+1.$$

各項的次數如下：

• $x^2$：二次項
• $2x$：一次項
• $1$：常數項

其中最高次項為 $x^2$。

第二步：忽略低階項與常數倍

在 Big-O 分析中，當 $x$ 很大時，低階項相較於最高次項的影響會逐漸減小，因此只保留最高次項：

$$x^2+2x+1=O(x^2).$$

更精確地說，

$$x^2+2x+1=\Theta(x^2),$$

核心觀念

本題考查階乘函數的成長率與 Big-O 表示法。

對非負整數 $x$：

$$x! = 1\cdot 2\cdot 3\cdots x$$

階乘的成長速度遠快於任何固定次方的多項式 $x^k$，也快於固定底數的指數函數 $c^x$；但仍小於 $x^x$。

階乘的精確漸近估計可由 Stirling 公式表示：

$$x! \sim \sqrt{2\pi x}\left(\frac{x}{e}\right)^x$$

因此：

$$x! = \Theta\left(\sqrt{x}\left(\frac{x}{e}\right)^x\right)$$

---

解題方法

題目要求給出 running time 的最佳 Big-O 特性。由於執行時間本身已經是 $x!$，其最緊確的上界就是：

$$T(x)=x!$$

直接可得：

$$T(x)\in O(x!)$$

更精確地寫，利用 Stirling 公式：

$$T(x)=x! =\Theta\left(\sqrt{x}\left(\frac{x}{e}\right)^x\right)$$

所以最佳的 Big-O 表示為：

$$\boxed{O(x!)}$$

若要求漸近緊確界，則為：

$$\boxed{\Theta(x!)}$$

---

為何不能用較寬鬆的表示法取代

核心觀念

題目要求判斷：

$$1+2+3+\dots+n$$

的最佳 Big-O 時間複雜度。核心是估算總和隨 $n$ 增加時的成長速度。

使用等差級數公式：

$$1+2+3+\dots+n=\frac{n(n+1)}{2}$$

展開得：

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

在漸近分析中，常數係數與低階項不影響複雜度，因此主要成長項為 $n^2$。

解題方法

原式可視為首項為 $1$、末項為 $n$、共有 $n$ 項的等差級數：

$$S_n=\frac{(\text{首項}+\text{末項})\times\text{項數}}{2}$$

代入後：

$$S_n=\frac{(1+n)n}{2} =\frac{n^2+n}{2}$$

因此：

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

若題目只要求以 Big-O 表示，則最佳上界為：

$$O(n^2)$$

為何不是 $O(n)$

雖然每一項的數值是 $1,2,\dots,n$，但總共有 $n$ 項，而且平均每項約為 $n/2$，所以總和約為：

$$n\times\frac{n}{2}=\frac{n^2}{2}$$

因此成長速度是平方級，而不是線性級。

核心觀念

二元搜尋樹（BST）滿足：每個節點左子樹的鍵值小於該節點，右子樹的鍵值大於該節點。插入時從根節點開始比較，依大小往左或往右，直到找到空位置。

刪除有兩個子節點的節點時，可用其中序後繼（右子樹中的最小值）取代，再刪除原位置的後繼節點。本題依此規則刪除節點 $2$。

解題方法

原圖中的樹為：根節點 $6$，左子節點 $2$、右子節點 $8$；節點 $2$ 的左右子節點分別為 $1$、$4$，而 $4$ 的左子節點為 $3$。

（1）插入節點 $5$

依序比較：$5<6$，往左到 $2$；$5>2$，往右到 $4$；$5>4$，因此插入為 $4$ 的右子節點。

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

（2）刪除節點 $2$

核心觀念

二元搜尋樹（BST）中，每個節點的左子樹鍵值都小於該節點，右子樹鍵值都大於該節點。插入新節點時，從根節點開始比較，沿著比較結果指定的方向往下走，直到找到空位置。

解題方法

原樹的根節點是 $6$。插入 $5$ 時依序比較：

1. $5<6$，往 $6$ 的左子樹走，到節點 $2$。
2. $5>2$，往 $2$ 的右子樹走，到節點 $4$。
3. $5>4$，往 $4$ 的右子樹走；

核心觀念

本題考查二元搜尋樹（Binary Search Tree, BST）的刪除與插入：

• 左子樹所有節點值小於根節點。
• 右子樹所有節點值大於根節點。
• 刪除與插入後，仍須維持上述排序性質。

解題方法

應依序操作：

1. 刪除節點 2
   • 若節點 2 為葉節點，直接移除。
   • 若只有一個子節點，以該子節點取代 2。
   • 若有兩個子節點，以其中序後繼（右子樹最小值）或其中序前驅取代 2，再刪除該替代節點。

核心觀念

Preorder traversal（前序走訪）的順序固定為：

$$\text{根節點} \rightarrow \text{左子樹} \rightarrow \text{右子樹}$$

每棵子樹都以相同規則遞迴走訪。

解題方法

從二元搜尋樹的根節點開始：

1. 先記錄根節點。
2. 再走訪左子樹，且每個左子樹仍遵守「根、左、右」。
3. 最後走訪右子樹，且每個右子樹仍遵守「根、左、右」。

若根節點為 $r$，左、右子樹的前序序列分別為 $P_L$、$P_R$，則：

核心觀念

本題考查：

1. 使用 Prim’s algorithm 求加權無向圖的最小生成樹（Minimum Spanning Tree, MST）。
2. 使用 Breadth-First Search（BFS，廣度優先搜尋）決定走訪順序。
3. 分析 Prim 演算法的最壞時間複雜度。

但目前附上的兩張圖片是「成本與管理會計學」考卷第 4、5 頁，圖中沒有資料結構題目所需的 Fig. 2，因此缺少頂點、邊及權重資料；同時 BFS 也缺少起始頂點與鄰接點排列順序。

解題方法

若 Fig. 2 是加權無向圖，Prim 演算法如下：

1. 任選一個起始頂點加入樹集合 $S$。
2. 從所有「一端在 $S$、另一端不在 $S$」的邊中，選擇權重最小者。
3. 將該邊及新頂點加入 $S$。
4. 重複上述步驟，直到所有頂點均加入。
5. 最後得到 $|V|-1$ 條邊，即為最小生成樹。

若有相同權重，必須依題目指定的規則，或依頂點編號、鄰接串列順序等固定規則決定；否則最小生成樹可能不唯一，但其總權重仍為最小。

BFS 解法

BFS 使用佇列（queue）：

1. 將起始頂點標記為已拜訪並放入佇列。
2. 取出佇列前端頂點。
3. 依鄰接點順序拜訪所有尚未拜訪的鄰點，並依序加入佇列。
4. 重複直到佇列為空。

BFS 的走訪順序取決於：

• 起始頂點；
• 各頂點鄰接點的排列順序。

因此，缺少 Fig. 2、起始頂點及鄰接順序時，無法確定第（2）小題的唯一走訪結果。

核心觀念

本題考查最小生成樹（Minimum Spanning Tree, MST）與 Prim’s algorithm。

對於一個連通、帶權重的無向圖，最小生成樹必須符合：

• 包含所有頂點。
• 不含任何循環。
• 邊數必為 $|V|-1$。
• 所有邊權重總和最小。

Prim 演算法每次從「已加入生成樹的頂點集合」與「尚未加入的頂點集合」之間，選擇權重最小的邊加入生成樹。

解題方法

令起始頂點為 $s$，設：

• $S$：已加入最小生成樹的頂點集合。
• $E_T$：目前選入的邊集合。

Prim 演算法步驟如下：

1. 將起始頂點 $s$ 放入 $S$。
2. 從所有一端在 $S$、另一端不在 $S$ 的邊中，選擇權重最小者。
3. 將該邊及其未加入的端點加入 $E_T$ 與 $S$。
4. 重複上述步驟，直到所有頂點都加入 $S$。
5. 最後得到 $|V|-1$ 條邊，即為最小生成樹。

若每一步有多條邊權重相同，任選其中一條皆可形成最小生成樹，但最後的樹形可能不唯一。

圖形資訊檢核

核心觀念

本題考查圖形的廣度優先搜尋（Breadth-First Search, BFS）。BFS 從指定起點出發，依「距離起點由近到遠」的層次拜訪頂點，通常使用佇列（Queue）實作。

Prim’s algorithm 是最小生成樹演算法，與 BFS 的拜訪順序不同；BFS 不依據邊權重決定順序。

解題方法

BFS 的基本流程如下：

1. 將起始頂點標記為已拜訪並放入佇列。
2. 取出佇列前端頂點。
3. 依 Fig.2 所規定的鄰接頂點順序，將尚未拜訪的鄰點標記並加入佇列。
4. 重複上述步驟，直到佇列為空。

其關鍵偽程式碼為：

核心觀念

Prim’s algorithm 逐步建立最小生成樹（Minimum Spanning Tree, MST）。每次從尚未加入樹中的頂點，選出連接目前生成樹與外部頂點之間權重最小的邊。

其時間複雜度取決於圖的儲存方式與優先佇列實作。

解題方法

若採用最常見的鄰接矩陣實作：

1. 每次從 $V$ 個頂點中尋找最小的 key 值，需花費 $O(V)$。
2. 一共要加入 $V$ 個頂點。
3. 每加入一個頂點，需掃描其餘頂點以更新 key 值，亦需 $O(V)$。

因此：

$$T(V)=V\cdot O(V)=O(V^2)$$

所以 Prim’s algorithm 的最壞情況時間複雜度為：

$$\boxed{O(V^2)}$$

其中 $V$ 為頂點數。

核心觀念

本題考查最小堆（min-heap）的兩項基本操作：

• 插入：將新節點放在堆尾，再向上調整（percolate up）。
• 刪除指定節點：以最後一個節點補到被刪位置，再依情況向上或向下調整。
• 最小堆必須滿足：每個父節點的鍵值皆小於或等於其子節點。

圖形資訊不足

題目要求依 Fig.3 畫出操作後的堆，但目前附上的掃描圖是會計學考題第 5 頁，圖中沒有資料結構的 Fig.3，也沒有原始 min-heap 的節點內容。因此無法唯一確定插入 14 與刪除 13 後的實際樹形。

以下先說明正確操作方法。取得 Fig.3 的原始堆後，即可依此方法畫出唯一答案。

(1) 插入節點 14

將 14 放在目前堆的最後一個空位置，以維持完全二元樹形狀。

接著重複比較 14 與其父節點：

1. 若 $14$ 小於父節點，交換兩者。
2. 繼續向上比較。
3. 當 14 大於或等於父節點，或已到達根節點時停止。

插入後必須同時滿足：

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

(2) 刪除節點 13

刪除指定節點 13 後，將堆中最後一個節點移至 13 原本的位置，以維持完全二元樹形狀。

設補入的節點為 $x$：

核心觀念

本題考查最小堆積（min-heap）的插入操作。最小堆積必須同時符合：

1. 完全二元樹的形狀。
2. 每個節點的鍵值皆小於或等於其子節點，即
   $\text{parent} \leq \text{children}$

解題方法

插入節點 $14$ 時，依序執行：

1. 將 $14$ 放在完全二元樹的下一個空位置，以維持完全二元樹形狀。
2. 比較 $14$ 與其父節點：
   • 若 $14$ 小於父節點，便與父節點交換。
   • 持續向上比較，直到父節點小於或等於 $14$，或 $14$ 成為根節點。
3. 此過程稱為向上調整（up-heap／percolate up）。

若以陣列表示堆積，節點位於索引 $i$ 時，其父節點索引為

$\left\lfloor \frac{i}{2} \right\rfloor$

核心觀念

1. 最小堆積（Min-Heap）定義：

   • 結構性質：必須是一棵完全二元樹（Complete Binary Tree），所有節點依序由上而下、由左至右緊密排列。
   • 堆積性質（Min-Heap Property）：樹中任一節點的鍵值（Key）皆小於或等於其所有子節點的鍵值，亦即對所有節點 $i$（若子節點存在），滿足：
     $\text{Key}(\text{Parent}(i)) \le \text{Key}(i)$
   • 根節點（Root）恆為整個堆積中的最小值。

2. 刪除根節點（Delete-Min）操作步驟：

   • 步驟一（替換）：將堆積中「最後一個節點」（完全二元樹最底層最右側之節點，Last Node）的值移至根節點，並自原位置刪除該最後節點，使堆積大小減 $1$。
   • 步驟二（向下調整，Heapify-down / Sift-down）：
     從根節點開始，比較當前節點與其左右子節點的值：
     • 若當前節點大於子節點中的較小者，則將當前節點與該較小之子節點互換（Swap）。
     • 重複此比較與交換程序，直至當前節點小於等於其所有子節點，或已抵達葉節點為止。

---

解題方法與詳細步驟

原題目附圖（Fig. 3）中共有 $10$ 個節點，依層序（Level-order）排列的最小堆積陣列為：
$[13,\, 21,\, 16,\, 24,\, 31,\, 19,\, 68,\, 65,\, 26,\, 32]$

其原始樹狀結構如下：

• Level 1（根節點）：$13$
• Level 2：左子節點為 $21$，右子節點為 $16$
• Level 3：$21$ 的子節點為 $24$（左）、$31$（右）；$16$ 的子節點為 $19$（左）、$68$（右）
• Level 4：$24$ 的子節點為 $65$（左）、$26$（右）；$31$ 的左子節點為 $32$（最後一個節點）

刪除值為 $13$ 的根節點之詳細調整流程如下：

步驟 1：以最後節點覆蓋根節點

• 移除根節點 $13$。
• 取出堆積中最後一個節點 $32$（位於 $31$ 的左子節點），填入根節點位置，並將堆積大小由 $10$ 縮減為 $9$。
• 此時根節點值為 $32$。

步驟 2：執行向下調整（Sift-down）

1. 比較根節點（值為 $32$）與其子節點：
   • 左子節點為 $21$，右子節點為 $16$。

核心觀念

最小堆（min-heap）是一棵近似完整二元樹，且每個父節點的鍵值不大於子節點。含有 $n$ 個元素時，高度為：

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

因此，凡是需要沿著樹高向上或向下調整堆序的操作，最壞時間通常為 $\Theta(\log n)$。

解題方法

題目所附圖片為會計學考卷頁面，未包含題目提到的 Fig.3，也未顯示「above two operations」的具體內容，因此無法依原題確定兩個操作的名稱與精確答案。

若依最小堆題目最常見的設定，假設兩個操作為：

1. 插入元素（insert）：先放入下一個空位置，再向上調整（sift-up）。最壞情況下，元素由葉節點一路上移至根節點，最多經過 $h$ 層，因此：

   $T_{\text{insert}}(n)=\Theta(\log n)$