111 年 國立臺灣聯合大學系統（清華、政治、陽明交通、中央四校聯招）研究所電機類《資料結構》

核心觀念

單向鏈結串列的每個節點通常包含：

• data：資料內容
• next：指向下一個節點的指標

若要刪除節點 x，必須讓 x 的前一個節點直接指向 x 的下一個節點：

$$prev \to next = x \to next$$

單向鏈結串列只能由目前節點沿著 next 向後走，因此刪除指定節點時，通常需要先找到：

1. 被刪除節點 x
2. x 的前驅節點 prev

若刪除的是首節點，因為沒有前驅節點，必須直接更新串列首指標：

$$head = head \to next$$

---

解題方法

假設函式接收：

• head：串列首節點
• selected：要刪除的節點指標

處理流程如下：

1. 若串列為空，直接回傳 NULL。

2. 若 selected 就是首節點，將 head 移到下一個節點，釋放原首節點。

3. 從首節點開始搜尋，尋找滿足

   $$current \to next = selected$$

   的節點。此節點就是 selected 的前驅節點。

4. 將前驅節點的 next 改為被刪除節點的 next。

5. 釋放被刪除節點所占用的記憶體。

6. 回傳更新後的 head。

---

關鍵程式碼

核心觀念

本題旨在測驗單向鏈結串列（Singly Linked List）的節點指標操作與**單次走訪（One-Pass Algorithm）**的實作能力。

1. 節點指標交換 vs. 資料交換：
   在實作交換操作時，有兩種主要策略：
   • 交換值（Swap Values）：直接交換兩節點儲存的資料欄位（Data field）。此法實作極為簡潔，時間複雜度為 $O(n)$，且不涉及指標結構的重新鏈結。
   • 交換鏈結（Swap Pointers/Nodes）：改變節點之間的指標指向（next 指標）。此法在節點攜帶龐大資料結構（Large Payload）或禁止拷貝時更具一般性與彈性。
     在研究所入學考試中，兩種寫法皆可視為有效解。本解題提供最穩健且符合題意的交換指標連結法，同時附上簡潔的交換數值法作為對照。
2. 單次走訪（One-Pass）限制：
   題目要求僅能遍歷串列一次（走訪次數上限為 $n$ 步），因此必須在一次迴圈中依序定位第 $m$ 個節點與第 $n$ 個節點及其前驅節點（Predecessor Node）。
3. 虛擬頭節點（Dummy Head / Sentinel Node）：
   引入 Dummy Node 可以將「第 1 個節點（Head）參與交換」的特例情況轉化為「一般內部節點交換」，消除大量邊界條件判斷（Edge Cases）。

---

解題方法

步驟一：特例處理（Boundary Cases）

• 若 $m = n$，串列不需做任何變動，直接回傳原串列即可。
• 若串列為空或只有一個節點，亦直接回傳。

步驟二：配置虛擬頭節點與單次走訪指標定位

• 建立一個 dummy 節點，令 dummy->next = head。
• 使用走訪指標 curr 從 dummy 出發，透過單一迴圈同步記錄目前走訪步數（計數器 idx 從 0 開始）：
  • 當 idx == m - 1 時，標記 prevM = curr、nodeM = curr->next。
  • 當 idx == n - 1 時，標記 prevN = curr、nodeN = curr->next，此時已找到所有必要指標，可直接跳出迴圈。

步驟三：指標重鏈結（Pointer Rewiring）

在單向鏈結串列中交換節點指標時，必須區分兩節點是否相鄰（Adjacent）：

• 情況 1：節點不相鄰（$n > m + 1$）
  1. prevM->next = nodeN;
  2. prevN->next = nodeM;
  3. 交換兩節點的後繼指標： $$\text{temp} = \text{nodeM}\to\text{next}; \quad \text{nodeM}\to\text{next} = \text{nodeN}\to\text{next}; \quad \text{nodeN}\to\text{next} = \text{temp};$$
• 情況 2：節點相鄰（$n = m + 1$）
  此時 prevN 即為 nodeM：
  1. prevM->next = nodeN;
  2. nodeM->next = nodeN->next;
  3. nodeN->next = nodeM;

---

程式碼實作（指標交換版）

核心觀念

• 中序 (infix) → 後序 (postfix)、前序 (prefix) 轉換皆利用 堆疊 (stack) 來暫存運算子，並遵守 運算子優先權（*、/ > +、‑）以及 左結合性。
• 後序表達式：運算子出現在其兩個運算元之後。
• 前序表達式：運算子出現在其兩個運算元之前。

---

一、後序 (Postfix) 轉換步驟

步驟	輸入符號	堆疊 (Top→Bottom)	輸出
1	a		a
2	/	/	a
3	b	/	a b
4	) (遇到 '/' 仍在堆疊)		a b /
5	+	+	a b /
6	c	+	a b / c
7	‑ (+ 與 - 同優先度，左結合 → 先彈出 +)	‑	a b / c +
8	(	‑ (左括號壓入)	a b / c +
9	f	‑ (	a b / c + f
10	/	‑ / (	a b / c + f
11	d	‑ / (	a b / c + f d
12	) (彈出直到左括號)	‑	a b / c + f d /
13	* (* 優先度高於 ‑，壓入)	‑ *	a b / c + f d /
14	g	‑ *	a b / c + f d / g
15	結束 (彈出剩餘運算子)	空	a b / c + f d / g * ‑

後序結果
$a\;b\;/\;c\;+\;f\;d\;/\;g\;*\;-$

---

二、前序 (Prefix) 轉換步驟

前序可透過「將中序逆向掃描」的方式取得，同樣利用堆疊，但左括號、右括號的角色互換。以下採用「從右至左」掃描的標準演算法。

步驟	輸入符號 (右→左)	堆疊 (Top→Bottom)	輸出 (逆序累積)
1	g		g

核心觀念

本題考查核心資料結構——鏈結串列（Linked Lists） 在不同變體下實作動態集合操作（Dynamic-Set Operations） 的最壞情況漸近時間複雜度（Worst-case Running Time）。

考點源自經典演算法聖經 Introduction to Algorithms（CLRS）第 10 章〈Elementary Data Structures〉：

1. 鏈結結構特性：
   • 單向鏈結串列（Singly Linked List）：節點僅有向後指標 next，無法在 $O(1)$ 時間內反向取得前驅節點（Predecessor）。
   • 雙向鏈結串列（Doubly Linked List）：節點具有 next 與 prev 雙向指標，已知某節點指標時，可於 $O(1)$ 時間存取前後相鄰節點。
2. 有序性（Sorted vs. Unsorted）：
   • 串列即使經過排序（Sorted），由於不具備隨機存取（Random Access）能力，無法進行二分搜尋法（Binary Search），循序搜尋仍需走訪節點。
   • 排序串列若按升冪排列（Ascending order），極小值（MINIMUM）位於頭部（Head）；但極大值（MAXIMUM）位於尾部（Tail）。若單向串列僅維護開頭指標 head，需走訪至尾端；若有雙向環狀或維護尾指標，方可在 $O(1)$ 取得。

---

解題方法與操作推導

令串列中的元素個數為 $n$。各項操作於最壞情況下的時間複雜度推導如下：

1. $\text{SEARCH}(L, k)$

• Unsorted 串列（單向與雙向）：目標鍵值可能位於串列末端或根本不存在，必須線性走訪所有 $n$ 個節點，耗時 $O(n)$。
• Sorted 串列（單向與雙向）：即使鍵值已排序，因指標串列無法在 $O(1)$ 內跳躍至中點（無隨機存取性），二分搜尋無法派上用場。最壞情況下仍需自頭端循序比對至最後一個節點，耗時 $O(n)$。

2. $\text{INSERT}(L, x)$

• Unsorted 串列（單向與雙向）：新節點 $x$ 可直接插入於串列開頭（Head Insertion），只需修改常數個指標，耗時 $O(1)$。
• Sorted 串列（單向與雙向）：為維持由小到大的排序性，插入前必須先自頭端走訪找到適當的插入位置（前驅節點），最壞情況（如插入值最大）需走訪整條串列，耗時 $O(n)$。

3. $\text{DELETE}(L, x)$

注意：依據 CLRS 定義，$\text{DELETE}(L, x)$ 給定的是欲刪除節點的指標（Pointer） $x$，而非欲搜尋的鍵值 $k$。

• Singly Linked 串列（未排序與已排序）：要將節點 $x$ 移除，必須先取得其前驅節點 $p$（使 $p.\text{next} = x.\text{next}$）。由於單向串列無法由 $x$ 反向取得前驅節點，必須從頭節點出發循序搜尋 $x$ 的前驅，最壞情況耗時 $O(n)$。
• Doubly Linked 串列（未排序與已排序）：節點 $x$ 內建前驅指標 $x.\text{prev}$。

核心觀念

穩定排序是指：若兩筆資料的排序鍵相同，排序後仍維持它們在原始資料中的先後次序。

堆積排序（Heap sort）不穩定。它會將堆頂元素與目前未排序區間的最後一個元素交換；這種跨越多個位置的交換，可能改變相同鍵值資料的相對順序。

解題方法

以 $A$、$B$ 標記兩筆鍵值相同但彼此不同的資料。原始資料如下：

$$[2_A,\ 2_B,\ 1]$$

採用最大堆積，將資料由小到大排序。這個序列已符合最大堆積條件：根節點 $2_A$ 不小於子節點 $2_B$ 與 $1$。

1. 將堆頂 $2_A$ 與未排序區間末端的 $1$ 交換：

   $[1,\ 2_B,\ 2_A]$

2. 對前兩個元素重新調整最大堆積，將 $1$ 與 $2_B$ 交換：

   $[2_B,\ 1,\ 2_A]$

核心觀念

• 開放定址雜湊（Open Addressing）：所有鍵值都存於雜湊表本身，碰撞時必須重新尋找空位。
• 一次探測（Primary Clustering）：在線性探測或二次探測中，若多個鍵在同一段連續區域產生碰撞，會形成長度不斷增長的區段，導致搜尋成本提升。
• 二次聚集（Secondary Clustering）：即使使用不同的二次探測步幅，只要兩個鍵的 初次雜湊值 相同，它們之後的探測序列完全相同，仍會產生聚集。
• 雙重雜湊（Double Hashing）：利用兩個獨立的雜湊函數
  $h(k,i)=\bigl(h_1(k)+i\cdot h_2(k)\bigr)\bmod m$
  其中 $h_1$ 為主雜湊，$h_2$ 為次雜湊（探測步幅），$i$ 為探測次數，$m$ 為表長。只要 $h_2(k)$ 與 $m$ 互質，探測序列會遍歷整個表。

---

解題方法：設計雙重雜湊並證明避免聚集

1. 選取表長 $m$ 為質數（或 $m=2^p$ 且 $h_2$ 為奇數），確保與次雜湊 $h_2(k)$ 必有互質性。
2. 主雜湊函數 $h_1$：常用的除留餘法
   $h_1(k)=k \bmod m$
   只要 $k$ 為整數或可映射為整數（例如將字串轉為 ASCII 數值），此函數分布均勻。
3. 次雜湊函數 $h_2$：必須保證 $1\le h_2(k)\le m-1$ 且與 $m$ 互質。常見設計
   $h_2(k)=1+\bigl(k \bmod (m-1)\bigr)$
   若 $m$ 為質數，$m-1$ 與 $m$ 互質，故 $h_2(k)$ 必與 $m$ 互質。
4. 插入/搜尋程序
   • 計算 $h_1(k)$ 作為起始位置。
   • 若該槽已被佔用，計算 $h_2(k)$ 作為步幅，依次檢查
     $\text{slot}= \bigl(h_1(k)+i\cdot h_2(k)\bigr)\bmod m,\quad i=1,2,\dots$
   • 當遇到空槽（插入）或匹配鍵（搜尋）即停止。

避免 Primary Clustering

• 在一次探測中，若兩鍵的 $h_1$ 不同，探測序列的起始點不同，即使 $h_2$ 相同，它們的搜尋路徑也不會重疊。
• 因此不會形成長串連續的已佔用區段，從而消除一次探測的聚集現象。

核心觀念

• Quick Sort：利用 partition 將資料分成兩個子集合，再遞迴排序。
• 時間複雜度分析：以遞迴式 $T(n)=T(k)+T(n-1-k)+\Theta(n)$ 估算，其中 $k$ 為左子集合大小。
• 最壞情況：若每次選出的 pivot 都是目前子集合的最小或最大元素，則 $k=0$（或 $k=n-1$），導致遞迴式退化為 $T(n)=T(n-1)+\Theta(n)$。

解題方法與詳細證明

1. 遞迴式的推導

   • 假設每次都選到最小值作為 pivot。
   • 第一次 partition 需比較 $n-1$ 次，產生子問題大小 $0$ 與 $n-1$。
   • 形成遞迴式
     $T(n)=T(0)+T(n-1)+c\,n \quad (c>0\text{ 為常數})$
     簡化為 $T(n)=T(n-1)+c\,n$。

2. 遞迴式求解（累加法）

$$\begin{aligned} T(n) &= c\,n + T(n-1) \\ &= c\,n + c\,(n-1) + T(n-2) \\ &\;\;\vdots \\ &= c\sum_{i=1}^{n} i + T(0) \\ &= c\frac{n(n+1)}{2}+O(1) \\ &= \Theta(n^{2}) \end{aligned}$$

因此在最壞情況下 Quick Sort 的時間複雜度為 $O(n^{2})$。

3. 最壞情形的實際輸入
   • 若實作選取 第一個元素（或最後一個）作為 pivot，則已排序或逆序的陣列會產生上述退化。
   • 也可因 pivot 選擇方式固定而在特定分布的資料上產生同樣的情形。

在同樣條件下的改進

改進方式	說明	為何能把最壞變成最佳
隨機化 pivot（Randomized Quick Sort）	每次在子集合中隨機抽取一個元素作為 pivot。	隨機化讓最壞情況的概率極低，期望分割比例接近 $1/2$，遞迴式變為 $E[T(n)]=2E[T(n/2)]+\Theta(n)$。

核心觀念

• 最小生成樹 (MST)：在連通無向圖 $G=(V,E)$ 中，選取 $|V|-1$ 條邊，使得子圖仍連通且邊權總和最小。
• 唯一性條件：若圖中所有邊權皆不同，則 MST 唯一。若存在相同權重的邊，可能會產生多個不同的 MST。
• Kruskal 演算法：依權重遞增挑選邊，加入不會形成迴圈的邊，直至取得 $|V|-1$ 條邊。
• Prim 演算法：從任意起點開始，逐步擴張已建樹的頂點集合，於每一步選取連接集合與外部的最小權重邊。

解題方法

1. 判斷圖是否可能有多個 MST：檢查是否存在權重相等且位於同一環路上的邊。
2. 以具體圖形示範 Kruskal 與 Prim 可能產生不同的 MST。
3. 說明兩演算法在「權重相同時的分支選擇」上之差異，導致最終結果不同。

範例與說明

考慮圖 $G$ 如下（所有邊均為無向）：

頂點	邊	權重
$A$ – $B$	$e_1$	$1$
$B$ – $C$	$e_2$	$1$
$C$ – $A$	$e_3$	$1$
$A$ – $D$	$e_4$	$2$
$B$ – $D$	$e_5$	$2$
$C$ – $D$	$e_6$	$2$

圖示（文字說明）：$A,B,C$ 形成等權重三角形，$D$ 與三角形每個頂點相連，權重均為 $2$。

可能的 MST

• 必須包含 $D$ 的任一條連接邊（權重 $2$）。
• 於三角形 $A\!-\!B\!-\!C$ 中，只需選兩條權重 $1$ 的邊。
  因此，所有符合條件的 MST 共有 $3 \times 1 = 3$ 種（選擇哪條 $2$ 權重邊以及哪兩條 $1$ 權重邊）。

Kruskal 的結果

1. 按權重排序：$e_1, e_2, e_3$（權重 $1$），接著 $e_4, e_5, e_6$（權重 $2$）。
2. 依序加入 $e_1$（$A$–$B$）與 $e_2$（$B$–$C$），此時已形成連通的 $A\!-\!B\!-\!C$ 子圖。
3. 第三條權重 $1$ 的 $e_3$ 會產生迴圈，略過。

核心觀念

• 瓶頸路徑 (Bottleneck Path)：給定圖 $G=(V,E)$，每條邊 $e$ 有權重 $w(e)$。對一條 $u\to v$ 的路徑 $P$，其「最大邊權」定義為 $\displaystyle B(P)=\max_{e\in P}w(e)$。題目要求找出所有 $u\to v$ 路徑中，使 $B(P)$ 最小的那條路徑。
• 最小生成樹 (Minimum Spanning Tree, MST) 的 唯一路徑性質：在任意圖的任一 MST 中，任兩點 $u,v$ 之間的唯一路徑，其最大邊權恰是所有 $u\to v$ 路徑中可以達到的最小值。此性質根源於 割屬性 (Cut Property)：對於任意把圖切成兩部的割，割中權重最小的邊必屬於所有 MST。
• 最小化最大邊權的等價轉換：把「最小化路徑最大邊權」視為「在所有邊權 $\le T$ 的子圖中檢查 $u$、$v$ 是否相通」的二分搜尋問題。

---

解題方法
下面提供兩種等價且皆能得到 $O(E\log V)$ 時間的解法，依需求可自行選擇實作方式。

方法一：先建 MST 再在 MST 中搜尋路徑

1. 建構 MST

   • 使用 Kruskal（或 Prim）演算法。
   • Kruskal 步驟：
     1. 按權重遞增排序所有邊。
     2. 依序把不會形成迴圈的邊加入，使用 Union‑Find（DSU）維護連通性。
   • 時間複雜度：$O(E\log E)=O(E\log V)$（因 $E\le V^2$，$\log E = O(\log V)$）。
   • 空間複雜度：$O(V+E)$（儲存圖與 DSU）。

2. 在 MST 中找 $u\to v$ 路徑

   • MST 為樹，任兩點間的路徑唯一。
   • 以 BFS/DFS 從 $u$ 出發，記錄走過的邊的最大權重 maxEdge。
   • 當到達 $v$ 時，maxEdge 即為答案。
   • 時間複雜度：$O(V)$（樹的遍歷），空間 $O(V)$（遞迴或佇列）。

3. 正確性說明（簡述）

   • 由割屬性可證：在 MST 中任一割的最小邊一定屬於 MST。
   • 若有另一條 $u\to v$ 路徑 $P'$，則其最大邊權 $\ge$ MST 中 $u\to v$ 路徑的最大邊權；否則把 $P'$ 中的最小「跨割」邊加入 MST 會產生更小的生成樹，與 MST 定義矛盾。故 MST 路徑即為瓶頸最小的路徑。

方法二：改版 Dijkstra（ Bottleneck Dijkstra）

1. 資料結構

   • 距離陣列 dist[x] 表示從 $u$ 到 $x$ 目前已知的最小「瓶頸值」 $\displaystyle \min\max w$。初始 dist[u]=0，其餘 $\infty$。
   • 最小堆 (priority queue) 以 dist 為鍵。

2. 演算法步驟

核心觀念

1. 二元搜尋樹（Binary Search Tree, BST）定義：
   對於樹中任意節點 $x$：
   • 其左子樹中的所有節點值皆小於節點 $x$ 的值（$\text{Left}(x) < x$）。
   • 其右子樹中的所有節點值皆大於節點 $x$ 的值（$\text{Right}(x) > x$）。
2. BST 插入運算（Insertion）：
   • 由根節點（Root）開始比對：欲插入鍵值小於當前節點則往左子樹搜尋，大於則往右子樹搜尋。
   • 重複此比對過程直到遇到空指標（null），該空位即為新鍵值插入之處（新節點恆為葉節點或原本空缺之子節點位置）。
3. BST 刪除運算（Deletion）：
   依據待刪除節點擁有子節點（Children）的數量分為三種情況：

   • 情況一（Degree 0）：待刪節點為葉節點（Leaf），直接將其移除，父節點對應指標設為 null。

   • 情況二（Degree 1）：待刪節點僅有單一子節點（只有左子樹或只有右子樹），直接以該子節點取代待刪節點的位置。

   • 情況三（Degree 2）：待刪節點同時具有左右子樹。為了維持 BST 的排序性質，通常有兩種標準替代方案：

     1. 前驅節點（Inorder Predecessor）取代：左子樹中的最大值節點（左子樹一路向右找到底）。
     2. 後繼節點（Inorder Successor）取代：右子樹中的最小值節點（右子樹一路向左找到底）。

     取代後，原本的前驅或後繼節點即退化為情況一或情況二，將其自原位置刪除即可。

---

解題方法

(a) 依序插入 7, 3, 6, 9, 8, 4, 2 建構 BST

初始樹為空樹，逐一進行插入：

1. 插入 7：樹為空，7 成為根節點（Root）。
2. 插入 3：$3 < 7$，放入 7 的左子節點。
3. 插入 6：$6 < 7$ 走左邊至 3；$6 > 3$，放入 3 的右子節點。
4. 插入 9：$9 > 7$，放入 7 的右子節點。
5. 插入 8：$8 > 7$ 走右邊至 9；$8 < 9$，放入 9 的左子節點。
6. 插入 4：$4 < 7 \to 3$；$4 > 3 \to 6$；$4 < 6$，放入 6 的左子節點。
7. 插入 2：$2 < 7 \to 3$；$2 < 3$，放入 3 的左子節點。

所得之二元搜尋樹結構如下：

         7
       /   \
      3     9
     / \   /
    2   6 8
       /
      4

---

(b) 刪除節點 3

在 (a) 建立的樹中，節點 3 同時具有左子樹（含節點 2）與右子樹（含節點 6, 4），屬於 Degree 2 的刪除情況。標準教科書實作有以下兩種替代方式（考試時兩者皆被認可，建議將兩種皆寫出或指明取代方式）：