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

核心觀念

Bellman–Ford 演算法以「鬆弛」更新最短距離。對有向邊 $u\to v$，權重為 $w(u,v)$，更新公式為：

$$d(v)\leftarrow \min\{d(v),\,d(u)+w(u,v)\}.$$

初始設定 $d(S)=0$，其餘頂點的距離皆為 $\infty$。本題採用逐邊立即更新：同一輪前面更新的距離，後面處理邊時就可以使用，因此邊的處理順序會影響收斂輪數。

題目定義：若第 $P+1$ 輪所有距離皆無改善，則收斂所需輪數為 $P$，不把最後的確認輪計入。

解題方法

原圖共有 $S,A,B,C,D,E,F,G$ 八個頂點；所有邊皆為有向邊，其中斜向連接 $C$ 與 $A$ 的邊是 $C\to A$，權重為 $3$。依指定處理順序，各邊權重如下：

邊	$AB$	$AD$	$BC$	$BF$	$CA$	$CD$	$CE$	$CF$	$DG$	$EG$	$FG$	$SA$	$SB$
權重	$4$	$11$	$8$	$11$	$3$	$2$	$5$	$1$	$2$	$1$	$9$	$3$	$6$

以下距離向量皆依 $(S,A,B,C,D,E,F,G)$ 排列。

第 1 輪

初始距離為：

$$(0,\infty,\infty,\infty,\infty,\infty,\infty,\infty).$$

由於 $SA$、$SB$ 排在最後，處理前十一條邊時，其起點距離皆為 $\infty$，不會產生更新。最後兩條邊得到：

$$d(A)=0+3=3,\qquad d(B)=0+6=6.$$

因此第 1 輪結束時為：

$$(0,3,6,\infty,\infty,\infty,\infty,\infty).$$

第 2 輪

依指定順序逐邊鬆弛：

處理邊	更新計算	結果
$AB$	$d(B)\leftarrow\min(6,3+4)$	$d(B)=6$，不變
$AD$	$d(D)\leftarrow\min(\infty,3+11)$	$d(D)=14$
$BC$	$d(C)\leftarrow\min(\infty,6+8)$	$d(C)=14$
$BF$	$d(F)\leftarrow\min(\infty,6+11)$	$d(F)=17$
$CA$	$d(A)\leftarrow\min(3,14+3)$	$d(A)=3$，不變
$CD$	$d(D)\leftarrow\min(14,14+2)$	$d(D)=14$，不變

核心觀念

Bellman–Ford 每一輪依指定順序掃描所有邊，並以

$$d(v)\leftarrow\min\{d(v),\,d(u)+w(u,v)\}$$

更新距離。掃描時若前面的邊已更新某個頂點，後面的邊可以在同一輪接著使用新距離，因此一輪可能沿著多條邊傳遞最短距離。若從 $S$ 到某頂點的最短路徑有 $k$ 條邊，掃描 $k$ 輪後必能找到該距離；實際輪數也會受到邊的處理順序影響。

解題方法

圖中有 $8$ 個頂點 $S,A,B,C,D,E,F,G$，邊為 $SA,SB,AB,AD,BC,BF,CA,CD,CE,CF,DG,EG,FG$。依圖讀得 $S\to A$ 權重 $3$、$S\to B$ 權重 $6$、$B\to C$ 權重 $8$、$C\to F$ 權重 $1$、$A\to D$ 權重 $11$、$D\to G$ 權重 $2$，其餘邊權重如圖。

選擇合適的鬆弛順序，可以在一輪內得到全部正確距離。例如依序處理 $SA,SB,BC,CA,AD,CD,CE,CF,DG,EG,FG,BF,AB$，會得到

$$d(A)=3,\quad d(B)=6,\quad d(C)=14,\quad d(D)=14,\quad d(E)=19,\quad d(F)=15,\quad d(G)=16.$$

因此最少只需 $1$ 輪。

核心觀念

Bellman–Ford 對有向邊 $u\to v$ 的鬆弛規則為：

$$d(v)\leftarrow \min\{d(v),\,d(u)+w(u,v)\}.$$

初始化為 $d(S)=0$，其餘頂點距離皆為 $\infty$。每一輪依指定順序處理全部邊，且本輪更新的距離可立即供後續邊使用，因此邊的排列順序會影響收斂輪數。

依原卷前題的定義，若第 $P$ 輪後所有距離已正確，而第 $P+1$ 輪沒有任何改善，則收斂輪數為 $P$；確認沒有改善的那一輪不計入。

解題方法

圖中共有 $S,A,B,C,D,E,F,G$ 八個頂點，起點為 $S$。依圖上箭頭讀得 $C\to A$，權重為 $3$；其餘邊與權重如下：

有向邊	權重	有向邊	權重
$S\to A$	$3$	$S\to B$	$6$
$A\to B$	$4$	$A\to D$	$11$
$B\to C$	$8$	$B\to F$	$11$
$C\to A$	$3$	$C\to D$	$2$
$C\to E$	$5$	$C\to F$	$1$
$D\to G$	$2$	$E\to G$	$1$
$F\to G$	$9$

先求出正確的最短距離，作為各順序的收斂判準：

$$\begin{aligned} d(A)&=3,\\ d(B)&=\min\{6,3+4\}=6,\\ d(C)&=6+8=14,\\ d(D)&=\min\{3+11,14+2\}=14,\\ d(E)&=14+5=19,\\ d(F)&=\min\{6+11,14+1\}=15,\\ d(G)&=\min\{14+2,19+1,15+9\}=16. \end{aligned}$$

其中 $G$ 的最短路徑為 $S\to A\to D\to G$，總權重為 $3+11+2=16$。

依各選項順序逐輪鬆弛，可得下表；距離向量依序為 $(d(A),d(B),d(C),d(D),d(E),d(F),d(G))$，並省略始終為 $0$ 的 $d(S)$。

選項	第 $1$ 輪結束	第 $2$ 輪結束	第 $3$ 輪結束
（A）	$(3,6,\infty,\infty,\infty,\infty,\infty)$	$(3,6,14,14,19,15,16)$	無改善
（B）	$(3,6,\infty,\infty,\infty,\infty,\infty)$	$(3,6,14,14,19,15,16)$	無改善
（C）	$(3,6,\infty,\infty,\infty,\infty,\infty)$	$(3,6,14,14,\infty,17,\infty)$	$(3,6,14,14,19,15,16)$

核心觀念

路徑是從任一輸入，沿著導線與邏輯閘到達某一輸出的連續路徑。若訊號進入同一個閘的不同輸入端，或分別經過不同邏輯閘，便是不同路徑；因此要把訊號分流到不同閘的路徑分別計數。

解題方法

圖中每一位的進位邏輯由三個 AND 閘接到一個 OR 閘，分別形成 $A_iB_i$、$A_iC_{i-1}$、$B_iC_{i-1}$；加總輸出 $S_i$ 則由一個三輸入 XOR 閘產生。第一位的進位輸入 $C_0=C_{in}$ 是一個輸入訊號。

令 $C_i$ 表示從所有輸入到第 $i$ 位進位輸出 $C_i$ 的路徑數。第一位的三個 AND 閘各接兩個輸入，所以：

$$C_1=2+2+2=6$$

對後續各位，$A_iB_i$ 的 AND 閘有 2 條輸入路徑；$A_iC_{i-1}$ 與 $B_iC_{i-1}$ 兩個 AND 閘，各有 1 條來自新輸入的路徑，以及 $C_{i-1}$ 的 $C_{i-1}$ 條路徑。因此：

$$C_i=2+(1+C_{i-1})+(1+C_{i-1})=4+2C_{i-1}$$

逐位計算：

$$C_1=6,\qquad C_2=16,\qquad C_3=36,\qquad C_4=76$$

核心觀念

臨界路徑是從任一輸入到任一輸出的路徑中，經過最多個邏輯閘的路徑；只計算沿途經過的閘數，不計導線或輸入、輸出端點。

解題方法

圖中是 4-bit ripple carry adder：每一位的進位由三個 AND 閘與一個 OR 閘組成，並傳給下一位；各位的和由 XOR 閘組成。沿著進位鏈走到最高位的 $C_{out}$，會得到最長路徑。

從 $C_{in}$ 到 $C_{out}$，第一位進位經過一個 AND 閘與一個 OR 閘，共 $2$ 個閘；之後第 2、3、4 位各再經過一個 AND 閘與一個 OR 閘，共 $6$ 個閘。因此：

$$2+3\times 2=8$$

其他輸入到輸出的路徑至多經過這段進位鏈，再接上和位所需的 XOR 閘，不會超過 8 個閘。

選項分析

核心觀念

本題承接前一題的「關鍵路徑」：從任一輸入到任一輸出，經過最多邏輯閘的路徑。將邏輯閘視為頂點、訊號線視為有向邊，組合邏輯電路沒有回授迴圈，因此形成有向無環圖（DAG）。

一般圖的最長路徑問題很困難，但 DAG 可利用拓樸排序與動態規劃，在線性時間內求得最長路徑。

解題方法

圖中有四級加法電路，進位訊號依序由低位元傳往高位元，各級也分支產生 $S_1,S_2,S_3,S_4$，最後產生 $C_{out}$；訊號連線沒有形成有向環。原卷第 6 題寫的是求解「Question 11」的時間複雜度，但本頁前一題實際標為第 5 題，題號引用不一致。

依「承接前一題，求關鍵路徑」的合理解讀，演算法如下：

1. 建立圖並進行拓樸排序。
   使用鄰接串列記錄連線，計算各頂點的入度，依拓樸順序處理邏輯閘，確保處理某個閘時，它的所有前驅都已處理完畢。

2. 計算抵達每個邏輯閘的最長路徑。
   設 $d(v)$ 為從任一輸入到邏輯閘 $v$，最多經過的邏輯閘數。外部輸入的路徑長度設為 $0$，每經過一個邏輯閘增加 $1$，因此：

   $$d(v)=1+\max_{u\to v}d(u).$$

   若 $v$ 直接連接外部輸入，該輸入在上式中的值就是 $0$。

3. 取所有輸出端的最大值。
   比較通往 $S_1,S_2,S_3,S_4$ 與 $C_{out}$ 的最長路徑，最大值就是關鍵路徑經過的邏輯閘數。

核心觀念

2-SAT 的每個子句是兩個文字的析取，例如 $(x+y)$ 表示 $x\lor y$。整個公式以括號相乘表示合取，因此每個子句都必須為真，公式才可滿足。

判斷時可利用：若某個文字已為真，子句 $(\neg x+y)$ 會迫使 $y$ 為真；若 $x$ 已為真，子句 $(\neg x+y)$ 則迫使 $y$ 為真。若推導出互相矛盾的要求，該公式便不可滿足。

解題方法

先找能迫使變數取值的子句，再將推得的值代入其餘子句。特別地，$(a+b)(a+\neg b)$ 會迫使 $a$ 為真：若 $a$ 為假，兩個子句分別要求 $b$ 與 $\neg b$ 為真，造成矛盾。同理，$(\neg a+b)(\neg a+\neg b)$ 會迫使 $\neg a$ 為真。

選項分析

• (A) 不可滿足。 前兩個子句 $(a+b)(a+\neg b)$ 迫使 $a$ 為真；後兩個子句 $(\neg a+b)(\neg a+\neg b)$ 迫使 $a$ 為假，互相矛盾。

• (B) 不可滿足。 $(a+b)(a+\neg b)$ 迫使 $a$ 為真；$(\neg a+c)(\neg a+\neg c)$ 迫使 $a$ 為假，因此無法同時滿足。

核心觀念

對每個子句 $(x+y)$，2-SAT 的蘊含圖會加入兩條有向邊：

$$\neg x\to y,\qquad \neg y\to x$$

圖中的頂點是每個變數及其否定文字。本題有 $a,b,c,d$ 四個變數，因此共有 $8$ 個頂點。

解題方法

依序將每個子句轉成兩條有向邊：

子句	對應的有向邊
$(a+b)$	$\neg a\to b$、$\neg b\to a$
$(\neg a+b)$	$a\to b$、$\neg b\to\neg a$
$(\neg b+c)$	$b\to c$、$\neg c\to\neg b$
$(\neg b+d)$	$b\to d$、$\neg d\to\neg b$
$(\neg c+\neg d)$	$c\to\neg d$、$d\to\neg c$

因此圖有 $8$ 個頂點、$10$ 條邊。

讀圖（實心黑底為黑色節點、白底為紅色節點）

• Tree A：根 20（黑）；左子 15（紅）、右子 30（紅）。15 只有左子 10（黑），10 的右子 12（紅）。30 的子節點 25（黑，左子 22 紅）、35（黑，子節點 32 紅、45 紅）。
• Tree B：根 20（黑）；左子 12（黑，子節點 10 紅、15 紅）、右子 30（紅）。30 的子節點 25（黑，子節點 22 紅、32 紅）、35（黑，右子 45 紅）。
• Tree C：根 22（黑）；左子 15（紅，子節點 10 黑、20 黑；10 的右子 12 紅）、右子 30（紅，子節點 25 黑、35 黑；35 的子節點 32 紅、45 紅）。

核心觀念

合法的紅黑樹必須同時是二元搜尋樹，並滿足：(1) 根為黑；(2) 紅節點的子節點必為黑；(3) 從任一節點到其下所有 NIL 的路徑，黑節點數（黑高）相同。

(A) 解題

• Tree A：不合法（黑高不一致）。 紅節點 15 的右邊是 NIL：路徑 $20\to15\to\text{NIL}$ 只經過 1 個黑節點（20）；但 $20\to15\to10\to\text{NIL}$ 經過 2 個黑節點（20、10）。同一個節點到不同 NIL 的黑節點數不同，違反性質 (3)。

讀圖

有向圖共 10 個頂點（0～9），邊為：
$2\to8$、$8\to1$、$1\to0$、$2\to4$、$2\to3$、$4\to3$、$3\to0$、$2\to5$、$0\to7$、$0\to6$、$6\to5$、$5\to9$。

核心觀念

遞移閉包（transitive closure）矩陣 $A^+$ 中，$A^+[i][j]=1$ 表示存在一條長度至少 1 的路徑從 $i$ 到 $j$。題目問矩陣中 1 的個數，就是「所有可達的 $(i,j)$ 配對數」。本圖沒有環，所以對角線全為 0（頂點不能經由長度 $\ge1$ 的路徑回到自己）。

解題方法

由沒有出邊的頂點往上推每個頂點的可達集合：

頂點	可達集合	個數
9	∅	0
7	∅	0
5	{9}	1
6	{5, 9}	2
0	{7, 6, 5, 9}	4

核心觀念

拓樸排序是將有向圖的所有頂點排成線性順序，使每條有向邊 $u\to v$ 都滿足：$u$ 排在 $v$ 前面。有向無環圖才存在拓樸排序，且答案不一定唯一。

本題採用 Kahn 演算法：每次選取目前入度為 $0$ 的頂點，加入排序並刪除其出邊，接著更新其餘頂點的入度。

解題方法

圖中共有 $0$ 至 $9$ 共十個頂點；其中箭頭方向為 $2\to4$，而 $2$ 也有邊指向 $8$、$3$、$5$。依圖中箭頭，各頂點的出邊如下：

頂點	出邊指向的頂點
$2$	$4,8,3,5$
$4$	$3$
$8$	$1$
$1$	$0$
$3$	$0$
$0$	$7,6$
$6$	$5$
$5$	$9$
$7,9$	無

依序選取入度為 $0$ 的頂點：

1. 先選 $2$：初始只有 $2$ 的入度為 $0$。刪除它的出邊後，$4$、$8$ 的入度變成 $0$；$3$ 仍有來自 $4$ 的邊，$5$ 仍有來自 $6$ 的邊。

核心觀念

有向圖存在拓樸排序，若且唯若圖中沒有有向環。若沿著有向邊能從某頂點回到該頂點，就形成有向環，因而不存在拓樸排序。

解題方法

依圖中箭頭，原圖有路徑 $2\to3\to0\to6\to5$。將邊 $2\to5$ 反向後，新增的邊是 $5\to2$，因此形成有向環：

$$5\to2\to3\to0\to6\to5$$

核心觀念

拓樸排序是將有向圖的所有頂點排成一個序列，使每條邊 $u\to v$ 都滿足「$u$ 排在 $v$ 前面」。有向圖存在拓樸排序，若且唯若它沒有有向環。

在原本無環的圖中新增 $1\to3$，只有當原圖已存在從 $3$ 到 $1$ 的有向路徑時，才會形成有向環。

解題方法

依圖中的箭頭，原圖包含 $2\to4\to3\to0$、$2\to8\to1\to0$ 與 $0\to6\to5\to9$ 這三條路徑，另有 $2\to3$、$2\to5$、$0\to7$。本小題從原圖出發，僅新增 $1\to3$，因此 $2\to5$ 的方向維持不變。

由頂點 $3$ 出發，只能沿箭頭到達 $0,7,6,5,9$，無法到達 $1$。所以新增 $1\to3$ 不會形成有向環，仍然存在拓樸排序；新增的限制是 $1$ 必須排在 $3$ 前面。

使用「每次取出入度為 $0$ 的頂點」的方法，可依序排列：

核心觀念

拓樸排序要求每條有向邊 $u\to v$ 都符合「$u$ 排在 $v$ 前面」。一般 BFS 依照距離逐層拜訪頂點，並不會檢查某個頂點的所有前置頂點是否都已排在它之前。

解題方法

附圖是頂點編號為 $0$ 至 $9$ 的有向圖；本小題詢問的是 BFS 能否一般性地產生拓樸順序，不要求替附圖列出拓樸排序。考慮以下有向無環圖：邊為 $s\to a$、$s\to b$、$b\to x$、$x\to a$，其中 $s$ 是唯一的起點。

從 $s$ 執行 BFS 時，$a$ 和 $b$ 都在第一層，$x$ 在第二層，因此 BFS 會先拜訪 $a$，再拜訪 $x$。但圖中有邊 $x\to a$，拓樸排序必須讓 $x$ 在 $a$ 前面。

核心觀念

Kruskal 演算法將所有邊依權重由小到大檢查；只有在加入某邊不會形成環時，才將它選入最小生成樹（MST）。

解題方法

圖中是頂點 $0$ 至 $9$ 的無向加權圖。由小到大檢查相關邊：$5$–$9$ 的權重為 $1$、$0$–$3$ 為 $2$、$2$–$3$ 為 $3$、$0$–$5$ 為 $4$、$0$–$6$ 為 $5$。

核心觀念

Prim 演算法從指定起始頂點出發，逐步擴張最小生成樹。設 $S$ 為已加入樹中的頂點集合，每一步都選擇「一端在 $S$、另一端在 $S$ 外」的最小權重邊，並加入該邊連接的新頂點。

原題未指定起始頂點，因此選邊順序沒有唯一答案；以下採用從頂點 $0$ 起始，並將加入第一條邊計為第一步。

解題方法

依圖，頂點 $0$ 連到 $3、5、6、7、1$ 的邊權重依序為 $2、4、5、8、13$；另有 $w(2,3)=3$、$w(5,9)=1$ 及 $w(3,4)=6$，這些邊會影響前五步的選擇。

初始 $S=\{0\}$，依序執行：

步驟	選取的邊	權重	加入後的頂點集合 $S$
第一步	$(0,3)$	$2$	$\{0,3\}$
第二步	$(2,3)$	$3$	$\{0,2,3\}$
第三步	$(0,5)$	$4$	$\{0,2,3,5\}$
第四步	$(5,9)$	$1$	$\{0,2,3,5,9\}$

核心觀念

最小生成樹（MST）是在連通無向加權圖中，連接所有頂點且總權重最小的生成樹。若圖中所有邊的權重互不相同，MST 唯一。Dijkstra 演算法則是從指定起點找出各頂點的最短路徑；它產生的最短路徑樹，目標不等同於總邊權重最小的生成樹。

解題方法

圖中有 $10$ 個頂點，邊權重由 $1$ 到 $14$，各不相同。為判斷 Dijkstra 的最短路徑樹是否必為 MST，可用頂點 $1$ 作起點，比較該樹與 Kruskal 算法得到的 MST。

Kruskal 依權重由小到大選取不形成環的邊，得到權重為 $1,2,3,4,5,6,7,8,10$ 的 $9$ 條邊，總權重為

$$1+2+3+4+5+6+7+8+10=46.$$

從頂點 $1$ 執行 Dijkstra，最短路徑樹的邊為 $1\!-\!8$（7）、$1\!-\!0$（13）、$8\!-\!2$（10）、$0\!-\!3$（2）、$0\!-\!5$（4）、$0\!-\!7$（8）、$0\!-\!6$（5）、

核心觀念

二分搜尋適用於已排序的陣列。每次比較中間元素與目標值，排除不可能包含目標值的一半，因此時間複雜度為 $O(\log n)$，額外空間複雜度為 $O(1)$。

解題方法

圖中程式使用升冪排列的陣列，搜尋範圍由 left 和 right 表示，中間索引為 mid = left + (right - left) / 2。若 arr[mid] 小於目標值，目標只可能在右半部，應令 left = mid + 1；若大於目標值，目標只可能在左半部，應令 right = mid - 1。

第 13 行的條件方向與第 14、17 行的範圍更新不一致。將條件改為 arr[mid] > target，即可使兩個分支符合二分搜尋的規則。

修正程式

核心觀念

雙向鏈結串列的每個節點都有 prev 與 next 兩個指標。插入節點時，前後兩個方向都要接好；刪除節點時，必須先更新相鄰節點的指標，再釋放節點記憶體。

解題方法

原卷印刷內容顯示，struct Node 包含 data、prev、next；insertEnd 走訪到尾端後只設定新節點的前向連結，deleteNode 則在更新串列連結前就呼叫 free(temp)。依照雙向鏈結串列的連結規則，可定位出以下兩個錯誤。

錯誤一：第 27 行未設定新節點的 prev

尾端節點的 next 指向新節點後，新節點的 prev 也必須指回原尾端節點。否則從新節點往前走會失效。

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

錯誤二：第 39 行過早釋放節點

第 39 行釋放 temp 後，後續程式仍會讀取 temp->prev 與 temp->next，造成釋放後使用。應先完成前後節點的連結更新，再釋放 temp。

修正後的程式碼

核心觀念

雙向鏈結串列的每個節點都有 prev 與 next 兩個指標。插入節點時，前後兩個方向都要接好；刪除節點時，必須先更新相鄰節點的指標，再釋放節點記憶體。

解題方法

原卷印刷內容顯示，struct Node 包含 data、prev、next；insertEnd 走訪到尾端後只設定新節點的前向連結，deleteNode 則在更新串列連結前就呼叫 free(temp)。依照雙向鏈結串列的連結規則，可定位出以下兩個錯誤。

錯誤一：第 27 行未設定新節點的 prev

尾端節點的 next 指向新節點後，新節點的 prev 也必須指回原尾端節點。否則從新節點往前走會失效。

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

錯誤二：第 39 行過早釋放節點

第 39 行釋放 temp 後，後續程式仍會讀取 temp->prev 與 temp->next，造成釋放後使用。應先完成前後節點的連結更新，再釋放 temp。

修正後的程式碼

核心觀念

Min heap 必須滿足每個節點的值小於子節點，也就是父節點值小於或等於子節點值。插入時要把新值向上移動；刪除最小值時，則要用最後一個元素補到根節點，再向下調整。

解題方法

圖中第 14 題給出 insert、heapify 與 deleteMin 函式；insert 在第 41 行比較父節點與新元素，deleteMin 在第 74 行搬移元素。逐一對照 min heap 的向上與向下調整規則，可找出兩處錯誤。

第一處在第 41 行。min heap 插入時，只有父節點大於新元素，才需要交換；原程式使用 <，會把較大的元素往上移，破壞 min heap 性質。

while (i != 0 && heap->arr[parent(i)] > heap->arr[i]) {

核心觀念

Min heap 必須滿足每個節點的值小於子節點，也就是父節點值小於或等於子節點值。插入時要把新值向上移動；刪除最小值時，則要用最後一個元素補到根節點，再向下調整。

解題方法

圖中第 14 題給出 insert、heapify 與 deleteMin 函式；insert 在第 41 行比較父節點與新元素，deleteMin 在第 74 行搬移元素。逐一對照 min heap 的向上與向下調整規則，可找出兩處錯誤。

第一處在第 41 行。min heap 插入時，只有父節點大於新元素，才需要交換；原程式使用 <，會把較大的元素往上移，破壞 min heap 性質。

while (i != 0 && heap->arr[parent(i)] > heap->arr[i]) {

核心觀念

這題考的是以 bottom-up heap construction 將陣列轉成 min-heap。Min-heap 必須滿足：每個父節點的值都小於或等於其子節點的值。

題目使用從索引 $1$ 開始的陣列，因此索引 $i$ 的父節點與子節點位置為：

$$\operatorname{parent}(i)=\left\lfloor\frac{i}{2}\right\rfloor,\qquad \operatorname{left}(i)=2i,\qquad \operatorname{right}(i)=2i+1$$

葉節點不需要調整。若共有 $n$ 個元素，最後一個非葉節點是 $\lfloor n/2\rfloor$；本題 $n=11$，因此從索引 $5$ 開始，依序往上調整至索引 $1$。

解題方法

每次對節點執行向下調整：比較節點與其子節點，若父節點比最小的子節點大，就交換，並在交換後的位置繼續調整。

初始陣列（索引 $1$ 至 $11$）為：

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

依序由索引 $5$ 調整至索引 $1$：

1. **調整索引 $5$：**值為 $9$，子節點是索引 $10$ 的 $6$ 與索引 $11$ 的 $1$。與較小的 $1$ 交換。

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

2. **調整索引 $4$：**值為 $2$，子節點為 $4$ 和 $7$。父節點已小於兩個子節點，不需交換。

3. **調整索引 $3$：**值為 $10$，子節點為 $3$ 和 $8$。與較小的 $3$ 交換。

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

核心觀念

這題的關鍵在於「path」的定義，以及 $k$ 是否要求路徑中的頂點不能重複。

圖論通常將 path（簡單路徑） 定義為頂點不重複的路徑。判定問題可寫成：

輸入圖 $G$、起點 $u$、終點 $v$ 與長度 $k$，判斷是否存在一條從 $u$ 到 $v$、恰含 $k$ 條邊的簡單路徑。

這個問題屬於 NP：給定一條候選路徑，可以在多項式時間內檢查端點、邊數及頂點是否重複。

解題方法

以 Hamiltonian Cycle 問題歸約到此判定問題。給定一個有 $n$ 個頂點的圖 $G$，任選頂點 $r$，將 $r$ 拆成兩個頂點 $r_1,r_2$：

1. 保留 $G-r$ 中原有的邊。
2. 對每個 $r$ 在 $G$ 中的鄰點 $x$，在新圖中加入邊 $(r_1,x)$ 與 $(r_2,x)$。
3. 新增頂點 $s,t$，並只加入邊 $(s,r_1)$ 與 $(r_2,t)$。

令新圖為 $G'$。它共有 $n+2$ 個頂點，並將題目中的參數設為：

$$u=s,\qquad v=t,\qquad k=n+1$$

因為 $s,t$ 的度數都是 $1$，任何從 $s$ 到 $t$、長度為 $n+1$ 的簡單路徑，都必須經過 $G'$ 的全部 $n+2$ 個頂點。

若 $G$ 有 Hamiltonian Cycle，沿著該環移除 $r$，會留下 $G-r$ 上的一條涵蓋所有其餘頂點的路徑。

核心觀念

每個節點有三個指標：左子節點指標 $lc$、右子節點指標 $rc$，以及父節點指標 $p$。要計算整棵樹中的 NULL 指標，可分成「子節點指標」與「父節點指標」兩類計數。

含有 $n$ 個節點的二元樹有 $n-1$ 條父子連線：除根節點外，每個節點恰有一個父節點。

解題方法

一、計算左、右子節點指標中的 NULL 數量

每個節點各有兩個子節點指標，因此共有 $2n$ 個子節點指標。每條父子連線會占用一個子節點指標；共有 $n-1$ 條連線，因此非 NULL 的子節點指標有 $n-1$ 個。

所以 NULL 子節點指標數為：

$$2n-(n-1)=n+1$$

核心觀念

這段程式利用每個節點的父指標 p，沿著節點到根節點的路徑向上走。兩條路徑第一次相交的節點，就是 n1 和 n2 的最低共同祖先（Lowest Common Ancestor，LCA）。

在同一棵樹中，兩個節點往上走的祖先路徑會在 LCA 相交；LCA 是兩者共同祖先中距離它們最遠、也就是最深的那一個。

解題方法

令 n1、n2 到根節點的距離分別為 $d_1$、$d_2$。若直接讓兩個指標各自往上走，較深的節點會先到根，因此兩者不一定會同時走到 LCA。

程式讓指標在到達 NULL 時改從另一個起點重新走：

• a 先走 n1 到根，再從 n2 開始走。
• b 先走 n2 到根，再從 n1 開始走。

兩條路徑的長度差因此被補齊，指標會在 LCA 相遇。若其中一個節點本身就是另一個節點的祖先，兩者則會在該祖先相遇。

關鍵程式碼

核心觀念

這段程式和「找兩條鏈結串列的交會點」是同一招：讓兩個指標各走「自己的路＋對方的路」，兩邊總長度相同，所以會同時抵達交會點。

設根的深度為 $0$，$d_1=\operatorname{depth}(n1)$、$d_2=\operatorname{depth}(n2)$，$L$ 為兩者的最低共同祖先（LCA），$\ell=\operatorname{depth}(L)$。

證明

1. 兩個指標的路線。 每一輪迴圈 $a$、$b$ 各前進一步。

• $a$：第 $0$ 步在 $n1$，往上走 $d_1$ 步到根，第 $d_1+1$ 步變成 NULL，第 $d_1+2$ 步跳到 $n2$，接著從 $n2$ 往上走。
• $b$：對稱地，第 $d_2+2$ 步跳到 $n1$，接著從 $n1$ 往上走。

2. 同時抵達 $L$。 令

$$t=d_1+d_2-\ell+2$$

第 $t$ 步時，$a$ 已從 $n2$ 往上走了 $t-(d_1+2)=d_2-\ell$ 步，恰好到達 $n2$ 的深度 $\ell$ 祖先，也就是 $L$；$b$ 已從 $n1$ 往上走了 $t-(d_2+2)=d_1-\ell$ 步，同樣到達 $L$。所以第 $t$ 步時 $a=b=L$，迴圈最晚在這一步停止。

（若 $d_1=d_2$，兩者在第 $d_1-\ell$ 步就同時到達 $L$，還沒走到 NULL；以下證明這也是最早的相遇點。）

3. 不會更早在別處相遇。 假設第 $s<t$ 步時 $a=b=X$：

• 兩者都還在第一段（往上走自己的祖先）：$a$ 在 $n1$ 的祖先、$b$ 在 $n2$ 的祖先，同一步時深度分別為 $d_1-s$、$d_2-s$。若 $X$ 是同一個節點，深度必須相同，所以 $d_1=d_2$，而且 $X$ 是兩者的共同祖先；