108 年 國立臺灣大學生物機電系碩士班丙組《資料結構（C）》

核心觀念

本題考查兩個重點：

1. 各種排序法的時間複雜度。
2. 鏈結串列不支援隨機存取，適合使用能順序走訪、且不需頻繁索引存取的排序法。

「random linked list」表示資料排列是任意的鏈結串列，不代表具有 $O(1)$ 隨機存取能力。對基於比較的排序而言，下限為：

$$\Omega(n\log n)$$

Merge sort 能在鏈結串列上達到：

$$O(n\log n)$$

因此達到比較排序的最佳漸近時間複雜度。

---

解題方法

設鏈結串列共有 $n$ 個節點。

Merge sort 的處理流程如下：

1. 使用快慢指標將鏈結串列切成左右兩半。
2. 遞迴排序左右兩個子串列。
3. 以合併程序依序比較兩串列的節點，重新串接成有序串列。

遞迴式為：

$$T(n)=2T\left(\frac{n}{2}\right)+O(n)$$

其中：

• $2T(n/2)$：分別排序左右兩半。
• $O(n)$：合併兩個已排序串列，每個節點最多處理一次。

依 Master Theorem：

$$T(n)=O(n\log n)$$

鏈結串列合併時只需調整節點指標，不需要搬移大量資料，也不需要透過索引存取節點，因此特別適合鏈結串列。

---

選項分析

A. Insertion sort

Insertion sort 將每個新節點插入目前已排序的部分。

對陣列而言，插入位置後方的元素需要搬移；對鏈結串列而言，雖然節點插入本身只需 $O(1)$，但尋找正確插入位置通常需要順序走訪，平均仍須檢查 $O(n)$ 個節點。

因此總時間複雜度為：

$$O(n^2)$$

此方法適合資料量小或接近排序的資料，但不具備本題要求的最低漸近時間複雜度。故 A 錯誤。

B. Quick sort

Quick sort 在理想分割下的遞迴式為：

$$T(n)=2T\left(\frac{n}{2}\right)+O(n)$$

平均時間複雜度為：

$$O(n\log n)$$

但若 pivot 每次都選到最大值或最小值，分割會極度不平衡：

$$T(n)=T(n-1)+O(n)=O(n^2)$$

Quick sort 也較依賴索引存取與原地分割。雖然可以設計鏈結串列版本，但其最差時間複雜度不是穩定的 $O(n\log n)$，因此不是本題的最佳選擇。

核心觀念

本題考查單向鏈結串列（singly linked list）的反轉。

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

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

原串列：

$$A \rightarrow B \rightarrow C \rightarrow NULL$$

反轉後：

$$C \rightarrow B \rightarrow A \rightarrow NULL$$

反轉的關鍵是：逐一將每個節點的 next 指標改為指向前一個節點。由於修改指標後會失去原本的後續串列，因此必須先保存下一個節點的位置。

---

解題方法

採用三個指標：

• prev：目前節點的前一個節點
• curr：目前正在處理的節點
• nextNode：暫存目前節點原本的下一個節點

初始設定：

$$prev = NULL$$ $$curr = head$$

每次迭代執行以下步驟：

1. 先保存 curr 的下一個節點：
   nextNode = curr.next
2. 將目前節點的指標反轉：
   curr.next = prev
3. 將 prev 向前移動：
   prev = curr
4. 將 curr 向前移動：
   curr = nextNode

當 curr == NULL 時，所有節點均已處理完畢，此時 prev 即為反轉後的新首節點。

---

偽程式碼

ReverseLinkedList(head):
    prev ← NULL
    curr ← head

    while curr ≠ NULL:
        nextNode ← curr.next
        curr.next ← prev
        prev ← curr
        curr ← nextNode

    head ← prev

題目要求「以 head 作為輸入，無輸出」，因此偽程式碼直接在程序內更新 head。若使用函式實作，則通常會回傳新的首節點：

ReverseLinkedList(head):
    prev ← NULL
    curr ← head

    while curr ≠ NULL:
        nextNode ← curr.next
        curr.next ← prev
        prev ← curr
        curr ← nextNode

    return prev

---

指標變化示範

假設原串列為：

$$A \rightarrow B \rightarrow C \rightarrow NULL$$

初始狀態：

prev = NULL
curr = A

第一次迭代：

核心觀念

本題考查**後序運算式（Postfix Expression / 逆波蘭表示法 RPN）**的堆疊（Stack）求值演算法，核心依據為堆疊的「後進先出（LIFO, Last-In-First-Out）」性質：

1. 遇運算元（Operand）：直接將該數值推入（Push）堆疊頂端。
2. 遇二元運算子（Operator）：
   • 從堆疊中依序彈出（Pop）兩個元素：
     • 第一個彈出的元素為右運算元（$op_2$）
     • 第二個彈出的元素為左運算元（$op_1$）
   • 計算 $op_1 \text{ op } op_2$ 之值。
   • 將計算結果推入（Push）堆疊頂端。

---

解題方法

題目給定之後序運算式為：
$8 \ 2 \ 3 \ \hat{} \ / \ 2 \ 3 \ x \ + \ 5 \ 1 \ x \ -$

目標為求出在第一個乘法運算子 x 運算完畢後，堆疊最頂端的兩個元素。

我們由左至右逐一掃描 Token，並追蹤堆疊狀態（以 [底 ... 頂] 表示堆疊內容）：

步驟	讀入 Token	動作說明	運算式與結果	堆疊內容 [底 $\to$ 頂]
初始	-	堆疊為空	-	[ ]
1	8	運算元 $\to$ Push 8	-	[8]
2	2	運算元 $\to$ Push 2	-	[8, 2]
3	3	運算元 $\to$ Push 3	-	[8, 2, 3]
4	^	彈出 $op_2=3$、$op_1=2$	$2^3 = 8$，Push 8	[8, 8]

核心觀念

二元樹常見的走訪順序如下：

• Preorder（前序）：Root → Left → Right
• Inorder（中序）：Left → Root → Right
• Postorder（後序）：Left → Right → Root

題目未指定兩個 traversal 的種類。以下採用最典型且能唯一建樹的組合：

Preorder + Inorder，且每個節點的鍵值皆不重複。

Preorder 的第一個元素必定是整棵樹的根。找到根在 Inorder 中的位置後：

• 根左側的元素構成左子樹
• 根右側的元素構成右子樹

再對左右子樹遞迴處理，即可重建原二元樹。

---

解題方法

假設：

• preorder：前序序列
• inorder：中序序列
• preIndex：目前要從前序序列取出的元素位置

例如：

$$\text{Preorder}=[A,B,D,E,C,F]$$ $$\text{Inorder}=[D,B,E,A,C,F]$$

前序第一個元素為 $A$，所以 $A$ 是根。$A$ 在中序序列中的位置如下：

$$[D,B,E]\ A\ [C,F]$$

因此：

• 左子樹的中序序列為 $[D,B,E]$
• 右子樹的中序序列為 $[C,F]$

前序中接下來屬於左子樹的元素會先被處理，因此左子樹根為 $B$：

$$[D]\ B\ [E]$$

右子樹根為 $C$：

$$[]\ C\ [F]$$

最後得到：

        A
       / \
      B   C
     / \   \
    D   E   F

---

虛擬碼

function BuildTree(preorder, inorder):
    preIndex = 0

    # 建立 inorder 中每個節點的位置，方便快速查找
    position = empty map

    for i = 0 to length(inorder) - 1:
        position[inorder[i]] = i

    return BuildSubtree(
        preorder,
        0,
        length(inorder) - 1,
        preIndex,
        position
    )


function BuildSubtree(preorder, inLeft, inRight, preIndex, position):

    # 沒有節點
    if inLeft > inRight:
        return NULL

    # Preorder 的下一個節點就是目前子樹的根
    rootValue = preorder[preIndex]
    preIndex = preIndex + 1

    root = new TreeNode(rootValue)

    # 找出根在 Inorder 中的位置
    rootIndex = position[rootValue]

    # 先建立左子樹，再建立右子樹
    root.left = BuildSubtree(
        preorder,
        inLeft,
        rootIndex - 1,
        preIndex,
        position
    )

    root.right = BuildSubtree(
        preorder,
        rootIndex + 1,
        inRight,
        preIndex,
        position
    )

    return root

其中 preIndex 必須在所有遞迴呼叫之間共用。實作時可將它設計成：

• 全域變數；
• 參照參數；
• 包含索引的物件或結構。

核心觀念

本題考查「建立堆積（heap）」的時間複雜度。建立堆積常見有兩種方法：

1. 逐一插入元素：每次插入後向上調整。
2. 使用 Bottom-up Build-Heap：從最後一個非葉節點開始，依序向下調整。

標準的 Bottom-up Build-Heap 時間複雜度為 $\Theta(n)$，因此其最佳情況也屬於 $O(n)$。

---

解題方法

對含有 $n$ 個元素的陣列建立堆積時，葉節點本身已符合堆積條件，只需要處理非葉節點。對高度為 $h$ 的節點，向下調整最多需要 $O(h)$ 時間。

高度為 $h$ 的節點數量約為：

$$\frac{n}{2^{h+1}}$$

因此，所有節點的調整成本總和為：

$$T(n) = \sum_{h=0}^{\log n} \frac{n}{2^{h+1}}O(h)$$

整理可得：

$$T(n) = O\left( n\sum_{h=0}^{\log n}\frac{h}{2^h} \right)$$

其中級數 $\sum_{h=0}^{\infty}\frac{h}{2^h}$ 收斂為常數，因此：

$$T(n)=O(n)$$

在最佳情況下，每個非葉節點都已符合堆積條件，向下調整只需進行常數時間的檢查；但仍須掃描整個陣列中的非葉節點，因此總時間仍為：

$$\Theta(n)$$

所以最佳情況的漸進複雜度為 $O(n)$。

---

選項分析

核心觀念

Inorder traversal（中序走訪）的順序為：

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

遞迴版本會利用系統的 call stack 記錄「尚未處理的根節點」。在不能使用遞迴時，必須自行使用 stack 模擬這個過程。

對目前節點而言：

1. 持續將所有左子節點推入 stack。
2. 左側走到底後，取出 stack 頂端節點並輸出。
3. 將目前節點移至其右子節點。
4. 重複上述步驟，直到目前節點為空且 stack 也為空。

---

解題方法

假設二元樹節點定義如下：

typedef struct Node {
    int data;
    struct Node *left;
    struct Node *right;
} Node;

非遞迴的 inorder traversal：

void inorder(Node *root) {
    Node *current = root;
    Node *stack[100];
    int top = -1;

    while (current != NULL || top != -1) {
        /* 將目前節點及其所有左子節點依序放入 stack */
        while (current != NULL) {
            stack[++top] = current;
            current = current->left;
        }

        /* 左子樹已處理完，輸出根節點 */
        current = stack[top--];
        printf("%d ", current->data);

        /* 接著處理右子樹 */
        current = current->right;
    }
}

演算法流程

以某個節點為根的子樹為例：

• 先沿著 left 指標向下走，並把沿途節點存入 stack。
• 最左側節點沒有左子樹，因此先被取出並輸出。
• 輸出後，轉向該節點的右子樹。
• 若右子樹存在，便從右子樹開始再次沿左側下降。
• 若右子樹不存在，便回到 stack 中上一個尚未輸出的節點。

因此，stack 會保存從根節點到目前路徑上「尚未輸出的祖先節點」。

---

正確性說明

每次執行：

while (current != NULL) {
    stack[++top] = current;
    current = current->left;
}

核心觀念

本題要求判斷有向圖 $G=(V,E)$ 是否至少包含一個有向環（cycle）。

有向圖的深度優先搜尋（DFS）中，每個頂點可分為三種狀態：

• 白色（WHITE）：尚未拜訪。
• 灰色（GRAY）：已拜訪，且目前仍在 DFS 的遞迴路徑中。
• 黑色（BLACK）：已完成所有相鄰頂點的搜尋，已離開 DFS 路徑。

若 DFS 過程中發現一條邊 $u\rightarrow v$，而 $v$ 仍為灰色，代表目前搜尋路徑中存在：

$$v\leadsto u\rightarrow v$$

因此形成有向環。

必須注意：有向圖不能只用單純的 visited 判斷環，因為「曾經拜訪過」不等於「目前仍在遞迴路徑中」。

---

解題方法

使用 DFS 搭配三色標記：

1. 對所有頂點依序檢查，確保不連通的圖也能被處理。
2. 若頂點尚未拜訪，從該頂點開始 DFS。
3. 探索 $u$ 的每一條出邊 $u\rightarrow v$：
   • $v$ 為白色：遞迴搜尋 $v$。
   • $v$ 為灰色：找到回邊，表示存在 cycle。
   • $v$ 為黑色：該頂點已完成處理，不代表目前路徑有環。
4. 若所有 DFS 都結束仍未找到回邊，則圖中沒有環。

---

參考偽程式碼

WHITE = 0
GRAY  = 1
BLACK = 2

function containsCycle(G):
    for each vertex u in G:
        color[u] = WHITE

    for each vertex u in G:
        if color[u] == WHITE:
            if DFS(u) == true:
                return true

    return false


function DFS(u):
    color[u] = GRAY

    for each vertex v in Adj[u]:
        if color[v] == GRAY:
            return true

        if color[v] == WHITE:
            if DFS(v) == true:
                return true

    color[u] = BLACK
    return false

其中 Adj[u] 表示頂點 $u$ 的鄰接串列。

---

正確性說明