108 關務特考三等 資訊處理 資料結構 考古題詳解

核心觀念

此題考雙向鏈結串列的指標更新。對每個走訪到的節點，程式先保存原本的 prev，再交換該節點的 prev 與 next。交換後，current->prev 指向的是該節點原本的 next，因此程式會沿原本的 next 方向前進。

temp 每次保存目前節點原本的 prev。迴圈結束後，若 temp 不為 NULL，程式將 *head 設為 temp->prev。

解題方法

依序追蹤每個被走訪節點的 prev、next，並留意走訪起點是否為串列的第一個節點。若從第一個節點開始，所有節點都會交換；若從中間節點開始，其前方節點不會被處理。

（一）從資料為 17 的節點開始

走訪順序為 $17 \to 21 \to 35 \to 74 \to 95$，五個節點的 prev、next 都交換。最後，temp 指向 74；此時 temp->prev 指向 95，因此 X 改指向 95。

執行後的串列為：

也就是原串列順序反轉，X 指向資料為 95 的節點。

（二）從資料為 21 的節點開始

走訪順序為 $21 \to 35 \to 74 \to 95$，資料為 17 的節點沒有被走訪，因此其指標維持原狀。

核心觀念

本題評量二元搜尋樹（Binary Search Tree, BST）與堆積（Heap）的核心理論與實作，包含四大觀念：

1. 二元搜尋樹的定義與搜尋特性：

• 對於 BST 中的任一節點 $x$，其左子樹中所有節點的鍵值皆小於 $x$ 的鍵值；其右子樹中所有節點的鍵值皆大於 $x$ 的鍵值（即 $\text{Left} < \text{Root} < \text{Right}$）。
• 在搜尋目標鍵值 $K$ 時，每次與節點 $x$ 比較：
• 若 $K < x$，則搜尋路徑轉向左子樹，同時確立往後所有受檢節點之上界必小於 $x$。
• 若 $K > x$，則搜尋路徑轉向右子樹，同時確立往後所有受檢節點之下界必大於 $x$。
• 搜尋過程中的每一步，皆使目標所在的合法數值區間 $(\text{lower\_bound}, \text{upper\_bound})$ 持續限縮，後續拜訪的節點數值絕不可超出已確立的有效區間。

2. 二元搜尋樹的走訪特性：

• 中序遍歷（In-order Traversal）的單調性：對任何合法的二元搜尋樹進行中序走訪（左 $\to$ 根 $\to$ 右），其輸出序列必然為由小到大的嚴格遞增排序序列。
• 樹的重建唯一性：已知前序（Pre-order，根 $\to$ 左 $\to$ 右）或後序（Post-order，左 $\to$ 右 $\to$ 根），搭配 BST 中序必然為遞增排序的性質，即可唯一決定二元樹的結構。

3. 最小堆積（Min Heap）的定義與要件：

• 結構性質（Shape Property）：必須為完全二元樹（Complete Binary Tree）。若以一維陣列表示，包含 $n$ 個節點的堆積必須緊湊連續存放於索引 $1$ 到 $n$。
• 堆積性質（Heap Property）：任一非根節點 $i$ 的值，皆必須大於或等於其父節點的值，即 $\text{key}(\text{parent}(i)) \le \text{key}(i)$，根節點恆為全樹最小值。

解題方法與詳細推導

（一）判斷搜尋 364 之序列是否可能為：3、400、388、220、267、383、382、279、364

• 方法：透過「搜尋區間收縮法」追蹤每一步的合法範圍。初始有效區間為 $[1, 1000]$。
• 逐步推導：

1. 拜訪 3：目標 $364 > 3$，向右子樹搜尋。確立下界為 3，後續合法區間為 $(3, 1000]$。
2. 拜訪 400：$400 \in (3, 1000]$。目標 $364 < 400$，向左子樹搜尋。確立上界為 400，後續合法區間為 $(3, 400)$。
3. 拜訪 388：$388 \in (3, 400)$。目標 $364 < 388$，向左子樹搜尋。確立上界為 388，後續合法區間為 $(3, 388)$。
4. 拜訪 220：$220 \in (3, 388)$。目標 $364 > 220$，向右子樹搜尋。確立下界為 220，後續合法區間為 $(220, 388)$。
5. 拜訪 267：$267 \in (220, 388)$。目標 $364 > 267$，向右子樹搜尋。確立下界為 267，後續合法區間為 $(267, 388)$。
6. 拜訪 383：$383 \in (267, 388)$。目標 $364 < 383$，向左子樹搜尋。確立上界為 383，後續合法區間為 $(267, 383)$。
7. 拜訪 382：$382 \in (267, 383)$。目標 $364 < 382$，向左子樹搜尋。確立上界為 382，後續合法區間為 $(267, 382)$。
8. 拜訪 279：$279 \in (267, 382)$。目標 $364 > 279$，向右子樹搜尋。確立下界為 279，後續合法區間為 $(279, 382)$。
9. 拜訪 364：$364 \in (279, 382)$，成功找到目標節點。

• 結論：序列中每一個受檢節點均嚴格落在當前的有效邊界之內，未違反二元搜尋樹之性質，故此搜尋過程有可能。

（二）判斷搜尋 364 之序列是否可能為：926、203、912、241、913、246、364

• 方法：透過「搜尋區間收縮法」檢驗節點是否落入合法區間。
• 逐步推導：

1. 拜訪 926：目標 $364 < 926$，向左子樹搜尋。後續合法區間限縮為 $[1, 926)$。
2. 拜訪 203：$203 \in [1, 926)$。目標 $364 > 203$，向右子樹搜尋。後續合法區間限縮為 $(203, 926)$。
3. 拜訪 912：$912 \in (203, 926)$。目標 $364 < 912$，向左子樹搜尋。後續合法區間限縮為 $(203, 912)$。
4. 拜訪 241：$241 \in (203, 912)$。目標 $364 > 241$，向右子樹搜尋。後續合法區間限縮為 $(241, 912)$。
5. 拜訪 913：檢查其值，$913 \notin (241, 912)$。

• 矛盾分析：在第 3 步拜訪 912 時，因目標值 $364 < 912$，搜尋進入 912 的左子樹；依照 BST 定義，912 之左子樹內的所有節點鍵值皆必須小於 912。然而後續出現的節點 913 卻大於 912，直接違反二元搜尋樹的定義。

• 結論：此搜尋過程不可能。

（三）前序遍歷為 30、20、10、15、25、23、39、35、42，求後序遍歷結果

• 方法：

1. 藉由 BST 特性，將所有節點鍵值由小到大排序，求得中序遍歷結果： $\text{In-order: } 10, 15, 20, 23, 25, 30, 35, 39, 42$
2. 結合前序與中序遍歷遞迴重建二元搜尋樹：

• 前序首個元素為樹根：30。
• 在中序中，30 左側為左子樹 $\{10, 15, 20, 23, 25\}$，30 右側為右子樹 $\{35, 39, 42\}$。
• 建構左子樹：
• 前序子序列為 $\{20, 10, 15, 25, 23\}$，故左子樹之根為 20。
• 中序中小於 20 為 $\{10, 15\}$（左子樹），大於 20 為 $\{23, 25\}$（右子樹）。
• 對 $\{10, 15\}$：前序為 $10, 15$，根為 10，15 為其右小孩。
• 對 $\{23, 25\}$：前序為 $25, 23$，根為 25，23 為其左小孩。
• 建構右子樹：
• 前序子序列為 $\{39, 35, 42\}$，故右子樹之根為 39。

核心觀念

本題考三種圖形演算法：

• Kruskal：依邊權重由小至大考慮邊；若加入該邊不會形成環，就納入生成樹。
• Prim：從一個起始節點出發，每次加入連接「已納入節點」與「未納入節點」的最小權重邊。
• Dijkstra：求單一起點到其他節點的最短距離。每次確定目前暫定距離最小的未確定節點，再更新其鄰點距離。

（一）Kruskal 演算法

將圖中邊依權重由小至大排列：

依序選邊，若會形成環則跳過：

1. 加入 $ab(1)$。
2. 加入 $df(2)$。
3. 加入 $cf(3)$。
4. 加入 $gj(3)$。
5. 加入 $ad(5)$。
6. $ac(6)$、$bc(6)$ 都會形成環，跳過。
7. 加入 $ce(7)$。
8. 加入 $gh(7)$。
9. 加入 $fh(8)$，此時已連通 9 個節點，共有 8 條邊，完成最小生成樹。

依序加入的邊：

總權重為 $1+2+3+3+5+7+7+8=36$。

（二）Prim 演算法

題目未指定起始節點，以下以 $a$ 為起點。每一步從已納入的節點集合，選擇連往集合外且權重最小的邊：

1. 從 $a$ 出發，選 $ab(1)$。
2. 已納入 $\{a,b\}$，選 $ad(5)$。
3. 已納入 $\{a,b,d\}$，選 $df(2)$。
4. 已納入 $\{a,b,d,f\}$，選 $fc(3)$。
5. 已納入 $\{a,b,c,d,f\}$，選 $ce(7)$。
6. 已納入 $\{a,b,c,d,e,f\}$，選 $fh(8)$。
7. 已納入 $\{a,b,c,d,e,f,h\}$，選 $hg(7)$。
8. 最後選 $gj(3)$，納入節點 $j$。

從 $a$ 起始時，依序加入的邊：

（三）Dijkstra 演算法的用途與限制

**用途：**求加權圖中某一起點到其他各節點的最短路徑距離，並可透過前驅節點還原路徑。

核心觀念

本題考查雜湊函數、負數取模，以及雜湊碰撞時的探測方法。每個桶有槽 1、槽 2；插入時先檢查指定桶的槽 1，再檢查槽 2。桶已滿時，依題目指定的探測方式尋找下一個可用桶。

負數取模以非負餘數表示，例如 $-12\bmod 11=10$、$-12\bmod 7=2$。

解題方法

（一）線性探測：11 桶 × 2 槽

先計算 $H(k)=k\bmod 11$。若該桶已滿，就依序檢查下一桶，桶號以 11 為循環。

最終雜湊表如下：

（二）平方探測：7 桶 × 2 槽

以 $i=0,1,2,\ldots$ 依序探測桶號：

每次探測到一個桶時，先檢查槽 1，再檢查槽 2。平方探測的桶號偏移依序為 $0,1,4,2,\ldots$。