114 年 國立成功大學工程科學系碩士班乙組《資料結構》

核心觀念

前序走訪的順序是「根、左子樹、右子樹」；中序走訪的順序是「左子樹、根、右子樹」。因此，前序序列的第一個節點是整棵樹的根，而該節點在中序序列中的位置，能將其餘節點分成左、右子樹。

解題方法

前序序列第一個節點是 $F$，所以 $F$ 為根。在中序序列 $A,B,C,D,E,F,G,H,I$ 中，$F$ 左側的 $A,B,C,D,E$ 屬於左子樹，右側的 $G,H,I$ 屬於右子樹。

左子樹的前序序列為 $B,A,D,C,E$，故其根為 $B$。在對應的中序序列 $A,B,C,D,E$ 中，$B$ 左側只有 $A$，右側為 $C,D,E$。因此，$A$ 是 $B$ 的左子節點；右子樹根為 $D$，且 $D$ 的左子節點為 $C$、右子節點為 $E$。

右子樹的前序序列為 $G,I,H$，故其根為 $G$。在對應的中序序列 $G,H,I$ 中，$G$ 沒有左子樹，右子樹包含 $H,I$；該右子樹的根為 $I$，而 $H$ 是 $I$ 的左子節點。

核心觀念

本題主要考驗遞迴函式之時間複雜度分析，核心觀念包含以下三項：

1. 遞迴關係式（Recurrence Relation）的建立：根據函式內部的條件分歧與 recursive calls 的次數，將執行時間表述為輸入規模 $n$ 的遞迴關係式。
2. 遞迴樹法（Recursion Tree Method）：將遞迴呼叫展開成樹狀結構，計算樹的高度、每層的節點數與工作量，最終加總求得總複雜度。
3. 主定理（Master Theorem）：用於快速求解符合 $T(n) = a T(n/b) + f(n)$ 形式之分治遞迴關係式漸近界限的定理。

解題方法

步驟一：建立遞迴關係式（Recurrence Relation）

觀察程式碼 mystery(n)：

• Base Case：當 $n \le 1$ 時，執行 if 判斷並回傳 1，花費常數時間 $O(1)$。
• Recursive Case：當 $n > 1$ 時，回傳敘述中寫著 mystery(n/2) + mystery(n/2)。注意這裡呼叫了 mystery(n/2) 兩次，加上一次加法運算與函式傳參，非遞迴部分的額外基本運算花費 $O(1)$。

因此，設 $T(n)$ 為輸入為 $n$ 時的執行時間，可建立遞迴關係式：
$T(n) = 2T\left(\frac{n}{2}\right) + O(1), \quad \text{for } n > 1$
$T(1) = O(1)$

步驟二：時間複雜度推導（提供兩種標準解法）

解法 A：遞迴樹法（Recursion Tree Method）

1. 樹的高度：每次將問題規模折半（$\frac{n}{2}$），直到規模縮小至 $1$。樹的高度為 $k = \log_2 n$。

2. 每層節點數與工作量：

   • 第 $0$ 層（根節點）：$1$ 個節點，規模為 $n$，工作量為 $c$。
   • 第 $1$ 層：$2$ 個節點，規模為 $\frac{n}{2}$，工作量為 $2 \times c$。
   • 第 $2$ 層：$4$ 個節點，規模為 $\frac{n}{4}$，工作量為 $4 \times c = 2^2 c$。
   • 第 $i$ 層：$2^i$ 個節點，規模為 $\frac{n}{2^i}$，工作量為 $2^i c$。
   • 第 $k = \log_2 n$ 層（葉節點）：$2^k = 2^{\log_2 n} = n$ 個葉節點，工作量為 $n \cdot T(1) = d \cdot n$。

3. 總工作量加總：
   $T(n) = \sum_{i=0}^{\log_2 n - 1} 2^i c + d \cdot n$
   利用等比級數求和公式：

核心觀念

本題考加權圖的深度優先搜尋（DFS）與廣度優先搜尋（BFS），並依搜尋順序計算首次發現新節點時所經過的邊之權重總和。DFS 會沿著目前可走且尚未拜訪的最小權重邊深入，無路可走時回溯；BFS 則用佇列依序處理節點，並按邊權重由小到大將新節點加入佇列。

解題方法與計算

圖中有頂點 $A,B,C,D,E,F$，無向邊及權重為 $AB=7$、$AC=12$、$AE=2$、$BE=3$、$BD=5$、$BF=14$、$CE=18$、$CD=1$、$DE=10$、$DF=4$。圖上權重 $10$ 對應邊 $ED$，沒有 $EF$ 邊。以下從 $E$ 開始，節點在首次發現時即標記為已拜訪；只加總搜尋樹中的發現邊。

(1) 深度優先搜尋

從 $E$ 出發，依未拜訪鄰點的邊權重由小到大選擇：

在每一次遍歷中，先自左向右比較相鄰元素並將較大的向右移（等同於一次 bubble‑up），接著再自右向左比較相鄰元素將較小的向左移（一次 bubble‑down）。
此「左右來回」的兩階段交替執行，使得每回合同時把最大值送至最右端、最小值送至最左端，遂出現序列

核心觀念

最小生成樹（MST）要以最小總權重連接所有頂點，且不形成迴圈；若有 $|V|$ 個頂點，生成樹恰有 $|V|-1$ 條邊。

• Prim 演算法：從指定頂點開始，每次加入一條連接「已加入頂點」與「未加入頂點」的最小權重邊。
• Kruskal 演算法：將所有邊依權重由小到大排列，逐一加入不會形成迴圈的邊。

解題方法

依原卷圖，頂點為 $A,B,C,D,E,F,G$；圖上的邊與權重為 $A\!-\!D:7$、$A\!-\!E:3$、$A\!-\!B:11$、$A\!-\!C:15$、$D\!-\!C:4$、$D\!-\!G:9$、$C\!-\!G:6$、$G\!-\!F:2$、$C\!-\!F:12$、$F\!-\!E:10$、$C\!-\!E:8$、$E\!-\!B:1$。圖示沒有 $D\!-\!E$ 邊。

(1) Prim 演算法，從 $A$ 開始

從 $A$ 出發，先選連到未加入頂點的最小邊；之後每步都在連接已加入與未加入頂點的邊中選最小者：