1
考點：一般樹轉 Binary Tree 表示法：Single-Child 節點左右子判定與走訪序列對應
(a)（如簡答圖）
(b)（如簡答圖-2）
2有向圖相鄰矩陣／串列與弱連通分量（Isolated Parts）計數
考點：圖形的儲存表示法：Adjacency Matrix／Adjacency List／Incidence Matrix、弱連通元件（Weakly Connected Component）計數：忽略邊方向的 DFS／BFS 走訪
(a) 相鄰矩陣（列＝from，欄＝to）：
| 1 | 2 | 3 | 4 | 5 | 6 | |
|---|---|---|---|---|---|---|
| 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 |
相鄰串列：／／／／／
(b)
count = 0
visited = {}
for each vertex v in V:
if v not in visited:
count += 1
traverse_ignoring_direction(v, visited)
return count
traverse_ignoring_direction(v, visited): // 把有向邊當無向邊走的 DFS
visited.add(v)
for each u with edge v→u or u→v:
if u not in visited:
traverse_ignoring_direction(u, visited)
3
考點：AVL Tree 插入與四種旋轉（LL／RR／LR／RL）調整規則
（如簡答圖）
4
考點：Expression Tree 建構：由中序運算式依運算子優先權建樹、三種走訪順序的定義與追蹤方法
（如簡答圖）
void preorder(Node* T) {
if (T != NULL) {
visit(T);
preorder(T->left);
preorder(T->right);
}
}
5(a)Recursion Base Case，f(n)=3^n
考點：遞迴（Recursion）基本概念：分而治之與 Base Case
邊界條件： 時 。
int f(int n) {
if (n == 1) return 3;
return 3 * f(n - 1);
}
5(b)f(n)=3^n 遞迴程式
考點：遞迴（Recursion）基本概念：分而治之與 Base Case
int f(int n) {
if (n == 1)
return 3;
else
return 3 * f(n - 1);
}
6Dijkstra's Algorithm 與最小成本生成樹
考點：Minimum Spanning Tree（MST）與求解演算法（Kruskal's、Prim's）、最短路徑演算法比較表（DAG、Dijkstra's、Bellman-Ford's、Floyd-Warshall's）
(a)
Dijkstra(G, source):
for each vertex v in G:
dist[v] = infinity; visited[v] = false
dist[source] = 0
while exists unvisited vertex:
u = unvisited vertex with minimum dist[u]
visited[u] = true
for each neighbor v of u:
if not visited[v] and dist[u]+weight(u,v) < dist[v]:
dist[v] = dist[u]+weight(u,v)
parent[v] = u
return dist[], parent[]
(b) 邊：0-1(4)、0-7(8)、7-6(1)、6-5(2)、5-2(4)、2-8(2)、2-3(7)、3-4(9)，總成本 37。
7Bellman-Ford Algorithm 求最短路徑
考點：最短路徑演算法比較表（DAG、Dijkstra's、Bellman-Ford's、Floyd-Warshall's）
(a)
BellmanFord(G, source):
for each vertex v: dist[v] = infinity; parent[v] = nil
dist[source] = 0
for i = 1 to |V|-1: # 逐輪放寬「路徑可用的邊數上限」
for each edge (u,v,w) in G:
if dist[u]+w < dist[v]:
dist[v] = dist[u]+w
parent[v] = u
for each edge (u,v,w) in G: # 第 V 輪仍能鬆弛即存在負長度 cycle
if dist[u]+w < dist[v]: report "negative cycle"
return dist[], parent[]
(b) ，總成本 19。