108 年 國立陽明交通大學資訊工程學系碩士班《資料結構與演算法》

核心觀念

本題考資料結構的存取規則：

• **佇列（queue）**遵循先進先出（FIFO）。front() 取得最早放入、尚未取出的元素；back() 取得最後放入的元素。
• **堆疊（stack）**遵循後進先出（LIFO）。top() 取得最後放入、尚未取出的元素。

push() 只會加入元素，不會改變既有元素的順序，也不會移除元素。

解題方法

依序列出各元素放入容器後的狀態：

佇列：13（front）→ 2 → 5 → 27（back）
堆疊：底部 2 → 32 → 17 → 63（top）

因此：

• que.front() 的值是 13。
• que.back() 的值是 27。
• stk.top() 的值是 63。

程式輸出為：

13, 27, 63

選項分析

核心觀念

雙向鏈結串列的每個節點都有兩個指標：$prev[y]$ 指向前一個節點，$next[y]$ 指向下一個節點。要刪除節點 $x$，只需讓 $x$ 的前後節點彼此相連；若 $x$ 位於串列開頭，則更新串列的首節點指標 $head[L]$。

解題方法

依序檢查 $x$ 的前後節點：

• 若 $x$ 有前一個節點，令該節點的 $next$ 指標跳過 $x$，直接指向 $x$ 的下一個節點。
• 若 $x$ 沒有前一個節點，表示 $x$ 是首節點，將 $head[L]$ 更新為 $x$ 的下一個節點。
• 若 $x$ 有下一個節點，令該節點的 $prev$ 指標跳過 $x$，直接指向 $x$ 的前一個節點。

因此，$x$ 被從鏈結串列中移除。整個操作只修改固定數量的指標，時間複雜度為 $O(1)$，額外空間複雜度為 $O(1)$。

選項分析

核心觀念

二元堆積（binary heap）是一種完全二元樹，並符合堆積序性質：

• 最大堆積：每個父節點的鍵值都大於或等於子節點。
• 最小堆積：每個父節點的鍵值都小於或等於子節點。

完全二元樹的節點由上而下、由左而右填入，因此常以陣列儲存。採用從 $1$ 開始的索引時，節點 $i$ 的左子節點索引為 $2i$，右子節點索引為 $2i+1$。

含有 $n$ 個節點的堆積高度為 $\Theta(\log n)$。堆積排序的建堆時間為 $O(n)$，接著進行 $n$ 次取出最大值與調整堆積，每次調整至多花費 $O(\log n)$，所以總時間為 $O(n\log n)$。

解題方法

逐一檢查各選項所述是否符合堆積的定義、陣列索引規則，以及排序演算法的最壞情況時間複雜度。複選題必須選出所有正確敘述。

選項分析

(A) 正確。
堆積排序的建堆時間為 $O(n)$，排序階段需處理 $n$ 個節點，每次調整堆積最多沿樹高移動，耗時 $O(\log n)$。因此總時間為：

核心觀念

C/C++ 的二維陣列以列優先（row-major）連續儲存。宣告 int x[R][C] 時，每個 int 佔 $4$ bytes：

解題方法

題目給的前兩個輸出 0x7ffd9e21bc00、0x7ffd9e21bc04 相差 $4$，印證每個元素 $4$ bytes。

陣列為 int x[5][5]，每列 $C=5$ 個元素，x[3][2] 前面共有

個元素，位移 $17\times4=68=\texttt{0x44}$ bytes：

選項分析

核心觀念

最大堆積（Max Heap）具有兩個性質：

• 結構上是完全二元樹，陣列依照「由上而下、同層由左到右」的順序儲存。
• 每個父節點的值都不小於其子節點。

刪除根節點時，先將最後一個節點移到根節點，再向下調整：每次與較大的子節點比較，若父節點較小就交換，直到符合最大堆積性質。

解題方法

圖中的堆積由上而下依序為：根節點 $14$；第二層 $10,9$；第三層 $8,5,7,6$；第四層 $3,2,4$。其中 $3,2$ 是 $8$ 的子節點，$4$ 是 $5$ 的左子節點，因此原始陣列為：

1. 刪除根節點 $14$，將最後的 $4$ 移到根節點。

   移除陣列最後一格後，得到：

   $$[4,10,9,8,5,7,6,3,2]$$

2. 將 $4$ 與兩個子節點 $10,9$ 中較大的 $10$ 交換。

   因為 $4<10$，交換後為：

   $$[10,4,9,8,5,7,6,3,2]$$

3. 將 $4$ 與目前的子節點 $8,5$ 中較大的 $8$ 交換。

   因為 $4<8$，交換後為：

   $$[10,8,9,4,5,7,6,3,2]$$

核心觀念

最小成本生成樹（MST）要連通圖中的所有頂點，且不能形成環。若圖有 $n$ 個頂點，生成樹恰有 $n-1$ 條邊。Kruskal 演算法將邊依權重由小到大檢查，只加入不會形成環的邊。

解題方法

圖中有 $A,B,C,D,E,F,G$ 七個頂點，邊與權重為：$AB=1$、$AG=2$、$GE=3$、$ED=4$、$GC=5$、$CD=6$、$BC=7$、$AF=8$、$FE=9$。

依 Kruskal 演算法由小到大選邊：

• 加入 $AB$、$AG$、$GE$、$ED$，目前沒有形成環。
• 加入 $GC$，將頂點 $C$ 接入。
• $CD=6$ 會形成環，因為 $C$ 與 $D$ 已經透過 $C-G-E-D$ 相連，因此略過。

核心觀念

Kruskal 演算法將邊依權重由小到大考慮；若加入某條邊不會形成環，就將它加入最小生成樹。含有 $n$ 個頂點的生成樹共有 $n-1$ 條邊，因此本圖 7 個頂點要選出 6 條邊。

解題方法

圖中的頂點為 $A,B,C,D,E,F,G$，邊與權重為：$AB=1$、$AG=2$、$GE=3$、$ED=4$、$GC=5$、$CD=6$、$BC=7$、$AF=8$、$FE=9$。

依權重由小到大檢查：

• 加入 $AB(1)$、$AG(2)$、$GE(3)$、$ED(4)$、$GC(5)$，這些邊都不形成環。
• $CD(6)$ 會連接已經相通的 $C$ 與 $D$，形成環，跳過。
• $BC(7)$ 也會形成環，跳過。

核心觀念

Prim 演算法從指定起點開始，每一步都在「已納入樹的頂點」與「尚未納入的頂點」之間，選擇權重最小的邊加入。重複此步驟，直到所有頂點都納入最小生成樹；若圖有 $n$ 個頂點，生成樹會有 $n-1$ 條邊。

解題方法

圖中有 $A,B,C,D,E,F,G$ 七個頂點，邊的權重為：$AB=1$、$AG=2$、$GE=3$、$ED=4$、$GC=5$、$CD=6$、$BC=7$、$AF=8$、$FE=9$。從 $F$ 開始，逐步選取連接樹內與樹外頂點的最小權重邊：

1. 樹內只有 $F$：比較 $FA=8$、$FE=9$，選 $FA$。
2. 樹內為 $\{F,A\}$：可選邊中最小的是 $AB=1$。
3. 樹內為 $\{F,A,B\}$：可選邊中最小的是 $AG=2$。
4. 樹內為 $\{F,A,B,G\}$：可選邊中最小的是 $GE=3$。
5. 樹內為 $\{F,A,B,G,E\}$：可選邊中最小的是 $ED=4$。

核心觀念

AVL 樹是符合二元搜尋樹次序的自我平衡二元樹。每個節點的平衡因子定義為：

每次插入後，若某節點的平衡因子變成 $+2$ 或 $-2$，就要依失衡方向進行旋轉，使各節點的平衡因子回到 $-1、0、+1$。

解題方法

依序插入題目中的數字。插入 $5$ 時，節點 $20$ 發生左左失衡，右旋後，相關子樹為：

    10
   /  \
  5   20

接著插入 $25$，節點 $30$ 發生左右失衡，先對其左子節點左旋，再對節點 $30$ 右旋。插入 $45$ 後，節點 $30$ 發生右右失衡，對節點 $30$ 左旋。此時根節點 $50$ 發生左右失衡，再先左旋其左子節點，後對 $50$ 右旋。

最後的 AVL 樹為：

核心觀念

AVL 樹是符合二元搜尋樹順序，且每個節點左右子樹高度差最多為 $1$ 的二元搜尋樹。定義平衡因子為：

插入新值時，先依二元搜尋樹規則找到位置，再由插入處向上檢查平衡因子。若某節點的平衡因子變成 $2$ 或 $-2$，便依失衡方向進行旋轉。

解題方法

依序插入題目中的數字。下表列出每次插入後造成的旋轉，以及旋轉後的根節點：

關鍵在最後一次插入。插入 $45$ 後，從根節點 $50$ 往下的搜尋路徑是：

核心觀念

AVL 樹要求每個節點左右子樹高度差至多為 $1$。插入後沿路徑往上找第一個失衡節點，依新節點落在它的哪一側決定修復類型：

• LL：左子的左側 → 右旋一次。
• RR：右子的右側 → 左旋一次。
• LR：左子的右側 → 先左旋左子、再右旋失衡點（一次雙旋修復）。
• RL：右子的左側 → 先右旋右子、再左旋失衡點。

解題方法

逐一插入並記錄每次修復：

關鍵兩步：

核心觀念

採用常見的 B-tree 階數定義：order 3 表示每個節點最多有 3 個子節點，因此最多存 2 個鍵值。插入後若節點出現 3 個鍵值，就將中間鍵值提升至父節點，左右鍵值分別留在分裂後的兩個節點。

解題方法

依序插入，並在節點超出容量時分裂：

1. 插入 $20,30,40$ 後，根節點成為 $[20,30,40]$，分裂並提升中間值 $30$，形成根節點 $[30]$，左右子節點為 $[20]$、$[40]$。
2. 插入 $50,60,70$ 後，最右側葉節點分裂並提升 $50$。此時根節點為 $[30,50]$，葉節點依序為 $[20]$、$[40]$、$[60,70]$。
3. 插入 $10,5$ 後，最左側葉節點成為 $[5,10,20]$，分裂並提升 $10$。原根節點因此成為 $[10,30,50]$，也超出容量；再將中間值 $30$ 提升，形成新根節點 $[30]$。
4. 插入 $25$ 至鍵值範圍 $10$ 與 $30$ 之間的葉節點；插入 $45$ 至鍵值範圍 $30$ 與 $50$ 之間的葉節點。

最後的 B-tree 為：

核心觀念

B-tree 的「階數」為 3，表示每個節點最多有 3 個子節點，因此最多存放 2 個鍵值。節點插入新鍵值後若超過 2 個，便將鍵值排序，取中間鍵值升到父節點，左右兩側的鍵值分別形成兩個節點。若根節點也溢位，則建立新根節點。

解題方法

依序插入題目中的數字，追蹤根節點及會發生溢位的節點：

1. 插入 $20,30$，根節點為 $[20,30]$。
2. 插入 $40$ 後，根節點溢位。將中間鍵值 $30$ 升為根，得到根節點 $[30]$，左右子節點為 $[20]$、$[40]$。
3. 插入 $50,60$ 後，右側節點 $[40,50,60]$ 溢位，將 $50$ 升至根，得到根節點 $[30,50]$，子節點依序為 $[20]$、$[40]$、$[60]$。
4. 插入 $70$，右側子節點成為 $[60,70]$。再插入 $10,5$，左側節點形成 $[5,10,20]$，溢位後將 $10$ 升至根。此時根節點也溢位，鍵值為 $[10,30,50]$；將中間鍵值 $30$ 升為新根。
5. 新根為 $[30]$。

核心觀念

依常見定義，B-tree 的「order 3」表示每個節點最多有 $3$ 個子節點，因此最多可存 $2$ 個鍵值。插入後若節點含有 $3$ 個鍵值，就必須分裂：將中間鍵值提升至父節點，左右兩側鍵值分別留在新節點中。

若父節點因接收提升的鍵值而超出容量，也要再分裂；每分裂一個節點，就計為一次 node split operation。

解題方法

依序插入題目給的數字，記錄節點何時累積到 $3$ 個鍵值而分裂：

1. 插入 $20,30$ 後，根節點為 $[20,30]$。

2. 插入 $40$ 後，根節點成為 $[20,30,40]$，分裂並提升中間鍵值 $30$。分裂次數：$1$。

   樹為根節點 $[30]$，左右子節點分別為 $[20]$、$[40]$。

3. 插入 $50,60$ 時，右側葉節點由 $[40]$ 增至 $[40,50,60]$，因此分裂並提升 $50$ 至根節點。分裂次數：$2$。

   根節點變為 $[30,50]$，葉節點為 $[20]$、$[40]$、$[60]$。

4. 插入 $70$，右側葉節點成為 $[60,70]$，未超出容量。插入 $10$，左側葉節點成為 $[10,20]$，也未超出容量。

核心觀念

這段程式使用 Dijkstra 單源最短路徑演算法，從頂點 START = 4 出發，計算起點到各頂點的目前最短距離，並將結果存入陣列 d。

• d[v]：目前已知從起點到頂點 $v$ 的最短距離。
• s[v]：頂點 $v$ 是否已確定最短距離。
• 1000：代表沒有直接邊，可視為很大的距離。
• 鬆弛：若經由頂點 $u$ 到達 $w$ 比目前距離更短，就更新 $d[w]$：

程式將起點的距離設為 $0$，因此 $d[4] = 0$。

解題方法

起點為頂點 $4$。初始化時，程式從矩陣第 $4$ 列讀入各頂點的直接距離，並將起點標記為已確定：

每次迴圈從尚未確定的頂點中，選出 d 最小者，再依該頂點的出邊進行鬆弛。依序執行如下：

迴圈結束時：

核心觀念

這段程式使用 Dijkstra 最短路徑演算法，從起點 START = 4 計算到各頂點的最短距離。

s[j] 表示頂點 $j$ 是否已確定最短距離；d[j] 表示目前從起點到頂點 $j$ 的最短距離估計。每輪選出尚未確定、且 d 值最小的頂點 $u$，再用

更新其他頂點。矩陣中的 1000 代表沒有直接連線。

解題方法

起點是頂點 $4$。初始化後：

接著依照每輪選出的最小距離頂點進行鬆弛：

核心觀念

這段程式使用鄰接矩陣表示加權圖，並以類似 Dijkstra 演算法的方式反覆選出目前距離最小、尚未處理的頂點，再更新其他頂點的暫定距離。

時間複雜度要看程式實際執行的迴圈次數，以及每次迴圈內的工作量；不必先判斷演算法是否完整求出所有最短路徑。

解題方法

初始化時，第一個 for 迴圈執行 $N$ 次，每次設定一個 s[i] 與 d[i]，耗時為 $O(N)$。

主要迴圈執行 $N-2$ 次，因此迴圈次數為 $O(N)$。每次迴圈包含：

• 透過 j 迴圈掃描全部 $N$ 個頂點，找出距離最小的未處理頂點，耗時 $O(N)$。
• 透過 w 迴圈掃描全部 $N$ 個頂點，嘗試更新距離，耗時 $O(N)$。

所以每次主要迴圈耗時為 $O(N)+O(N)=O(N)$，總耗時為：

核心觀念

這題考的是隨機快速排序的平均時間，以及「重複分割直到切分夠平衡」對遞迴深度的影響。

令目前子陣列長度為 $m$。一次呼叫 $P(A,p,r)$ 會掃描整個子陣列，因此耗時為 $\Theta(m)$。若每次分割都能讓較大的子問題至多為原問題的 $2/3$，遞迴就會維持平衡，深度為 $\Theta(\log n)$。

解題方法

先看一次分割成功的機率。假設元素互異，隨機選取的樞紐元素，其排序名次均勻分布。若樞紐左側有 $k$ 個元素，左右子問題大小分別為 $k$ 與 $m-1-k$。符合接受條件的樞紐名次，約落在中間三分之一，因此一次分割成功的機率是常數；當 $m$ 增大時，此機率約為 $1/3$。

所以重複分割直到成功所需的嘗試次數，期望為常數。每次嘗試耗時 $\Theta(m)$，故該節點的期望分割成本仍為 $\Theta(m)$。

成功後，較大的子問題至多為原問題的 $2/3$；另一個子問題也不能太小，因為兩邊大小總和為 $m-1$。因此遞迴深度為 $\Theta(\log n)$。每一層處理的子陣列長度總和為 $\Theta(n)$，總時間為

核心觀念

每次呼叫 $P(A,p,r)$ 時，樞紐元素從目前子陣列中均勻隨機選出。分割後，演算法 $Q$ 會檢查較大的那一側是否不超過子陣列的 $2/3$；若符合，重複迴圈就停止。

解題方法

將樞紐在子陣列中的相對位置視為 $0$ 到 $1$ 之間的均勻隨機比例 $x$。分割後兩側的比例約為 $x$ 與 $1-x$。要讓較大的一側不超過 $2/3$，須同時滿足：

因此：

符合條件的位置占整個區間的比例為：

核心觀念

這題考的是幾何分布的期望值。Q 每次執行 P 都隨機選一個樞紐，直到分割結果符合條件才停止；若每次成功機率為 $p$，所需執行次數的期望值為：

解題方法

設目前子陣列長度為 $n$。要讓較大的分割部分至多占子陣列的 $2/3$，樞紐必須落在中間的 $1/3$ 區段：左、右兩部分都不能超過 $2n/3$。

在標準分析中，假設元素互異、樞紐的排名等機率出現，能符合條件的樞紐約占全部樞紐的 $1/3$，因此每次 P 成功的機率為：

代入幾何分布的期望值：

此期望值包含最後一次成功的執行。

核心觀念

每一對括號是一次「把相鄰兩段合併」的加法，產生的中間和＝這兩段涵蓋的所有數字總和。數字順序不能改變，所以這是區間動態規劃（與矩陣鏈乘、石子合併同型）。

令 $S(i,j)$ 為第 $i$ 到第 $j$ 個數的總和，$dp[i][j]$ 為把這段加成一個數的最小中間和總和：

解題方法

輸入 $4,4,8,5,4,3,5$，總和 $33$。依區間長度由短到長填表（每列由左而右是起點 $1,2,\ldots$ 的區間）：

核心觀念

每一對括號是一次「把相鄰兩段合併」的加法，產生的中間和＝這兩段涵蓋的所有數字總和。數字順序不能改變，所以這是區間動態規劃（與矩陣鏈乘、石子合併同型）。

令 $S(i,j)$ 為第 $i$ 到第 $j$ 個數的總和，$dp[i][j]$ 為把這段加成一個數的最小中間和總和：

解題方法

輸入 $4,4,8,5,4,3,5$，總和 $33$。依區間長度由短到長填表（每列由左而右是起點 $1,2,\ldots$ 的區間）：

核心觀念

每一對括號是一次「把相鄰兩段合併」的加法，產生的中間和＝這兩段涵蓋的所有數字總和。數字順序不能改變，所以這是區間動態規劃（與矩陣鏈乘、石子合併同型）。

令 $S(i,j)$ 為第 $i$ 到第 $j$ 個數的總和，$dp[i][j]$ 為把這段加成一個數的最小中間和總和：

解題方法

輸入 $4,4,8,5,4,3,5$，總和 $33$。依區間長度由短到長填表（每列由左而右是起點 $1,2,\ldots$ 的區間）：

例：$dp[1][3]=16+\min(0+12,\ 8+0)=24$；$dp[4][7]=17+\min(0+19,\ 9+8,\ 19+0)=34$。

整段 $[1,7]$ 依最後一次合併的切點 $k$：

核心觀念

這是 容量縮放（capacity scaling） 版的 Ford–Fulkerson（CLRS 習題 26-5 的情境）：門檻 $K$ 從不超過 $C$ 的最大 2 的冪次開始，每個階段只找殘餘容量 $\ge K$ 的增廣路徑，找不到就把 $K$ 減半。三個基本事實：

1. 最大流值＝最小割容量（最大流最小割定理），這個數值唯一。
2. 任一割最多切到 $|E|$ 條邊、每條容量 $\le C$，所以割容量 $\le C|E|$。
3. 在殘餘網路中只保留容量 $\ge K$ 的邊做 BFS/DFS，就能在 $O(V+E)=O(E)$ 時間找到（或確定沒有）容量至少 $K$ 的增廣路徑（$G$ 連通，所以 $E\ge V-1$）。

選項分析

• (A) 正確。 最小割的「容量」是一個最小值，必然唯一；可能不唯一的是達到這個值的割本身。
• **(B) 錯誤。

核心觀念

容量縮放（capacity scaling）的 Ford–Fulkerson：門檻 $K$ 從 $2^{\lfloor\lg C\rfloor}$ 開始，每個階段只沿殘餘容量 $\ge K$ 的增廣路徑推流，找不到就把 $K$ 減半，直到 $K<1$。

解題方法

把總時間拆成三個因子相乘：

1. 階段數：$K$ 從約 $C$ 減半到 $1$，共 $\lfloor\lg C\rfloor+1=O(\lg C)$ 個階段。
2. 每階段的增廣次數：上一階段（門檻 $2K$）結束時，殘餘網路中從 $s$ 經容量 $\ge2K$ 的邊可達的點集 $S$ 形成一個割，割上每條邊的殘餘容量都 $<2K$，所以剩下還能增加的流量 $<2K|E|$。本階段每次增廣至少增加 $K$，因此最多 $2|E|=O(E)$ 次。
3. 每次增廣的成本：在只保留容量 $\ge K$ 的殘餘邊上做 BFS/DFS，$O(V+E)=O(E)$（網路連通，$E\ge V-1$）。

核心觀念

這題考最大流與最小割定理、割的唯一性，以及整數容量對最大流的影響。

• 割：將頂點分成包含來源 $s$ 的集合 $S$ 與包含匯點 $t$ 的集合 $T=V\setminus S$。割的容量是所有由 $S$ 指向 $T$ 的邊容量總和：
  $c(S,T)=\sum_{u\in S,\ v\in T} c(u,v).$
• 殘餘網路：正向邊的殘餘容量為 $c(u,v)-f(u,v)$；反向邊的殘餘容量反映可撤回的流量。
• 最大流最小割定理：當殘餘網路中不存在從 $s$ 到 $t$ 的增廣路徑時，最大流值等於某個最小割容量。由殘餘網路中從 $s$ 可到達的頂點可構造出這個最小割。
• 整數容量定理：若每條邊的容量都是整數，則存在一個整數最大流；但這不代表每個最大流都必須是整數。

解題方法

逐項檢查敘述是否能由定理直接推出。涉及「唯一」的敘述，須區分「各邊容量不同」與「不同邊集合的容量總和不同」；涉及「可能」的敘述，則只要有一個符合條件的例子即可判定。

選項分析

(A) 錯誤。 各邊容量互不相同，不代表不同割的容量總和互不相同。割容量是多條邊容量的總和，而不同整數可以有相同的總和，例如 $1+4=2+3$。因此，容量互異無法保證最小割唯一。