108 年 國立中央大學資訊管理學系碩士班甲組《資料結構》

核心觀念

本題考查二元搜尋樹的中序走訪、選擇排序，以及圖形的深度優先與廣度優先走訪。

• 二元搜尋樹（BST）：左子樹鍵值小於根節點，右子樹鍵值大於或等於根節點。本題將重複的 $33$ 保留為另一個節點，遇到相等鍵值時往右子樹搜尋。
• 中序走訪：依序走訪「左子樹、根節點、右子樹」。對二元搜尋樹做中序走訪，會得到由小到大的鍵值。
• 選擇排序：每一輪從尚未排序的部分找出最小值，與該部分的第一個元素交換。
• 圖形走訪：DFS 優先沿著尚未走訪的鄰點深入；BFS 則依距離起點的層次逐層走訪。

(A) 建立二元搜尋樹並做中序走訪

依序插入 $33, 78, 11, 48, 20, 55, 33, 99$：

1. $33$ 為根節點。
2. $78>33$，放在 $33$ 的右側。
3. $11<33$，放在 $33$ 的左側。
4. $48>33$，再比較 $78$；$48<78$，放在 $78$ 的左側。
5. $20<33$，再比較 $11$；$20>11$，放在 $11$ 的右側。
6. $55>33$、$55<78$、$55>48$，放在 $48$ 的右側。
7. 第二個 $33$ 遇到相同鍵值時往右；依序比較 $78$、$48$ 後，放在 $48$ 的左側。
8. $99>33$、$99>78$，放在 $78$ 的右側。

          33
         /  \
       11    78
         \   / \
         20 48  99
            / \
           33 55

中序走訪順序為「左子樹 → 根節點 → 右子樹」：

• 先走訪左子樹：$11, 20$
• 再走訪根節點：$33$
• 最後走訪右子樹：先走訪 $48$ 的左子樹 $33$，再走訪 $48$、$55$，最後走訪 $78$、$99$

結果：

(B) 選擇排序

待排序資料為 $3, 2, 6, 4, 1, 5$。每一輪從未排序區間選出最小值，與該區間的第一個元素交換。

核心觀念

鄰接矩陣的第 $i$ 列、第 $j$ 行描述頂點 $i$ 到頂點 $j$ 的連結。非對角線項代表不同頂點間的邊；對角線項代表自環。矩陣對稱時，表示每對頂點間的連結方向相同，可用無向圖表示。加權矩陣中，有限數值記錄邊的權重，$\infty$ 表示沒有邊。

解題方法

依原卷圖，Question 2 給出一個 $4 \times 4$ 矩陣，頂點為 $1,2,3,4$；(A) 的未列數值為 $\infty$，(B) 則規定對角線為 $0$、非對角線為 $1$。頁面旁的圖屬於 Question 1(C)，與本題無關。

逐格查看矩陣：先用對角線判斷有無自環，再查看非對角線的有限值來列出頂點間的邊。若 $x_{ij} \ne x_{ji}$，則須分別判斷兩個方向。

(A) 加權有向圖

矩陣為

依題目所用的表示方式，對角線上的 $0$ 表示沒有自環；正的有限值表示該方向有邊，且數值為權重。因此，頂點 $1$、$3$ 各有一條權重為 $1$ 的自環；頂點 $2$、$4$ 沒有自環。

非對角線的有限值給出五條有向邊：

核心觀念

• 2‑3 樹定義：每個內部節點的子數只能是 2（稱為 2‑node）或 3（稱為 3‑node），且所有葉子位於同一層，樹的高度 $h$ 為根到葉子的邊數。
• 葉子數與分支數的關係：若把每個內部節點視為「分支因子」，則從根到任一葉子經過的分支因子乘積即為該葉子所在的子樹大小。
• 上下界：最小葉子數發生在所有內部節點皆為 2‑node，最大葉子數發生在所有內部節點皆為 3‑node。

解題方法

1. 下界：

   • 當每層皆為 2‑node 時，根的子樹個數為 $2$，其子樹再各自分成 $2$ 個，如此遞迴 $h$ 層。
   • 因此葉子總數 $L_{\min}=2^h$。

2. 上界：

   • 當每層皆為 3‑node 時，根的子樹個數為 $3$，每層再各自分成 $3$ 個，遞迴 $h$ 層。
   • 故葉子總數 $L_{\max}=3^h$。

3. 可行範圍的完整性（任意 $L$ 滿足 $2^h\le L\le3^h$ 都可構成）：

   • 以歸納法證明。
   • 基礎步（$h=0$）：樹僅有根且同時是葉子，唯一葉子數 $L=1$，且 $2^0=3^0=1$，範圍成立。
   • 歸納假設：假設對高度 $h-1$ 的所有 2‑3 樹，葉子數可取得任意 $L'$ 滿足 $2^{h-1}\le L'\le3^{h-1}$。
   • 歸納步：對高度 $h$ 的樹，根可以是 2‑node 或 3‑node。
     • 若根為 2‑node，則兩個子樹皆為高度 $h-1$ 的 2‑3 樹，葉子數 $L=L_1+L_2$，其中 $L_1,L_2$ 各滿足 $2^{h-1}\le L_i\le3^{h-1}$。

核心觀念

• 第 k 小元素：在大小為 $n$ 的集合中，排序後第 $k$ 個位置的元素（$1\le k\le n$）。
• 選擇問題 (Selection problem)：在不完全排序的情況下找出第 $k$ 小（大）元素。
• 分割 (Partition) 原理：與 QuickSort 相同，選取樞紐 (pivot) 後，使左側皆 ≤ 樞紐，右側皆 ≥ 樞紐。
• 迭代快速選擇：利用分割的返回位置 $p$ 判斷第 $k$ 小元素位於左、右或正好是樞紐，重複迭代直至找到。

解題方法

1. 選擇樞紐

   • 直接選取區間最右端元素 $A[high]$ 作為樞紐 (簡化實作)。

2. Partition（非遞迴）

   • 設 $i = low-1$，遍歷 $j=low$ 到 $high-1$：若 $A[j]\le pivot$，則 $i++$ 並交換 $A[i]$、$A[j]$。
   • 迴圈結束後，將樞紐與 $A[i+1]$ 交換，返回索引 $p=i+1$。

3. 迭代 QuickSelect

   • 設 $low=0,\ high=n-1$。
   • 進入 while 迴圈：
     • 執行 Partition 取得 $p$。
     • 若 $p == k-1$，則 $A[p]$ 為第 $k$ 小元素，結束。
     • 若 $p > k-1$，將搜尋區間縮至左側：$high = p-1$。
     • 若 $p < k-1$，將搜尋區間縮至右側：$low = p+1$。

4. 終止條件

   • 迴圈必於找到 $p = k-1$ 時停止，因為每次 Partition 至少排除一個不可能是第 $k$ 小的元素，時間上期望 $O(n)$。

程式實作（非遞迴）