108 年 國立政治大學資訊管理學系碩士班科技組《資料結構》

核心觀念

Splay tree（伸展樹）是二元搜尋樹的一種。當某個節點被存取、插入或刪除後，會進行 splay（伸展）操作，沿著該節點到根節點的路徑旋轉，使該節點移動到：

$$\text{根節點（root）}$$

而不是移動到葉節點（leaf）。

常見的伸展旋轉包含：

• Zig：節點的父節點就是根節點，進行一次旋轉。
• Zig-Zig：節點與父節點位於祖父節點的同一側，進行兩次同方向旋轉。
• Zig-Zag：節點與父節點位於相反側，進行兩次不同方向旋轉。

這些旋轉的共同目的，都是將指定節點提升至根節點。

解題方法

判斷敘述中的「splaying a node means」所描述的操作目標即可。

若節點目前位於樹中的內部位置，伸展操作會持續對它與父節點、祖父節點進行旋轉。例如：

$$\text{節點 } x \longrightarrow \text{父節點位置} \longrightarrow \text{根節點}$$

核心觀念

本題考查 Map 與 Dictionary 對於鍵（key）重複性的定義差異。

• Map：由多筆 entry 組成，每筆 entry 為一組 $(key, value)$。同一個 key 可以對應多個 value，因此允許多筆 entry 擁有相同 key。
• Dictionary：通常要求每個 key 唯一。一個 key 至多對應一筆資料；若插入相同 key，通常會更新原有 value，或拒絕此次插入。

因此，兩者主要差異之一，就是是否允許重複的 key。

解題方法

直接比較題目敘述與兩種抽象資料型態的定義：

1. 題目指出 Map 可以有相同 key 的多筆 entry。
2. 題目指出 Dictionary 不允許相同 key。
3. 這正符合一般資料結構教材對 Map 與 Dictionary 的區分。

例如：

Map 可儲存：

$$(101,\text{資料結構}),\quad (101,\text{演算法})$$

其中 key 101 重複，但 value 不同，這在 Map 中是允許的。

核心觀念

Map（映射）由許多鍵值對組成：

$$(k,v)$$

其中每個 key 對應一個 value。使用未排序串列（unsorted list）實作 Map 時，資料沒有依照 key 排列，因此執行 get(k) 必須逐一比較每個元素的 key，直到找到目標鍵 $k$。

這本質上是線性搜尋（linear search）。

解題方法

假設 Map 中共有 $n$ 筆資料：

$$(k_1,v_1),(k_2,v_2),\ldots,(k_n,v_n)$$

執行 get(k) 時，最多需要比較：

$$k_1,\ k_2,\ \ldots,\ k_n$$

若目標 key 位於最後一筆，或 Map 中根本沒有 key $k$，就必須檢查全部 $n$ 筆資料，因此最壞情況時間複雜度為：

$$T(n)=O(n)$$

更精確地說：

• 最好情況：目標 key 位於第一筆，時間為 $\Theta(1)$。
• 最壞情況：目標 key 位於最後一筆，或 key 不存在，時間為 $\Theta(n)$。
• 平均情況：若目標位置均勻分布，平均約需檢查 $\frac{n+1}{2}$ 筆，仍為 $\Theta(n)$。

核心觀念

雜湊函數（hash function）的作用，是將鍵值（key）映射至雜湊表中的某個位置。若雜湊表共有 $m$ 個槽位（slot），通常定義為：

$$h: U \rightarrow \{0,1,2,\ldots,m-1\}$$

其中 $U$ 是所有可能鍵值的集合，$h(k)$ 是鍵值 $k$ 對應的陣列索引。

因此，雜湊函數的輸出範圍必須與實際雜湊表的索引範圍相符，才能直接利用 $h(k)$ 存取陣列位置。

---

解題方法

題目指出：

• Array 的大小為 $2N$；
• 雜湊函數的輸出範例卻是 $[0,N-1]$。

大小為 $2N$ 的陣列，其合法索引為：

$$0,1,2,\ldots,2N-1$$

因此，若雜湊函數的結果要直接作為陣列索引，應定義為：

$$h(k)\in [0,2N-1]$$

或寫成：

$$h(k)\in \{0,1,2,\ldots,2N-1\}$$

核心觀念

雜湊表（hash table）利用雜湊函數 $h(k)$ 將鍵值 $k$ 映射至表格中的索引：

$$h(k)=i$$

其中 $i$ 為雜湊表中的位置。

**碰撞（collision）**的正式定義是：

兩個不同的鍵值被雜湊函數映射到相同的索引。

若 $k_1 \ne k_2$，但滿足：

$$h(k_1)=h(k_2)$$

則發生碰撞。

例如：

$$h(12)=3,\qquad h(25)=3$$

因為 $12\ne25$，但兩者都被映射至索引 $3$，所以產生碰撞。

解題方法

判斷題目敘述是否正確時，直接對照碰撞的定義：

• 題目敘述描述的是「一個鍵被映射到不同索引」。
• 碰撞的正確情況是「不同的鍵被映射到同一索引」。

兩者在「鍵的數量」與「索引是否相同」上都相反。

雜湊函數在相同輸入下應產生相同輸出，因此同一個鍵 $k$ 應固定映射至同一個索引：

$$h(k)=i$$

若同一個鍵在不同時間被映射至不同索引，通常代表雜湊函數不穩定、雜湊表內容或計算條件發生改變，並非碰撞的標準定義。

選項分析

本題雖未列出選項，但題目本身是一個是非判斷敘述：

核心觀念

本題考查雜湊表碰撞處理中的「Double Hashing（雙重雜湊）」與「Linear Probing（線性探測）」之區別。

雙重雜湊使用兩個雜湊函數：

$$h(k,i)=\bigl(h_1(k)+i\cdot h_2(k)\bigr)\bmod m$$

其中：

• $h_1(k)$：第一次計算出的起始位置。
• $h_2(k)$：決定每次探測時的跳躍步長。
• $i=0,1,2,\ldots$：第 $i$ 次探測。
• $m$：雜湊表大小。

因此，雙重雜湊發生碰撞後，不是固定檢查下一個相鄰位置，而是依照第二個雜湊函數所決定的步長跳躍探測。

解題方法

判斷題目敘述所描述的探測方式：

Double hashing handles collisions by putting the colliding items in the next closest available table cell.

其中「放入下一個最近且可用的表格位置」表示從碰撞位置開始，依序檢查下一格、下下格，直到找到空位。這正是線性探測的作法：

$$h(k,i)=\bigl(h(k)+i\bigr)\bmod m$$

雙重雜湊則採用：

核心觀念

二元搜尋樹（Binary Search Tree, BST）遵守：

• 左子樹所有鍵值 $<$ 根節點鍵值
• 右子樹所有鍵值 $>$ 根節點鍵值

三種深度優先走訪順序為：

• Preorder：根、左、右
• Inorder：左、根、右
• Postorder：左、右、根

其中，BST 的鍵值必須透過 inorder traversal 才能保證以遞增順序走訪。

---

解題方法

題目宣稱「BST 的 postorder traversal 會以遞增順序走訪鍵值」，只要依照 postorder 定義建立反例即可判斷。

考慮以下 BST：

    2
   / \
  1   3

其 postorder 順序為：

1. 走訪左子樹：$1$
2. 走訪右子樹：$3$
3. 最後走訪根節點：$2$

因此走訪結果為：

$$1,\ 3,\ 2$$

此序列並非遞增，因為 $3>2$。

根本原因是 postorder 將根節點放在最後；但在一般 BST 中，根節點不一定是最大鍵值，右子樹中的節點可能比根節點大。

---

正確觀念對照

核心觀念

本題考查二元搜尋樹（Binary Search Tree, BST）的性質，以及前序走訪（preorder traversal）的順序。

• BST 對任一節點 $x$ 而言：
  • 左子樹所有鍵值小於 $x$；
  • 右子樹所有鍵值大於 $x$。
• 前序走訪順序為：

$$\text{Root} \rightarrow \text{Left Subtree} \rightarrow \text{Right Subtree}$$

因此，前序走訪的第一個鍵值一定是樹根。

解題方法

題目敘述：

A preorder traversal of a binary search tree visits the keys in decreasing order.

意思是：某棵二元搜尋樹的前序走訪結果會依鍵值遞減排列。

設樹根鍵值為 $r$。由於前序走訪首先拜訪樹根，後續所有節點都必須小於 $r$，才能維持遞減順序。

若樹根存在右子樹，則右子樹中的每個鍵值都大於 $r$。前序走訪在拜訪完左子樹後會拜訪右子樹，因此右子樹節點會出現在樹根之後，形成：

$$r < \text{右子樹中的鍵值}$$

這與整體遞減順序矛盾。因此，樹根不能有右子樹。

同樣地，對樹中的每一個節點套用相同推理，可知任何節點都不能有右子樹。這棵 BST 必須呈現只含左子節點的單鏈結構：

核心觀念

本題考查二元搜尋樹（Binary Search Tree, BST）的刪除操作時間複雜度。

BST 的特性為：

• 每個節點左子樹的鍵值小於該節點。
• 每個節點右子樹的鍵值大於該節點。
• 搜尋、插入、刪除通常只需沿著「根到某一葉節點」的路徑進行。
• 若樹高為 $h$，根到最深節點最多經過 $h$ 層，因此相關操作的時間複雜度通常為 $O(h)$。

---

解題方法

刪除 BST 中的鍵值，主要分為三種情況：

1. 刪除葉節點

   直接將該節點移除即可。尋找該節點最多需走過樹高 $h$，因此時間為：

   $O(h)$

2. 刪除只有一個子節點的節點

   將該節點的子節點接到其父節點下方。尋找節點與重新連結皆不超過樹高，因此時間為：

   $O(h)$

3. 刪除具有兩個子節點的節點

   通常尋找其中序後繼（右子樹中的最小節點）或中序前驅（左子樹中的最大節點），再進行節點替換與刪除。

   搜尋與調整仍然只會沿著樹中的路徑進行，因此時間為：

   $O(h)$

所以，BST 刪除一個鍵值的精確複雜度應寫為：

$O(h)$

---

與 $O(n)$ 的關係

一棵含有 $n$ 個節點的樹，其高度最多為：

$h \leq n-1$

因此：

$O(h) \subseteq O(n)$

也就是說，若刪除操作為 $O(h)$，則它也必然屬於 $O(n)$。

在最壞情況下，BST 退化成鏈結串列：

核心觀念

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

1. 二元搜尋樹性質：對任一節點，其左子樹所有鍵值小於該節點，右子樹所有鍵值大於該節點。
2. 高度平衡性質：對每個節點 $v$，其左、右子樹高度差的絕對值不得超過 $1$。

平衡因子定義為：

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

AVL 樹要求：

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

等價地表示為：

$$\left|h(\text{left}(v))-h(\text{right}(v))\right|\leq 1$$

其中 $h(T)$ 表示子樹高度。若某一側沒有子樹，必須依題目或課本慣例設定其高度；常見設定為空樹高度 $-1$、葉節點高度 $0$。

解題方法

題幹敘述：

An AVL tree is a binary search tree where for every internal node, the heights of its children are at the most one difference.

可分成兩個條件判斷：

• 「a binary search tree」：表示 AVL 樹必須是二元搜尋樹。
• 「for every internal node, the heights of its children are at the most one difference」：表示

核心觀念

本題考查雜湊（Hashing）的負載因子（load factor）與查詢效率之關係。

負載因子定義為：

$$\alpha=\frac{n}{m}$$

其中：

• $n$：目前儲存的元素數量
• $m$：雜湊表陣列的大小
• $\alpha$：負載因子

「接近 100%」表示 $\alpha$ 接近 $1$，也就是陣列中的位置幾乎都已被使用。

解題方法

判斷此敘述是否正確，須觀察負載因子升高時碰撞（collision）的情況。

當 $\alpha$ 接近 $1$ 時，可使用的空間很少，新的元素較容易與既有元素發生碰撞，導致：

• 插入時需要尋找更多位置；
• 查詢時需要檢查更多候選位置；
• 刪除與搜尋的平均成本上升；
• 嚴重時，時間複雜度會由平均 $O(1)$ 退化為 $O(n)$。

以開放定址法（open addressing）為例，所有元素都直接放在陣列中。當 $\alpha$ 越接近 $1$，空位越少，線性探測、二次探測等方法需要探查的次數越多，因此效率會明顯下降。當 $\alpha=1$ 時，表格已完全沒有空位，無法再直接插入新元素。

核心觀念

本題考查 Skip List（跳躍串列） 的結構定義。

Skip List 由多層已排序串列組成，通常包含：

• 最底層串列：存放所有資料元素。
• 上層串列：從下一層挑選部分元素形成，作為快速跳躍與搜尋的索引。
• 每一層皆維持與底層相同的排序順序。

因此，若由底層往上觀察，每一層都是下一層的子序列（subsequence）。題目所述：

A skip list is a series of lists where each list is a subsequence of the previous one.

其意義是：Skip List 是一系列串列，且每一個串列都是前一個串列的子序列。

解題方法

判斷此敘述是否符合 Skip List 的正式定義即可。

設最底層串列為

$$L_0=(a_1,a_2,a_3,a_4,a_5,a_6)$$

上方各層可能為：

核心觀念

Skip list（跳躍表）以多層有序鏈結串列組成：

• 第 $0$ 層包含所有 $n$ 筆資料。
• 上層以機率 $p$ 隨機抽取部分節點，形成較稀疏的索引層。
• 搜尋時由最高層開始，向右前進；若再向右會超過目標值，便下降一層。

標準隨機 Skip list 的高度期望為 $O(\log n)$，因此搜尋、插入與刪除的期望時間皆為：

$$O(\log n)$$

而非 $O(n)$。

解題方法

判斷此敘述的關鍵，在於區分「期望時間」與「最壞情況時間」。

在標準 Skip list 中，假設每個節點晉升至上一層的機率為固定常數 $p$，則第 $i$ 層的節點數期望約為：

$$np^i$$

當上層節點數降至常數級時，有：

$$np^h \approx 1$$

因此：

$$h \approx \log_{1/p} n = O(\log n)$$

搜尋過程中，每一層平均只需前進常數次，總共經過 $O(\log n)$ 層，所以：

$$T_{\text{search}}(n)=O(\log n)$$

插入時，先搜尋新節點應插入的位置，再依隨機結果將節點加入若干層，因此：

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

刪除時，同樣先找到目標節點，再從其出現的各層移除。節點出現的層數期望為常數，且尋找位置需 $O(\log n)$，因此：

$$T_{\text{delete}}(n)=O(\log n)$$

核心觀念

在圖論中，若兩條邊連接相同的端點，則稱這兩條邊為平行邊（parallel edges）。

對無向圖而言，邊 $e_1$ 與 $e_2$ 若皆連接頂點 $u$、$v$，可表示為：

$$e_1=(u,v),\qquad e_2=(u,v)$$

即使兩條邊是不同的邊，只要它們的端點相同，就屬於平行邊。含有平行邊的圖通常稱為多重圖（multigraph）。

解題方法

題目給出的敘述是：

Two edges in a graph are parallel if they have the same end vertices.

將其翻譯為中文：

圖中的兩條邊若具有相同的端點，則稱為平行邊。

這正是平行邊的定義，因此敘述成立。

對有向圖而言，還需考慮方向；兩條有向邊必須具有相同的起點與相同的終點，例如：

核心觀念

本題考查圖論中「相鄰頂點（adjacent vertices）」的定義。

在無向圖 $G=(V,E)$ 中，若存在一條邊 $e\in E$，其兩個端點正好是頂點 $u$ 與 $v$，則稱 $u$ 與 $v$ 相鄰，記作：

$$u\sim v$$

形式化表示為：

$$u\sim v \iff \exists e\in E,\ \text{使得 } e=\{u,v\}$$

其中：

• $V$：頂點集合
• $E$：邊集合
• $u,v$：圖中的兩個頂點
• $e$：連接 $u$ 與 $v$ 的邊

解題方法

直接依照相鄰頂點的定義判斷：

題目敘述為：

若存在一條邊，其兩個端點是這兩個頂點，則這兩個頂點相鄰。

核心觀念

無向圖的「頂點度數」是與該頂點相接的邊數。無向圖中的每一條邊都會連接兩個端點，因此會對兩個頂點各貢獻 $1$ 度。

因此，無向圖的握手定理為：

$$\sum_{v\in V}\deg(v)=2|E|$$

其中：

• $V$：頂點集合
• $E$：邊集合
• $\deg(v)$：頂點 $v$ 的度數

---

解題方法

逐一計算每條邊對所有頂點度數總和的貢獻：

1. 任取一條無向邊 $(u,v)$。
2. 該邊使頂點 $u$ 的度數增加 $1$。
3. 同時使頂點 $v$ 的度數增加 $1$。
4. 因此，一條邊總共使度數總和增加 $2$。

若圖中共有 $|E|$ 條邊，則：

$$\sum_{v\in V}\deg(v)=2|E|$$

題目敘述聲稱度數總和等於邊數 $|E|$，少了倍數 $2$，所以敘述錯誤。

例如，若無向圖只有一條邊連接兩個頂點，則兩個頂點的度數皆為 $1$：

核心觀念

在含有 $n$ 個頂點的「簡單無向圖」中，任意兩個不同頂點之間最多只能有一條邊，且不允許自迴圈。

每條邊對應一組不同頂點，因此最多的邊數等於從 $n$ 個頂點中選出 $2$ 個：

$$\binom{n}{2} = \frac{n(n-1)}{2}$$

此數值是簡單無向圖的最大邊數。

解題方法

要判斷敘述是否正確，只需比較無向圖的最大可能邊數與題目所給的數值。

對每一對不同頂點建立一條邊，可得到完全圖 $K_n$。其邊數為：

$$|E(K_n)| = \binom{n}{2} = \frac{n(n-1)}{2}$$

因此，任何含有 $n$ 個頂點的簡單無向圖皆滿足：

核心觀念

本題考查圖形資料結構中，判斷兩個頂點是否相鄰所需的時間複雜度。

若圖以 edge list（邊串列） 儲存，資料內容通常是：

$$(u_1,v_1),(u_2,v_2),\ldots,(u_m,v_m)$$

其中每一筆代表一條邊，$m$ 為圖中的邊數。判斷頂點 $u$ 與 $v$ 是否相鄰，必須確認邊 $(u,v)$ 或 $(v,u)$ 是否存在於串列中。

解題方法

逐一檢查每條邊：

1. 讀取一筆邊 $(x,y)$。
2. 判斷是否符合 $(x=u \land y=v)$，或無向圖中的 $(x=v \land y=u)$。
3. 若找到則表示兩頂點相鄰；若檢查完所有邊仍未找到，則表示不相鄰。

最壞情況下，目標邊位於串列最後，或根本不存在，因此需要檢查全部 $m$ 條邊：

$$T(m)=O(m)$$

若以漸進緊確界表示，線性搜尋的最壞情況為：

$$\Theta(m)$$

因此，單純使用 edge list 時，無法保證以 $O(1)$ 時間完成相鄰性判斷。

選項分析

題目敘述：

核心觀念

鄰接矩陣以二維陣列表示圖。若圖有 $n$ 個頂點，矩陣大小為 $n \times n$，其中：

• $A[i][j]=1$ 表示頂點 $i$ 與頂點 $j$ 之間有邊；
• $A[i][j]=0$ 表示兩者之間沒有邊。

刪除一個頂點時，不只要刪除該頂點所對應的資料，還必須移除：

1. 該頂點對應的整列；
2. 該頂點對應的整欄。

這是因為該頂點與其他所有頂點的邊資訊，分別儲存在矩陣的一整列與一整欄中。

解題方法

假設要刪除頂點 $v$：

• 刪除第 $v$ 列，需要處理約 $n$ 個元素；
• 刪除第 $v$ 欄，也需要處理約 $n$ 個元素。

因此總處理量為：

$$n+n=2n$$

忽略常數後，時間複雜度為：

$$\Theta(n)$$

若要求刪除後仍維持緊密的 $(n-1)\times(n-1)$ 鄰接矩陣，還可能需要搬移其他列與欄的資料，但其複雜度至少不是 $O(1)$，通常仍以 $O(n^2)$ 的資料搬移方式實作；在常見的分析中，刪除頂點所需檢查或清除其相關列、欄至少為 $O(n)$。

核心觀念

本題考查圖論中的「生成樹（spanning tree）」定義。

對一個連通圖 $G=(V,E)$ 而言，生成樹 $T$ 必須同時符合：

1. $T$ 包含原圖 $G$ 的所有頂點：
   $V(T)=V(G)$
2. $T$ 是樹，因此必須連通且不含環。
3. 若圖中共有 $|V|$ 個頂點，生成樹必定恰有：
   $|V|-1$
   條邊。

因此，生成樹可以視為「保留所有頂點，但刪除部分邊，使圖成為樹」的結果。

解題方法

題幹指出：

A spanning tree of a graph is a tree that covers all connected vertices in a graph.

其中 spanning 的意義是「涵蓋整個圖的頂點」，tree 的意義是「連通且無環」。所以生成樹就是涵蓋圖中所有頂點的樹。

若原圖有 $n$ 個頂點，生成樹需滿足：

$|E(T)|=n-1$

核心觀念

本題考查：

• 運算子的優先順序與結合律。
• 算術運算式轉換為二元樹。
• 二元樹的表示方式：
  • 內部節點儲存運算子。
  • 外部節點（葉節點）儲存運算元或數值。
• 關係運算子 $>$ 的優先順序低於算術運算子，因此整個運算式的根節點為 $>$。

算術運算子的優先順序為：

$$*、/ \;>\; +、-$$

同一層級的 $*、/、+、-$ 採由左至右結合。因此：

$$8*6/3=((8*6)/3)$$

以及：

$$9/3*7=((9/3)*7)$$

解題方法

原式為：

$$2+8*6/3-2>9/3*7-(2+3)*5$$

依照優先順序補上完整括號：

$$\left(\left(2+\left(\frac{8*6}{3}\right)\right)-2\right) > \left(\left(\frac{9}{3}*7\right)-\left((2+3)*5\right)\right)$$

改以二元運算子表示為：

$$\bigl((2+((8*6)/3))-2\bigr) > \bigl(((9/3)*7)-((2+3)*5)\bigr)$$

因此，根節點是關係運算子 $>$：

• 左子樹表示 $((2+((8*6)/3))-2)$。
• 右子樹表示 $(((9/3)*7)-((2+3)*5))$。

二元樹表示

                                  >
                                /   \
                               -     -
                              / \   / \
                             +   2 /   *
                            / \   / \ / \
                           2   /  /  7  +
                              / \ / \   / \
                             *  3 9  3 2   3
                            / \
                           8   6

核心觀念

題目考的是「運算式二元樹（expression tree）」的遞迴求值。

在運算式二元樹中：

• 葉節點儲存運算元，例如數字 $3$、$8$。
• 非葉節點儲存二元運算子，例如 $+$、$-$、$\times$、$\div$。
• 左子樹代表運算子的左運算元，右子樹代表右運算元。

因此，節點 $v$ 所代表的運算式值可由下列遞迴定義求得：

$$\operatorname{value}(v)= \begin{cases} v.key, & \text{若 }v\text{ 為葉節點}\\ \operatorname{value}(v.left)\;v.key\;\operatorname{value}(v.right), & \text{若 }v\text{ 為運算子節點} \end{cases}$$

求值順序是後序走訪（postorder traversal）：先計算左子樹，再計算右子樹，最後執行目前節點的運算子。

解題方法

先判斷目前節點是否為葉節點：

1. 若是葉節點，直接回傳其運算元。
2. 若不是葉節點，遞迴計算左子樹與右子樹。
3. 依目前節點的運算子，合併兩個子樹的結果。

完整虛擬碼

以下假設：

• v.key 儲存運算元或運算子。
• v.left 與 v.right 分別為左、右子節點。
• 運算子只有二元運算，例如 +、-、*、/。

Algorithm: evaluateExpression(T, v)
Input: A binary tree T and a node v in T
Output: The value of the expression rooted at v

if v.left == NULL and v.right == NULL then
    return v.key

leftValue  = evaluateExpression(T, v.left)
rightValue = evaluateExpression(T, v.right)

if v.key == '+' then
    return leftValue + rightValue
else if v.key == '-' then
    return leftValue - rightValue
else if v.key == '*' then
    return leftValue * rightValue
else if v.key == '/' then
    return leftValue / rightValue

核心觀念

本題考查以二元樹表示算術／比較運算式，以及遞迴走訪二元樹。

• 葉節點代表運算元，例如數字 $2、3、8$。
• 內部節點代表二元運算子，例如 $+、-、*、/、>$。
• 每個內部節點的左子樹是左運算式，右子樹是右運算式。
• 為確保運算優先順序與結合方式完全正確，每個二元運算都加上一對括號。

若內部節點 $v$ 的元素為運算子，則其表示式為：

$$(\text{左子樹表示式} \; \text{運算子} \; \text{右子樹表示式})$$

解題方法

採用後序結構的遞迴組合方式：

1. 若 $v$ 是葉節點，直接輸出其內容。
2. 若 $v$ 是內部節點：
   • 先輸出左括號 (。
   • 遞迴輸出左子樹。
   • 輸出目前節點的運算子。
   • 遞迴輸出右子樹。
   • 最後輸出右括號 )。

如此可保證每個內部節點都形成：

(左運算式 運算子 右運算式)

完整虛擬碼

Algorithm: printExpression(T, v)
Input: A binary tree T and a node v in T

if v is an external node of T then
    print(element(v))
else
    print("(")
    printExpression(T, left(v))
    print(element(v))
    printExpression(T, right(v))
    print(")")

其中：

• external node 表示葉節點。
• left(v) 取得 $v$ 的左子節點。
• right(v) 取得 $v$ 的右子節點。

核心觀念

本題考查最大堆積（max-heap）的自底向上建構法（bottom-up heap construction）。

最大堆積必須同時滿足：

1. 完全二元樹：以陣列儲存時，節點位置固定。
2. 堆積順序：每個父節點值都不小於其子節點值。

採用 1-based 陣列索引時：

$$\text{left}(i)=2i,\qquad \text{right}(i)=2i+1$$ $$\text{parent}(i)=\left\lfloor \frac{i}{2}\right\rfloor$$

對含有 $n=18$ 個元素的陣列，葉節點為第 $10$ 至第 $18$ 個位置，因此不必再調整。內部節點為：

$$\left\lfloor\frac{n}{2}\right\rfloor,\ldots,1 =9,\ldots,1$$

自底向上依序對節點 $9,8,\ldots,1$ 執行下濾（sift-down）。每次都是將一個新根節點加入兩個已經建好的子堆，並向下交換至正確位置。

---

解題方法與逐步建構

原始陣列為：

$$A= [13,2,16,21,15,79,32,24,20,14,7,82,51,43,55,59,8,1]$$

第 1 步：處理節點 $i=9$

節點 $9$ 的值為 $20$，子節點為：

• 左子節點：$A[18]=1$
• 沒有右子節點

因為 $20>1$，不需交換。

$$A= [13,2,16,21,15,79,32,24,20,14,7,82,51,43,55,59,8,1]$$

---

第 2 步：處理節點 $i=8$

節點 $8$ 的值為 $24$，子節點為 $59$ 與 $8$。

選擇較大的子節點 $59$，交換：

$$24\leftrightarrow59$$

陣列更新為：

$$A= [13,2,16,21,15,79,32,59,20,14,7,82,51,43,55,24,8,1]$$

---

第 3 步：處理節點 $i=7$

節點 $7$ 的值為 $32$，子節點為 $43$ 與 $55$。

選擇較大的子節點 $55$，交換：

$$32\leftrightarrow55$$

陣列更新為：

$$A= [13,2,16,21,15,79,55,59,20,14,7,82,51,43,32,24,8,1]$$

---

第 4 步：處理節點 $i=6$

節點 $6$ 的值為 $79$，子節點為 $82$ 與 $51$。

選擇較大的子節點 $82$，交換：

$$79\leftrightarrow82$$

陣列更新為：

$$A= [13,2,16,21,15,82,55,59,20,14,7,79,51,43,32,24,8,1]$$

---

第 5 步：處理節點 $i=5$

節點 $5$ 的值為 $15$，子節點為 $14$ 與 $7$。

因為：

$$15>14,\qquad 15>7$$

不需交換。

$$A= [13,2,16,21,15,82,55,59,20,14,7,79,51,43,32,24,8,1]$$

---

第 6 步：處理節點 $i=4$

節點 $4$ 的值為 $21$，子節點為 $59$ 與 $20$。

選擇較大的子節點 $59$，交換：

$$21\leftrightarrow59$$

此時 $21$ 移至位置 $8$，其子節點為 $24$ 與 $8$。因為 $24>21$，再交換：

$$21\leftrightarrow24$$

陣列更新為：

$$A= [13,2,16,59,15,82,55,24,20,14,7,79,51,43,32,21,8,1]$$

---

核心觀念

本題考查兩個操作：

1. 使用 Bottom-up Build-Max-Heap 將陣列建成最大堆積（max-heap）。
2. 對最大堆積連續執行兩次 remove()，每次刪除根節點的最大值。

採用 1-based index 表示陣列：

• 父節點索引：$\lfloor i/2 \rfloor$
• 左子節點索引：$2i$
• 右子節點索引：$2i+1$

最大堆積必須滿足：

$$A[\lfloor i/2 \rfloor] \geq A[i]$$

remove() 的流程為：

1. 移除根節點。
2. 將最後一個元素移到根節點。
3. 由根向下與較大的子節點交換，直到恢復最大堆積性質。

---

解題方法：建立最大堆積

原始陣列為：

$$[13,2,16,21,15,79,32,24,20,14,7,82,51,43,55,59,8,1]$$

由最後一個非葉節點 $i=\lfloor 18/2 \rfloor=9$ 開始，依序向前進行下濾（sift-down）。

主要交換結果如下：

• $i=8$：$24$ 與子節點 $59$ 交換。
• $i=7$：$32$ 與較大子節點 $55$ 交換。
• $i=6$：$79$ 與子節點 $82$ 交換。
• $i=4$：$21$ 與 $59$ 交換，接著 $21$ 與 $24$ 交換。
• $i=3$：$16$ 與 $82$ 交換，接著與 $79$ 交換。
• $i=2$：$2$ 依序與 $59$、$24$、$21$ 交換。
• $i=1$：$13$ 依序與 $82$、$79$、$51$ 交換。

建成的最大堆積為：

$$\boxed{ [82,59,79,24,15,51,55,21,20,14,7,16,13,43,32,2,8,1] }$$

其樹狀結構為：

                 82
          /              \
        59                79
      /   \             /    \
    24     15          51     55
   / \     / \        / \    / \
 21  20  14  7      16 13  43 32
 / \  /
2  8 1

---

第一次 remove()

原本根節點為最大值 $82$，將最後元素 $1$ 移至根：

$$[1,59,79,24,15,51,55,21,20,14,7,16,13,43,32,2,8]$$

向下調整：

1. $1$ 與較大的子節點 $79$ 交換：

核心觀念

本題考查：

• 陣列區間的平均值計算。
• 迭代式迴圈設計。
• 迴圈次數與時間複雜度分析。
• 累加器（accumulator）的使用方式。

從索引 $i$ 到 $j$，包含頭尾共有：

$$n=j-i+1$$

個整數。因此平均值為：

$$\text{average} = \frac{\displaystyle\sum_{k=i}^{j} A[k]}{j-i+1}$$

解題時先以變數 sum 累加區間內所有元素，迴圈結束後再除以元素個數。

解題方法

設：

• sum：目前累加總和，初始值為 $0$。
• k：目前處理到的索引，從 $i$ 走到 $j$。
• count：元素個數，等於 $j-i+1$。

完成後的虛擬碼如下：

Algorithm IterativeAverage (A, i, j):
Input: an array A and starting index i and end index j
Output: the average of (j-i+1) integers in A

    sum ← 0

    for k ← i to j do
        sum ← sum + A[k]

    return sum / (j - i + 1)

正確性說明

迴圈執行到索引 $k$ 時，sum 所代表的值為：

$$\sum_{t=i}^{k} A[t]$$

因此迴圈結束於 $k=j$ 時：

$$\text{sum} = \sum_{t=i}^{j} A[t]$$

再除以區間內的元素數量 $j-i+1$，即可得到正確平均值：

$$\text{average} = \frac{\text{sum}}{j-i+1}$$

核心觀念

本題考查：

1. Divide and Conquer（分治法）。
2. Binary Recursion（二元遞迴）：每次問題分成兩個子問題。
3. 平均數的加權合併。
4. 遞迴時間方程式與 Master Theorem。

若左半部有 $n_1$ 個元素、平均為 $\bar{A}_1$；右半部有 $n_2$ 個元素、平均為 $\bar{A}_2$，總平均不是兩個平均數直接相加再除以二，而是：

$$\bar{A} = \frac{n_1\bar{A}_1+n_2\bar{A}_2}{n_1+n_2}$$

由於陣列索引範圍為 $i$ 到 $j$，元素個數為：

$$n=j-i+1$$

解題方法

將區間 $[i,j]$ 分成左右兩半，令：

$$m=\left\lfloor\frac{i+j}{2}\right\rfloor$$

則：

• 左半部索引為 $i$ 到 $m$，元素個數為 $m-i+1$。
• 右半部索引為 $m+1$ 到 $j$，元素個數為 $j-m$。

遞迴取得兩半的平均數後，再依照各自元素數量加權合併。

完整虛擬碼

Algorithm MergeAverage(A, i, j):
Input:  an array A and starting index i and end index j
Output: The average of A[i], A[i+1], ..., A[j]

if i == j then
    return A[i]

m ← floor((i + j) / 2)

leftAverage ← MergeAverage(A, i, m)
rightAverage ← MergeAverage(A, m + 1, j)

leftCount ← m - i + 1
rightCount ← j - m

return (leftCount × leftAverage + rightCount × rightAverage)
       / (leftCount + rightCount)

基底條件

當 $i=j$ 時，區間內只有一個元素，因此平均數就是該元素本身：

$$\operatorname{MergeAverage}(A,i,i)=A[i]$$

遞迴合併

左半部平均為 leftAverage，右半部平均為 rightAverage，所以整體平均為：

$$\frac{ (m-i+1)\cdot\text{leftAverage} + (j-m)\cdot\text{rightAverage} }{ j-i+1 }$$

程式中的分母也可寫成：

$$\text{leftCount}+\text{rightCount}=j-i+1$$

時間複雜度推導

設 $T(n)$ 表示處理 $n$ 個元素所需的時間。

每次遞迴會：

• 將問題分成兩個約為 $n/2$ 的子問題。
• 執行常數次的索引計算、乘法、加法與除法。

因此遞迴時間方程式為：

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

當 $n$ 不是 $2$ 的次方時，嚴格寫法為：