114 年 國立成功大學智慧資訊安全碩士學位學程《資料結構》

解題步驟

1. 設 $B$ 為 $A(1,1)$ 的起始位址，元素大小 $s=2$。
   假設採用 Column‑major 佈局（因 Row‑major 會得到負的欄數），則

$\text{addr}(i,j)=B+ \big[(j-1)\cdot M+(i-1)\big]\times s$

其中 $M$ 為列數（行數）。

2. 由已知兩點建立方程式

$$\begin{cases} 1115 = B+[(2-1)M+(3-1)]\times2 = B+ (M+2)\times2 = B+2M+4\\[4pt] 1207 = B+[(3-1)M+(2-1)]\times2 = B+ (2M+1)\times2 = B+4M+2 \end{cases}$$

• 從後序 $EFBCDA$ 取最後一個節點為根：A。
• 在中序 $EF\underline{A}CBD$ 以 A 為界，左子樹中序為 $EF$，右子樹中序為 $CBD$。

左子樹

• 後序對應為前兩個字元 $EF$，根為最後一個 F。
• 中序 $E\underline{F}$，左子樹僅有節點 E，右子樹空。

右子樹

• 後序剩餘 $BCD$，根為最後一個 D。
• 中序 $CB\underline{D}$，左子樹中序為 $CB$，右子樹空。

核心觀念

廣度優先搜尋（BFS）從起點開始，依照相鄰串列的字母順序逐層探索。搜尋樹中的邊稱為樹邊；原圖中未被選為樹邊的邊，若連接的兩個頂點彼此都不是對方在搜尋樹中的祖先，便是交叉邊（cross edge）。

解題方法

由圖可讀出，從 $C$ 出發可依序到達 $A、B、D$。按照字母順序處理相鄰頂點，BFS 搜尋樹的層次為：

• 第 0 層：$C$
• 第 1 層：$A、B、D$
• 第 2 層：$E、F$

因此，樹邊為 $C\to A$、$C\to B$、$C\to D$，以及 $D\to E$、$D\to F$。第 1 層的 $A、B、D$ 互為同層頂點；第 2 層的 $E、F$ 也互為同層頂點。選項所列的四條邊都不是搜尋樹邊，且各自連接的端點互不為祖先或後代，所以都是交叉邊。

選項分析

核心觀念

本題考查遞迴式的漸進時間複雜度，主要使用 Master Theorem。

標準形式為：

$$T(n)=aT\left(\frac{n}{b}\right)+f(n)$$

其中：

• $a=3$：每次遞迴產生 3 個子問題
• $b=4$：每個子問題的規模為 $n/4$
• $f(n)=n\log n$：分割與合併等非遞迴工作的成本

首先計算臨界函數：

$$n^{\log_b a}=n^{\log_4 3}$$

因為：

$$\log_4 3\approx 0.792$$

所以：

$$n^{\log_4 3}=n^{0.792}$$

接著比較 $f(n)=n\log n$ 與 $n^{0.792}$ 的成長速度。

由於 $n\log n$ 的成長速度大於 $n^{0.792}$，因此遞迴外成本 $n\log n$ 會主導整體複雜度。

---

解題方法：套用 Master Theorem

Master Theorem 的第三種情況是：

若存在常數 $\varepsilon>0$，使得

$$f(n)=\Omega\left(n^{\log_b a+\varepsilon}\right)$$

且滿足正規性條件：

$$af\left(\frac{n}{b}\right)\leq cf(n)$$

其中 $c<1$，則：

$$T(n)=\Theta(f(n))$$

本題中：

$$f(n)=n\log n$$

而：

$$n^{\log_4 3}=n^{0.792}$$

可取 $\varepsilon$ 為任意小於 $0.208$ 的正數，例如 $\varepsilon=0.1$，則：

$$n\log n=\Omega(n^{0.892})$$

因此符合第三種情況。

再驗證正規性條件：

$$3f\left(\frac n4\right) =3\left(\frac n4\log\frac n4\right)$$

利用對數公式：

$$\log\frac n4=\log n-\log4$$

因此：

核心觀念

最大堆須符合：每個父節點的值都不小於子節點。以陣列表示時，索引 $i$ 的左右子節點分別在 $2i$ 與 $2i+1$。

刪除最大值時，先移除根節點，再把堆中最後一個元素移到根部，逐層與較大的子節點交換，直到恢復最大堆性質。

解題方法

原卷圖中，索引 $[0]$ 是空位，堆的元素從 $[1]$ 開始：索引 $[1]$ 到 $[7]$ 依序為 $75,58,67,42,55,30,29$。刪除根節點 $75$ 後，堆大小由 $7$ 減為 $6$。

1. 將最後一個元素 $29$ 移到根部，並移除原索引 $[7]$ 的元素：$[29,58,67,42,55,30]$。
2. 根節點 $29$ 的子節點是 $58$ 和 $67$。與較大的 $67$ 交換：$[67,58,29,42,55,30]$。
3. 索引 $[3]$ 的 $29$ 只有索引 $[6]$ 的子節點 $30$；索引 $[7]$ 已超出堆的範圍。將 $29$ 與 $30$ 交換，得到 $[67,58,30,42,55,29]$。

核心觀念

本題綜合考查：

• 二元樹深度與最大節點數
• MSD／LSD 基數排序
• Merge sort 是否為就地排序
• 二元樹的 threaded links 數量
• 複選題中「以上皆正確」的判斷

解題方法

逐一檢查各敘述是否符合標準定義與定理。只要有一個敘述錯誤，選項 e「以上敘述皆正確」也必定錯誤。

選項分析

a) 正確

若二元樹根節點深度定義為 $0$，則深度為 $k$ 的滿二元樹共有：

$$1+2+2^2+\cdots+2^k =\sum_{i=0}^{k}2^i =2^{k+1}-1$$

因此，深度為 $k$ 的二元樹最多有 $2^{k+1}-1$ 個節點。題目給定 $k\ge 1$，敘述成立。

b) 錯誤

MSD（Most Significant Digit first）由最高位開始排序；LSD（Least Significant Digit first）由最低位開始排序。

LSD 基數排序通常採用穩定排序，依序處理各位數即可，流程較單純。MSD 則從最高位開始分組，之後還要對各分組遞迴處理，實作與控制流程通常較複雜。

因此，題目所述「MSD 比 LSD 簡單」不正確。

c) 正確

核心觀念

本題考兩個步驟：先用 Median-of-3 選出 pivot，再透過 partition 將資料分到 pivot 兩側。完成分割後，pivot 左側的值都小於 pivot，右側的值都大於 pivot。

解題方法

題目給定 $left=1$、$right=9$，所以

$$middle=\left\lfloor\frac{1+9}{2}\right\rfloor=5$$

三個候選值為 $key[1]=75$、$key[5]=55$、$key[9]=3$，其中位數是 $55$。依題意將它與 $key[1]$ 交換，讓 pivot $55$ 位於分割範圍的左端。

接著計算有幾個值小於 $55$：$58$、$67$、$75$、$95$ 大於 $55$；$42$、$30$、$29$、$3$ 小於 $55$，共有 $4$ 個。因此 pivot 分割完成後，應位於第 $1+4=5$ 個位置，也就是 $key[5]$。

以常見的雙指標分割法操作，分割後可得到：

$$[30,\ 3,\ 29,\ 42,\ \boxed{55},\ 75,\ 67,\ 95,\ 58]$$

核心觀念

題目描述「一開始每個節點各自成一個集合，再依序合併節點集合，遇到兩端已在同一集合的邊就會形成環」，這是 Kruskal 演算法搭配不相交集合（Disjoint Set）的作法。Prim 演算法則是從一個起點逐步擴張，不是依序合併所有節點的集合。

Kruskal 依邊權重由小到大檢查；若邊的兩端已在同一集合，加入該邊就會形成環。

解題方法

圖中相關的邊依權重由小到大排列如下：

$$(4,5):7,\quad (0,5):10,\quad (2,3):12,\quad (1,2):16,\quad (0,6):18,\quad (4,6):20$$

一開始有 $7$ 個集合，分別包含節點 $0$ 到 $6$。依序加入前五條邊後，集合變化為：

• 加入 $(4,5)$：集合數由 $7$ 變 $6$。
• 加入 $(0,5)$：集合數由 $6$ 變 $5$。
• 加入 $(2,3)$：集合數由 $5$ 變 $4$。
• 加入 $(1,2)$：集合數由 $4$ 變 $3$。
• 加入 $(0,6)$：集合數由 $3$ 變 $2$。

核心觀念

本題比較最大堆積與二元搜尋樹在優先佇列、字典查詢、插入及找最大值時的操作效率。題目兩處寫「Binary search」，但因選項提到插入操作，以下依常見考題用法，將它視為「二元搜尋樹（Binary Search Tree, BST）」。

• 最大堆積的根節點是最大值，插入需向上調整。
• 二元搜尋樹的查詢、插入及找最大值，時間取決於樹高 $h$；平衡時約為 $O(\log n)$，退化時可能為 $O(n)$。

解題方法

逐項比對各操作的用途與時間複雜度：

操作	最大堆積	二元搜尋樹
插入	$O(\log n)$	平衡時 $O(\log n)$；最壞 $O(n)$
找最大值	$O(1)$，直接看根節點	$O(h)$，沿右子樹走到最右側節點

最大堆積特別適合快速取得最大值，也適合實作優先佇列。插入方面，二元搜尋樹沒有比堆積更快的普遍保證。

選項分析

• a) Heap is suitable for a priority queue. 正確。
  最大堆積可在 $O(1)$ 取得最高優先權的元素，並能在 $O(\log n)$ 插入或刪除最大值，因此適合實作優先佇列。

核心觀念

以循環鏈結串列（circular linked list）實作 Queue 時，通常維護一個 rear 指標：

• 隊首 front = rear->next
• 從隊尾加入元素（enqueue / Push）
• 從隊首移除元素（dequeue / Pop）
• rear = NULL 表示佇列為空

循環結構可讓隊首與隊尾相鄰，因此加入與移除元素都能在固定次數的指標操作內完成。時間複雜度如下：

$$\text{Push} = O(1), \qquad \text{Pop} = O(1), \qquad \text{isEmpty} = O(1)$$

但若要尋找特定元素，必須從隊首逐一走訪，最壞情況可能檢查整個佇列：

$$\text{Find} = O(n)$$

其中 $n$ 為佇列中的元素數量。

解題方法

判斷各操作是否需要線性時間，重點在於：

1. 操作是否只需修改或檢查固定數量的指標。
2. 操作是否必須逐一走訪所有節點。

循環鏈結串列的 rear 指標可直接定位隊尾，而 rear->next 可直接定位隊首。因此 Push() 和 Pop() 不需要搜尋整個串列。

Find() 則必須從隊首開始，依序比較節點內容。若目標元素位於最後一個節點，或根本不存在，就需要走訪 $n$ 個節點，因此最壞時間為：

$$T(n) = O(n)$$

選項分析

哈希表設定

• 桶數 = 11 (0 ~ 10)
• 雜湊函式 $h(key)=key\ \bmod\ 11$
• 使用鏈結法 (chaining)

依序插入資料並記錄衝突次數

資料	$h(key)$	桶內已有元素數	衝突比較次數
3	3	0	0
41	8	0	0
15	4	0	0
36	3	1 (3)	1

使用雙雜湊的開放定址法：

• 主雜湊 $h_1(key)=\text{key}\bmod 11$
• 次雜湊 $h_2(key)=\text{key}\bmod 7$
• 實際探測位置 $h(key)=\bigl(h_1(key)+i\cdot h_2(key)\bigr)\bmod 11,\qquad i=0,1,2,\dots$

對鍵值 $58$：

1. 初始位置
   $h_1(58)=58\bmod 11=3$
2. 次雜湊步長
   $h_2(58)=58\bmod 7=2$

核心觀念

本題考查最短路徑演算法對「負權重邊」的處理能力。負權重邊的權重小於 $0$；這和「負權重環」不同。負權重環會讓路徑成本持續下降，因而沒有有限的最短路徑。

Dijkstra 演算法的貪婪策略會將目前距離最小的頂點定案，並假設之後不會再找到更短的路徑。這個假設要求邊權重皆為非負；若有負權重邊，已定案的距離可能被後續路徑改寫。

解題方法

原卷第 13 題詢問哪個演算法「不能允許負權重邊」來求最短路徑，選項依序是 Johnson、Bellman-Ford、Floyd-Warshall、Dijkstra 與「以上皆非」。判斷關鍵是：負權重邊會不會破壞演算法的核心步驟。

以 $s\to a$ 權重 $2$、$s\to b$ 權重 $5$、$b\to a$ 權重 $-10$ 為例。Dijkstra 會先將距離為 $2$ 的 $a$ 定案，但經過 $b$ 到 $a$ 的路徑成本是 $5+(-10)=-5$，比 $2$ 更小。這表示 Dijkstra 的貪婪定案在負權重邊存在時可能失效。

選項分析

• (A) Johnson's algorithm：錯。 Johnson 演算法可處理負權重邊，通常先用 Bellman-Ford 計算頂點勢能，再重新加權，使邊權重非負，之後使用

核心觀念

二元樹中，每個節點的度數是其子女數，因此節點度數只能是 $0$、$1$ 或 $2$。度數為 $0$ 的節點就是葉節點，題目以 $n_0$ 表示其數量。

解題方法

題目給定一棵非空二元樹，共有 $n$ 個節點，其中 $n_0$ 個是葉節點；要求度數為 $1$ 的節點數。非空樹共有 $n-1$ 條邊，而每條邊都從一個節點連向其子女。

設度數為 $1$、$2$ 的節點數分別為 $n_1$、$n_2$。依節點總數與邊數建立關係：

$$n_0+n_1+n_2=n$$ $$n_1+2n_2=n-1$$

由第一式得 $n_2=n-n_0-n_1$，代入第二式：

$$n_1+2(n-n_0-n_1)=n-1$$

整理可得：

$$n_1=n-2n_0+1$$

核心觀念

本題考最大流與最小割定理：網路中的最大流量，等於所有 $S$-$T$ 割中最小的割容量。割容量是從割的 $S$ 側指向 $T$ 側的所有邊容量總和；反向邊不計入。

解題方法

圖中由 $S$ 指向上方左節點的容量為 $4$，由 $S$ 指向下方左節點的容量為 $6$；下方左節點指向下方右節點的容量為 $3$。斜邊方向為上方左節點指向下方右節點、容量 $1$，以及下方右節點指向上方左節點、容量 $8$。

先取一組可行流量：

• $S$ 至上方左節點送 $4$，其中 $3$ 沿上方水平邊到上方右節點，再送至 $T$；另 $1$ 沿容量為 $1$ 的斜邊到下方右節點，再送至 $T$。
• $S$ 至下方左節點送 $3$，再沿容量為 $3$ 的邊到下方右節點，最後送至 $T$。

核心觀念

本題考的是遞迴函式的呼叫次數分析。Fibonacci 函式以遞迴方式計算費氏數列，由於存在大量重疊子問題（overlapping subproblems），導致呼叫次數呈指數成長。題目要求計算 Fibonacci(10) 所「產生」的遞迴呼叫次數。

---

解題方法

從原卷頁圖確認程式碼為：

int Fibonacci(int n) {
    if (n < 1) return 0;
    if (n < 3) return 1;

圖上只列出兩個基底條件，未明確寫出遞迴式。依標準 Fibonacci 遞迴定義，補上：

    return Fibonacci(n - 1) + Fibonacci(n - 2);
}

題目問的是 Fibonacci(10) 會**產生（generate）**多少次遞迴呼叫。注意：最初的 Fibonacci(10) 本身不算被「產生」的遞迴呼叫，只有它內部衍生出來的呼叫才算。

定義 $C(n)$ 為呼叫 Fibonacci(n) 時產生的遞迴呼叫總次數（含所有子孫呼叫）。

• 當 $n < 1$ 或 $1 \le n < 3$ 時，直接 return，不產生任何遞迴呼叫，故 $C(0) = C(1) = C(2) = 0$。
• 當 $n \ge 3$ 時，Fibonacci(n) 呼叫 Fibonacci(n-1) 和 Fibonacci(n-2)，這本身就是 2 次呼叫，再加上這兩個子呼叫各自內部產生的呼叫數：

$$C(n) = 2 + C(n-1) + C(n-2)$$

逐步計算：

$n$	$C(n)$
0	0
1	0
2	0
3	$2 + C(2) + C(1) = 2 + 0 + 0 = 2$
4	$2 + C(3) + C(2) = 2 + 2 + 0 = 4$
5	$2 + C(4) + C(3) = 2 + 4 + 2 = 8$
6	$2 + C(5) + C(4) = 2 + 8 + 4 = 14$
7	$2 + C(6) + C(5) = 2 + 14 + 8 = 24$

核心觀念

循環單向串列的尾端指標 last 指向最後一個節點，而 last->link 指向第一個節點。要在串列前端插入新節點，非空時須讓新節點接到原本的第一個節點，再讓 last->link 改指向新節點；空串列則讓新節點的 link 指回自己，並將 last 設為新節點。

解題方法

圖中 last 指向尾端節點，尾端節點的 link 繞回第一個節點。依此結構，非空時保留原本的尾端節點，只更新新節點與 last->link；空串列時，新節點同時是第一個與最後一個節點。

核心觀念

本題考無向圖的割點與雙連通分量。

• 若移除頂點 $u$ 後，圖的連通分量數增加，$u$ 就是割點。
• 雙連通分量是無法再拆成更小雙連通子圖的部分；依常見定義，橋邊也單獨算一個分量。
• 使用 DFS 判斷時，令 $\operatorname{disc}[u]$ 為頂點 $u$ 的發現時間，$\operatorname{low}[u]$ 為從 $u$ 的 DFS 子樹經由樹邊與至多一條回邊可到達的最早發現時間。
• 非根節點 $u$ 若有 DFS 子節點 $v$ 滿足 $\operatorname{low}[v]\geq \operatorname{disc}[u]$，則 $u$ 是割點。DFS 根節點則須有至少兩個 DFS 樹子節點才是割點。

解題方法

圖中可讀出上方有三角形 $1$、$2$、$3$，頂點 $2$ 以邊 $2$–$8$ 接到下方；中間的頂點 $5$、$8$、$9$ 形成三角形；頂點 $4$、$5$、$6$、$7$ 之間的邊構成完整圖 $K_4$。

以頂點 $1$ 為 DFS 根，依序走訪 $1,2,3,8,9,5,4,6,7$。依 DFS 樹與回邊可得：

頂點 $u$	$\operatorname{disc}[u]$	$\operatorname{low}[u]$
$1$	1	1
$2$	2	1
$3$	3	1
$8$	4	4