109 年 國立臺灣大學工程科學及海洋工程學系碩士班丁組《資料結構（A）》

核心觀念

本題考查：

• 偶數與奇數的判斷：
  $x \text{ 為偶數} \iff x \bmod 2 = 0$
  $x \text{ 為奇數} \iff x \bmod 2 \ne 0$
• 陣列的原地（in-place）重新排列。
• 遞迴與雙指標分割（two-pointer partition）。

目標不是將陣列排序，而是滿足：

$$\text{所有偶數} \quad \text{出現在所有奇數之前}$$

偶數彼此之間、奇數彼此之間的原有順序不必保留，因此可以直接交換元素。

解題方法

使用兩個索引：

• left 從左側向右尋找尚未處理的位置。
• right 從右側向左尋找尚未處理的位置。

當：

• a[left] 是奇數；
• a[right] 是偶數；

代表兩者位置錯誤，將它們交換。

交換或確認元素位置正確後，將已處理的位置向內縮小，最後遞迴處理剩餘區間。

參考程式碼

void rearrangeEvenOdd(int a[], int left, int right)
{
    if (left >= right)
        return;

    if (a[left] % 2 != 0 && a[right] % 2 == 0) {
        int temp = a[left];
        a[left] = a[right];
        a[right] = temp;
    }

    if (a[left] % 2 == 0)
        left++;

    if (a[right] % 2 != 0)
        right--;

    rearrangeEvenOdd(a, left, right);
}

呼叫方式如下：

rearrangeEvenOdd(a, 0, n - 1);

其中 n 為陣列長度。若陣列為空，傳入 right = -1 也會立即結束。

正確性說明

每次遞迴都維持以下條件：

核心觀念

單向鏈結串列的每個節點只有 next 指標，沒有指向前一個節點的 prev 指標。因此，若要真正移除節點 node，必須讓其前驅節點改指向：

$$node.next$$

也就是：

$$prev.next = node.next$$

其中 prev 是 node 在串列中的前一個節點。

若 node 是首節點，則沒有前驅節點，必須直接更新串列首指標：

$$head = head.next$$

---

解題方法

由於題目要求其他節點的順序完全不變，最穩定且適用所有情況的方法是：

1. 若 node 是首節點，將 head 往後移一格。
2. 否則從 head 開始走訪，尋找 node 的前驅節點 prev。
3. 找到後執行 prev.next = node.next，跳過 node。
4. 將 node.next 設為 null，使被移除節點與串列脫離。

關鍵程式碼

以下以 Java 風格表示：

class SListNode {
    int data;
    SListNode next;
}

class SList {
    SListNode head;

    void removeNode(SListNode node) {
        if (node == null || head == null) {
            return;
        }

        // 移除首節點
        if (head == node) {
            head = head.next;
            node.next = null;
            return;
        }

        // 尋找 node 的前驅節點
        SListNode prev = head;

        while (prev.next != null && prev.next != node) {
            prev = prev.next;
        }

        // node 必須確實存在於串列中
        if (prev.next == node) {
            prev.next = node.next;
            node.next = null;
        }
    }
}

核心觀念

二元搜尋樹（Binary Search Tree, BST）具有以下性質：

• 左子樹中每個 key 小於根節點 key。
• 右子樹中每個 key 大於根節點 key。
• 對 BST 進行「中序走訪」（inorder traversal），訪問順序為：

$$\text{左子樹} \rightarrow \text{根節點} \rightarrow \text{右子樹}$$

所得的 key 序列會按照遞增順序排列。因此，BST 中第 $k$ 個被中序走訪訪問的節點，就是第 $k$ 小的 key。

---

解題方法：中序走訪搭配計數

採用「中序走訪＋計數器」的方法：

1. 從 BST 的根節點開始，優先走訪左子樹。
2. 每訪問一個節點，就將計數器加 $1$。
3. 當計數器等於 $k$ 時，該節點的 key 即為第 $k$ 小的 key，立即停止。
4. 若計數器尚未達到 $k$，再繼續走訪右子樹。
5. 對每個子樹重複相同程序，直到找到第 $k$ 個節點。

此方法的關鍵在於：中序走訪保證節點按照 key 由小到大被訪問，所以第 $k$ 次訪問必然對應第 $k$ 小的 key。

非遞迴實作概念

為避免遞迴，可使用堆疊模擬中序走訪：

1. 沿著左鏈一路將節點放入堆疊，直到目前節點為空。
2. 取出堆疊頂端節點，視為下一個最小 key，並將計數器加 $1$。
3. 若計數器等於 $k$，回傳該節點的 key。
4. 將目前節點改為該節點的右子樹，再重複上述流程。

這樣即可按照中序順序逐一產生 BST 的 key，而不必先將全部 key 排列後再尋找第 $k$ 個。

---

正確性說明

根據 BST 的定義：

核心觀念

本題考查漸近成長率，主要使用：

1. $O(\cdot)$ 的定義：若存在常數 $c>0$ 與 $n_0$，使得 $$0\le f(n)\le c\,g(n),\qquad n\ge n_0,$$ 則稱 $f(n)=O(g(n))$。
2. 對數與指數的轉換公式： $$n^x=e^{x\ln n}.$$
3. 多項式的最高次項決定其漸近成長率。

以下假設題目中的 $n1+a//\log n$ 是指

$$n^{1+\frac{a}{\log n}},\qquad a>0.$$

（a）比較 $n\log n$ 與 $n^{1+\frac{a}{\log n}}$

解題方法

關鍵在於化簡第二個函數的指數部分。取自然對數作為 $\log$ 的底數，則

$$n^{1+\frac{a}{\log n}} =n\cdot n^{\frac{a}{\log n}}.$$

再利用 $n^x=e^{x\log n}$：

$$n^{\frac{a}{\log n}} =e^{\frac{a}{\log n}\log n} =e^a.$$

因此

$$n^{1+\frac{a}{\log n}} =e^a n.$$

其中 $e^a$ 是與 $n$ 無關的常數，所以

$$n^{1+\frac{a}{\log n}}=\Theta(n).$$

另一方面，

$$n\log n=\Theta(n\log n).$$

比較兩者：

$$\frac{n\log n}{n^{1+\frac{a}{\log n}}} = \frac{n\log n}{e^a n} = \frac{\log n}{e^a} \longrightarrow \infty.$$

因此 $n\log n$ 的成長速度較快。

若 $\log$ 的底數為 $b>1$，則

$$n^{\frac{a}{\log_b n}} = n^{\frac{a\ln b}{\ln n}} =e^{a\ln b} =b^a,$$

仍然只是常數，因此結論不受對數底數影響。

（b）證明 $\log p(n)=O(\log n)$

解題方法

設 $p(n)$ 是一個固定次數的多項式：

$$p(n)=c_dn^d+c_{d-1}n^{d-1}+\cdots+c_1n+c_0,$$

核心觀念

題目要求支援：

• push(x)：將元素 $x$ 放入堆疊頂端。
• pop()：移除並回傳堆疊頂端元素。
• findMin()：回傳目前所有元素中的最小值。

三種操作都必須在最壞情況下達到 $O(1)$ 時間。

普通堆疊能在 $O(1)$ 時間完成 push 與 pop，但若每次 findMin 都掃描整個堆疊，時間會是 $O(n)$。因此，必須額外儲存「截至目前位置的最小值」。

---

解題方法：每個節點儲存目前最小值

令堆疊中的每個節點儲存一組資料：

$$(value,\ minPrefix)$$

其中：

• value 是該節點原本存入的元素。
• minPrefix 是從堆疊底部到此節點為止的最小值。

例如依序插入 $5,3,7,2$ 後，堆疊內容如下：

value	minPrefix
5	5
3	3
7	3
2	2

最上方節點的 minPrefix 就是整個堆疊的最小值。

---

操作設計

設堆疊頂端節點的最小值為 top.minPrefix。

1. push(x)

若堆疊為空，則：

$$minPrefix=x$$

若堆疊不為空，則：

$$minPrefix=\min(x,\ top.minPrefix)$$

再將 $(x,minPrefix)$ 放入堆疊頂端。

push(x):
    if stack is empty:
        newMin = x
    else:
        newMin = min(x, stack.top.minPrefix)

    stack.push((x, newMin))

2. pop()

直接移除堆疊頂端節點，回傳其 value。

pop():
    if stack is empty:
        report underflow

    (value, minPrefix) = stack.pop()
    return value

3. findMin()

直接讀取堆疊頂端節點的 minPrefix。

核心觀念

本題考查：

• 無向加權圖（weighted undirected graph）的基本性質。
• 生成樹（spanning tree）：包含所有頂點且不含 cycle 的 connected subgraph。
• 最小生成樹（Minimum Spanning Tree, MST）：所有生成樹中，邊權重總和最小者。
• 具有 $n$ 個頂點的生成樹必恰有 $n-1$ 條邊，因此本題的 MST 必須有

$$8-1=7$$

條邊。

可使用 Kruskal 演算法：

1. 將所有邊依權重由小到大排序。
2. 依序加入邊。
3. 若加入某邊會形成 cycle，則捨棄。
4. 選滿 $n-1$ 條邊時即得到 MST。

由於每條邊的權重皆不相同，因此本題所構造的圖具有唯一的 MST。

---

(a) 構造符合條件的圖

取 8 個頂點：

$$V=\{A,B,C,D,E,F,G,H\}$$

以下列出 16 條無向邊及其權重：

邊	權重	邊	權重
$AB$	1	$AC$	8
$BC$	2	$BD$	9
$CD$	3	$CE$	10
$DE$	4	$DF$	11
$EF$	5	$EG$	12
$FG$	6	$FH$	13
$GH$	7	$AH$	14
$BE$	15	$CG$	16

其中主要連通路徑為：

$$A\mathbin{-}B\mathbin{-}C\mathbin{-}D\mathbin{-}E\mathbin{-}F\mathbin{-}G\mathbin{-}H$$

並加入其他 9 條弦邊：

$$AC,\ BD,\ CE,\ DF,\ EG,\ FH,\ AH,\ BE,\ CG$$

因此：

• 頂點數為 $8$。
• 邊數為 $16$。
• 沒有自迴路，也沒有重複邊，所以是 simple graph。
• 由路徑 $A-B-C-D-E-F-G-H$ 可知圖是 connected。
• 所有權重 $1,2,\ldots,16$ 均不相同。

---

(b) 使用 Kruskal 演算法求 MST

依權重由小到大考慮各邊：

核心觀念

本題考查陣列型、原地（in-place）Quicksort 的分割（partition）程序：

1. 選取目前子陣列的最後一個元素作為 pivot。
2. 將小於或等於 pivot 的元素移到左側，大於 pivot 的元素留在右側。
3. 將 pivot 與分割位置交換，使 pivot 到達最終排序位置。
4. 對 pivot 左右兩個子陣列遞迴執行相同程序。

此處採用常見的 Lomuto partition，分割範圍為 $A[\ell \ldots r]$：

pivot = A[r]
i = ℓ

for j = ℓ to r − 1:
    if A[j] ≤ pivot:
        swap(A[i], A[j])
        i = i + 1

swap(A[i], A[r])

題目中的空格只是分隔兩組字母，不列入排序，因此初始陣列為

$$[E,\ S,\ O,\ E,\ E,\ X,\ A,\ M]$$

---

解題方法與逐步交換

第一次分割：$[E,S,O,E,E,X,A,M]$

目前子陣列為整個陣列，最後元素為

$$\text{pivot}=M$$

依序掃描前 $7$ 個元素：

掃描元素	動作	交換後陣列
$E$	$E\le M$，與自身交換	$[E,S,O,E,E,X,A,M]$
$S$	$S\le M$，與自身交換	$[E,S,O,E,E,X,A,M]$
$O$	$O>M$，不交換	—
$E$	與 $O$ 交換	$[E,S,E,O,E,X,A,M]$
$E$	與 $O$ 交換	$[E,S,E,E,O,X,A,M]$
$X$	$X>M$，不交換	—
$A$	與 $O$ 交換	$[E,S,E,E,A,X,O,M]$

掃描結束後，將 pivot $M$ 與目前分割位置的 $X$ 交換：

$$[E,S,E,E,A,X,O,M] \longrightarrow [E,S,E,E,A,M,O,X]$$

因此 $M$ 已位於最終位置：

$$[E,S,E,E,A]\quad M\quad [O,X]$$

---

第二次分割：左子陣列 $[E,S,E,E,A]$

目前子陣列為 $A[0\ldots4]$，pivot 為最後元素

$$\text{pivot}=A$$

前面的 $E,S,E,E$ 都大於 $A$，因此掃描過程沒有元素交換。最後將 pivot $A$ 與子陣列第一個元素 $E$ 交換：

$$[E,S,E,E,A,M,O,X] \longrightarrow [A,S,E,E,E,M,O,X]$$

此時：

$$A\quad [S,E,E,E]\quad M\quad [O,X]$$

---

第三次分割：子陣列 $[S,E,E,E]$

核心觀念

本題考查陣列型、原地（in-place）Quicksort 的分割（partition）程序：

1. 選取目前子陣列的最後一個元素作為 pivot。
2. 將小於或等於 pivot 的元素移到左側，大於 pivot 的元素留在右側。
3. 將 pivot 與分割位置交換，使 pivot 到達最終排序位置。
4. 對 pivot 左右兩個子陣列遞迴執行相同程序。

此處採用常見的 Lomuto partition，分割範圍為 $A[\ell \ldots r]$：

pivot = A[r]
i = ℓ

for j = ℓ to r − 1:
    if A[j] ≤ pivot:
        swap(A[i], A[j])
        i = i + 1

swap(A[i], A[r])

題目中的空格只是分隔兩組字母，不列入排序，因此初始陣列為

$$[E,\ S,\ O,\ E,\ E,\ X,\ A,\ M]$$

---

解題方法與逐步交換

第一次分割：$[E,S,O,E,E,X,A,M]$

目前子陣列為整個陣列，最後元素為

$$\text{pivot}=M$$

依序掃描前 $7$ 個元素：

掃描元素	動作	交換後陣列
$E$	$E\le M$，與自身交換	$[E,S,O,E,E,X,A,M]$
$S$	$S\le M$，與自身交換	$[E,S,O,E,E,X,A,M]$
$O$	$O>M$，不交換	—
$E$	與 $O$ 交換	$[E,S,E,O,E,X,A,M]$
$E$	與 $O$ 交換	$[E,S,E,E,O,X,A,M]$
$X$	$X>M$，不交換	—
$A$	與 $O$ 交換	$[E,S,E,E,A,X,O,M]$

掃描結束後，將 pivot $M$ 與目前分割位置的 $X$ 交換：

$$[E,S,E,E,A,X,O,M] \longrightarrow [E,S,E,E,A,M,O,X]$$

因此 $M$ 已位於最終位置：

$$[E,S,E,E,A]\quad M\quad [O,X]$$

---

第二次分割：左子陣列 $[E,S,E,E,A]$

目前子陣列為 $A[0\ldots4]$，pivot 為最後元素

$$\text{pivot}=A$$

前面的 $E,S,E,E$ 都大於 $A$，因此掃描過程沒有元素交換。最後將 pivot $A$ 與子陣列第一個元素 $E$ 交換：

$$[E,S,E,E,A,M,O,X] \longrightarrow [A,S,E,E,E,M,O,X]$$

此時：

$$A\quad [S,E,E,E]\quad M\quad [O,X]$$

---

第三次分割：子陣列 $[S,E,E,E]$

核心觀念

Splay tree 的每次搜尋、插入或刪除操作，都會將「最後存取到的節點」旋轉至根節點。若搜尋的鍵值不存在，則將搜尋路徑上最後一個節點旋轉至根。

依題目列出的樹形，初始樹為：

        3
       / \
      2   10
         /  \
        8   12
       / \
      6   9
       \
        7

要執行 remove(5)，先搜尋鍵值 5。搜尋路徑為：

$$3 \rightarrow 10 \rightarrow 8 \rightarrow 6 \rightarrow \text{空}$$

鍵值 5 不存在，因此最後存取到的節點是 6。

解題方法

將節點 6 splay 至根。

1. 節點 6 與父節點 8、祖父節點 10 形成左左鏈，先進行一次右旋，再進行一次右旋：

$$(6,8,10)\quad\Rightarrow\quad 6 \text{ 上升至 } 10 \text{ 的位置}$$