110 公務人員升官等薦任 資訊處理 資料結構 考古題詳解

核心觀念： B+ 樹是適合外部記憶體索引的平衡多路搜尋樹。樹中所有葉節點位於同一層，索引鍵（或其分隔鍵）出現在內部節點；資料紀錄或指向資料紀錄的指標則存放於葉節點。葉節點通常依鍵值排序，並以指標串接，方便依序或範圍查詢。

解題方法： 說明時掌握「內部節點負責導引搜尋、葉節點存放資料項目」即可。搜尋鍵值時，從根節點依分隔鍵選擇子樹，直到抵達葉節點；範圍查詢則先找到起始鍵所在的葉節點，再沿葉節點鏈結順序掃描。

解題技巧： 不要把 B+ 樹和一般 B 樹混為一談：B+ 樹的資料項目集中在葉節點，內部節點主要作為索引；葉節點鏈結是支援順序及範圍查詢的重要特徵。樹保持平衡，因此搜尋、插入與刪除的高度通常為 $O(\log n)$。

（二）完美雜湊函數（Perfect Hash Function）

核心觀念： 完美雜湊函數是針對一個已知、固定的鍵集合設計的雜湊函數，使集合中的不同鍵映射至不同的雜湊位置，也就是在該鍵集合上沒有碰撞。若雜湊位置恰好涵蓋大小為 $n$ 的表格中的 $n$ 個位置，稱為最小完美雜湊函數。

解題方法： 判斷是否為完美雜湊函數，檢查指定鍵集合中是否存在兩個不同鍵 $k_1$、$k_2$，使得 $h(k_1)=h(k_2)$。若沒有碰撞，即符合完美雜湊的條件。此性質是針對預先指定的鍵集合成立，不代表對所有可能輸入都沒有碰撞。

解題技巧： 「完美」不表示雜湊表一定最小，也不表示查詢任意未知鍵都不會發生碰撞。只有表格大小也恰為鍵集合大小時，才是「最小完美雜湊」。

（三）霍夫曼編碼（Huffman Coding）

核心觀念： 霍夫曼編碼是依符號出現頻率或機率建立的最佳前綴碼。頻率較高的符號通常取得較短的碼字，頻率較低的符號通常取得較長的碼字；

核心觀念

本題考單向環狀鏈結串列的指標重接。節點的位置由 next 指標決定，因此交換節點時，只要重新指定相關節點的 next，不必也不能更動 info。

環狀串列沒有 NULL 尾端；最後一個節點的 next 會指回串列中的節點。以下第（一）小題假設環中至少有 3 個不同節點；第（二）小題假設環中至少有 4 個不同節點。

解題方法

（一）交換 p 後面連續兩個節點

令 b = p->next、c = b->next、d = c->next。原本的連結是：

$p \to b \to c \to d$

交換 b、c 的位置後，改接成：

$p \to c \to b \to d$

void swapnodes(NODE *p)
{
 if (p == NULL)
 return;

 NODE *b = p->next;
 NODE *c = b->next;
 NODE *d = c->next;

 /* 確保 p、b、c 是不同節點 */
 if (b == p || c == p || b == c)
 return;

 p->next = c;
 c->next = b;
 b->next = d;
}

本題圖中 p 指向 A，因此 b 是 B、c 是 C、d 是 D。重接後為 A → B → D → C → E；環狀串列的最後一個節點仍照原本的 next 指標接回環中。

（二）交換 p 前後的節點

令 b 為 p 的前一個節點，d = p->next 為 p 的後一個節點。由於是單向串列，無法直接沿 next 找前一個節點；先從環中尋找 a，使得 a->next->next == p。如此 a->next 就是 b。

再令 e = d->next。原本的連結是：

核心觀念

本題考的是二維 KD-tree（k-d 樹）。每個資料節點都在其所在的區域內新增一條分割線，方向依序交替：

• 前次分割左右空間（垂直線），本次分割上下空間（水平線）。
• 前次分割上下空間（水平線），本次分割左右空間（垂直線）。

二元樹的左右子樹依分割軸的座標大小決定：垂直線左側進左子樹、右側進右子樹；水平線下側進左子樹、上側進右子樹。圖中的節點 3 位於節點 2 水平分割線下方，且是節點 2 的左子節點，可確認水平分割時下側對應左子樹。

解題方法

沿著二元樹逐層比較新節點與各分割節點的位置，直到找到該節點所屬的空區域；再依該區域的分割方向規則，決定新節點要畫出的分割線。

1. 節點 7：先在節點 1 的左側，再位於節點 2 分割線下方，接著在節點 3 垂直線右側，到達節點 6 所在區域。節點 6 分割上下空間，節點 7 位於分割線上方，因此是節點 6 的右子節點。節點 7 新增垂直分割線。
2. 節點 8：沿相同路徑到節點 6，位於節點 6 水平分割線上方，進入節點 7 的區域；又位於節點 7 垂直線右側，因此是節點 7 的右子節點。節點 8 新增水平分割線。
3. 節點 9：位於節點 1 右側，進入節點 5 的區域；又在節點 5 水平分割線上方，因此是節點 5 的右子節點。節點 9 新增垂直分割線。
4. 節點 10：位於節點 1 左側，進入節點 2 的區域；又在節點 2 水平分割線上方，因此是節點 2 的右子節點。節點 10 新增垂直分割線。
5. 節點 11：位於節點 1 右側，進入節點 5 的區域；

核心觀念

本題考查最小成本擴張樹與單一起點最短路徑：

• Kruskal 演算法：依邊權重由小到大檢查，若加入該邊不會形成環，就將它加入擴張樹。
• Prim 演算法：從指定起點開始，每次選擇連接已納入節點與未納入節點、且權重最小的邊。
• Dijkstra 演算法：每次確定目前暫定距離最小的未處理節點，再用該節點更新鄰點距離。

依原頁圖形，實際邊權重為：

題目文字列出的邊與原頁圖形不一致；以下依題目要求，以原頁圖形為準作答。

解題方法

（一）Kruskal 演算法

將邊依權重由小到大排列：

依序檢查：

1. 加入 $de$，連接 $d,e$。
2. 加入 $ce$，將 $c$ 接入。
3. 加入 $be$，將 $b$ 接入。
4. $bd$ 會形成環，略過。
5. 加入 $ab$，將 $a$ 接入。
6. $ac$ 會形成環，略過。
7. 加入 $ef$，將 $f$ 接入。六個節點已連通，共有五條邊，完成 MST。

加入 MST 的邊順序：

總成本為 $2+3+4+6+8=23$。

（二）Prim 演算法，從 $a$ 出發

每次從已納入的節點集合，挑選通往集合外節點且權重最小的邊：

1. 從 $a$ 出發，候選邊為 $ab(6), ac(7)$，加入 $ab$。
2. 已納入 $\{a,b\}$，最小候選邊為 $be(4)$，加入 $be$。
3. 已納入 $\{a,b,e\}$，最小候選邊為 $de(2)$，加入 $de$。
4. 已納入 $\{a,b,d,e\}$，最小候選邊為 $ec(3)$，加入 $ec$。
5. 尚未納入的節點只剩 $f$，加入 $ef(8)$。

加入 MST 的邊順序：

總成本同為 $23$。

（三）Dijkstra 演算法的目的節點順序

以 $a$ 為來源，初始暫定距離為：

其餘節點距離為無限大。

1. 確定 $b$，距離為 $6$。更新 $d(d)=6+5=11$、$d(e)=6+4=10$。
2. 確定 $c$，距離為 $7$。