111 年 國立成功大學資訊工程系碩士班《程式設計》

核心觀念

兩個空格考的是以鏈結串列實作的堆疊：

• Stack_pop：移除頂端節點，讓 top 指向下一個（較舊的）節點。
• Stack_push：新節點的 prev 指向原本的頂端，再把 top 更新為新節點。

top == NULL 表示空堆疊，推入與彈出都是 $O(1)$。

解題方法

Stack_pop 已先保存頂端的值與節點位址 tmp，接著只要把 top 往下移，再釋放舊節點：

stk->top = tmp->prev;      /* TODO (A) */

Stack_push 要先把新節點接到原頂端之上，程式之後再把 top 改成新節點：

new_node->prev = stk->top; /* TODO (B) */

轉換程式如何運作

pre_to_post 用堆疊記錄「還在等運算元的運算子」，並用字元 'A' 當作標記，表示「這個運算子的第一個運算元已經輸出完畢」：

• 讀到運算子：推入堆疊。
• 讀到運算元：直接輸出；接著只要頂端是標記 'A'，就代表某個運算子的兩個運算元都已完成——彈出標記，再彈出並輸出該運算子（迴圈中 char top = Stack_pop(stk); 彈出的是標記，`pri

核心觀念

本題考查不相交集合（disjoint-set）的樹狀表示，以及依高度合併（union by height）。每個集合由一棵樹表示，根節點代表集合；合併兩個集合時，將較矮樹的根接到較高樹的根下，並保留兩棵樹原有的內部結構。

解題方法

原圖中，根節點 $1$ 的最長路徑為 $1\to a\to4$，高度為 $2$；根節點 $6$ 的最長路徑為 $6\to7\to9\to12$，高度為 $3$。因此要把根節點 $1$ 接到根節點 $6$ 之下，並保留兩棵樹各自原有的子樹關係。

合併後根節點仍是 $6$，而 $1$ 成為 $6$ 的子節點；$a$ 仍是 $1$ 的子節點，$7$、$b$、$8$ 仍是 $6$ 的子節點。這與選項 (A) 的圖相符。

此合併可用下列步驟表示：

核心觀念

紅黑樹同時滿足二元搜尋樹的大小關係與下列顏色限制：

• 根節點與所有空葉節點（NIL）皆為黑色。
• 紅節點的子節點必須為黑色，不能有相鄰的紅節點。
• 從任一節點到其各個後代 NIL 的路徑，黑節點數必須相同。

插入時先依二元搜尋樹規則找到位置，將新節點設為紅色；若父節點也是紅色，再透過重新著色與旋轉修復。

紅黑樹轉換成 2-3-4 樹時，將每個黑節點及其直接相連的紅色子節點合併成同一個節點，鍵值由小到大排列。

解題方法

原圖的根為黑色 $50$，左子節點為黑色 $10$，右子節點為紅色 $80$；$80$ 的左右子節點分別為黑色 $65$、$90$，而 $65$ 的左右子節點 $60$、$70$ 皆為紅色。

1. 插入 $62$

依大小關係搜尋：

$$62>50,\qquad 62<80,\qquad 62<65,\qquad 62>60.$$

因此，$62$ 成為 $60$ 的右子節點，初始設為紅色。此時 $60$ 與 $62$ 相鄰且皆為紅色，必須修復。

2. 父節點與叔節點皆為紅色：重新著色

新節點 $62$ 的父節點是紅色 $60$，叔節點是紅色 $70$，祖父節點是黑色 $65$。因此將：

• $60$、$70$ 改為黑色。
• $65$ 改為紅色。

接著向上處理 $65$。此時 $65$ 與其父節點 $80$ 皆為紅色，仍有衝突。

3. 處理右—左型衝突

以 $50$ 為祖父節點，$80$ 是其紅色右子節點，$65$ 是 $80$ 的紅色左子節點；叔節點 $10$ 為黑色，屬於右—左型。

修復步驟為：

1. 對 $80$ 做右旋，使 $65$ 位於 $80$ 上方。
2. 將 $65$ 改為黑色、$50$ 改為紅色。
3. 對 $50$ 做左旋，使 $65$ 成為根。

結果如下，括號表示節點顏色：

              65（黑）
             /        \
        50（紅）      80（紅）
        /     \       /     \
   10（黑） 60（黑）70（黑）90（黑）
                \
                62（紅）

核心觀念

Bloom filter 用多個雜湊函數將元素映射到位元陣列的位置。查詢元素時：

• 若任一對應位置是 $0$，元素一定不在集合中。
• 若所有對應位置都是 $1$，元素可能在集合中；Bloom filter 允許誤判，因此不能據此斷定元素一定在集合中。

解題方法

圖中的 Bloom filter 有 16 個位元，索引為 $0$ 到 $15$；值為 $1$ 的索引是 $1、2、5、9、12、13$，其餘索引的值都是 $0$。依題目公式，分別計算兩個數字的三個雜湊位置，再查表檢查那些位置的位元。

對 $8$：

$$\begin{aligned} f_1(8)&=\lfloor 0.48\times16\rfloor=7\\ f_2(8)&=\lfloor 0.92\times16\rfloor=14\\ f_3(8)&=\lfloor 0.04\times16\rfloor=0 \end{aligned}$$

索引 $7、14、0$ 的值都是 $0$，所以 $8$ 一定不在集合中。

對 $9$：

核心觀念

B-tree 刪除節點時，除了移除指定鍵值，還要維持各節點的鍵值數量、子樹範圍與葉節點深度等性質。若刪除的是內部節點中的鍵，通常以其前驅或後繼鍵替換；若刪除後節點不足，則透過向兄弟節點借鍵或與兄弟合併修復。具體操作會受 B-tree 的階數或最小度數影響。

解題方法

原頁上方可見一棵標示「(D)」的樹，以及第 4 題的 Bloom filter；第 5 題題幹下方沒有顯示所指的 B-tree 圖形。

核心觀念

Patricia 以位元索引記錄分岔位置，略過不必判斷的位元。本題由左至右將四個位元編為 $1,2,3,4$，分支依該位元的值選擇：$0$ 走左分支，$1$ 走右分支。

必須區分兩種表示法：

• 原圖的 Patricia：資料存於節點中，利用自指與回指結束搜尋；索引 $0$ 的頭節點也必須保留。
• 壓縮二元 trie：內部節點表示分岔位元，資料放在葉節點；省略只有單一分支的路徑。

在 Patricia 中，沿指標前進時，若下一個節點的索引不大於目前節點索引，便停止搜尋，將該節點的資料當作比對對象。

解題方法

原圖中，1000 是索引 $0$ 的頭節點，入口指向 0010(1)；0010(1) 的 $0$ 分支指向自身，$1$ 分支回指 1000(0)。因此，原有資料為 1000 與 0010。

插入時，先搜尋找到比對資料，再找出新資料與它由左至右第一個不同的位元。新節點以該位元作為索引，插入適當位置，使向下連結的索引維持遞增。

一、依序插入四筆資料

1. 插入 1001

搜尋經過 0010(1) 的 $1$ 分支，抵達 1000(0)。比較：

$$1001 \quad\text{與}\quad 1000$$

第一個差異在第 $4$ 位，因此建立 1001(4)，接在 0010(1) 的 $1$ 分支：

• $0$ 分支指向 1000(0)。
• $1$ 分支指向自身 1001(4)。

2. 插入 1100

搜尋路徑為：

$$0010(1)\xrightarrow{1}1001(4)\xrightarrow{0}1000(0)$$

1100 與 1000 第一個差異在第 $2$ 位，因此建立 1100(2)，插在 0010(1) 與 1001(4) 之間：

• $0$ 分支指向 1001(4)。
• $1$ 分支指向自身 1100(2)。

3. 插入 0000

由 0010(1) 的 $0$ 分支抵達自身，取得比對資料 0010。比較：

$$0000 \quad\text{與}\quad 0010$$

第一個差異在第 $3$ 位，因此建立 0000(3)，接在 0010(1) 的 $0$ 分支：

• $0$ 分支指向自身 0000(3)。
• $1$ 分支回指 0010(1)。

4. 插入 0001

搜尋路徑為：

$$0010(1)\xrightarrow{0}0000(3)\xrightarrow{0}0000(3)$$

0001 與 0000 第一個差異在第 $4$ 位，因此建立 0001(4)，接在 0000(3) 的 $0$ 分支：

• $0$ 分支回指 0000(3)。
• $1$ 分支指向自身 0001(4)。

二、(i) 最終 Patricia

下圖括號內為位元索引；標示「回指」與「自指」的端點代表指標連結，不是新增的節點。

核心觀念

本題考查深度優先搜尋（DFS）的首次拜訪順序。DFS 的規則是：

• 目前節點還有未拜訪的鄰點時，必須選一個鄰點繼續深入。
• 只有目前節點的所有鄰點都已拜訪，才能回溯至上一層。
• 回溯經過的節點不會再次列入拜訪序列。

題目未指定鄰點的檢查順序，因此合法的 DFS 序列可以有多種；判斷重點是是否符合上述規則。

解題方法

原圖是無向圖，節點 $1$ 的鄰點為 $3、7、8$，節點 $6$ 的鄰點為 $3、4$。斜線連接的是 $1$ 與 $7$，僅從節點 $6$ 下方經過，沒有形成 $1$–$6$ 或 $6$–$7$ 的邊；線段交叉處也不代表新增節點。

依原图連線，各節點的鄰點如下：

節點	鄰點
$1$	$3、7、8$
$2$	$4、5、8、9$
$3$	$1、5、6$
$4$	$2、6$
$5$	$2、3$
$6$	$3、4$
$7$	$1、9$
$8$	$1、2$
$9$	$2、7$

逐一沿選項模擬 DFS：下一個節點若不是目前節點的未拜訪鄰點，就檢查能否合法回溯，直到找到能前往該節點的祖先。回溯途中若仍有未拜訪的鄰點，就不能繼續往上退。

選項分析

(A) $1\ 7\ 9\ 2\ 4\ 6\ 3\ 5\ 8$：正確。

前八個節點可以沿著相連的邊一路深入：

$$1\to7\to9\to2\to4\to6\to3\to5$$

到達 $5$ 時，其鄰點 $2、3$ 都已拜訪，因此可以回溯。沿 $5\to3\to6\to4\to2$ 回溯時，$3、6、4$ 也都沒有未拜訪的鄰點；回到 $2$ 後，再拜訪尚未拜訪的鄰點 $8$，符合 DFS。

核心觀念

線性探測（linear probing）是開放定址法的一種。先用雜湊函數計算起始位置：

$$f(x)=x\bmod 17$$

若該位置已被占用，就依序檢查下一格；到索引 16 後，會繞回索引 0，直到找到空格為止。

解題方法

依題目給定的順序逐一插入。每個數字先計算雜湊位置，再從該位置開始線性探測：

插入值	起始索引	探測過程	放入索引
23	6	6 為空	6
52	1	1 為空	1
11	11	11 為空	11
1	1	1 已有 52，2 為空	2
50	16	16 為空	16
99	14	14 為空	14
65	14	14 已有 99，15 為空	15
20	3	3 為空	3
35	1	1、2、3 已占用，4 為空	4
34	0	0 為空	0

核心觀念

本題考查快速排序（Quick Sort）的 Lomuto 分割法。分割時選取最後一個元素 arr[end] 作為樞紐值 pivot，再將陣列分成兩部分：

• 左側元素都小於 pivot。
• 右側元素都大於或等於 pivot。
• pivot 放到分割後的正確位置，並回傳該位置的索引。

解題方法

i 記錄目前小於樞紐值的區域最後一個位置。每當 arr[j] < pivot，就把小於樞紐值的區域向右擴大一格，再交換 arr[i] 與 arr[j]。

因此，(A) 要遞增 i：

i++;

掃描結束後，i 指向小於樞紐值區域的最後一格；先遞增 i，再將 arr[end] 的樞紐值交換到這個位置。此位置就是樞紐值分割後的索引，因此 (B) 回傳 i：

return i;

分割完成後，樞紐值已在最終位置，不需再納入遞迴。因此只需排序樞紐值左側與右側：

• (C)：QuickSort(arr, front, pivot - 1);
• (D)：QuickSort(arr, pivot + 1, end);

完整程式碼

核心觀念

樹的走訪順序由「根節點的處理時機」決定：

• 前序走訪：先處理根，再走左子樹、右子樹。
• 中序走訪：先走左子樹，再處理根，最後走右子樹。
• 後序走訪：先走左子樹、右子樹，最後處理根。

本題的「處理根」是交換該節點的左右子指標。

解題方法

觀察函式中的執行順序：

1. 若左子樹存在，先遞迴處理左子樹。
2. 若右子樹存在，再遞迴處理右子樹。
3. 最後交換目前節點的 left 與 right。

if (p->left != NULL) unknown(p->left);
if (p->right != NULL) unknown(p->right);

q = p->left;
p->left = p->right;
p->right = q;

核心觀念

unknown 會先遞迴處理左右子樹，再交換目前節點的左右子指標。每個節點都如此操作後，整棵樹會左右鏡射。葉節點是沒有左、右子節點的節點。

原始樹根節點為 20，左子樹根節點為 18；18 的左子節點是 13，13 的左子節點是葉節點 3。右子樹根節點為 15。

解題方法

遞迴先處理子樹、再交換指標，因此不會漏掉任何節點：

if (p->left != NULL) unknown(p->left);
if (p->right != NULL) unknown(p->right);

q = p->left;
p->left = p->right;
p->right = q;

鏡射後，原本的左子樹會移到根節點右側；原本在該子樹最左側的葉節點，會成為整棵樹最右側的葉節點。沿鏡射後的右側路徑追蹤：

$$20 \to 18 \to 13 \to 3$$

因此，最右側的葉節點值為 3。

核心觀念

Min-Heap 的根節點是最小鍵值，因此執行「取出下一個工作」時，會移除根節點 $Q[1]$。為維持完整二元樹結構，將最後一個節點移到根，再沿著較小的子節點向下調整，直到恢復 Min-Heap 性質。

本題採 1 起始索引：節點 $Q[i]$ 的左右子節點索引分別是 $2i$ 與 $2i+1$。

解題方法

原 Min-Heap 的鍵值依序為：

$$[6,8,10,12,24,15,13,20,18,26]$$

移除最小值 $6$，將最後一個值 $26$ 移到根，並刪除原最後一格：

$$[26,8,10,12,24,15,13,20,18]$$

接著向下調整：

1. 根節點 $26$ 的子節點是 $8$、$10$，與較小的 $8$ 交換。
2. 索引 $2$ 的 $26$ 有子節點 $12$、$24$，與較小的 $12$ 交換。
3. 索引 $4$ 的 $26$ 有子節點 $20$、$18$，與較小的 $18$ 交換。

調整後的堆為：

$$[8,12,10,18,24,15,13,20,26]$$

因此 $Q[4]=18$。

選項分析

• (A) 15：錯誤。 $15$ 原本位於 $Q[6]$，取出最小值並向下調整後仍位於 $Q[6]$。
• (B) 18：正確。 最後節點 $26$ 向下調整時，依序與 $8$、$12$、$18$ 交換，因此 $Q[4]=18$。

核心觀念

最小堆積（Min-Heap）中每個父節點都不大於子節點，根節點是優先權最高的工作。題目以 1 起算索引：索引 $i$ 的左右子節點為 $2i$、$2i+1$。

取出最小值：把最後一個元素移到根，再一路與較小的子節點交換（向下調整），直到恢復堆積性質。

解題方法

初始堆積：

$$[6,8,10,12,24,15,13,20,18,26]$$

Step 1（第一次取出，取出 6）：把 26 移到根並向下調整，26 依序與 8、12、18 交換：

$$[8,12,10,18,24,15,13,20,26]$$

Step 2（第二次取出，取出 8）：把最後的 26 移到根，堆積剩 8 個元素：

$$[26,12,10,18,24,15,13,20]$$

向下調整：

核心觀念

最小堆積（Min-Heap）是完全二元樹，且每個父節點的鍵值都不大於其子節點。題目以 $Q[1]$ 作為根節點，$Q[0]$ 不使用；索引 $i$ 的父節點為 $\lfloor i/2 \rfloor$，左右子節點分別為 $2i$ 與 $2i+1$。

取出最小值時，將最後一個元素移到根節點，再沿著較小的子節點向下調整；插入新值時，先放在陣列末端，再與父節點比較並向上調整。

解題方法

題目中的 Step 1、Step 2 都是取出目前優先權最高的工作，也就是連續取出最小值。官方題本列出的 Step 1 是取出下一個工作，Step 2 則是在 Step 1 後再次取出下一個工作。

初始堆積依 $Q[1]$ 至 $Q[10]$ 排列為：

$$[6,8,10,12,24,15,13,20,18,26]$$

第一次取出 $6$，將末端的 $26$ 移到根節點並向下調整：

$$[26,8,10,12,24,15,13,20,18] \to [8,26,10,12,24,15,13,20,18] \to [8,12,10,26,24,15,13,20,18] \to [8,12,10,18,24,15,13,20,26]$$

第二次取出 $8$，將末端的 $26$ 移到根節點並向下調整：

$$[26,12,10,18,24,15,13,20] \to [10,12,26,18,24,15,13,20] \to [10,12,13,18,24,15,26,20]$$

接著插入 $11$，先放在新末端 $Q[9]$，再依序與父節點比較：

核心觀念

F-heap（Fibonacci heap）的最小堆序性質要求：每個非根節點的鍵值不得小於其父節點的鍵值。執行減鍵後，若節點 $x$ 的鍵值小於父節點 $y$ 的鍵值，便違反此性質，因此必須將 $x$ 從 $y$ 的子節點串列中切下，並移至根串列。

CUT(H,x,y) 將 $x$ 從父節點 $y$ 移除後，$x$ 成為根節點，所以其父指標必須設為 NIL，並將標記清除。

解題方法

先檢查減鍵是否有效：若新鍵值 $k$ 大於原鍵值，就不符合 decrease key 的操作定義，回傳錯誤。將 $x.key$ 更新成 $k$ 後，比較 $x$ 與父節點 $y$ 的鍵值：

• 若 $x.key < y.key$，違反最小堆序，執行切割與級聯切割。
• 若父節點不存在，$x$ 已是根節點，不需切割。
• 更新後若 $x$ 小於目前最小根節點，便更新 H.min。

因此兩個缺漏處分別是：

• (1) x.key < y.key
• (2) NIL