111 年 國立政治大學資訊科學系碩士班《資料結構與演算法》

核心觀念

本題考查遞迴式的漸近分析，重點是判斷各層遞迴所產生的成本總和。

給定：

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

其中每次遞迴問題規模縮小為原來的 $\frac{1}{3}$，而當層額外成本為 $n$。

---

解題方法：遞迴樹展開

逐層展開遞迴式：

$$T(n)=T\left(\frac{n}{3}\right)+n$$ $$=T\left(\frac{n}{9}\right)+\frac{n}{3}+n$$ $$=T\left(\frac{n}{27}\right)+\frac{n}{9}+\frac{n}{3}+n$$

第 $i$ 層的非遞迴成本為：

$$\frac{n}{3^i}$$

當問題規模縮小至 $1$ 時：

$$\frac{n}{3^k}=1$$

因此遞迴深度為：

$$k=\log_3 n$$

所有非遞迴成本的總和為幾何級數：

$$n+\frac{n}{3}+\frac{n}{9}+\cdots+\frac{n}{3^{\log_3 n}}$$

其總和為：

$$\sum_{i=0}^{\log_3 n}\frac{n}{3^i} =n\sum_{i=0}^{\log_3 n}\left(\frac{1}{3}\right)^i$$

由幾何級數公式：

$$\sum_{i=0}^{k}r^i=\frac{1-r^{k+1}}{1-r}$$

可得：

$$T(n)=\Theta\left( n\cdot \frac{1-(1/3)^{\log_3 n+1}}{1-1/3} \right)$$

由於幾何級數的和受到常數 $\frac{1}{1-1/3}=\frac{3}{2}$ 限制，因此：

$$T(n)=\Theta(n)$$

---

以 Master Theorem 驗證

標準形式為：

核心觀念

本題考查單向鏈結串列（singly linked list）的基本操作，以及「以指標重新連結節點」的能力。

每個節點包含：

1. 資料欄位 data
2. 指向下一個節點的指標 next

串列以指標 head 指向第一個節點：

$$head \rightarrow node_1 \rightarrow node_2 \rightarrow \cdots \rightarrow NULL$$

本題以下採用 第 $1$ 個元素為第一個元素 的編號方式。空串列以 head = NULL 表示。

---

資料結構定義

typedef struct Node {
    int data;
    struct Node *next;
} Node;

typedef struct {
    Node *head;
} LinkedList;

---

2.1 Initializing an empty linked list

解題方法

建立串列時，尚未有任何節點，因此只需將 head 設為 NULL。

void initialize(LinkedList *list) {
    list->head = NULL;
}

複雜度

• 時間：$O(1)$
• 額外空間：$O(1)$

---

2.2 Inserting a node of value $x$, before the first element

解題方法

新節點必須成為新的第一個節點，連結順序如下：

原本：

$$head \rightarrow A \rightarrow B$$

插入 $x$ 後：

$$head \rightarrow X \rightarrow A \rightarrow B$$

操作順序：

1. 建立新節點 newNode
2. 將 newNode->next 指向原本的 head
3. 將 head 改為 newNode

void insertFirst(LinkedList *list, int x) {
    Node *newNode = malloc(sizeof(Node));

    if (newNode == NULL) {
        return;  // 記憶體配置失敗
    }

    newNode->data = x;
    newNode->next = list->head;
    list->head = newNode;
}

為何必須先設定 newNode->next

若先執行：

list->head = newNode;

再設定 newNode->next，原本的第一個節點位置可能遺失。因此必須先保存連結：

newNode->next = list->head;
list->head = newNode;

複雜度

• 時間：$O(1)$
• 額外空間：$O(1)$，不計新建立的節點本身

---

2.3 Inserting a node of value $x$, before the $i$-th element

位置定義

「插入第 $i$ 個元素之前」代表：

• $i=1$：插入串列最前端
• $i>1$：找到第 $i-1$ 個節點，將新節點接在其後
• $i=n+1$：插入目前串列尾端

例如原本為：

$$A \rightarrow B \rightarrow C$$

在第 $2$ 個元素前插入 $X$：

$$A \rightarrow X \rightarrow B \rightarrow C$$

解題方法

先處理 $i=1$ 的特殊情況，因為此時需要修改 head。其餘情況使用指標走訪到第 $i-1$ 個節點。

int insertBefore(LinkedList *list, int i, int x) {
    if (i < 1) {
        return 0;  // 位置不合法
    }

    if (i == 1) {
        insertFirst(list, x);
        return 1;
    }

    Node *prev = list->head;

    // 找到第 i-1 個節點
    for (int pos = 1; pos < i - 1 && prev != NULL; pos++) {
        prev = prev->next;
    }

    // 若 prev 不存在，表示 i 超出允許範圍
    if (prev == NULL) {
        return 0;
    }

    Node *newNode = malloc(sizeof(Node));

    if (newNode == NULL) {
        return 0;
    }

    newNode->data = x;
    newNode->next = prev->next;
    prev->next = newNode;

    return 1;
}

指標連結重點

插入前：

$$prev \rightarrow target$$

插入後：

$$prev \rightarrow newNode \rightarrow target$$

因此必須依序執行：

newNode->next = prev->next;
prev->next = newNode;

若先執行 prev->next = newNode，卻尚未保存原本的 target，便可能失去後半段串列。

複雜度

最壞情況需走訪至串列尾端：

• 時間：$O(n)$
• 額外空間：$O(1)$，不計新建立的節點

---

2.4 Delete the $i$-th element

解題方法

刪除第 $i$ 個節點時：

• $i=1$：將 head 移至第二個節點
• $i>1$：找到第 $i-1$ 個節點，將它直接連到第 $i+1$ 個節點，再釋放第 $i$ 個節點

原本：

$$A \rightarrow B \rightarrow C$$

刪除 $B$ 後：

$$A \rightarrow C$$

程式碼

核心觀念

本題考查以單向鏈結串列（singly linked list）實作堆疊（stack）。

堆疊遵守後進先出（Last In, First Out, LIFO）：

• push：將元素放入堆疊頂端。
• pop：移除並回傳堆疊頂端元素。
• top：取得堆疊頂端元素，但不移除。

以鏈結串列實作時，令指標 top 指向串列第一個節點：

$$top \rightarrow \text{堆疊頂端} \rightarrow \cdots \rightarrow \text{堆疊底端}$$

因此，所有堆疊操作都在鏈結串列的頭端進行。鏈結串列頭端插入與刪除皆不需移動其他節點，時間複雜度為 $O(1)$。

---

資料結構定義

typedef struct Node {
    int data;
    struct Node *next;
} Node;

Node *top = NULL;

其中：

• data 儲存元素值。
• next 指向下一個節點。
• top == NULL 表示堆疊為空。

---

3.1 Push：將元素放入堆疊頂端

解題方法

新節點必須插入鏈結串列頭端，並將 top 更新為新節點。

操作順序如下：

1. 配置一個新節點。
2. 將資料存入新節點。
3. 令新節點的 next 指向原本的 top。
4. 將 top 更新為新節點。

void push(int value) {
    Node *newNode = (Node *)malloc(sizeof(Node));

    if (newNode == NULL) {
        printf("Stack overflow\n");
        return;
    }

    newNode->data = value;
    newNode->next = top;
    top = newNode;
}

假設原本堆疊為：

top -> A -> B -> NULL

執行 push(C) 後：

top -> C -> A -> B -> NULL

複雜度

• 時間複雜度：$O(1)$
• 額外空間複雜度：$O(1)$
• 新增節點所使用的總空間：每個元素一個節點，因此為 $O(n)$

---

3.2 Pop：移除並取得堆疊頂端元素

解題方法

堆疊頂端就是鏈結串列的第一個節點，因此直接刪除頭節點即可。

操作順序如下：

1. 檢查堆疊是否為空。
2. 暫存目前的 top 節點。
3. 儲存該節點的資料。
4. 將 top 移至下一個節點。
5. 釋放原本頂端節點的記憶體。
6. 回傳被移除的元素。

int pop(int *result) {
    if (top == NULL) {
        printf("Stack underflow\n");
        return 0;
    }

    Node *temp = top;
    *result = temp->data;
    top = top->next;
    free(temp);

    return 1;
}

使用方式：

int value;

if (pop(&value)) {
    printf("Popped value = %d\n", value);
}

假設原本堆疊為：

top -> C -> A -> B -> NULL

執行 pop() 後：

• 回傳 C
• 堆疊變為：

核心觀念

深度優先搜尋（DFS）從來源頂點 $s$ 出發，沿著尚未拜訪的鄰點一路深入；走到沒有未拜訪鄰點的頂點時，再回到上一層繼續搜尋。遞迴版 DFS 會用函式呼叫堆疊記錄搜尋路徑；本題要求用堆疊操作實作，便以明確的堆疊取代遞迴。

題目提到的「上述堆疊操作」未附在題幹中。以下假設可使用 push、pop 與 isEmpty，並以鄰接串列表示圖。為了讓堆疊版的拜訪順序與遞迴 DFS 一致，每個堆疊項目除了頂點，也記錄該頂點下一個要檢查的鄰點位置。

解題方法

令 Adj[v] 表示頂點 $v$ 的鄰點串列，visited[v] 記錄是否拜訪過。堆疊中的項目 (v, i) 表示目前正在搜尋頂點 $v$，而 i 是下一個要檢查的鄰點索引。

核心觀念

本題考查 Insertion Sort（插入排序法），並特別要求使用不穩定排序（not stable）。

• 排序鍵值：撲克牌的「數字」。
• 花色：不參與比較，因此 club 10 與 spade 10 視為相同鍵值。
• 穩定排序：相同鍵值的元素，排序後仍維持原本相對順序。
• 不穩定排序：相同鍵值的元素，排序後可以改變原本相對順序。

原始資料中：

$$\text{spade 10 在 club 10 之前}$$

題目輸出卻是：

$$\text{club 10 在 spade 10 之前}$$

因此，題目要求相同數字的牌也可以交換順序，插入排序的比較條件必須讓相等元素發生移動。

---

解題方法

Insertion Sort 將陣列分成兩部分：

1. 左側：已排序區域。
2. 右側：尚未處理區域。

每次取出右側第一張牌作為 key，將左側大於或等於 key 的牌向右移動，再把 key 插入適當位置。

為了使排序不穩定，比較條件使用：

$$A[j].number \geq key.number$$

而不是穩定版本使用的：

$$A[j].number > key.number$$

當兩張牌數字相同時，A[j].number >= key.number 仍會成立，因此原本位於前面的相同數字牌會向右移動，造成花色順序改變。

---

關鍵演算法

InsertionSort(A):
    for i = 1 to n - 1:
        key = A[i]
        j = i - 1

        while j >= 0 and A[j].number >= key.number:
            A[j + 1] = A[j]
            j = j - 1

        A[j + 1] = key

比較時只使用：

A[j].number

不使用：

A[j].suit

因此花色不會影響排序結果。

---

逐步執行

初始陣列為：

$$[\text{club 11},\ \text{spade 10},\ \text{club 10},\ \text{heart 7}]$$

第一次插入：spade 10

已排序區域：

$$[\text{club 11}]$$

比較：

$$11 \geq 10$$

成立，因此將 club 11 向右移動：

$$[\text{club 11},\ \text{club 11},\ \text{club 10},\ \text{heart 7}]$$

插入 spade 10：

$$[\text{spade 10},\ \text{club 11},\ \text{club 10},\ \text{heart 7}]$$

---

第二次插入：club 10

目前已排序區域為：

核心觀念

本題考查最小生成樹（Minimum Spanning Tree, MST）與 Kruskal 演算法。

對含有 $n$ 個頂點的連通無向圖而言，生成樹必須符合：

• 包含全部 $n$ 個頂點；
• 不含任何環；
• 恰有 $n-1$ 條邊。

最小生成樹則是在所有生成樹中，使邊權總和最小者。本題有 $6$ 個頂點，因此最小生成樹必須包含：

$$6-1=5$$

條邊。

Kruskal 演算法的原則是：

1. 將所有邊依權重由小到大排序；
2. 依序選取邊；
3. 若加入該邊不會形成環，便將其加入生成樹；
4. 直到選出 $n-1$ 條邊為止。

其正確性建立在最小生成樹的切割性質：對任意切割，跨越該切割的最小權重邊可安全地加入某棵最小生成樹。

解題方法

由鄰接矩陣取出上三角部分，即可得到每條無向邊：

$$\begin{array}{c|c} \text{邊} & \text{權重} \\ \hline (v_1,v_6) & 8\\ (v_2,v_6) & 9\\ (v_3,v_4) & 9\\ (v_4,v_5) & 9\\ (v_3,v_5) & 10\\ (v_5,v_6) & 11\\ (v_3,v_6) & 12\\ (v_1,v_5) & 13\\ (v_2,v_3) & 14\\ (v_2,v_5) & 15\\ (v_1,v_3) & 16\\ (v_2,v_4) & 17\\ (v_1,v_4) & 18\\ (v_4,v_6) & 19 \end{array}$$

依權重排序後，逐邊執行 Kruskal 演算法：

步驟	考慮的邊	權重	是否加入	理由
1	$(v_1,v_6)$	8	加入	不形成環
2	$(v_2,v_6)$	9	加入	不形成環

核心觀念

本題考查加權圖中的「緊密集合（compact set）」判定。

對頂點集合 $C \subseteq V$，若滿足

$$\min\{E(v_i,v_k)\mid v_i\in C,\ v_k\in V\setminus C\} > \max\{E(v_i,v_j)\mid v_i,v_j\in C\},$$

則 $C$ 為 compact set。

其中：

• 左側是集合 $C$ 與外部頂點之間的最小距離，稱為最小外部距離。
• 右側是集合 $C$ 內部頂點之間的最大距離，稱為最大內部距離。
• 核心條件是：集合內部最遠的兩點，仍然比集合與外部最近的兩點更接近。

因此，compact set 可視為圖中一個「內部緊密、外部隔離」的群集。

解題方法

對每一個候選集合 $C$，依序計算：

$$d_{\text{out}}(C) = \min\{E(v_i,v_k)\mid v_i\in C,\ v_k\in V\setminus C\},$$

以及

$$d_{\text{in}}(C) = \max\{E(v_i,v_j)\mid v_i,v_j\in C\}.$$

最後檢查：

$$d_{\text{out}}(C)>d_{\text{in}}(C).$$

若成立，則 $C$ 是 compact set；若不成立，則不是。

本題題幹未附上第 6 題的圖形或完整距離矩陣，因此無法重新列出各邊權重進行數值驗算。依題目括號中已給出的第 6 題距離關係，符合條件的集合為：