115 年 國立中正大學資訊管理學系碩士班乙組《資料結構》

核心觀念

本題考多元樹的表示法，以及將一般樹轉換為二元樹的左子女－右兄弟表示法：

• 一般樹中，每個節點可有多個子女，子女順序依題目列出的順序。
• 轉成二元樹時，每個節點的左子節點指向它的第一個子女；右子節點指向它的下一個兄弟。
• 因此，二元樹中的右子鏈代表一般樹中同一父節點下的兄弟，不代表一般樹中的子女。

解題方法

先依括號中的巢狀結構整理各節點的子女：

• $A$ 的子女：$B,D$
• $B$ 的子女：$E,F$
• $E$ 的子女：$Z,L,K$
• $D$ 的子女：$H,P,C,O$
• $H$ 的子女：$M$
• $C$ 的子女：$W$
• $O$ 的子女：$X$

(a) 對應的一般樹

A
├── B
│   ├── E
│   │   ├── Z
│   │   ├── L
│   │   └── K
│   └── F
└── D
    ├── H
    │   └── M
    ├── P
    ├── C
    │   └── W
    └── O
        └── X

(b) 轉換後的二元樹

左邊表示左子女，右邊表示右兄弟：

核心觀念

有向圖的鄰接矩陣以 $A_{ij}=1$ 表示存在由頂點 $i$ 指向頂點 $j$ 的邊，沒有邊則記為 $0$；鄰接串列則列出每個頂點的所有出邊終點。

計算圖中的「孤立部分」時，本題依題目給的結果 $2$，採用弱連通分量：忽略箭頭方向後，彼此可連通的一群頂點算一個部分。

解題方法

圖中頂點為 $1$ 至 $6$。依箭頭方向讀出邊為
$1\to2$、$2\to1$、$2\to3$、$2\to4$、$3\to3$、$4\to1$、$4\to3$、$5\to6$；其中 $3\to3$ 是自我迴圈。

以頂點 $1,2,3,4,5,6$ 依序作為鄰接矩陣的列與欄，得到：

$$A= \begin{array}{c|cccccc} & 1&2&3&4&5&6\\\hline 1&0&1&0&0&0&0\\ 2&1&0&1&1&0&0\\ 3&0&0&1&0&0&0\\ 4&1&0&1&0&0&0\\ 5&0&0&0&0&0&1\\ 6&0&0&0&0&0&0 \end{array}$$

依各頂點的出邊整理鄰接串列：

頂點	鄰接串列
1	2
2	1, 3, 4
3	3
4	1, 3
5	6
6	$\varnothing$

計算弱連通分量時，把每條有向邊視為無向連線，再以深度優先搜尋或廣度優先搜尋逐一標記頂點。每遇到尚未拜訪的頂點，就代表找到一個新的分量，計數加一。

核心觀念

題目未明訂大小寫的比較規則；以下採一般字母字典序、不區分大小寫，將 I 視為字母 i，因此：

$a<I<m<t<w<y$

AVL 樹是具有自我平衡功能的二元搜尋樹。每個節點的平衡因子定義為：

$BF(v)=h(\text{左子樹})-h(\text{右子樹})$

AVL 樹必須滿足：

$|BF(v)|\leq 1$

本題採空樹高度為 $0$、葉節點高度為 $1$。插入新鍵值時，先依二元搜尋樹規則放置，再由插入位置向上檢查平衡因子。第一個失衡節點需要旋轉：

• 左左型（LL）：右旋
• 右右型（RR）：左旋
• 左右型（LR）：先左旋，再右旋
• 右左型（RL）：先右旋，再左旋

逐步插入與旋轉

第 1 個鍵值：w

w

第 2 個鍵值：y

因為 $y>w$，插入 w 的右子樹。

w
 \
  y

w 的平衡因子為 $-1$，仍符合 AVL 條件。

第 3 個鍵值：a

因為 $a<w$，插入 w 的左子樹。

  w
 / \
a   y

w 的平衡因子為 $0$。

第 4 個鍵值：m

比較路徑為：

$m<w,\qquad m>a$

因此 m 插入 a 的右子樹。

    w
   / \
  a   y
   \
    m

此時：

$BF(a)=0-1=-1$

$BF(w)=2-1=1$

整棵樹仍然平衡。

第 5 個鍵值：t

比較路徑為：

$t<w,\qquad t>a,\qquad t>m$

因此 t 插入 m 的右子樹。

      w
     / \
    a   y
     \
      m
       \
        t

此時 a 的右子樹高度為 $2$：

$BF(a)=0-2=-2$

m 的平衡因子為 $-1$，因此 a 屬於右右型（RR），對 a 做一次左旋：

表達式二元樹

          (+)
        /     \
      (+)      (*)
     /   \    /   \
   (-)    g  h    (-)
  /   \        \
(*)    (*)       j
/ \    / \
A   b  /   f
      / \
     c   (-)
        /   \
       d     e

前序走訪 (Pre‑order) 演算法（遞迴版）

核心觀念

遞迴函式必須包含兩個部分：

1. 邊界條件（boundary condition）：問題規模小到可直接求解時停止遞迴。
2. 遞迴關係式（recurrence formula）：將原問題轉換成規模較小的同類問題。

由於

$$3^n=3\cdot 3^{n-1},$$

因此可將函數定義為

$$f(n)= \begin{cases} 3, & n=1,\\ 3f(n-1), & n>1. \end{cases}$$

其中 $f(1)=3$ 是邊界條件。

---

解題方法

每次將指數 $n$ 減少 $1$，並在結果外乘上 $3$：

$$\begin{aligned} f(n)&=3f(n-1)\\ &=3\left(3f(n-2)\right)\\ &=3^2f(n-2)\\ &\cdots\\ &=3^{n-1}f(1)\\ &=3^{n-1}\cdot 3\\ &=3^n. \end{aligned}$$

因此遞迴函式如下：

Function f(n)
    if n == 1 then
        return 3
    else
        return 3 * f(n - 1)

前提是輸入 $n$ 為正整數。

若採用 $f(0)=1$ 作為邊界條件，也可寫成：

$$f(n)= \begin{cases} 1, & n=0,\\ 3f(n-1), & n>0. \end{cases}$$

兩種寫法皆正確；本題因指定 $n$ 為正整數，使用 $f(1)=3$ 最直接。

---

(a) 遞迴函式

int f(int n) {
    if (n == 1) {          // boundary condition
        return 3;
    }

    return 3 * f(n - 1);   // recursive case
}

例如：

$$f(4)=3f(3)=3(3f(2))=3(3(3f(1)))=3^4=81.$$

---

(b) 遞迴程式

以下為完整的 C 語言程式：

核心觀念

本題考查 Dijkstra 最短路徑演算法。給定起點後，求出起點到所有其他節點的最短距離，並以 predecessor 記錄各節點的前一個節點，形成「最短路徑樹」（Shortest Path Tree）。

Dijkstra 演算法適用於所有邊權重皆為非負數的圖。它不等同於最小生成樹（Minimum Spanning Tree, MST）；最小生成樹追求整棵樹的總邊權重最小，Dijkstra 則追求「從指定起點到各節點的路徑個別最短」。

解題方法

設定：

• dist[v]：起點 $s$ 到節點 $v$ 的目前最短距離
• prev[v]：最短路徑中，節點 $v$ 的前一個節點
• visited[v]：節點 $v$ 是否已確定最短距離

初始化：

$$dist[s] = 0$$ $$dist[v] = \infty \quad (v \ne s)$$

每次從尚未確定的節點中，選出 dist 最小者 $u$，再檢查 $u$ 的所有鄰接節點 $v$。若經過 $u$ 到 $v$ 的距離更短，便進行鬆弛（relaxation）：

$$\text{若 } dist[u] + w(u,v) < dist[v]$$

則更新：

$$dist[v] = dist[u] + w(u,v)$$ $$prev[v] = u$$

Dijkstra 演算法虛擬碼

核心觀念

本題考單源最短路徑。Bellman–Ford 演算法透過反覆「鬆弛」邊，逐步更新起點到各節點的最短距離，適用於含負權重邊的圖；若有負權重環，則不存在有限的最短路徑。

令 $d_k(v)$ 表示從起點到節點 $v$、最多經過 $k$ 條邊的最短距離，則：

$$d_k(v)=\min\left(d_{k-1}(v),\ \min_{(u,v)\in E}\left[d_{k-1}(u)+w(u,v)\right]\right)$$

圖中邊沒有方向箭頭，因此視為無向圖；實作時，每條邊都要以兩個方向進行鬆弛。

解題方法

以節點 $0$ 為起點、節點 $3$ 為終點。圖上相關邊包括：

• $0$–$1$：4、$0$–$7$：8
• $1$–$2$：8、$7$–$6$：1
• $6$–$5$：2、$2$–$5$：4
• $2$–$3$：7、$5$–$3$：14、$4$–$3$：9、$5$–$4$：10

依 Bellman–Ford 更新距離，與抵達節點 $3$ 有關的節點距離為：

• 到節點 $2$：$0\to1\to2$，距離 $4+8=12$
• 到節點 $5$：$0\to7\to6\to5$，距離 $8+1+2=11$
• 到節點 $4$：$0\to7\to6\to5\to4$，距離 $8+1+2+10=21$

節點 $3$ 可由 $2$、$5$ 或 $4$ 抵達，對應距離分別為：

$$\begin{aligned} 0\to1\to2\to3 &: 12+7=19\\ 0\to7\to6\to5\to3 &: 11+14=25\\ 0\to7\to6\to5\to4\to3 &: 21+9=30 \end{aligned}$$

因此，最短路徑為 $0\to1\to2\to3$，總長度為 $19$。

演算法偽碼