109 年 國立中央大學資訊工程學系碩士班《資料結構與演算法》

核心觀念

深度優先搜尋（DFS）會沿著尚未拜訪的鄰接頂點持續深入；只有目前頂點的所有鄰接頂點都已拜訪，才能回溯至上一層。

DFS 走訪序列只記錄各頂點「第一次被拜訪」的順序，不記錄回溯經過的頂點。因此，序列中連續出現的兩個頂點不一定直接相連。題目未指定鄰接頂點的選擇順序，所以同一張圖可以有多種合法的 DFS 序列。

解題方法

依原圖，這是無向圖，外圈的邊形成 $1\!-\!2\!-\!10\!-\!3\!-\!6\!-\!7\!-\!4\!-\!0\!-\!8\!-\!1$，另外還有邊 $2\!-\!6$、$7\!-\!5$ 與 $1\!-\!4$，共 12 條邊。其中，$5$ 只與 $7$ 相連。

逐一模擬各選項：下一個頂點若是目前頂點尚未拜訪的鄰點，就向下深入；若需要回溯，則檢查沿途每個被離開的頂點是否已無未拜訪的鄰點。

以下以 $\to$ 表示首次拜訪，回溯則另外說明。

選項分析

• (A) 正確：$1,2,6,7,4,0,8,5,3,10$

  先沿著
  $1\to2\to6\to7\to4\to0\to8$
  深入。到達 $8$ 時，其鄰點 $1$、$0$ 都已拜訪，可以依序經 $0$、$4$ 回溯至 $7$，再拜訪 $5$。

  $5$ 只有鄰點 $7$，因此回溯至 $7$；此時 $7$ 的鄰點皆已拜訪，繼續回溯至 $6$，再沿著 $6\to3\to10$ 深入。整個順序合法。

• (B) 正確：$1,8,0,4,7,5,6,3,10,2$

核心觀念

最小堆積（Min-Heap）是一棵完全二元樹，且每個節點的值都小於或等於其子節點。以從 $0$ 開始的陣列表示時，索引 $i$ 的父節點索引為：

$$\left\lfloor \frac{i-1}{2} \right\rfloor$$

插入新值時，先將它放在陣列末端，再沿父節點向上比較；若新值小於父節點，就交換，直到堆積順序成立。

解題方法

原陣列有 $11$ 個元素，因此新數字 $9$ 先放在索引 $11$。逐層向上比較：

1. 索引 $11$ 的父節點索引為 $\lfloor(11-1)/2\rfloor=5$，該位置的值為 $16$。因為 $9<16$，交換，$9$ 移至索引 $5$。
2. 索引 $5$ 的父節點索引為 $\lfloor(5-1)/2\rfloor=2$，該位置的值為 $15$。因為 $9<15$，交換，$9$ 移至索引 $2$。

核心觀念

中序線索二元樹會把原本未使用的左、右子指標改作「線索」，分別指向該節點的中序前驅與中序後繼。若某一側已有子節點，該側指標仍指向子節點，不改作線索。

解題方法

圖中與節點 3 有關的結構是：節點 6 的左子節點為 3，節點 3 的左子節點為 2，且節點 3 沒有右子節點。依中序走訪規則「左子樹、根、右子樹」，相關順序為節點 2、節點 3、節點 6。

因此，節點 3 的左指標指向子節點 2；右指標因沒有右子節點，改作中序後繼線索，指向節點 6。

選項分析

核心觀念

拓樸排序是有向無環圖中所有頂點的一種排列，使每條有向邊 $u\to v$ 的起點 $u$ 都排在終點 $v$ 前面。若以 $\operatorname{pos}(v)$ 表示頂點 $v$ 在排列中的位置，必須滿足：

$$\operatorname{pos}(u)<\operatorname{pos}(v) \qquad \text{對每條有向邊 }u\to v。$$

此限制也適用於間接路徑：若存在 $u\to\cdots\to v$，則 $u$ 必須排在 $v$ 前面。因此，不能只因兩個頂點沒有直接連邊，就判定它們的順序可以互換。

解題方法

原圖共有六個頂點 $0,1,2,3,4,5$，依箭頭方向讀出八條有向邊：

$$0\to4,\quad 0\to1,\quad 2\to3,\quad 2\to1,\quad 4\to3,\quad 4\to1,\quad 4\to5,\quad 3\to5。$$

採用逐步移除入度為零的頂點的方法：入度為零代表所有前置限制都已滿足，可以排入下一個位置。

1. 一開始可選 $0$ 或 $2$：只有這兩個頂點的入度為零。
2. $4$ 必須等 $0$ 排入後才能選，因為有 $0\to4$。
3. $1$ 與 $3$ 都必須等 $4$、$2$ 排入後才能選；其中 $1$ 還要求 $0$ 已排入，而 $0$ 本來就必須先於 $4$。
4. $5$ 必須等 $4$、$3$ 排入後才能選，因為有 $4\to5$ 與 $3\to5$。

核心觀念

快速排序（quick sort）的第一次分割會選出一個樞紐（pivot），並將資料分成兩側：樞紐左側的元素不大於樞紐，右側的元素不小於樞紐。分割後，樞紐位於它的最終位置；但左右兩側的元素不必各自排序。

解題方法

依序檢查序列中的候選樞紐。若某個元素符合「左側元素全部不大於它，右側元素全部不小於它」，它就能是第一次分割的樞紐。

給定序列為：

$$3,9,1,14,20,24,22,21$$

檢查 $14$：

• 左側為 $3,9,1$，皆小於 $14$。
• 右側為 $20,24,22,21$，皆大於 $14$。

因此，$14$ 符合樞紐條件。

檢查 $20$：

• 左側為 $3,9,1,14$，皆小於 $20$。
• 右側為 $24,22,21$，皆大於 $20$。

因此，$20$ 也符合樞紐條件。兩側元素的排列不必有序，所以 $24,22,21$ 的順序不影響判斷。

選項分析

核心觀念

每個 bucket 有 2 個槽位。數字先放入雜湊函數指定的 bucket；若該 bucket 已滿，就依線性探測法往下一個 bucket 找，直到找到尚有空位的 bucket。

本題的雜湊函數為：

$$h(n)=n\bmod 11$$

「滿 bucket」指其中 2 個槽位都已放入數字。題目要加總所有滿 bucket 內的數字。

解題方法

依序計算每個數字的雜湊位置，並在碰撞時往後探測：

數字	雜湊位置	插入結果
6	6	bucket 6：6
16	5	bucket 5：16
22	0	bucket 0：22
44	0	bucket 0：22、44（滿）
53	9	bucket 9：53
24	2	bucket 2：24
45	1	bucket 1：45
7	7	bucket 7：7
74	8	bucket 8：74
4	4	bucket 4：4
109	10	bucket 10：109
78	1	bucket 1：45、78（滿）

核心觀念

後序式（postfix expression）中，運算子寫在運算元之後。對二元運算子而言，從左至右掃描時：

• 遇到運算元，就將它推入堆疊。
• 遇到運算子，就必須從堆疊取出兩個運算元，完成運算後再將結果推回。
• 掃描結束時，堆疊必須恰好剩下一個結果。

若遇到運算子時堆疊中的項目少於兩個，該後序式就不合法。

解題方法

依序掃描 $bcd+*/aefg*+*$，括號內表示堆疊中的項目：

符號	動作	堆疊內容
$b$	推入運算元	$b$
$c$	推入運算元	$b,\ c$
$d$	推入運算元	$b,\ c,\ d$

核心觀念

對有向圖的鄰接矩陣 $A$，慣例是：若頂點 $v_i$ 有一條邊指向 $v_j$，則 $A_{ij}=1$；沒有邊則 $A_{ij}=0$。

因此：

• 第 $i$ 列的總和 $\sum_j A_{ij}$，計算從 $v_i$ 指出去的邊數，也就是 $v_i$ 的出度。
• 第 $j$ 欄的總和 $\sum_i A_{ij}$，計算指向 $v_j$ 的邊數，也就是 $v_j$ 的入度。

解題方法

核心觀念

這題考圖的邊數能否單獨判定圖為樹，以及「二元樹」比一般樹多出的限制。

對含 $n$ 個頂點的無向圖，若圖連通且有 $n-1$ 條邊，則它是樹。反過來，樹也恰有 $n-1$ 條邊。但邊數條件本身不保證連通，也不保證符合二元樹的結構限制。

二元樹除了必須是樹，還要求以某個頂點為根後，每個頂點最多有兩個子節點。

解題方法

只要找出一個符合 $|E|=|V|-1$、卻不是二元樹的圖，就能否定題目中的「任意圖」這項主張。

例如，取一個三角形和一個孤立頂點：

核心觀念

深度優先搜尋（DFS）會沿著一條路徑持續往深處探索，直到無路可走時，再回到上一個分岔點繼續搜尋。這種「後進先出」的回溯順序，正好可以用堆疊（stack）實作。

遞迴版 DFS 會使用程式執行環境的呼叫堆疊記錄尚未完成的呼叫；迭代版 DFS 則可自行建立堆疊，記錄待探索的節點。

解題方法

核心觀念

圖 $G$ 的連通分量是 $G$ 的一個極大連通子圖：子圖中的任意兩個頂點彼此連通，而且不能再加入 $G$ 中其他頂點及相關邊，同時仍保持為連通子圖。

題目給出的 $V(G')\subseteq V(G)$ 與 $E(G')\subseteq E(G)$，只表示 $G'$ 的頂點和邊來自 $G$，也就是 $G'$ 是 $G$ 的子圖。這些包含關係不足以保證 $G'$ 是連通分量；還必須滿足連通性與極大性。

解題方法

檢查題目所述條件是否足以推出「連通分量」。只要找出一個符合頂點、邊包含關係，卻不是連通分量的子圖，就能否定此敘述。

核心觀念

本題考兩個堆疊共用一個陣列的配置方式。堆疊 0 從陣列左端往右成長，堆疊 1 從右端往左成長，因此兩個堆疊能共用陣列空間。

題目未指定 top 的初始值與溢位處理方式；以下採用常見慣例：top[0] = -1、top[1] = MEMORY_SIZE，並在容量不足時回報溢位。

解題方法

top[0] 指向堆疊 0 最上方的元素；堆疊 1 則在推入前先將 top[1] 減一，再用它指向新元素。因此兩個堆疊目前的元素數分別為：

$$\text{stack 0 元素數} = top[0] + 1$$ $$\text{stack 1 元素數} = \text{MEMORY\_SIZE} - top[1]$$

將兩者相加，先確認總元素數小於題目指定的 MEMORY_SIZE - 1，再依照堆疊編號更新對應的 top 並存入元素。

核心觀念

本題考「回溯法」產生排列。每一層遞迴決定一個位置要放哪個元素：

• 位置 $1$ 到 $i-1$ 已經決定。
• 位置 $i$ 到 $n$ 尚未決定。
• 將尚未決定的元素逐一換到位置 $i$，再遞迴處理下一個位置。
• 遞迴返回後，把交換還原，才能嘗試下一個候選元素。

當 $i=n$ 時，所有位置都已決定，輸出目前排列。

解題方法

在每一層，位置 $i$ 可以選用的元素，正是目前仍位於 $list[i]$ 到 $list[n]$ 的元素，因此迴圈範圍為 $j=i$ 到 $n$，包含兩端。

每次選定 $list[j]$ 後，先與 $list[i]$ 交換，讓選定的元素固定在目前位置；再呼叫 perm(list, i+1, n)，處理下一個位置。遞迴完成後，執行相同的交換以還原陣列。

核心觀念

最小生成樹（MST）是連通、無向、加權圖 $G=(V,E)$ 的一棵生成樹，使所有邊的權重總和最小。生成樹包含全部 $|V|$ 個頂點，且恰有 $|V|-1$ 條邊。

本題可使用 Kruskal 演算法。若目前選入的邊形成數個連通分量，將不同分量之間權重最小的邊加入，仍能保留取得 MST 的可能性。若某條邊的兩端已在同一分量，加入後會形成環，因此必須略過。

解題方法：Kruskal 演算法

先將所有邊依權重由小到大排序，再依序檢查。只有當一條邊連接兩個不同的連通分量時，才將它加入 MST。選入 $|V|-1$ 條邊後，演算法完成。

Kruskal(G):
    將所有邊依權重由小到大排序
    對每個頂點建立一個獨立集合
    T = 空集合

    對排序後的每條邊 (u, v, w):
        若 Find(u) != Find(v):
            將 (u, v, w) 加入 T
            Union(u, v)
            若 |T| = |V| - 1:
                停止

    回傳 T

Find(x) 用來判斷頂點 $x$ 所屬的連通分量；Union(u,v) 將兩個分量合併。

核心觀念

生成樹是連通圖中包含所有頂點的無環子圖。題目所說的「第二佳成本」是把所有生成樹的成本由小到大排列後，第二個成本；因此若有不同生成樹同為最小成本，第二佳成本也可以等於最小成本。

用到的關鍵性質是生成樹的換邊性質：在一棵生成樹中加入一條原本不在樹上的邊，會形成唯一的環。從這個環移除一條邊，就會得到另一棵生成樹。

解題方法

先用 Kruskal 或 Prim 找出一棵最小生成樹 $T$，其成本記為 $W$。對每一條不在 $T$ 中的邊 $e=(u,v)$：

1. 加入 $e$，形成環；這個環由 $e$ 和 $T$ 中 $u$ 到 $v$ 的唯一路徑組成。
2. 找出該路徑上權重最大的邊 $f$。
3. 移除 $f$，得到另一棵生成樹，其成本為 $$W+w(e)-w(f).$$
4. 將所有這類成本取最小值，便是第二佳成本。

選擇路徑上的最大權重邊，是因為固定加入 $e$ 時，移除越重的邊，新生成樹的成本越低。若 $w(e)=w(f)$，換邊後成本仍為 $W$，但生成樹已不同，正好能處理多棵最小生成樹的情況。

偽程式碼：

T = 用 Kruskal 找一棵最小生成樹
W = T 的總權重
bestSecond = +∞

對每條不在 T 中的邊 e = (u, v, weight):
    pathMax = T 中 u 到 v 路徑上的最大邊權
    candidate = W + weight - pathMax
    bestSecond = min(bestSecond, candidate)

若 bestSecond = +∞：
    不存在第二棵生成樹
否則：
    回傳 bestSecond

核心觀念

本題考查排序後的雙指標法（two-pointer）。排序能讓指標移動方向具有明確規則：固定一個數後，若三數總和太小，就增加左側數值；若總和太大，就減少右側數值。

解題方法

先將 $S$ 由小到大排序。依序固定第 $i$ 個數 $S[i]$，接著令左指標 $j=i+1$、右指標 $r=n-1$，檢查 $S[i]+S[j]+S[r]$：

• 若總和等於 $M$，表示找到三個數。
• 若總和小於 $M$，將 $j$ 右移。因為固定 $i,r$ 時，右指標左側的數不會更大，增加左指標數值才可能讓總和變大。
• 若總和大於 $M$，將 $r$ 左移。因為固定 $i,j$ 時，左指標右側的數不會更小，減少右指標數值才可能讓總和變小。

每次移動一個指標，都會排除目前不可能成功的組合。固定 $i$ 時，兩個指標最多各移動 $n$ 次，因此掃描時間為 $O(n)$。

關鍵程式碼

核心觀念

要證明一個決定問題是 NP-complete（NP 完全），需完成兩件事：

1. 屬於 NP：若答案為「是」，存在一份可在多項式時間內驗證的證明。
2. NP-hard（NP 困難）：從已知的 NP 完全問題，能在多項式時間內歸約到此問題。

題目以「實數」描述輸入；計算複雜度分析須假設數值有有限的位元表示。以下採用標準模型：輸入為二進位編碼的整數或有理數，且 $k$ 是輸入的一部分。

解題方法

一、證明問題屬於 NP

若答案為「是」，證明可以列出 $S$ 中被選出的 $k$ 個元素。驗證者檢查：

• 所列元素確實屬於 $S$，且沒有重複使用同一元素；
• 這些元素的和等於 $M$。

整數的加法與比較可在輸入位元長度的多項式時間內完成；有理數也可用精確運算驗證。因此，此問題屬於 NP。若 $k>|S|$，答案直接為「否」。

二、從 Subset Sum 歸約

使用已知的 NP 完全問題 Subset Sum：給定正整數 $a_1,\ldots,a_n$ 與目標值 $T$，判斷是否存在一個索引子集 $I$，使得

$$\sum_{i\in I}a_i=T.$$

將它轉換成題目的問題。令

$$A=3^n.$$

對每個 $i=0,1,\ldots,n-1$，在新集合中放入兩個數：

$$x_i=Aa_{i+1}+3^i,\qquad y_i=3^i.$$

設定新問題的參數為

$$k'=n,\qquad M'=AT+\sum_{i=0}^{n-1}3^i.$$

直觀上，$x_i$ 代表選入 $a_{i+1}$，$y_i$ 代表不選；以 $3^i$ 作為第 $i$ 個位置的標記，讓目標和強制每一對恰選一個數。

三、證明轉換正確

若 Subset Sum 有解 $I$，對每個 $i$：

• 若 $i+1\in I$，選 $x_i$；
• 若 $i+1\notin I$，選 $y_i$。

恰好選出 $n$ 個數，其總和為

題目條件的補充

$O(nkM)$ 這個時間界是偽多項式（pseudo-polynomial）的：表格大小與 $M$ 的數值成正比，所以必須能把「目前的和」當成陣列索引 $0,1,\dots,M$。題目說「$M$ 夠小時可以做到」，指的就是這種情況——$S$ 中的數都是非負整數（或是可以統一乘上同一個倍數化成非負整數，例如都只有固定位數的小數）。若 $S$ 含任意實數或負數，和的可能值無法用 $0\sim M$ 的索引涵蓋，這個方法就不適用。以下在此前提下設計演算法。

核心觀念

這是 0/1 背包（subset sum）的變形：除了「和是多少」，還要追蹤「用了幾個數」。用動態規劃把狀態定為（考慮到第幾個數、已選幾個、目前和），每個數只有「選」或「不選」兩種轉移。

解題方法

令 $S=\{s_1,\dots,s_n\}$，定義布林陣列

$$D[j][t]=\text{是否能從已處理過的數中選出恰好 } j \text{ 個，使總和恰為 } t,\quad 0\le j\le k,\ 0\le t\le M .$$

1. 初始化：$D[0][0]=\text{true}$，其餘為 false。
2. 依序處理每個數 $s_i$（$i=1\ldots n$）。為了讓每個數最多用一次，$j$ 由大到小、$t$ 由大到小更新：

$$D[j][t] \leftarrow D[j][t]\ \lor\ \big(t\ge s_i \ \land\ D[j-1][t-s_i]\big),\qquad j=k,\dots,1,\ \ t=M,\dots,s_i .$$

（大於 $M$ 的數不可能被選，直接略過；這一步正需要「數為非負」的前提。）
3. 全部處理完後，答案為 $D[k][M]$。