108 年 國立成功大學電機工程學系碩士班丁組《資料結構》

核心觀念

本題考查圖形走訪的時間複雜度，以及 DFS、BFS 與連通分量的關係。

對無向圖 $G=(V,E)$：

• $|V|=n$：頂點數
• $|E|=e$：邊數
• 無向圖的邊數滿足 $e\leq \frac{n(n-1)}{2}=O(n^2)$

標準走訪複雜度如下：

圖形表示法	DFS	BFS
Adjacency list	$O(n+e)$	$O(n+e)$
Adjacency matrix	$O(n^2)$	$O(n^2)$

使用 adjacency matrix 時，每拜訪一個頂點，都必須掃描該頂點對應的整列，共有 $n$ 個位置；最多拜訪 $n$ 個頂點，因此為 $O(n^2)$。

使用 adjacency list 時，只需掃描所有頂點及實際存在的邊，因此為 $O(n+e)$。

---

解題方法

逐一將各選項與上述標準複雜度比較，並注意題目沒有假設圖形一定連通。若圖形連通，因為至少需要 $n-1$ 條邊，所以 $n=O(e)$，此時 $O(n+e)$ 可寫成 $O(e)$；但對一般不連通圖，不能直接省略 $n$。

---

選項分析

(A) 錯誤

以 adjacency list 表示圖形時，DFS 的標準複雜度是

$$O(n+e)$$

不能一律寫成 $O(e)$。

例如圖形有 $n$ 個孤立頂點，則 $e=0$，但 DFS 仍須處理頂點，時間至少與 $n$ 有關。因此一般圖形應寫成 $O(n+e)$。

若題目額外保證圖形連通，才可利用 $e\geq n-1$，將複雜度簡化為 $O(e)$。

---

(B) 正確

以 adjacency matrix 表示圖形時，DFS 拜訪一個頂點後，必須掃描其對應的一整列，以確認它與哪些頂點相鄰。

每個頂點最多掃描 $n$ 個位置，最多處理 $n$ 個頂點，因此：

核心觀念

循環佇列（circular queue）遵守先進先出（FIFO）原則：

• enqueue(X)：將元素 $X$ 放入 Rear 端。
• dequeue()：從 Front 端移除最早進入的元素。
• 佇列大小為 $4$，最多同時容納 $4$ 個元素。
• 當 Rear 到達陣列尾端時，會循環回到索引 $0$。

本題要求的是所有操作完成後，從 Front 到 Rear 的元素順序。

解題方法

依序追蹤佇列內容。以「左端為 Front、右端為 Rear」表示：

操作	佇列內容（Front → Rear）	說明
初始狀態	空	佇列尚無元素
enqueue(A)	A	放入 A
enqueue(B)	A, B	B 排在 A 後方
dequeue()	B	移除 Front 的 A
enqueue(C)	B, C	C 從 Rear 端加入
enqueue(D)	B, C, D	D 從 Rear 端加入

核心觀念

本題考查雜湊表（hash table）採用開放定址法（open addressing）時的碰撞處理。

• 雜湊表大小為 $7$，索引位置為 $0,1,\ldots,6$。
• 雜湊函數：

$$h(x)=x\bmod 7$$

• 採用二次探測（quadratic probing），標準探測公式為：

$$h_i(x)=\bigl(h(x)+i^2\bigr)\bmod 7,\qquad i=0,1,2,\ldots$$

因此，發生碰撞時，依序檢查：

$$h(x),\quad h(x)+1^2,\quad h(x)+2^2,\quad h(x)+3^2,\ldots$$

每個 bucket 容量為 $1$，表示每個位置只能存放一個元素。

解題方法

依照題目給定的鍵值順序逐一插入。若原始位置已被占用，便按照二次探測公式尋找下一個空位。

初始雜湊表如下：

索引	0	1	2	3	4	5	6
內容	空	空	空	空	空	空	空

1. 插入鍵值 $8$

$$h(8)=8\bmod 7=1$$

位置 $1$ 為空，直接放入。

索引	0	1	2	3	4	5	6
內容	空	8	空	空	空	空	空

2. 插入鍵值 $17$

$$h(17)=17\bmod 7=3$$

位置 $3$ 為空，直接放入。

索引	0	1	2	3	4	5	6
內容	空	8	空	17	空	空	空

3. 插入鍵值 $24$

$$h(24)=24\bmod 7=3$$

位置 $3$ 已有 $17$，發生碰撞。使用二次探測：

• $i=1$：

$$(3+1^2)\bmod 7=4$$

位置 $4$ 為空，因此將 $24$ 放入位置 $4$。

索引	0	1	2	3	4	5	6
內容	空	8	空	17	24	空	空

4. 插入鍵值 $3$

核心觀念

二元樹的「後序走訪」順序為：

$$\text{左子樹} \rightarrow \text{右子樹} \rightarrow \text{根節點}$$

「中序走訪」順序為：

$$\text{左子樹} \rightarrow \text{根節點} \rightarrow \text{右子樹}$$

當所有節點的標籤皆不重複時，可以利用下列定理重建二元樹：

1. 後序走訪的最後一個節點必為整棵樹的根。
2. 在中序走訪中找到根節點後，根左側的節點屬於左子樹，根右側的節點屬於右子樹。
3. 將左右子樹分別對應到後序序列，再遞迴處理，即可唯一決定整棵樹。

本題所有節點 $A$ 至 $I$ 均不重複，因此適用上述定理。

---

解題方法與樹的重建

已知：

• 後序：

$$G,D,B,H,I,E,F,C,A$$

• 中序：

$$D,G,B,A,H,E,I,C,F$$

第一步：找出整棵樹的根

後序走訪的最後一個節點是 $A$，所以：

$$\text{根節點}=A$$

在中序序列中，$A$ 將節點分成：

• 左子樹：$D,G,B$
• 右子樹：$H,E,I,C,F$

因此：

• 左子樹的後序序列為 $G,D,B$
• 右子樹的後序序列為 $H,I,E,F,C$

---

第二步：重建 $A$ 的左子樹

左子樹資料為：

• 後序：$G,D,B$
• 中序：$D,G,B$

後序最後一個節點為 $B$，所以 $B$ 是左子樹的根。

在中序序列 $D,G,B$ 中，$B$ 左側有：

$$D,G$$

右側沒有節點，因此 $B$ 沒有右子樹，且其左子樹包含 $D,G$。

接著處理 $B$ 的左子樹：

• 後序：$G,D$
• 中序：$D,G$

後序最後一個節點為 $D$，所以 $D$ 是此子樹的根。中序中 $D$ 右側有 $G$，因此 $G$ 是 $D$ 的右子節點。

故 $A$ 的左子樹為：

    B
   /
  D
   \
    G

---

第三步：重建 $A$ 的右子樹

右子樹資料為：

• 後序：$H,I,E,F,C$
• 中序：$H,E,I,C,F$

後序最後一個節點為 $C$，所以 $C$ 是右子樹的根。

在中序序列 $H,E,I,C,F$ 中：

• $C$ 左側：$H,E,I$
• $C$ 右側：$F$

因此：

• $C$ 的左子樹後序為 $H,I,E$
• $C$ 的右子樹後序為 $F$

這題要求計算給定二元樹的後序遍歷 (Postorder Traversal) 和層序遍歷 (Level-order Traversal)。

核心觀念：

• 後序遍歷 (Postorder Traversal)： 遍歷順序為 左子樹 -> 右子樹 -> 根節點 (Left -> Right -> Root)。
• 層序遍歷 (Level-order Traversal)： 遍歷順序為 從上到下、從左到右。通常使用佇列 (Queue) 來實現。

給定的樹結構 (根據圖示)：

      A
     / \
    B   C
   /|\ / \
  D E F   G
 / \
H   I

• 根節點是 A。
• A 的左子節點是 B，右子節點是 C。
• B 的左子節點是 D，右子節點是 E。
• C 的左子節點是 F，右子節點是 G。
• D 的左子節點是 H，右子節點是 I。
• E, F, G, H, I 沒有子節點。

1. 後序遍歷 (Postorder Traversal)：
我們按照 Left -> Right -> Root 的順序遍歷。

• 遍歷 A 的左子樹 (B)：
  • 遍歷 B 的左子樹 (D)：
    • 遍歷 D 的左子樹 (H)：
      • H 沒有左子樹。
      • H 沒有右子樹。
      • 訪問 H。 (H)
    • 遍歷 D 的右子樹 (I)：
      • I 沒有左子樹。
      • I 沒有右子樹。
      • 訪問 I。 (H, I)
    • 訪問 D。 (H, I, D)
  • 遍歷 B 的右子樹 (E)：
    • E 沒有左子樹。
    • E 沒有右子樹。
    • 訪問 E。 (H, I, D, E)
  • 訪問 B。 (H, I, D, E, B)
• 遍歷 A 的右子樹 (C)：
  • 遍歷 C 的左子樹 (F)：
    • F 沒有左子樹。
    • F 沒有右子樹。
    • 訪問 F。 (H, I, D, E, B, F)
  • 遍歷 C 的右子樹 (G)：
    • G 沒有左子樹。
    • G 沒有右子樹。
    • 訪問 G。

核心觀念

Merge sort（合併排序）採用「分割—排序—合併」的分治法：

1. 將序列遞迴分割成單一元素。
2. 單一元素視為已排序。
3. 依照大小比較兩個已排序序列，逐步合併成更大的已排序序列。

合併時，每次比較兩個序列目前最前面的元素，將較小者放入結果序列；其中一邊用完後，直接接上另一邊剩餘元素。

其時間複雜度為：

$$T(n)=2T\left(\frac{n}{2}\right)+O(n)=O(n\log n)$$

額外空間複雜度為 $O(n)$。

解題方法

原始序列為：

$$(15,9,3,6,13,8,2,4)$$

先持續二分，直到每組只剩一個元素。

第一步：分割序列

$$(15,9,3,6,13,8,2,4)$$

分成左右兩組：

$$(15,9,3,6)\quad (13,8,2,4)$$

繼續分割：

$$(15,9)\quad (3,6)\quad (13,8)\quad (2,4)$$

最後分割為單一元素：

$$(15)\ (9)\ (3)\ (6)\ (13)\ (8)\ (2)\ (4)$$

第二步：由下而上合併

合併 $(15)$ 與 $(9)$

比較 $15$ 與 $9$：

$$9<15$$

因此：

$$(15)+(9)\rightarrow(9,15)$$

合併 $(3)$ 與 $(6)$

比較 $3$ 與 $6$：

$$3<6$$

因此：

$$(3)+(6)\rightarrow(3,6)$$

合併 $(13)$ 與 $(8)$

比較 $13$ 與 $8$：

$$8<13$$

因此：

$$(13)+(8)\rightarrow(8,13)$$

合併 $(2)$ 與 $(4)$

比較 $2$ 與 $4$：

$$2<4$$

因此：

$$(2)+(4)\rightarrow(2,4)$$

此時得到四組已排序序列：

$$(9,15)\quad(3,6)\quad(8,13)\quad(2,4)$$

第三步：合併兩個元素的排序序列

Suffix Trie 建構

將字串 $S=\text{acbabbabb}$ 的所有後綴插入 Trie，根節點記為 $\varepsilon$。

ε
 ├─a
 │   ├─c─b‑a‑b‑b‑a‑b‑b   (1)
 │   └─b─b
 │       ├─a‑b‑b         (4)
 │       │   └─a‑b‑b     (7)
 │       └─b‑a‑b‑b       (5)
 └─c
     └─b─a‑b‑b‑a‑b‑b      (2)
         └─b‑a‑b‑b        (3)

核心觀念

AVL 樹是具有自我平衡能力的二元搜尋樹，必須同時滿足：

1. 二元搜尋樹性質：左子樹所有鍵值小於根，右子樹所有鍵值大於根。
2. 每個節點的平衡因子必須介於 $-1$ 與 $1$：

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

其中 $h$ 表示子樹高度。

若插入後某節點的 $|BF|=2$，便需進行旋轉：

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

本題每次插入都先依二元搜尋樹規則放置，再由插入點向上檢查平衡因子。

---

解題方法與逐步插入

1. 插入 8

空樹直接以 8 為根。

8

---

2. 插入 9

$9>8$，放在 8 的右側。

8
 \
  9

此時各節點皆平衡。

---

3. 插入 10

$10>8$，再往右；$10>9$，放在 9 的右側。

插入後：

8
 \
  9
   \
    10

節點 8 的平衡因子為：

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

插入發生在右子樹的右側，屬於 RR 型，因此對 8 做左旋：

  9
 / \
8  10

---

4. 插入 2

$2<9$，往左；$2<8$，放在 8 的左側。

   9
  / \
 8  10
/
2

所有節點皆符合 AVL 平衡條件。

---

5. 插入 1

$1<9$、$1<8$、$1<2$，放在 2 的左側。

    9
   / \
  8  10
 /
2
/
1

節點 9 的平衡因子為：

$$BF(9)=3-1=2$$

插入發生在左子樹的左側，屬於 LL 型，因此對 9 做右旋：

    8
   / \
  2   9
 /     \
1       10

---

6. 插入 5

$5<8$、$5>2$，放在 2 的右側。

    8
   / \
  2   9
 / \   \
1   5   10

節點 2 的平衡因子為：

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

節點 8 的平衡因子為：

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

不需旋轉。

---

7. 插入 3

$3<8$、$3>2$、$3<5$，放在 5 的左側。

    8
   / \
  2   9
 / \   \
1   5   10
   /
  3

節點 5 的平衡因子為：

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

節點 2 的平衡因子為：

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

節點 8 的平衡因子仍在 $[-1,1]$ 內，因此不需旋轉。

---

8. 插入 6

$6<8$、$6>2$、$6>5$，放在 5 的右側。

    8
   / \
  2   9
 / \   \
1   5   10
   / \
  3   6

各節點平衡因子：

$$BF(5)=1-1=0$$ $$BF(2)=1-2=-1$$ $$BF(8)=3-2=1$$

所有節點皆平衡，不需旋轉。

---

9. 插入 4

$4<8$、$4>2$、$4<5$、$4>3$，放在 3 的右側。

    8
   / \
  2   9
 / \   \
1   5   10
   / \
  3   6
   \
    4

這題考驗對圖論中最短路徑演算法的理解，特別是計算單源最短路徑問題。由於圖中的邊權都是正數，可以使用 Dijkstra 演算法。

核心觀念：

• Dijkstra 演算法： 一種用於尋找圖中單一源點到所有其他頂點最短路徑的貪心演算法。
• 演算法步驟：
  1. 初始化：源點的距離為 0，所有其他頂點的距離為無限大。使用一個集合 S 記錄已確定最短路徑的頂點，初始為空。使用一個優先佇列 (Priority Queue) 存儲待處理的頂點，按距離排序。
  2. 迭代：當優先佇列不為空時：
     • 從優先佇列中取出距離最小的頂點 u。
     • 將 u 加入集合 S。
     • 對於 u 的所有未在 S 中的鄰居 v：
       • 如果 dist(source, u) + weight(u, v) < dist(source, v)，則更新 dist(source, v) 為 dist(source, u) + weight(u, v)，並更新優先佇列中 v 的距離。
  3. 重複步驟 2 直到優先佇列為空。

給定的圖 (根據圖示，Page 2)：
節點：A, B, C, D, E, F, G
邊及權重：

• A-B: 5
• A-C: 2
• B-D: 1
• B-E: 2
• C-D: 4
• C-F: 1
• D-E: 3
• E-G: 4
• F-G: 2

源點：A

Dijkstra 演算法步驟：

初始化：

• dist(A) = 0
• dist(B) = inf, dist(C) = inf, dist(D) = inf, dist(E) = inf, dist(F) = inf, dist(G) = inf
• S = {} (已確定最短路徑的節點集合)
• Priority Queue (PQ) = {(0, A)} (距離, 節點)

迭代 1：

• 從 PQ 取出 (0, A)。
• u = A, dist(A) = 0.
• S = {A}.
• A 的鄰居：B, C。
  • 更新 B：dist(A) + weight(A, B) = 0 + 5 = 5。由於 5 < inf，更新 dist(B) = 5。PQ 加入 (5, B)。
  • 更新 C：dist(A) + weight(A, C) = 0 + 2 = 2。由於 2 < inf，更新 dist(C) = 2。PQ 加入 (2, C)。
• PQ = {(2, C), (5, B)}

迭代 2：

• 從 PQ 取出 (2, C)。
• u = C, dist(C) = 2.
• S = {A, C}.
• C 的鄰居：D, F。
  • 更新 D：dist(C) + weight(C, D) = 2 + 4 = 6。由於 6 < inf，更新 dist(D) = 6。PQ 加入 (6, D)。
  • 更新 F：dist(C) + weight(C, F) = 2 + 1 = 3。由於 3 < inf，更新 dist(F) = 3。PQ 加入 (3, F)。
• PQ = {(3, F), (5, B), (6, D)}

迭代 3：

• 從 PQ 取出 (3, F)。
• u = F, dist(F) = 3.
• S = {A, C, F}.
• F 的鄰居：G。
  • 更新 G：dist(F) + weight(F, G) = 3 + 2 = 5。由於 5 < inf，更新 dist(G) = 5。PQ 加入 (5, G)。
• PQ = {(5, B), (5, G), (6, D)}

迭代 4：

• 從 PQ 取出 (5, B)。 (假設 B 比 G 先取出，如果 PQ 相同距離會隨機選或按插入順序)
• u = B, dist(B) = 5.
• S = {A, C, F, B}.
• B 的鄰居：D, E。

核心觀念

稀疏矩陣只儲存非零元素，以節省記憶體。每個節點記錄：

$$(\text{列號},\text{欄號},\text{值},\text{next})$$

以下採用「每一列各自形成單向鏈結串列」的表示法，節點依欄號遞增排列。

矩陣乘法的基本公式為：

$$C_{ij}=\sum_k M_{1,ik}M_{2,kj}$$

若以鏈結串列計算，對於 $M_1$ 第 $i$ 列的每個非零節點 $(i,k,a)$，必須找到 $M_2$ 第 $k$ 列的所有非零節點 $(k,j,b)$，再將乘積 $ab$ 累加至 $C_{ij}$。

---

(A) 以鏈結串列表示兩個稀疏矩陣

$M_1$ 的鏈結串列

$$M_1= \begin{bmatrix} 0&10&0&0&12\\ 0&0&0&0&0\\ 0&0&5&0&0\\ 15&12&0&0&0 \end{bmatrix}$$

各列表示如下：

• 第 1 列：$(1,2,10)\rightarrow(1,5,12)\rightarrow\text{NULL}$
• 第 2 列：$\text{NULL}$
• 第 3 列：$(3,3,5)\rightarrow\text{NULL}$
• 第 4 列：$(4,1,15)\rightarrow(4,2,12)\rightarrow\text{NULL}$

完整節點表：

節點	列	欄	值	next
$N_1$	1	2	10	$N_2$
$N_2$	1	5	12	NULL
$N_3$	3	3	5	NULL
$N_4$	4	1	15	$N_5$
$N_5$	4	2	12	NULL

因此 $M_1$ 的列首指標為：

$$\text{rowHead}_{M_1}=[N_1,\text{NULL},N_3,N_4]$$

---

$M_2$ 的鏈結串列

$$M_2= \begin{bmatrix} 0&0&8&0\\ 0&0&0&0\\ 0&0&10&23\\ 0&0&25&0 \end{bmatrix}$$

各列表示如下：

• 第 1 列：$(1,3,8)\rightarrow\text{NULL}$
• 第 2 列：$\text{NULL}$
• 第 3 列：$(3,3,10)\rightarrow(3,4,23)\rightarrow\text{NULL}$
• 第 4 列：$(4,3,25)\rightarrow\text{NULL}$

完整節點表：

節點	列	欄	值	next
$P_1$	1	3	8	NULL
$P_2$	3	3	10	$P_3$
$P_3$	3	4	23	NULL
$P_4$	4	3	25	NULL

因此 $M_2$ 的列首指標為：

$$\text{rowHead}_{M_2}=[P_1,\text{NULL},P_2,P_4]$$

---

(B) 矩陣乘法的維度檢查

題目給定：

• $M_1$ 是 $4\times5$ 矩陣；
• $M_2$ 是 $4\times4$ 矩陣。

矩陣乘法 $M_1M_2$ 必須滿足：

$$(4\times5)(5\times4)$$

但目前題目實際給的是：

$$(4\times5)(4\times4)$$

中間維度 $5$ 與 $4$ 不相等，因此依照題面資料，$M_1\times M_2$ 沒有定義，無法直接計算。