108 年 國立臺灣大學電子工程學研究所丁組《資料結構（B）》

核心觀念

Binary heap（二元堆積）必須同時符合兩項條件：

1. 結構條件：是一棵完全二元樹（complete binary tree）。
2. 堆積性質：
   • Max-heap：每個節點的鍵值不小於其子節點。
   • Min-heap：每個節點的鍵值不大於其子節點。

其中，「完全二元樹」表示除了最後一層之外，其餘各層皆填滿，且最後一層的節點必須由左至右排列。

因此，完全二元樹是 binary heap 的必要結構條件。

解題方法

題目敘述為：

A binary heap may not be a complete binary tree.

意思是：「二元堆積可能不是完全二元樹。」

根據定義，二元堆積一定要先具備完全二元樹的結構，再額外滿足 min-heap 或 max-heap 的順序條件。若一棵二元樹不是完全二元樹，即使節點大小符合堆積順序，也不能稱為 binary heap。

例如，下列樹雖符合 max-heap 的大小關係：

核心觀念

本題考查「將任意完全二元樹轉換成 Heap 的時間複雜度」。

Heap 通常指符合下列條件的完全二元樹：

1. 結構上是完全二元樹。
2. 順序上符合 Heap-order：
   • Max-Heap：每個父節點皆不小於子節點。
   • Min-Heap：每個父節點皆不大於子節點。

將完全二元樹轉成 Heap，最有效率的方法是使用自底向上的 Build-Heap：

• 從最後一個非葉節點開始。
• 依序對每個內部節點執行 Heapify。
• 葉節點不需要調整。

---

解題方法

設樹中共有 $n$ 個節點。對高度為 $h$ 的節點執行 Heapify，最多需要向下調整 $O(h)$ 層。

完全二元樹中，高度越大的節點數量越少：

• 高度 $0$ 的節點約有 $\frac{n}{2}$ 個；
• 高度 $1$ 的節點約有 $\frac{n}{4}$ 個；
• 高度 $2$ 的節點約有 $\frac{n}{8}$ 個；
• 一般而言，高度為 $h$ 的節點數量至多為 $\frac{n}{2^{h+1}}$。

因此，所有節點執行 Heapify 的總成本為：

$$T(n) = \sum_{h=0}^{\lfloor \log n \rfloor} \frac{n}{2^{h+1}}O(h)$$

提出 $n$：

$$T(n) = O(n)\sum_{h=0}^{\lfloor \log n \rfloor}\frac{h}{2^{h+1}}$$

由於級數

核心觀念

本題考查兩個定義：

1. Min-heap（最小堆積）
   必須是完全二元樹，且每個節點的鍵值皆不大於其子節點：

   $\text{parent} \leq \text{child}$

2. Preorder traversal（前序走訪）
   順序為：

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

題目問的是「是否存在」一個具有七個相異元素的 min-heap，使其前序走訪結果恰好為遞增排序。

---

解題方法

直接構造一個符合條件的例子即可證明敘述為真。

取完全二元樹如下：

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

其前序走訪順序為：

$1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow 6 \rightarrow 7$

正好是由小到大的排序結果。

接著檢查 min-heap 條件：

核心觀念

陣列實作動態排序串列時，元素通常必須維持遞增或遞減順序。因此插入或刪除元素時，不能只修改一個位置，還要搬移一段連續元素。

若陣列目前有 $n$ 個元素：

• 插入新元素：需將插入位置之後的元素向右搬移。
• 刪除既有元素：需將被刪除位置之後的元素向左搬移。

若操作位置均勻分布，平均搬移量約為一半元素，而不是四分之一。

解題方法

設插入位置可能是第 $0,1,\ldots,n$ 個位置，共有 $n+1$ 種可能。

若插入在位置 $i$，需搬移後方的 $n-i$ 個元素，因此平均搬移數為

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

因此，陣列插入排序串列的平均搬移量為

$$\Theta(n).$$

刪除元素時，若刪除第 $i$ 個元素，需搬移其後的 $n-i-1$ 個元素。平均搬移數為

核心觀念

本題考查中序表示法（infix notation）與後序表示法（postfix notation）的運算式表示方式，以及運算子優先權與括號的作用。

• 中序表示法：運算子寫在兩個運算元之間，例如 $A+B$。
• 後序表示法：運算子寫在兩個運算元之後，例如 $AB+$。
• 後序表示法不需依賴括號或運算子優先權即可決定運算順序，通常可利用堆疊直接由左至右處理。

解題方法

判斷題幹中的因果敘述是否完全正確。

中序表示法並非「需要括號」才能表達運算式。例如：

$$A+B\times C$$

依照運算子優先權，乘法先於加法，因此可直接判定為：

$$A+(B\times C)$$

不加括號也不會產生歧義。

括號只是在需要改變預設運算順序時使用，例如：

$$(A+B)\times C$$

相較之下，後序表示法將運算順序直接編碼在符號排列中：

$$A+B\times C \longrightarrow ABC\times+$$

觀念解析與推導

雜湊表（Hash Table）採用**獨立鏈結法（Separate Chaining）**時，其操作效能取決於負載因子（Load Factor）$\alpha = \frac{N}{M}$（其中 $N$ 為元素總數，$M$ 為桶數/陣列大小）。

1. 鏈長與效能關聯：當資料量 $N$ 不斷增加而表長 $M$ 不變時，負載因子 $\alpha$ 會大幅提升，導致每個桶位（Bucket）所連結的單向串列（Chain）過長。

核心觀念

本題考查雜湊表（hash table）發生碰撞（collision）時的開放定址法（open addressing），以及其中的二次探測（quadratic probing）。

若雜湊函數產生的初始位置為 $h(k)$，二次探測通常依序檢查：

$$h(k),\quad h(k)+1^2,\quad h(k)+2^2,\quad h(k)+3^2,\ldots$$

實際位置須對雜湊表大小 $m$ 取模：

$$\operatorname{index}_i=(h(k)+i^2)\bmod m$$

其中 $i$ 表示第 $i$ 次探測所使用的位移量。

解題方法

題目敘述「在第 $i$ 次碰撞時，將 $i^2$ 加到該位址上」，其意義就是發生碰撞後，不採用固定的線性位移，而是依照碰撞次數使用平方位移：

觀念與推導

根據題目定義，單一節點之二元樹高度為 $0$。高度為 $h$ 的二元樹最多可容納之節點數 $N_{\max}$ 為：
$N_{\max} = \sum_{i=0}^{h} 2^i = 2^{h+1} - 1$

當二元樹擁有 $n = 1000$ 個節點時，若要使高度最小，需滿足：

核心觀念

這題考查二元搜尋樹（BST）與 AVL 樹的定義。

• BST：對任一節點 $x$，左子樹所有鍵值小於 $x$，右子樹所有鍵值大於 $x$。
• AVL 樹：本身必須是 BST，且每一個節點都滿足平衡條件：

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

其中 $h$ 表示子樹高度。

題目只保證 $T$ 的左、右子樹各自為 AVL 樹，並未保證根節點 $T$ 本身左右子樹的高度差不超過 $1$。

解題方法

關鍵在於區分：

• 左子樹是 AVL 樹：表示左子樹內部的每個節點皆平衡。
• 右子樹是 AVL 樹：表示右子樹內部的每個節點皆平衡。
• $T$ 是 AVL 樹：除了左右子樹內部平衡外，根節點也必須平衡。

可構造下列 BST：

          10
         /  \
        5    20
       /
      3
     / \
    2   4

採用葉節點高度為 $0$、空子樹高度為 $-1$：

• 節點 $3$ 的左右子樹高度皆為 $0$，高度為 $1$，平衡。
• 節點 $5$ 的左子樹高度為 $1$、右子樹高度為 $-1$，高度差為

$$|1-(-1)|=2$$

此例中節點 $5$ 並不平衡，因此不符合左子樹為 AVL 的條件。改用以下合法構造：

核心觀念

後序表示法（postfix expression）將運算子放在運算元之後，計算時由左至右掃描：

• 遇到運算元：推入堆疊。
• 遇到二元運算子：取出堆疊頂端的兩個運算元，先取出者為右運算元，後取出者為左運算元，計算後再將結果推回堆疊。

本題的運算子皆為二元運算子，包含加法、減法與除法。

解題方法

將運算式

$$53+77-1-/$$

拆成後序符號：

$$5,\ 3,\ +,\ 7,\ 7,\ -,\ 1,\ -,\ /$$

依序利用堆疊計算：

讀入符號	操作	堆疊內容
$5$	推入	$[5]$
$3$	推入	$[5,3]$
$+$	$5+3=8$	$[8]$
$7$	推入	$[8,7]$
$7$	推入	$[8,7,7]$
$-$	$7-7=0$	$[8,0]$
$1$	推入	$[8,0,1]$

各選項分析與證明

(A) 正確
依據漸近記號之轉置對稱性（Transpose Symmetry）：
$f(n) \in O(g(n)) \iff \exists c > 0, n_0 > 0 \text{ 使得 } \forall n \ge n_0, 0 \le f(n) \le c \cdot g(n)$
等式兩邊同除以 $c$（取 $c' = 1/c > 0$）：
$\iff \exists c' > 0, n_0 > 0 \text{ 使得 } \forall n \ge n_0, 0 \le c' \cdot f(n) \le g(n) \iff g(n) \in \Omega(f(n))$

(B) 正確
依據定義，$\Theta(g(n)) = O(g(n)) \cap \Omega(g(n))$，故 $\Theta(g(n)) \subseteq \Omega(g(n))$。
對任意集合 $X$ 與 $Y$，若 $X \subseteq Y$，則 $X \cap Y = X$。
因此 $\Theta(g(n)) \cap \Omega(g(n)) = \Theta(g(n))$ 恆成立。

(C) 錯誤
$o(g(n)) \subseteq O(g(n)) - \Omega(g(n))$，但兩者不相等。
反例：設 $g(n) = n$，$f(n) = \begin{cases} n, & n \text{ 為偶數} \\ 1, & n \text{ 為奇數} \end{cases}$

• $f(n) \le n \implies f(n) \in O(n)$。

(A) 錯誤
對 BST 進行**中序追蹤（Inorder Traversal）**才能得到遞增排序結果；前序追蹤（Preorder Traversal）無法保證獲得排序結果。

(B) 正確
利用中序追蹤可以在 $O(n)$ 時間內按順序訪問樹中所有元素，因此尋找第 $k$ 小元素的最高時間複雜度為 $O(n)$（若節點額外紀錄子樹大小，可進一步優化至 $O(h)$）。

(C) 正確
根據 BST 定義，樹中任一節點的左子樹所有鍵值皆小於該節點鍵值，右子樹所有鍵值皆大於該節點鍵值，且其左右子樹各自皆須符合 BST 定義。因此 BST 的任意子樹必為另一棵 BST。

(D) 正確
高度為 $h$ 之最小 AVL Tree 的最少節點數遞迴式為：
$N(h) = N(h-1) + N(h-2) + 1$

核心觀念

本題考查：

• Adjacency Matrix 與 Adjacency List 的適用情境與操作複雜度。
• BFS、DFS 的記憶體需求。
• BFS 求無權圖最短路徑的性質。
• 使用 Adjacency List 進行拓樸排序的時間複雜度。

設圖中頂點數為 $|V|$，邊數為 $|E|$。

解題方法

逐一檢查各選項是否符合圖形表示法與圖形搜尋演算法的基本性質。

選項分析

(A) Adjacency List is more suitable for dense graph.

錯誤。

Adjacency Matrix 必須配置一個 $|V|\times |V|$ 的矩陣，因此空間複雜度為：

$$O(|V|^2)$$

Adjacency List 只儲存實際存在的邊，空間複雜度為：

$$O(|V|+|E|)$$

稀疏圖的 $|E|$ 遠小於 $|V|^2$，使用 Adjacency List 較節省空間；稠密圖的邊數接近 $|V|^2$，使用 Adjacency Matrix 通常較合適。

因此，Adjacency List 並非較適合稠密圖，選項錯誤。

---

(B) Using Adjacency Matrix, checking edge between vertices u and v takes constant time.

正確。

在 Adjacency Matrix 中，頂點 $u$ 與 $v$ 之間是否有邊，直接查詢矩陣位置 $A[u,v]$ 即可：

$$A[u,v]= \begin{cases} 1, & \text{若 }u\text{ 與 }v\text{ 之間有邊}\\ 0, & \text{否則} \end{cases}$$

矩陣查詢只需一次索引存取，因此時間複雜度為：

$$O(1)$$

---

(C) The big advantage of BFS is that it has much lower memory requirement than DFS.

錯誤。

BFS 使用 Queue，會保存某一層或多層尚未處理的頂點。最壞情況下，Queue 可能同時存放 $O(|V|)$ 個頂點。

DFS 使用遞迴堆疊或明確 Stack，最壞情況下也需要 $O(|V|)$ 的空間。因此，BFS 並沒有「遠低於 DFS」的記憶體需求。

在某些圖形中：

核心觀念

本題考查排序演算法的「輸入敏感性（input-sensitive）」。

若排序演算法對輸入不敏感，表示在元素個數為 $n$ 時，其執行時間的漸進複雜度不因原始排列不同而改變。也就是說，最佳、平均與最差情況的時間複雜度相同，或至少同階。

常見排序法的判斷如下：

• 若每次都固定執行相同數量的比較或處理，通常對輸入不敏感。
• 若執行過程會依資料排列決定提早結束、分割結果或遞迴深度，通常對輸入敏感。

解題方法

逐一比較各排序演算法在不同輸入排列下的時間複雜度：

• Bubble sort：可能因已排序而提早結束，時間會改變。
• Selection sort：不論資料排列，總比較次數固定為 $\Theta(n^2)$。
• Merge sort：每次分割與合併的結構固定，時間為 $\Theta(n\log n)$。
• Quick sort：樞紐元素造成的分割結果取決於輸入排列。
• Radix sort：依固定位數與基數逐位處理，時間不依初始排列改變。

因此選出 Selection sort、Merge sort 與 Radix sort。

選項分析

(A) Bubble sort：錯誤

標準的最佳化 Bubble sort 在每一輪檢查是否發生交換。若輸入已經排序完成，第一輪就可發現沒有交換，直接結束：

$$T_{\text{best}}(n)=\Theta(n)$$

若輸入為反向排序，則需要進行多輪交換：

$$T_{\text{worst}}(n)=\Theta(n^2)$$

最佳與最差情況不同，因此 Bubble sort 對輸入敏感。

(B) Selection sort：正確

Selection sort 每一輪都必須掃描尚未排序的部分，找出最小值。

比較次數固定為：

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

不論輸入原本是已排序、反向排序或隨機排列，都必須完成相同的掃描工作。因此其最佳、平均與最差時間複雜度皆為：

$$\Theta(n^2)$$

所以 Selection sort 對輸入不敏感。

(C) Merge sort：正確

核心觀念

本題考查雜湊表（hash table）及開放定址法（open addressing）的基本性質：

• 雜湊表利用雜湊函數將鍵值映射到表格位置，平均搜尋、插入、刪除時間皆可達 $O(1)$。
• 開放定址法發生碰撞時，資料仍直接存放在表格內，依探測序列尋找下一個位置。
• 常見探測方式包括：
  • 線性探測：
    $h(k,i)=(h'(k)+i)\bmod m$
  • 二次探測：
    $h(k,i)=(h'(k)+c_1i+c_2i^2)\bmod m$
  • 雙重雜湊：
    $h(k,i)=(h_1(k)+i h_2(k))\bmod m$

其中 $m$ 為表格大小，$i=0,1,2,\ldots$ 為探測次數。

---

解題方法

逐一檢查每個敘述是否符合雜湊表與探測法的定義，特別注意：

1. 雜湊表的主要優勢是平均時間複雜度，而不是限定某種操作比例。
2. 開放定址法是否能處理重複鍵值，要看資料使用方式；重複鍵值本身不會使探測法失效。
3. 刪除資料時，線性探測必須使用墓碑標記（tombstone），不能直接清空位置。
4. 二次探測不保證能走訪表格中的所有位置。
5. 雙重雜湊的步進距離會依鍵值改變，可降低群聚。

---

選項分析

（A）錯誤

「雜湊表一般用於插入與刪除比搜尋更頻繁的情況」並不是雜湊表的使用條件。

雜湊表的核心優勢是：

$$\text{平均搜尋}=\text{平均插入}=\text{平均刪除}=O(1)$$

因此，雜湊表適合需要快速查找、插入與刪除的情境，例如字典、符號表與資料庫索引。操作頻率比例並不是判斷是否使用雜湊表的依據。

所以此敘述錯誤。

---

（B）錯誤

開放定址法仍可處理具有重複鍵值的資料。

若兩筆資料具有相同鍵值，它們會產生相同的初始雜湊位置，但後續仍可透過探測序列放入不同位置。例如線性探測中：

$$h(k,0),h(k,1),h(k,2),\ldots$$

即使兩筆資料的鍵值相同，只要插入時不要求「相同鍵值必須覆蓋舊資料」，第二筆資料仍能繼續探測下一個空位。

唯一需要額外定義的是搜尋與刪除行為，例如：

• 搜尋一個鍵值時回傳任一筆資料；
• 搜尋時回傳所有相同鍵值的資料；
• 插入相同鍵值時更新原資料。

因此，重複鍵值會影響資料操作語意，但不代表開放定址法無法使用。

所以此敘述錯誤。

---

（C）錯誤

線性探測的刪除不能直接將資料位置設為空白，否則可能中斷搜尋路徑。

核心觀念

本題考查漸近時間複雜度的判斷，重點包括：

• 每次將問題規模縮小固定比例，所需步數為 $\Theta(\log n)$。
• Horner 法以逐次乘加計算多項式，運算次數與多項式次數成正比。
• 遞迴程式可用遞迴式與主定理分析。
• 巢狀迴圈要分別計算每層的迭代次數，再相乘。
• 迴圈變數若逐次累加，累積量可能呈平方成長。

解題方法與選項分析

(A) 正確。 若每一步都能花固定時間，將問題大小縮小固定比例 $r$（其中 $0<r<1$），經過 $k$ 步後，規模約為 $nr^k$。當規模降至常數時：

$$nr^k \le 1 \quad\Longrightarrow\quad k \ge \frac{\log n}{\log(1/r)}$$

因此步數為 $\Theta(\log n)$，自然也屬於 $O(\log n)$。

(B) 錯誤。 Horner 法將多項式改寫成連續的乘加形式。對 $n$ 次多項式，每個係數只需處理一次，因此總共進行 $\Theta(n)$ 次乘法與加法，時間複雜度為 $\Theta(n)$，不是 $\Theta(n^2)$。額外空間為 $O(1)$。

(C) 正確。 每次呼叫會遞迴呼叫 7 次，每次子問題大小為 $n/2$；遞迴之外的迴圈執行 $\Theta(n^3)$ 次。因此遞迴式為：

$$T(n)=7T(n/2)+\Theta(n^3)$$

主定理中，$a=7$、$b=2$，所以：

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

因為 $\log_2 7<3$，而非遞迴成本為 $\Theta(n^3)$，依主定理第三種情形：