110 年 國立臺灣大學資訊工程學系碩士班《資料結構與演算法》

核心觀念

快速排序每一層要做一次 $\Theta(n)$ 的分割。若每次選到的樞紐（pivot）都是目前子陣列的最小值或最大值，分割會極度不平衡（一邊 0 個、一邊 $n-1$ 個），遞迴式變成

這就是快速排序的最壞情況。

解題方法

題目問「最壞情況會在什麼情況下發生」，要找的是輸入資料與樞紐選法的具體組合：

• $C_2$： 已排好的遞增陣列、選最左元素當樞紐。每次樞紐都是最小值，分割成 0 與 $n-1$，必定是最壞情況。
• $C_3$： 已排好的遞減陣列、選最左元素當樞紐。每次樞紐都是最大值，同樣必定是最壞情況。
• $C_1$： 只描述「總是選最左（或最右）元素當樞紐」這個策略，沒有說明輸入資料。這個策略本身並不會造成最壞情況——對大多數輸入，它的表現是平均的 $\Theta(n\log n)$；

核心觀念

每個格子視為一個節點，只能向右或向下移動；相鄰格子的數值差必須為 $1$。這形成一個有向無環圖，因為移動只會往右或往下，不會回到先前的格子。

令 $dp[i][j]$ 表示「從第 $i$ 列、第 $j$ 欄出發，最多能走過幾個格子」。若右方或下方格子的數值與目前格子相差 $1$，就能延伸路徑：

其中只取符合移動方向且數值差為 $1$ 的相鄰格子；若沒有符合條件的格子，則 $dp[i][j]=1$。題目所問的移動次數，等於路徑格數減 $1$。

解題方法

由右下角往左上角計算各格的 $dp$ 值。因為每格只依賴右方與下方的結果，這個順序能確保計算時所需的值已經求出。

例如，第二列第四欄的數值為 $5$，下方是 $6$，相差 $1$；從該格可經過 $5\to6\to7$，共 $3$ 個格子，因此 $dp[2][4]=3$。接著，第二列第三欄的 $6$ 可向右接到 $5$，所以 $dp[2][3]=1+dp[2][4]=4$。

核心觀念

這題考查動態規劃的時間複雜度。蛇形序列只能向右或向下移動，因此每個格子只需根據左方與上方相鄰格子的結果，計算到達該格子的最長序列長度。

解題方法

令 $dp[i][j]$ 表示以第 $i$ 列、第 $j$ 欄為終點的最長蛇形序列「移動次數」。計算每個格子時，只需檢查上方與左方是否相鄰且數值相差 $1$：

核心觀念

蛇形序列只能向右或向下移動，且相鄰兩格的數值差必須為 $1$；序列長度計算的是移動次數。座標寫成 $(x,y)$：$x$ 是欄（向右增加）、$y$ 是列（向下增加）。

令 $dp[y][x]$ 表示「以 $(x,y)$ 為終點的蛇形序列，最多移動幾次」。只能從左邊或上方走過來：

解題方法

由左上往右下逐格計算：

核心觀念

這題考動態規劃。每一步只能向右或向下移動，且相鄰數字的差必須為 $1$。令 $D[y][x]$ 表示「以座標 $(x,y)$ 為終點的最長蛇序列有幾次移動」；座標中的 $x$ 是欄、$y$ 是列。

若左邊或上方的格子與目前數字相差 $1$，就能接在序列後面：

只取符合相鄰差為 $1$ 的前驅；若沒有符合條件的前驅，則令 $D[y][x]=0$。

解題方法

依序計算每格的最長序列移動次數，得到：

右下角的 $7$ 對應 $D[3][3]=6$，所以最長序列有 $6$ 次移動、共 $7$ 個數字。回溯其前驅，可得：

核心觀念

本題考的是「分治法」（divide and conquer）的定義：把原問題拆成數個規模較小、性質相同的子問題，遞迴求解子問題，再合併結果以得到原問題的解。

分治法常見的三個步驟是：

1. 分解：將問題拆成較小的子問題。
2. 征服：遞迴求解各子問題；子問題夠小時直接處理。
3. 合併：將子問題的解組合成原問題的解。

解題方法

題幹指出，對序列問題反覆拆成數個較小的同類問題，並以遞迴方式求解。這正符合分治法的「分解」與「征服」特徵，因此選擇 (B) Divide and conquer。

選項分析

• (A) Dynamic programming（動態規劃）：動態規劃也會處理子問題，但重點是利用子問題的重疊性，儲存並重用已算出的結果，以避免重複計算。

核心觀念

堆疊（Stack）遵循「後進先出」（LIFO, Last In, First Out）：最後放入的元素會最先取出。放入元素稱為 push，取出最上方元素稱為 pop。

解題方法

函式 $f(x)$ 先令 $p$ 加 $1$，再將 $x$ 存入 $A[p]$，也就是把元素放到目前堆疊頂端。函式 $g()$ 讀取 $A[p]$，再令 $p$ 減 $1$，因此取出的是最後放入的元素，且堆疊頂端往下移一格。

例如，依序呼叫 $f(a)$、$f(b)$，接著呼叫 $g()$，會先取出 $b$，符合後進先出的規則。

選項分析

核心觀念

佇列（Queue）遵守「先進先出」（FIFO）：先放入的元素會先被取出。常見實作方式是用兩個索引分別記錄佇列的前端與尾端：

• $p$ 指向下一個要取出的元素。
• $q$ 指向下一個要放入元素的位置。

解題方法

初始時 $p=q=0$。執行 $f(x)$ 時，先把 $x$ 放到 $A[q]$，再將 $q$ 加一；執行 $g()$ 時，先取出 $A[p]$，再將 $p$ 加一。因此，元素依照放入順序依序取出。

例如依序執行 $f(a)$、$f(b)$，陣列會依序存入 $A[0]=a$、$A[1]=b$，且 $q=2$。接著呼叫兩次 $g()$，會依序讀取 $A[0]$ 和 $A[1]$，先取出 $a$，再取出 $b$，符合 FIFO。

核心觀念

二元樹的後序走訪（postorder）順序是「左子樹、右子樹、根節點」。以陣列表示時，索引為 $i$ 的節點，其左、右子節點分別位於 $2i+1$ 與 $2i+2$；null 表示該位置沒有節點，不列入走訪結果。

解題方法

依索引關係還原樹：

• 索引 $0$ 的根節點是 $+$，左子節點為索引 $1$ 的 $a$，右子節點為索引 $2$ 的 $*$。
• $a$ 的兩個子節點位於索引 $3$、$4$，皆為 null。
• $*$ 的左子節點是索引 $5$ 的 $-$，右子節點是索引 $6$ 的 $d$。
• $-$ 的左、右子節點分別是索引 $11$ 的 $b$ 與索引 $12$ 的 $c$。

依後序順序走訪：

1. 左子樹只有 $a$，先輸出 $a$。
2. 右子樹以 $*$ 為根：先走訪 $-$，依序輸出其左子節點 $b$、右子節點 $c$，最後輸出 $-$，得到 bc-；再輸出 $d$，最後輸出 $*$，得到 bc-d*。

核心觀念

BFS（廣度優先搜尋）依序拜訪二元樹的節點：先拜訪根節點，再由上而下、每層由左至右拜訪。陣列表示中，索引 $i$ 的節點，其左、右子節點分別位於 $2i+1$ 與 $2i+2$；值為 null 的位置代表沒有節點，不列入遍歷結果。

解題方法

依陣列索引由小到大檢視非 null 節點，逐層列出：

例如，$T[2]=*$ 的子節點位置是 $T[5]$ 與 $T[6]$；$T[5]=-$ 的子節點位置是 $T[11]$ 與 $T[12]$。其餘相關位置為 null，不輸出。

依照每層由左至右的順序串接，BFS 結果為：

核心觀念

雜湊函數 $h(k)=k\bmod 9$ 會先把資料視為十六進位數，轉成十進位後取除以 $9$ 的餘數。餘數就是該資料的初始雜湊位置。若新資料的初始位置已被先前資料占用，就發生碰撞。

解題方法

依插入順序計算各資料的雜湊位置：

核心觀念

線性探測（linear probing）遇到碰撞時，依序檢查下一個位置；到陣列尾端後回到位置 $0$。本題雜湊值為 $h(k)=k\bmod 9$，但陣列有 $10$ 個位置，索引為 $0$ 至 $9$；線性探測時則依陣列長度 $10$ 循環。

解題方法

將各筆資料依序插入。十六進位數先換算成十進位，再計算其對 $9$ 的餘數：

核心觀念

本題考查單向鏈結串列在只有頭指標、以及同時持有頭尾指標時，從尾端插入與刪除的時間複雜度。

以下依一般題意，假設串列為單向鏈結串列。即使有尾指標，每個節點仍只連向下一個節點；尾指標無法直接找到尾節點的前一個節點。

解題方法

只有頭指標時，若要在尾端插入，必須從頭節點沿著串列走到最後一個節點，花費 $\Theta(n)$。刪除最後一個節點也要找到倒數第二個節點，花費同樣是 $\Theta(n)$。因此，兩者的成本比值為 $1$。

同時有頭指標與尾指標時，插入尾端可以直接使用尾指標，花費 $\Theta(1)$；刪除尾端仍須從頭開始尋找倒數第二個節點，花費 $\Theta(n)$。因此：

題目選項以大 $n$ 下的成本比例表示，故此比值不會是 $n$。

核心觀念

Kruskal 演算法依邊的權重由小到大檢查；只有在加入該邊不會形成環時，才將它納入最小生成樹。題目問的是「第六條被納入的邊」，因此被檢查但因成環而略過的邊不計入納入順序。

解題方法

圖中較小的邊依序為：$FB=1$、$HC=2$、$BC=3$、$IH=4$、$IF=5$、$AB=6$、$AE=7$、$EC=8$、$DE=9$。

依 Kruskal 演算法逐一檢查：

核心觀念

Prim 演算法從指定起點開始，逐步加入一個尚未納入的頂點；每一步都選擇一條連接「已納入頂點」與「未納入頂點」且權重最小的邊。題目問的是加入頂點的順序，起點 $A$ 算第 1 個。

解題方法

圖中與前幾步選擇相關的邊為：$A$ 到 $B、E、D、C$ 的權重分別是 $6、7、12、13$；$B$ 到 $F、C$ 的權重是 $1、3$；$F$ 到 $I$ 的權重是 $5$；$C$ 到 $H$ 的權重是 $2$；$H$ 到 $I$ 的權重是 $4$。

從 $A$ 開始，逐步比較連接已納入頂點與未納入頂點的邊：

1. 第 1 個：起點 $A$。
2. 第 2 個：從 $A$ 出發，最小邊是 $A\!-\!B$，權重 $6$，加入 $B$。
3. 第 3 個：目前候選邊中，$B\!-\!F$ 的權重 $1$ 最小，加入 $F$。
4. 第 4 個：目前最小候選邊是 $B\!-\!C$，權重 $3$，加入 $C$。

核心觀念

本題考有向網路的最大流。每條邊的流量不得超過容量，且除源點 $s$、匯點 $t$ 外，每個節點都須滿足流入量等於流出量。依最大流最小割定理，最大流值等於最小割的容量。

解題方法

圖中的邊與容量為：$s\to A$（10）、$s\to C$（10）、$A\to C$（2）、$A\to B$（4）、$A\to D$（8）、$C\to D$（9）、$D\to B$（6）、$D\to t$（10）、$B\to t$（10）。

先考慮割集左側 $\{s,C\}$，右側為其餘節點。從左側流向右側的邊只有 $s\to A$ 和 $C\to D$，因此割容量為

所以最大流不可能超過 19。

接著列出一組總流量為 19 的可行流：

核心觀念

KMP 的前綴函數 $\pi[i]$ 表示子字串 $P[1..i]$ 的「最長真前綴」，同時也是它的「後綴」的長度。真前綴不能等於整個子字串，因此 $\pi[i]\le i-1$。

解題方法

題目要計算 $\pi[7]$，先取出前 7 個字元：

依序檢查長度為 6 到 1 的真前綴與後綴，找出相同的最大長度：

讀表（依原卷）

核心觀念

字串比對自動機中，狀態 $q$ 表示「已經比對成功 $s$ 的前 $q$ 個字元」。轉移函數

兩個重要推論：

1. 前進的轉移：$\delta(q,a)=q+1$ 代表 $a=s[q+1]$。
2. 退回的轉移：$\delta(q,a)=k\le q$ 代表 $s[1..k]$ 是 $s[1..q]a$ 的後綴，可以推出字元之間的相等關係。

解題方法

設 $s=s_1s_2\cdots s_{10}$。

1. 前進的轉移直接給出字元：
   • $\delta(3,A)=4\Rightarrow s_4=A$
   • $\delta(4,A)=5\Rightarrow s_5=A$
   • $\delta(6,B)=7\Rightarrow s_7=B$
   • $\delta(9,C)=10\Rightarrow s_{10}=C$
2. $\delta(6,A)=2$：$s_1s_2$ 是 $s_1\cdots s_6A$ 的後綴，所以 $s_2=A$、$s_1=s_6$。

核心觀念

線性時間歸約 $A \leq_L B$ 表示可以在 $O(n)$ 時間內，將 $A$ 的任一輸入轉換成 $B$ 的輸入，且轉換前後的答案一致。因為轉換花費線性時間，轉換後輸入的長度至多為原輸入長度的線性倍數。

題目給定 PROBLEMA 是 NP-complete，且 PROBLEMA 線性時間歸約至 PROBLEMB。若 PROBLEMB 有多項式時間演算法，就能透過歸約得到 PROBLEMA 的多項式時間演算法；而 NP-complete 問題若能在多項式時間內求解，便有 $P=NP$。

解題方法

假設 PROBLEMB 有 $O(N^3)$ 演算法。對長度為 $n$ 的 PROBLEMA 輸入，先花 $O(n)$ 時間歸約成 PROBLEMB 輸入。新輸入長度至多為 $O(n)$，因此求解 PROBLEMB 花費：

加上歸約時間後，整體仍是 $O(n^3)$。所以 PROBLEMA 也有 $O(N^3)$ 演算法。由於 PROBLEMA 是 NP-complete，這代表 $P=NP$。

因此 $C_1$ 與 $C_3$ 成立，正確選項為 (A)。

選項分析

核心觀念

這題考的是以子集合和表示頂點覆蓋的多項式時間歸約。每個頂點對應一個數 $x_i$，其最高位記錄是否選入頂點覆蓋，其餘位記錄該頂點連接哪些邊；每條邊另有一個數 $y_i$，可補足該邊的位數。

解題方法

原卷圖中，頂點列為 $v_0,\ldots,v_4$，邊 $e_0,\ldots,e_4$；題目指定的頂點覆蓋是 $\{v_1,v_3,v_4\}$。表格在 $e_4,\ldots,e_0$ 之前另有一個頂點選取位，各頂點列該位皆為 $1$。因此選取 $x_1,x_3,x_4$ 後，最高位總和為 $3$，符合 $k=3$。

從表中讀出這三個頂點數：

先相加：

依圖中邊位 $e_4,\ldots,e_0$ 的順序，三列相加後各位分別為 $1,1,1,2,1$。每條邊的目標位數設為 $2$：已有兩個端點被選到的邊，其位數已達 $2$；只被一個端點覆蓋的邊，則用對應的 $y_i$ 補足。