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

核心觀念

本題考漸近記號的定義，以及用變數代換或 Master 定理判斷遞迴式的漸近解：

• $f(n)=O(g(n))$：$f(n)$ 最終不超過 $g(n)$ 的常數倍。
• $f(n)=\Omega(g(n))$：$f(n)$ 最終至少為 $g(n)$ 的常數倍。
• $f(n)=\Theta(g(n))$：同時為 $O(g(n))$ 與 $\Omega(g(n))$。
• $f(n)=o(g(n))$：對任何常數 $c>0$，$f(n)$ 最終都小於 $c g(n)$，也就是相對成長率趨近於 $0$。

遞迴式則先將子問題規模化成標準形式，再比較遞迴樹各層成本或套用 Master 定理。

解題方法與選項分析

(A) 正確。

$\Theta$ 的定義正是同時滿足 $O$ 與 $\Omega$：

$$f(n)=\Theta(g(n)) \iff f(n)=O(g(n))\text{ 且 }f(n)=\Omega(g(n)).$$

(B) 依本題採用的成長率判讀為正確。

當 $f(n)=O(g(n))$，且 $f(n)$ 不具備 $\Omega(g(n))$ 的下界時，在本題預期的成長率判讀下，$f(n)$ 相對於 $g(n)$ 的比例趨近於 $0$，因此 $f(n)=o(g(n))$。

嚴格而言，若 $f,g$ 是任意函數，$O(g)$ 且不是 $\Omega(g)$ 不必然推出 $o(g)$：若 $f(n)/g(n)$ 在 $0$ 與正數間振盪，仍可能不趨近於 $0$。本題公布並維持的答案將此敘述視為一般成長率比較下的等價關係。

(C) 正確。

令 $m=\log n$，並定義 $S(m)=T(2^m)$。因為 $\sqrt{n}=2^{m/2}$，原式可改寫為：

$$S(m)=2S(m/2)+\Theta(m).$$

核心觀念

Monge 陣列的定義是：任取上、下兩列 $i<k$，以及左、右兩欄 $j<\ell$，都要滿足

$$A[i,j]+A[k,\ell]\le A[i,\ell]+A[k,j].$$

若固定兩欄 $j<\ell$，把每一列在這兩欄的差記為 $A[r,j]-A[r,\ell]$，則 Monge 條件等價於：這個差值隨列號增加而不減。特別地，只檢查相鄰列的條件，就足以推出任意兩列的條件。

解題方法

逐一檢查選項所述條件是否足以推出 Monge 定義。對 $M_2$，可直接比較相鄰兩列的差值，找出違反條件的位置；也可利用差值是否不減，快速驗證修改後的陣列。

選項分析

**(A) 錯誤。**只檢查相隔兩列的列對，不足以保證相鄰列也符合條件。以 $M_2$ 為例，檢查列 $1,3$、$2,4$、$3,5$ 時，各欄的列差依序為：

$$\begin{aligned} M_2[1,*]-M_2[3,*]&=(-16,-11,-8,1),\\ M_2[2,*]-M_2[4,*]&=(-11,-7,-2,4),\\ M_2[3,*]-M_2[5,*]&=(10,13,15,23). \end{aligned}$$

這三組數列皆不減，因此所有相隔兩列的檢查都通過。然而，列 $1,2$ 在欄 $2,3$ 的條件不成立：

$$23+7>22+6.$$

所以只檢查列 $i,i+2$ 並不足夠。

**(B) 錯誤。**把 $M_2$ 的 $7$ 改成 $13$，檢查列 $1,2$、欄 $2,3$：

$$23+13\le 22+6$$

不成立，因此修改後仍不是 Monge 陣列。

**(C) 錯誤。**只改一個元素就能使 $M_2$ 成為 Monge 陣列：把列 $2$、欄 $3$ 的 $7$ 改成 $5$。修改後，各相鄰列的列差為：

核心觀念

這個程序用「兩個指標向外擴張」構造排列：先數出字串中 0 的個數 $k$，令第一個數為 $k$；之後遇到 1 就放目前最大值加 1（++right），遇到 0 就放目前最小值減 1（--left）。因為一開始的 $k$ 正好等於之後需要往下放的次數，最小值會恰好降到 0、最大值恰好升到 $n-1$，所以輸出一定是 $0\sim n-1$ 的排列，而且相鄰大小關係符合字串。

解題方法

逐一檢查選項：

• (A) 正確。 "000" 有 3 個 0，left = right = 3，起始為 {3}；三個 0 依序放入 2、1、0，得到 $\{3,2,1,0\}$。
• (B) 正確。 排列 $(3,1,2,0,4)$ 相鄰比較：$3>1$（0）、$1<2$（1）、$2>0$（0）、$0<4$（1），表示為 "0101"。而 findPermutation("0101")：0 有 2 個，起始 {2}；0→1、1→3、0→0、1→4，輸出 $\{2,1,3,0,4\}$，與 $(3,1,2,0,4)$ 不同。
• **(C) 正確。

核心觀念

模 $p$ 的乘法反元素是滿足 $ab\equiv 1\pmod p$ 的數。因為 $p=101$ 是質數，且 $a=55$ 不被 $101$ 整除，所以 $55$ 在模 $101$ 下有乘法反元素。

若 $b_0$ 是一個解，所有整數解都與 $b_0$ 模 $101$ 同餘；正整數解則可由 $b_0+101k$（$k\geq 0$）表示。

解題方法

用擴展歐幾里得算法求 $55$ 的模 $101$ 反元素：

$$101=55+46,\qquad 55=46+9,\qquad 46=5\cdot 9+1$$

回代得：

$$1=46-5(55-46)=6\cdot 46-5\cdot 55$$

再代入 $46=101-55$：

$$1=6\cdot 101-11\cdot 55$$

因此 $-11\cdot55\equiv1\pmod{101}$，所以

核心觀念

這題考的是重排不等式：若兩組數字分別由小到大排列，將相同排名的數字相乘後加總，總和最大。也就是把較大的 $A[i]$ 配給較大的 $B[\pi(i)]$。

關鍵是交換兩組配對時的差值。若 $a<b$ 且 $c\le d$，則

$$(ac+bd)-(ad+bc)=(b-a)(d-c)\ge 0.$$

因此，讓大小順序一致的配對不會比交錯配對差。

解題方法

將 $A$ 與 $B$ 各自由小到大排序，再依序相乘並加總，即可得到最大值。若配對中出現「較大的數配到較小的數」而「較小的數配到較大的數」，套用上式交換後，總和不會下降。持續交換直到兩邊的排名順序一致，便得到最大值。

以選項 (B) 為例：

$$A=[1,3,2,4],\qquad B=[3,4,2,1].$$

排序後分別為 $[1,2,3,4]$ 與 $[1,2,3,4]$，最大總和為

$$1\cdot1+2\cdot2+3\cdot3+4\cdot4=30.$$

回到原陣列，最佳配對是 $A$ 中的 $1,2,3,4$ 分別配上 $B$ 中的 $1,2,3,4$；對應的原始 $B$ 索引依序為 $4,3,1,2$。

選項分析

(A) 正確。
由

核心觀念

最小生成樹（MST）是連通圖中連接所有頂點、總權重最小的生成樹。含 $N$ 個頂點的生成樹恰有 $N-1$ 條邊。

判斷邊權變動時，可比較生成樹的總權重：若所有生成樹的權重都增加相同數值，最優解不變；若只改變一條未被選用的邊，則要分別看它變小或變大對候選生成樹的影響。

解題方法

逐項套用生成樹的邊數性質，以及 MST 的唯一性與最優性。對選項 C，任何生成樹都含 $N-1$ 條邊，因此每條邊都加上常數 $C$ 後，每棵生成樹的總權重都增加 $C(N-1)$，彼此的大小順序不變。

對未在 MST 中的邊，降低權重可能使它取代樹上的某條邊；提高權重則不會使原本的 MST 變差。

選項分析

• (A) 正確。 MST 是一棵生成樹。任何含 $N$ 個頂點的樹都有 $N-1$ 條邊，因此 MST 有 $N-1$ 條邊。

• (B) 正確。 若圖中所有邊權皆相異，MST 唯一。直觀上，選擇某一階段權重最小且可加入生成樹的邊時，不會有同權邊造成不同選擇；

核心觀念

最小生成樹（MST）必須涵蓋圖中的所有頂點，並且連通、無環。若圖有 $n$ 個頂點，生成樹恰有 $n-1$ 條邊；不連通的圖不存在生成樹。

Kruskal 演算法依權重由小到大選邊，遇到形成環的邊便略過。相同權重的邊若能互相替換，便可能產生不同的 MST；計數時看的是不同的邊集合，不是選邊順序。

解題方法

原卷印刷的頂點集合為 $V=\{A,B,C,D,E,F\}$，但附圖只畫出 $A,B,C,D,E$，未畫出 $F$ 及其連接邊。圖中可讀到的邊與權重如下：

權重	邊
$1$	$AB$
$2$	$AC、BC、CE$
$3$	$AD、BE$
$4$	$CD$
$5$	$DE$

先依圖中五個頂點計算，便能說明原公布答案 $B$ 的來源。

1. 選入 $AB$，權重為 $1$。
   $AB$ 是全圖唯一最輕的邊，必定出現在 MST 中。

2. 處理權重為 $2$ 的邊。
   選入 $AB$ 後，$AC$ 與 $BC$ 只能擇一，因為兩條都選會形成三角環 $A-B-C-A$。
   $CE$ 則必須選入：它是連接頂點 $E$ 的唯一最輕邊，其餘連到 $E$ 的邊為 $BE=3$、$DE=5$。

3. 連接頂點 $D$。
   連到 $D$ 的邊為 $AD=3$、$CD=4$、$DE=5$，因此必須選入唯一最輕的 $AD$。

所以五頂點圖恰有以下兩棵 MST：

$$T_1=\{AB,AC,CE,AD\}, \qquad T_2=\{AB,BC,CE,AD\}.$$

兩者的總權重皆為

核心觀念

廣度優先搜尋（BFS）從起點開始，先拜訪距離起點較近的節點，再逐層向外探索。對無權圖而言，BFS 找到的節點層數就是從起點到該節點的最短邊數；搜尋過程也能用來判斷可達性、檢查二分圖，以及分層列出節點。

解題方法

逐一確認各選項能否利用 BFS 的逐層探索或拜訪標記完成。迷宮可視為圖；無向圖可用顏色交替檢查二分性；有向圖沿著邊搜尋可達節點；節點層數可由 BFS 距離取得；連通分量則可從尚未拜訪的節點反覆啟動 BFS。

選項分析

• (A) 正確。 將迷宮中的可通行位置視為節點，相鄰位置間的移動視為邊。若每一步移動成本相同，BFS 首次抵達終點時，所經路徑就是最短路徑。
• (B) 正確。 從任一節點開始 BFS，將起點染成一種顏色，並將每個相鄰節點染成相反顏色。

核心觀念

紅黑樹是帶有紅、黑顏色規則的二元搜尋樹。其平衡性來自以下性質：

1. 每個節點是紅色或黑色。
2. 根節點為黑色。
3. 每個 NIL 葉節點為黑色。
4. 紅色節點的子節點必為黑色，因此不會有連續的紅色節點。
5. 從任一節點到其後代 NIL 葉節點的每條路徑，黑色節點數相同。

旋轉會調整樹的局部結構，同時維持二元搜尋樹的鍵值順序；插入或刪除後，會搭配重新著色與旋轉來恢復紅黑樹性質。

解題方法

逐項比對紅黑樹的定義與平衡性質。判斷路徑長度時，令最短路徑上的黑色節點數為 $b$。最短路徑不含相鄰紅色節點；最長路徑的黑色節點數也為 $b$，而每個黑色節點之間至多插入一個紅色節點，因此最長路徑長度至多為 $2b$，最短路徑長度至少為 $b$。所以最長路徑不超過最短路徑的兩倍。

選項分析

核心觀念

最小堆以陣列儲存時，若根節點位於索引 $0$，索引為 $i$ 的節點，其父節點索引為

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

插入新值時，先將它放在陣列末端，再沿著父節點往上比較；若新值小於父節點，就把父節點下移，直到找到正確位置。

解題方法

插入位置應是目前的 size，因為陣列索引從 $0$ 開始，而 size 表示目前已有元素數量。沿父節點上移時，必須使用 (cur-1)/2；找到位置後放入 x，最後將 size 加一。

int cur = size;
while (cur != 0 && data[(cur - 1) / 2] > x) {
    data[cur] = data[(cur - 1) / 2];
    cur = (cur - 1) / 2;
}
data[cur] = x;
size++;

例如，若新元素位置為索引 $2$，其父節點索引是 $\lfloor(2-1)/2\rfloor=0$。這也說明 cur/2 在偶數索引時會算錯。

選項分析

核心觀念

最小堆是一棵完全二元樹，且每個父節點的值都小於或等於子節點。以 0 起始索引儲存時，索引為 $i$ 的節點，其父節點索引為

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

插入新值時，先放在陣列末端，再沿父節點一路向上比較；只要父節點較大，就將父節點往下移，最後把新值放到空出的位置。

解題方法

依照題幹所說的 0 起始索引，程式空格應採用以下寫法：

int cur = size;
while (cur != 0 && data[(cur - 1) / 2] > x) {
    data[cur] = data[(cur - 1) / 2];
    cur = (cur - 1) / 2;
}
data[cur] = x;
size++;

逐次插入後的堆陣列如下：

插入值	插入並向上調整後的 data
40	[40]
15	[15, 40]
50	[15, 40, 50]
10	[10, 15, 50, 40]
30	[10, 15, 50, 40, 30]
20	[10, 15, 20, 40, 30, 50]
5	[5, 15, 10, 40, 30, 50, 20]

核心觀念

B-tree 的「最大度數為 3」表示每個節點最多有 $3$ 個子節點，因此最多有 $3-1=2$ 個鍵值。插入後若節點暫時含有 $3$ 個鍵值，就將中間鍵值升到父節點，左右兩側的鍵值分別留在分裂後的兩個節點中。

題目問「one number」的節點數，也就是恰好含有一個鍵值的節點數；根節點、內部節點與葉節點都要計入。

解題方法

依序插入鍵值；遇到節點有 $3$ 個鍵值時，就分裂並提升中間值。

1. 插入 $80,40,20$ 後，葉節點成為 $[20,40,80]$，分裂並提升 $40$，形成根節點 $[40]$，左右葉節點為 $[20]$、$[80]$。
2. 插入 $100,60$ 後，右側葉節點 $[60,80,100]$ 分裂，提升 $80$。此時根節點為 $[40,80]$，子節點依序為 $[20]$、$[60]$、$[100]$。
3. 插入 $30,50,70$ 後，$70$ 使中間葉節點成為 $[50,60,70]$。分裂並提升 $60$ 後，根節點暫成 $[40,60,80]$，也超過最多兩個鍵值，因此再分裂根節點並提升 $60$。樹形為：

$$\begin{array}{c} [60]\\ /\quad\backslash\\ [40]\qquad [80]\\ /\ \backslash\qquad /\ \backslash\\ [20,30]\ [50]\quad [70]\ [100] \end{array}$$

4. 插入 $10$ 後，左側葉節點 $[20,30]$ 溢位，分裂並提升 $20$，使其父節點成為 $[20,40]$。
5. 插入 $25,35$ 後，葉節點成為 $[25,30,35]$。

核心觀念

AVL 樹、B 樹與 B+ 樹都是搜尋樹，但適用情境不同。AVL 樹以維持平衡來支援記憶體中的搜尋；B 樹與 B+ 樹則採多路分支，降低樹高，常用於磁碟或其他區塊式儲存。

B+ 樹的資料記錄集中在葉節點，葉節點通常以鏈結串接，因此適合範圍查詢與循序掃描。AVL 樹雖然平衡，但高度通常大於多路搜尋樹，磁碟查詢時可能需要更多次磁碟存取。

解題方法

逐項判斷搜尋樹的性質與用途，再依序模擬 AVL 插入。AVL 樹每個節點的平衡因子為左子樹高度減右子樹高度；若插入造成失衡，就依失衡方向旋轉。

依序插入 $100,80,60,40,50,65,70,75,64$：

• 插入 $60$ 後，根節點 $100$ 發生 LL 失衡，右旋後以 $80$ 為根。
• 插入 $40$ 後，根節點 $80$ 發生 LL 失衡，右旋後以 $60$ 為根。
• 插入 $50,65,70$ 後，樹仍符合 AVL 平衡條件。
• 插入 $75$ 後，節點 $65$ 發生 RR 失衡，左旋後該子樹以 $70$ 為根。
• 插入 $64$ 後，節點 $80$ 發生 LL 失衡，右旋後其左子樹以 $70$ 為根。

最後的樹為：

核心觀念

本題考的是：負權邊對最短路徑演算法的影響，以及程式的實際執行順序。

• Dijkstra：邊權重皆非負時，才能保證已確定的頂點距離不必再更新。負權邊會破壞此保證，但不表示每次執行都必然算錯。
• Bellman–Ford 型鬆弛：反覆檢查 $$d[u]\leftarrow\min\{d[u],\,d[i]+w(i,u)\}$$ 在來源可達的範圍沒有負權環時，可以處理負權邊。
• Floyd–Warshall：利用 $$D[i][j]\leftarrow\min\{D[i][j],\,D[i][k]+D[k][j]\}$$ 計算所有頂點對的最短距離，也能處理沒有負權環的圖。

解題方法

依原圖，邊與權重為 $0\to2:7$、$0\to1:1$、$1\to3:2$、$2\to3:-5$、$3\to0:3$、$3\to4:3$、$4\to2:4$、$4\to1:2$。其中 $4\to2$ 的權重是 $+4$，唯一的負權邊是 $2\to3$，權重為 $-5$。

包含負權邊的簡單有向環有：

$$2\to3\to4\to2:\quad -5+3+4=2,$$ $$2\to3\to0\to2:\quad -5+3+7=5.$$

其餘不含負權邊的環皆為正權重，因此圖中沒有負權環。

由頂點 $4$ 出發，真正的最短距離如下：

終點	最短路徑	距離
$0$	$4\to2\to3\to0$	$4-5+3=2$
$1$	$4\to1$	$2$
$2$	$4\to2$	$4$
$3$	$4\to2\to3$	$4-5=-1$

故依頂點 $0,1,2,3,4$ 排列，距離為

$$(d[0],d[1],d[2],d[3],d[4])=(2,2,4,-1,0).$$

這組距離對每條邊都滿足 $d[v]\le d[u]+w(u,v)$，而表中各條路徑又確實達到相應距離，因此可確認結果正確。

選項分析

(A) Dijkstra 可以求出由 $4$ 到其他頂點的最短路徑：原標準答案不選；本圖存在可成功的執行順序。

從 $4$ 開始，先得到 $d[1]=2$、$d[2]=4$；接著選取頂點 $1$，使 $d[3]=4$。此時頂點 $2$、$3$ 的暫定距離同為 $4$，平手處理便成為關鍵：

• 先選 $2$：經由負權邊 $2\to3$，把 $d[3]$ 更新為 $-1$，之後得到 $d[0]=2$，結果正確。
• 先選 $3$：先把 $d[3]=4$ 確定下來，之後便不能更新成 $-1$，結果錯誤。

因此，Dijkstra 對本圖沒有一般正確性保證，但採取先選 $2$ 的平手規則時，確實能算出正確答案。這是本題疑義的關鍵。

(B) foo1 可以求出最短路徑：正確。

foo1 先以來源的直接邊初始化，再反覆檢查所有進入頂點 $u$ 的邊，屬於 Bellman–Ford 型的鬆弛程序。

本題 $V=5$，k=2,3,4 共執行三輪。省略來源本身的距離，依 $0,1,2,3$ 排列：

階段	$d[0]$	$d[1]$	$d[2]$	$d[3]$
初始化	$\mathrm{INF}$	$2$	$4$	$\mathrm{INF}$
第一輪	$\mathrm{INF}$	$2$	$4$	$-1$

核心觀念

這題考的是在有向無環圖（DAG）上，利用拓樸排序與動態規劃求最大權重路徑。DAG 的拓樸排序會讓每條邊都由較早處理的頂點指向較晚處理的頂點，因此計算某個頂點的最佳路徑時，其前驅頂點的答案都已經確定。

此外，DAG 中不可能有環，所以任何有向路徑都不會重複經過頂點；因此找到的路徑自然是簡單路徑。邊權可以是負數，演算法仍然適用。

解題方法

先將 $G$ 做拓樸排序。定義子問題：

$$dp[v] = \text{從 } s \text{ 到 } v \text{ 的所有有向路徑中，最大總權重}$$

若不存在從 $s$ 到 $v$ 的路徑，令 $dp[v] = -\infty$。初始化為：

$$dp[s] = 0,\qquad dp[v] = -\infty \quad (v \ne s)$$

對每個頂點 $v$，考慮所有指向 $v$ 的邊 $(u,v)$。若最佳路徑最後一條邊是 $(u,v)$，則路徑權重為 $dp[u]+w(u,v)$，因此遞迴式為：

$$dp[v] = \max_{(u,v)\in E} \bigl(dp[u]+w(u,v)\bigr)$$

核心觀念

本題考查最長回文子序列（Longest Palindromic Subsequence, LPS），可用區間動態規劃求解。子序列只要求字元順序不變，不要求連續；因此答案可以跳過輸入字串中的部分字元。

令 $s$ 為輸入字串，$dp[i][j]$ 表示子字串 $s[i\ldots j]$ 中，最長回文子序列的長度。單一字元必為回文，所以 $dp[i][i]=1$。

解題方法

考慮區間兩端的字元：

• 若 $s[i]=s[j]$，兩端可作為回文的首尾，故 $$dp[i][j]=dp[i+1][j-1]+2$$
• 若 $s[i]\ne s[j]$，最長回文子序列必須捨棄其中一端，故 $$dp[i][j]=\max(dp[i+1][j],\,dp[i][j-1])$$

依區間長度由短至長填表，計算 $dp[i][j]$ 時，較短區間的結果已經求得。最終 $dp[0][n-1]$ 即為最長回文子序列的長度。

若要輸出子序列本身，從區間兩端回溯：兩端字元相同時，將該字元加入答案的前半與後半；兩端不同時，往 $dp$ 值較大的子區間前進。回溯至區間長度為 $1$ 時，將該字元放在答案中央。

讀圖

題組附圖為有向圖，源點 $s=1$、匯點 $t=6$，共 9 條邊：
$1\to2$、$1\to4$、$2\to4$、$3\to2$、$4\to3$、$4\to5$、$3\to5$、$3\to6$、$5\to6$。

核心觀念

求從 $s$ 到 $t$ 的最大邊不相交（edge-disjoint）路徑數，可以化成最大流問題：把每條邊的容量設為 1，求 $s$ 到 $t$ 的整數最大流（例如用 Ford–Fulkerson／Edmonds–Karp）。由整數流定理，最大流存在整數解，每條邊的流量非 0 即 1；把流分解成路徑，就得到彼此不共用邊的路徑集合，且路徑數＝最大流值（Menger 定理）。

解題方法

1. 建立流網路：9 條邊容量都是 1。
2. 上界：$s=1$ 只有兩條出邊（$1\to2$、$1\to4$），所以最多 2 條路徑；匯點 6 也只有兩條入邊（$3\to6$、$5\to6$）。
3. 找出兩條邊不相交的路徑：
   • 路徑一：$1\to4\to5\to6$
   • 路徑二：$1\to2\to4\to3\to6$

核心觀念

本題要求的是「內部節點不相交路徑」：不同路徑可以共用起點 $s=1$ 與終點 $t=6$，但不能共用其他節點。

求最大路徑數，可利用節點分割法轉成最大流問題；也可找出所有路徑必經的內部節點，建立上界，再構造路徑證明此上界可以達到。

解題方法

圖中的有向邊為

$$1\to2,\quad 1\to4,\quad 2\to4,\quad 3\to2,\quad 4\to3,\quad 4\to5,\quad 3\to5,\quad 3\to6,\quad 5\to6。$$

其中中央斜邊的方向是 $4\to3$，因此節點 $4$ 可以通往節點 $3$。

一、找出必經節點，建立上界

由起點 $1$ 出發，第一步只能走向 $2$ 或 $4$：

• 若走 $1\to4$，立即經過節點 $4$。
• 若走 $1\to2$，因為節點 $2$ 唯一的出邊是 $2\to4$，仍然必須經過節點 $4$。

因此，從 $1$ 到 $6$ 的每一條路徑都必經內部節點 $4$。兩條路徑若同時存在，就會共用節點 $4$，違反題目要求，故

$$\text{最大內部節點不相交路徑數}\leq 1。$$

二、構造路徑，證明上界可達

取路徑

$$P_1:\quad 1\to4\to5\to6。$$

其中每一條邊都符合圖上的方向，因此確實存在至少一條合法路徑，得到

$$\text{最大內部節點不相交路徑數}\geq 1。$$

合併上下界，最大數量就是 $1$。

三、一般求法：節點分割與最大流

對較大的圖，可用以下方式求解：

核心觀念

紅黑樹的每條根至 NIL 葉節點路徑，黑色節點數相同；黑色 NIL 葉節點不計入樹中的節點數。以下令黑高 $h$ 表示每條根至 NIL 路徑上，不含 NIL 的黑色節點數。紅黑樹根為黑色，且紅色節點的子節點必為黑色。

解題方法

**最少節點數：**要在黑高固定為 $h$ 時讓節點數最少，不能插入紅色節點，因為紅色節點會增加節點數但不增加黑高。因此樹的每一層都是黑色，且為了讓所有路徑有相同黑高，形成高度為 $h$ 的滿二元樹：

$$N_{\min}(h)=1+2+2^2+\cdots+2^{h-1}=2^h-1$$

核心觀念

二元堆是完全二元樹，通常以從 $0$ 開始的陣列儲存。索引為 $i$ 的節點，其左子節點索引為 $2i+1$，右子節點索引為 $2i+2$。葉節點沒有子節點。

解題方法

節點 $i$ 有左子節點的條件是 $2i+1<n$。因此，葉節點必須滿足：

$$2i+1\ge n$$ $$i\ge \left\lceil \frac{n-1}{2}\right\rceil =\left\lfloor \frac{n}{2}\right\rfloor$$

陣列中最大的有效索引是 $n-1$，所以葉節點的索引範圍為：

核心觀念

這題考的是次序統計樹中的 OS-SELECT：在二元搜尋樹中尋找第 $i$ 小的鍵值。每個節點 $x$ 額外記錄其子樹大小：

$$\operatorname{size}[x] = \operatorname{size}[\operatorname{left}[x]] + \operatorname{size}[\operatorname{right}[x]] + 1$$

在以 $x$ 為根的子樹中，左子樹的所有鍵值都小於 $x$，所以 $x$ 在該子樹中的名次為：

$$r=\operatorname{size}[\operatorname{left}[x]]+1$$

解題方法

先計算左子樹有幾個節點，再加上根節點本身，即可得到根節點 $x$ 在目前子樹中的名次 $r$。

• 若 $i=r$，代表 $x$ 正是第 $i$ 小的節點，回傳 $x$。
• 若 $i<r$，目標在左子樹，遞迴搜尋左子樹時名次仍為 $i$。
• 若 $i>r$，目標在右子樹。

核心觀念

本題考查遞迴程式的時間複雜度，以及如何用代入法（反覆展開遞迴式）求解。每次呼叫在遞迴部分執行兩個規模為 $N-1$ 的呼叫，並額外執行一次 printf。

題目程式呼叫的是 foo，但未提供 foo 的定義。以下依題意假設 foo 與 bar 執行相同的遞迴邏輯；在此假設下即可建立遞迴式。

解題方法

令 $T(N)$ 表示 bar(N, X, Y, Z) 的執行時間。當 $N\leq 1$ 時，只執行一次輸出，耗時為常數，因此：

$$T(1)=\Theta(1)$$

當 $N>1$ 時，程式依序呼叫兩次規模為 $N-1$ 的遞迴函式，並執行一次常數時間的輸出，因此：

$$T(N)=2T(N-1)+\Theta(1)$$

以常數 $c>0$ 表示每層額外的固定成本，反覆代入：

$$\begin{aligned} T(N) &=2T(N-1)+c\\ &=2\bigl(2T(N-2)+c\bigr)+c\\ &=2^2T(N-2)+2c+c\\ &=2^2T(N-2)+c(2^2-1) \end{aligned}$$

繼續展開 $k$ 層，可得：