112 年 國立成功大學電腦與通信工程研究所丁組《資料結構》

核心觀念

本題考查漸近符號，用來描述輸入規模 $n$ 足夠大時，函數的成長速度。

• $O(g(n))$：上界，表示成長速度不超過 $g(n)$ 的量級。
• $\Omega(g(n))$：下界，表示成長速度至少達到 $g(n)$ 的量級。
• $\Theta(g(n))$：緊確界，同時滿足 $O(g(n))$ 與 $\Omega(g(n))$。

題目通常要求找出最精確的漸近成長量級。

---

解題方法

（a）$n!$

由階乘定義：

$$n! = 1 \times 2 \times 3 \times \cdots \times n$$

若只使用初等估計，由於每一項皆不大於 $n$，可得：

$$n! \leq n^n$$

因此：

$$n! = O(n^n)$$

但 $O(n^n)$ 並不是最精確的描述。使用 Stirling 公式：

$$n! \sim \sqrt{2\pi n}\left(\frac{n}{e}\right)^n$$

因此：

$$n! = \Theta\left(\sqrt{n}\left(\frac{n}{e}\right)^n\right)$$

其中常數 $\sqrt{2\pi}$ 不影響 $\Theta$ 表示法。

若課程僅要求以常見簡化形式表示，也可寫成：

$$n! = \Theta\left(\sqrt{n}\left(\frac{n}{e}\right)^n\right)$$

這是比 $\Theta(n^n)$ 更精確的答案；事實上，$n!$ 並非 $\Theta(n^n)$，因為：

$$\frac{n!}{n^n} \sim \sqrt{2\pi n}\,e^{-n} \longrightarrow 0$$

---

（b）$n^3 + 10^6n^2$

將多項式分解：

$$n^3 + 10^6n^2 = n^2(n+10^6)$$

核心觀念

本題考查中序表示式轉換為：

• Prefix（前序式）：運算子寫在運算元之前。
• Postfix（後序式）：運算子寫在運算元之後。

轉換時依據 C 語言的：

1. 運算子優先權
2. 相同優先權時的結合方向
3. 括號所指定的運算順序

本題涉及的優先權由高至低為：

$$! \;>\; *、/ \;>\; +、- \;>\; > \;>\; \&\& \;>\; ||$$

其中 $*、/、+、-$ 皆為左結合。

---

解題方法

先依照優先權與括號，將表示式分解成二元運算樹，再以樹根、左子樹、右子樹的順序讀出 Prefix；以左子樹、右子樹、樹根的順序讀出 Postfix。

---

（a）$(A*B)/D+E*(f*A+D)-C$

1. 依優先權加上結構

原式可分解為：

$$\left(\frac{A*B}{D}+E*(f*A+D)\right)-C$$

其中：

$$(A*B)/D$$

以及：

$$E*(f*A+D)$$

括號內：

$$f*A+D=(f*A)+D$$

因此完整結構為：

$$\bigl(((A*B)/D)+(E*((f*A)+D))\bigr)-C$$

2. Prefix（前序式）

由最外層運算子開始：

• 最外層為 $-$
• 左側為 $+$
• $+$ 的左側為 $/$
• $/$ 的左側為 $*$

依序寫出：

$$\boxed{- + / * A B D * E + * f A D C}$$

3. Postfix（後序式）

先寫左子樹，再寫右子樹，最後寫運算子：

• $A*B$：$A\ B\ *$
• $(A*B)/D$：$A\ B\ *\ D\ /$
• $f*A+D$：$f\ A\ *\ D\ +$
• $E*(f*A+D)$：$E\ f\ A\ *\ D\ +\ *$
• 最後與前半部相加，再減去 $C$

因此：

$$\boxed{A\ B\ *\ D\ /\ E\ f\ A\ *\ D\ +\ *\ +\ C\ -}$$

---

（b）$!((a \&\& c) || (c > d))$

1. 依 C 語言優先權加上結構

括號已明確指定主要運算順序：

核心觀念

本題考查遞迴函數的定義與字串串接。

對於輸入字串 $X=LS$：

• $L$ 是字串第一個字母。
• $S$ 是去除第一個字母後的剩餘字串。
• 遞迴定義為：

$$Z(LS)=Z(S)L$$

這表示先對剩餘字串 $S$ 遞迴處理，再把原本的第一個字母 $L$ 接到結果最後面。因此，字母的順序會被反轉。

解題方法

依照遞迴定義逐層拆解，再由最底層的 Base Case 往回代入。

令：

$$X=\text{happy}$$

逐步展開：

$$\begin{aligned} Z(\text{happy})&=Z(\text{appy})h\\ &=Z(\text{ppy})ah\\ &=Z(\text{py})pah\\ &=Z(\text{y})ppah\\ &=\text{yppah} \end{aligned}$$

其中：

$$Z(\text{y})=\text{y}$$

是因為 y 只有一個字母，符合 Base Case。

函數實際功能

核心觀念

本題考查二元樹的遞迴定義，以及二元樹各層節點數量的上限。

二元樹具有以下特性：

• 每個節點最多有兩個子節點。
• 子樹本身仍然是二元樹。
• 空樹也是二元樹的基本情況。

以下採用常見定義：根節點位於第 $0$ 層（level $0$）。

---

(a) 以遞迴方式定義二元樹

Base case：基底情況

空樹 $\varnothing$ 是一棵二元樹。

也可以將只有一個根節點、沒有左右子樹的樹視為最基本的非空二元樹。

Recursive case：遞迴情況

若 $T_L$ 與 $T_R$ 都是二元樹，且新增一個節點 $r$ 作為根節點，令 $T_L$ 成為 $r$ 的左子樹、$T_R$ 成為 $r$ 的右子樹，則所形成的樹也是二元樹：

$$T = \operatorname{Node}(r,T_L,T_R)$$

其中：

• $r$ 是根節點；
• $T_L$ 是左子樹；
• $T_R$ 是右子樹；
• $T_L$ 與 $T_R$ 可以是空樹。

因此，二元樹可形式化表示為：

$$\mathcal{B}= \{\varnothing\} \cup \{\operatorname{Node}(r,T_L,T_R)\mid T_L,T_R\in\mathcal{B}\}$$

這個定義完整表達二元樹的結構：先以空樹作為終止條件，再由兩棵較小的二元樹組合出較大的二元樹。

---

(b) 第 $i$ 層的最大節點數

解題方法

採用逐層觀察與數學歸納法。

二元樹中，每個節點最多產生兩個子節點，因此下一層的最大節點數至多是上一層的兩倍。

逐層推導

根節點位於第 $0$ 層，因此：

• 第 $0$ 層最多有 $1=2^0$ 個節點；
• 第 $1$ 層最多有 $2=2^1$ 個節點；
• 第 $2$ 層最多有 $4=2^2$ 個節點；
• 第 $3$ 層最多有 $8=2^3$ 個節點。

因此可觀察出第 $i$ 層的最大節點數為：

核心觀念

本題考的是遞迴作圖與自相似結構：先畫一條線，再把同一套分枝規則套用到新產生的短線上，逐步形成樹狀圖形。

每次對一條線執行 Draw()，都會在該線的上方三分之二範圍內，向左、向右各畫 $3$ 條較短的斜線，因此一次新增 $6$ 條子線。子線必須連接到母線，且能繼續產生自己的分枝。

解題方法

原卷附圖只有一條直立線，作為最初的主幹；框內規則要求先畫左右各 $3$ 條短枝，再選一條新線重複作圖。題目未指定分枝角度、長度比例與停止深度，因此採用對稱分枝、子線逐次縮短的方式示範。

第一步：在主幹上畫出六條短枝。

在主幹上方三分之二內選取三個位置，每個位置向左上與右上各畫一條較短的線，下方保留不分枝的幹段。

第二步：在子線上重複相同規則。

將每條子線與主幹相接的一端視為基部，另一端視為頂端。在子線靠近頂端的三分之二範圍內，再向它自己的左右兩側各畫 $3$ 條更短的線。

下圖示範主幹的六條分枝，並進一步對最上方左右兩條子線各執行一次 Draw()。● 表示實際連接點，⋮ 表示省略的下方幹段；圖形為比例示意。

核心觀念

本題考查「全點對最短路徑」（All-Pairs Shortest Paths, APSP）問題：給定圖 $G=(V,E)$，求任意兩個頂點 $i,j$ 之間的最短距離。

最典型的方法是 Floyd–Warshall 演算法。其核心定義為：

$$D^{(k)}[i][j] = \text{只允許前 } k \text{ 個頂點作為中繼點時，}i\text{ 到 }j\text{ 的最短距離}$$

當新增頂點 $k$ 作為中繼點時，從 $i$ 到 $j$ 的最短路徑只有兩種情況：

1. 不經過 $k$：

   $$D^{(k-1)}[i][j]$$

2. 經過 $k$：

   $$D^{(k-1)}[i][k]+D^{(k-1)}[k][j]$$

因此遞迴公式為：

$$D^{(k)}[i][j] = \min\left( D^{(k-1)}[i][j], D^{(k-1)}[i][k]+D^{(k-1)}[k][j] \right)$$

Floyd–Warshall 可處理負權重邊，但不能處理負權重循環，因為負權重循環會使最短距離沒有有限值。

---

解題方法

令頂點數為 $n=|V|$，使用二維矩陣 dist 儲存距離：

• dist[i][j]：目前已知的頂點 $i$ 到頂點 $j$ 的最短距離。
• 若 $(i,j)\in E$，初始化為邊權重 $w(i,j)$。
• 若 $i$ 與 $j$ 之間沒有直接邊，初始化為 $\infty$。
• dist[i][i]=0。

接著依序將每個頂點 $k$ 作為中繼點，更新所有起點 $i$ 與終點 $j$：

$$\text{dist}[i][j] \leftarrow \min\left( \text{dist}[i][j], \text{dist}[i][k]+\text{dist}[k][j] \right)$$

虛擬碼

FloydWarshall(V, E, w):
    n ← |V|
    dist ← n × n 的矩陣

    for each i in V:
        for each j in V:
            if i = j:
                dist[i][j] ← 0
            else if (i, j) ∈ E:
                dist[i][j] ← w(i, j)
            else:
                dist[i][j] ← ∞

    for each k in V:
        for each i in V:
            for each j in V:
                if dist[i][k] ≠ ∞ and dist[k][j] ≠ ∞:
                    dist[i][j] ← min(
                        dist[i][j],
                        dist[i][k] + dist[k][j]
                    )

    return dist

其中三層迴圈的順序必須是：

k → i → j

因為第 $k$ 層代表「允許頂點 $k$ 作為新的中繼點」，這是 Floyd–Warshall 正確性的關鍵。

---

輸入資料結構

輸入包含：

1. 頂點集合 $V$，頂點數為 $n$。
2. 邊集合 $E$。
3. 邊權重函數 $w$，其中： $$w(i,j)=\text{從 }i\text{ 到 }j\text{ 的邊權重}$$

可使用下列資料結構表示：

• V：頂點陣列或頂點編號 $1,2,\ldots,n$。
• w：$n\times n$ 的權重矩陣。
• ∞：代表兩點之間沒有直接邊。

若圖為有向圖，必須分別記錄 $w(i,j)$ 與 $w(j,i)$。若圖為無向圖，則有：

$$w(i,j)=w(j,i)$$

(a) 文字鍊自動機構圖

狀態集合 $V=\{q_0,q_1,\dots ,q_{16}\}$，初始狀態 $q_0$，終止狀態 $F=\{q_{7},q_{14},q_{16}\}$。邊以單字為標籤（$W$ 為所有單字），如下：

起始	標籤	終點
$q_0$	I	$q_1$
$q_1$	like	$q_2$
$q_2$	his	$q_3$
$q_3$	rabbit	$q_7$
$q_0$	They	$q_4$
$q_4$	hate	$q_5$
$q_5$	his	$q_6$
$q_6$	cat	$q_{14}$
$q_5$	to	$q_{12}$
$q_{12}$	have	$q_{13}$
$q_{13}$	a	$q_{15}$
$q_{15}$	hamster	$q_{16}$
$q_0$	I	$q_8$
$q_8$	think	$q_9$
$q_9$	that	$q_{10}$
$q_{10}$	his	$q_{11}$
$q_{11}$	hamster	$q_{12}$

核心觀念

本題考查兩個概念：

1. 字梯圖（word ladder graph）
   每個單字視為一個頂點；若兩個單字長度相同，且恰好只有一個字母不同，便在兩頂點之間連一條邊。

2. 無權重圖的最短路徑
   每次改變一個字母視為成本 $1$，因此所有邊權重相同。從起點到終點所需的最少轉換次數，就是圖上的最短路徑長度。

---

(a) 建立字梯圖

判斷相鄰頂點的方法

比較兩個單字的四個位置：

• 恰好一個位置不同：相鄰，連邊。
• 不同位置超過一個：不相鄰。
• 完全相同：不另外建立新邊。

例如：

• FOOL 與 POOL 只有第一個字母不同，因此相鄰。
• FOOL 與 POLL 有兩個字母不同，因此不相鄰。
• POLE 與 POPE 只有第三個字母不同，因此相鄰。

圖中的邊

由題目所給單字建立圖，可得到以下相鄰關係：

• FOOL：POOL、COOL、FOUL、FOIL
• POOL：FOOL、POLL
• POLL：POOL、POLE、PALL
• POLE：POLL、PALE、POPE
• PALE：POLE、SALE、PAGE
• SALE：PALE、SAGE
• SAGE：SALE、PAGE
• COOL：FOOL
• FOUL：FOOL、FOIL
• FOIL：FOOL、FOUL、FAIL
• FAIL：FOIL、FALL
• FALL：FAIL、PALL
• PALL：FALL、POLL
• POPE：POLE
• PAGE：PALE、SAGE

其中 POLE 在題目中重複出現，圖論上仍視為同一個頂點。

圖形表示

可用下列方式表示主要連線：

$$\text{FOOL} \begin{cases} \text{POOL} \rightarrow \text{POLL} \rightarrow \text{POLE} \rightarrow \text{PALE} \rightarrow \text{SALE} \rightarrow \text{SAGE}\\ \text{COOL}\\ \text{FOUL} \leftrightarrow \text{FOIL} \rightarrow \text{FAIL} \rightarrow \text{FALL} \leftrightarrow \text{PALL} \end{cases}$$

此外還有：

$$\text{POLE} - \text{POPE}$$

以及：

$$\text{PALE} - \text{PAGE} - \text{SAGE}$$

因此，題目給出的範例路徑為：

$$\text{FOOL} \rightarrow \text{POOL} \rightarrow \text{POLL} \rightarrow \text{POLE} \rightarrow \text{PALE} \rightarrow \text{SALE} \rightarrow \text{SAGE}$$

此路徑共有 $6$ 條邊，也就是 $6$ 次字母轉換。

---

(b) 搜尋最有效率的路徑

適合使用廣度優先搜尋 BFS

此圖是無權重圖，每次字母轉換的成本均為 $1$，因此應使用廣度優先搜尋（Breadth-First Search, BFS）。

BFS 從 FOOL 開始，按照距離由近到遠逐層搜尋：

• 第 $0$ 層：FOOL
• 第 $1$ 層：所有與 FOOL 只差一個字母的單字
• 第 $2$ 層：距離 FOOL 為 $2$ 的單字
• 依此類推，直到找到 SAGE

BFS 第一次抵達某個頂點時，所使用的路徑一定是從起點到該頂點的最短路徑。因此，第一次找到 SAGE 時，即得到最少轉換次數。

本題的一條最短路徑

沿著範例路徑搜尋：

$$\text{FOOL} \rightarrow \text{POOL} \rightarrow \text{POLL} \rightarrow \text{POLE} \rightarrow \text{PALE} \rightarrow \text{PAGE} \rightarrow \text{SAGE}$$

每一步都只改變一個字母，共有：

$$6$$

次轉換。

另一條同樣長度的最短路徑為：

$$\text{FOOL} \rightarrow \text{POOL} \rightarrow \text{POLL} \rightarrow \text{POLE} \rightarrow \text{PALE} \rightarrow \text{SALE} \rightarrow \text{SAGE}$$

為何不用 DFS

深度優先搜尋（DFS）可能先走進很長的路徑，再回頭尋找較短的路徑，因此：

• DFS 可以找到一條可行路徑；
• 但第一次找到的路徑不保證是最短路徑；
• 必須搜尋更多分支，才能確認最短答案。

為何不用 Dijkstra

Dijkstra 適用於邊權重不同且沒有負權重的圖。本題所有邊權重都是 $1$，使用 Dijkstra 會增加不必要的優先佇列處理；BFS 已能直接得到最短路徑。