110 年 國立臺灣聯合大學系統（清華、政治、陽明交通、中央四校聯招）研究所電機類《資料結構》

核心觀念

本題考查兩種字串比對方法：

1. 暴力字串比對（Brute-Force Matching）：逐一假設比對起點，從頭比較樣式字串 $P$ 與文字字串 $S$。
2. KMP（Knuth–Morris–Pratt）演算法：利用模式字串 $P$ 的前綴資訊，避免失敗後重新比較已經確認過的字元。

設：

• $N_P$：模式字串 $P$ 的長度
• $N_S$：文字字串 $S$ 的長度

---

（a）時間複雜度為 $O(N_P \cdot N_S)$ 的字串比對演算法

可使用暴力法。從 $S$ 的每一個可能起點開始，逐字比較 $P$ 與 $S$ 的對應內容。

int bruteForceMatch(char S[], int NS, char P[], int NP) {
    int i, j;

    for (i = 0; i <= NS - NP; i++) {
        j = 0;

        while (j < NP && S[i + j] == P[j]) {
            j++;
        }

        if (j == NP) {
            return i;   // 找到 P，回傳起始位置
        }
    }

    return -1;          // 找不到 P
}

其中，$i$ 表示目前在 $S$ 中嘗試的比對起點，$j$ 表示目前比對到 $P$ 的第幾個字元。

時間複雜度分析

最多有 $N_S-N_P+1$ 個可能的起點。對每一個起點，最壞情況可能比較完整個 $P$，因此最多比較：

$$(N_S-N_P+1)N_P$$

將其以大 $O$ 表示：

$$O\big((N_S-N_P+1)N_P\big)=O(N_PN_S)$$

例如，當 $S$ 與 $P$ 的前面許多字元都相同，直到最後一個字元才不相等時，每個起點都會產生大量重複比較，便會達到此最壞情況。

空間複雜度

除了輸入字串外，只使用 $i$、$j$ 等少量變數：

$$O(1)$$

---

（b）KMP 演算法的時間複雜度

KMP 的核心是建立模式字串 $P$ 的前綴函數，也常稱為 failure function 或部分匹配表。

對於 $P[0 \ldots j]$，定義：

$$\pi[j] = \text{既是 }P[0 \ldots j]\text{ 的前綴，也是其後綴的最長長度}$$

核心觀念

本題考查單向鏈結串列的走訪與節點重新連接。

每個節點包含：

• value：節點資料
• link：指向下一個節點的指標

若要將最小值節點移到串列前端，必須掌握兩個指標：

1. minItem：目前找到的最小值節點
2. minPrev：minItem 的前一個節點

單向鏈結串列只能由前往後走訪，因此必須保存最小節點的前驅，才能將它從原位置移除。

---

解題方法

先從 list->front 開始走訪整個串列：

1. 以第一個節點作為目前最小節點。
2. 逐一比較後續節點的 value。
3. 若找到更小的值，更新 minItem 與 minPrev。
4. 走訪結束後：
   • 若最小節點本來就是第一個節點，不需處理。
   • 否則先將最小節點從原位置摘除，再插入串列前端。

假設串列為：

A -> B -> C -> D

其中 C 是最小值節點，則：

minPrev->link = minItem->link;
minItem->link = list->front;
list->front = minItem;

結果為：

C -> A -> B -> D

原本其他節點 A、B、D 的相對順序仍保持不變。

---

C 程式碼

核心觀念

Queue（佇列）遵守先進先出（FIFO）：

• Q.pop()：移除佇列前端元素。
• Q.push(x)：將元素加入佇列尾端。

Stack（堆疊）遵守後進先出（LIFO）：

• T.push(x)：將元素放入堆疊頂端。
• T.pop()：移除堆疊頂端元素。

題目的關鍵在於：先將佇列中的元素依序取出並放入堆疊，元素順序會被堆疊的 LIFO 特性反轉；再將堆疊元素依序取出放回佇列，即可得到反轉後的佇列。

---

解題方法

假設原本佇列為：

$$Q=[a_1,a_2,\ldots,a_n]$$

其中 $a_1$ 位於佇列前端，$a_n$ 位於佇列尾端。

第一階段，反覆執行：

$$T.push(Q.pop())$$

元素移動順序為：

$$a_1,a_2,\ldots,a_n$$

放入堆疊後，堆疊頂端為 $a_n$，因此從堆疊取出時會依序得到：

$$a_n,a_{n-1},\ldots,a_1$$

第二階段，反覆執行：

$$Q.push(T.pop())$$

由於取出順序是 $a_n$ 到 $a_1$，放回佇列後，佇列前端至尾端便成為：

$$[a_n,a_{n-1},\ldots,a_1]$$

---

虛擬碼

ReverseQueue(Q, T):
    while Q is not empty:
        T.push(Q.pop())

    while T is not empty:
        Q.push(T.pop())

演算法結束後，$Q$ 即為原佇列的反轉結果，$T$ 為空。

---

操作示例

原佇列：

$$Q=[1,2,3,4]$$

第一階段：

操作	$Q$	$T$
T.push(Q.pop())	$[2,3,4]$	$[1]$
T.push(Q.pop())	$[3,4]$	$[1,2]$
T.push(Q.pop())	$[4]$	$[1,2,3]$
T.push(Q.pop())	$[]$	$[1,2,3,4]$

此時堆疊頂端為 $4$。

第二階段：

參考書等級：大學一年級二年級教材；適用於資料結構課本（如《Data Structures and Algorithm參考書等級：大學一年級二年級教材；適用於資料結構課本（如《Data Structures and Algorithm Analysis in C》）的實作章節。

(a) 使用 available‑space list 的優點

• 只需把刪除的節點搬入可用空間鏈表，未觸發 free，降低記憶體分配/釋放的系統呼叫次數，減少碎片化與執行時間開銷。
• 新增節點時若可用空間鏈表非空，可直接從該鏈表取用，省去 malloc，提升插入效能。

(b) clear：將一個已使用的鏈表內容全部清空，使其大小為 $0$，時間複雜度 $O(1)$

procedure clear(L)               // L 為欲清空的鏈表
    if L.head = NIL then return
    // 將整條使用中的鏈表接到 available‑space list
    L.tail.next ← avail.head
    avail.head ← L.head
    // 重置 L
    L.head ← NIL
    L.tail ← NIL
    L.size ← 0
end procedure

• avail 為全域的可用空間鏈表，head、tail 為指向首尾節點的指標。
• 所有舊節點一次性掛接到 avail，不需遍歷，故為 $O(1)$。

核心觀念

本題考查以堆疊（stack）實作迷宮走法，以及其與深度優先搜尋（Depth-First Search, DFS）和遞迴的關係。

堆疊遵守後進先出（Last In, First Out, LIFO）：

$$\text{最後走入的格子} \rightarrow \text{最先退回}$$

迷宮搜尋通常採用「沿著一條路徑盡量深入；遇到死路便退回上一個岔路」的回溯（backtracking）策略。堆疊正好能保存目前路徑上的岔路資訊，使搜尋能回到最近的可選位置。

---

解題方法

（a）使用堆疊的目的

堆疊的主要目的有兩個：

1. 保存目前搜尋路徑

   每走到一個新的格子，就將該格子的資訊存入堆疊。堆疊內容代表從起點到目前位置的路徑。

2. 支援回溯

   當目前格子沒有任何尚未嘗試的相鄰格子時，表示走到死路。此時將堆疊頂端資料取出，即可退回最近經過的岔路，繼續嘗試其他方向。

因此，堆疊將迷宮搜尋由「深入」與「退回」兩種動作串接起來，實作出深度優先搜尋。

---

（b）移動到新格子時應存入哪些資訊

至少必須將新格子的位置資訊存入堆疊，例如：

• 行座標與列座標 $(r,c)$；
• 或代表該格子的索引值；
• 必要時再記錄前一格位置、進入方向，或下一個待嘗試的方向。

較完整的堆疊元素可表示為：

$$(r,c,\text{nextDirection})$$

其中：

• $(r,c)$ 表示目前格子的位置；
• nextDirection 表示下一次要嘗試的方向，避免回溯後重複嘗試已失敗的方向。

若只要求說明基本資訊，答案為「新格子的座標」。但若要正確完成回溯搜尋，還必須能知道該格子尚有哪些方向尚未嘗試；這項資訊可直接存入堆疊，也可由其他陣列維護。

典型流程如下：

1. 將起點座標壓入堆疊，並標記為已拜訪。
2. 查看堆疊頂端格子的相鄰方向。
3. 若找到可走的新格子，將新格子的座標壓入堆疊。
4. 若沒有可走方向，將頂端格子彈出，回到前一個格子。
5. 堆疊頂端為終點時，即得到一條路徑。

若以座標 $(r,c)$ 表示格子，方向可寫成：

$$\Delta=\{(-1,0),(1,0),(0,-1),(0,1)\}$$

分別代表上、下、左、右四個方向。新位置為：

$$(r',c')=(r+\Delta r,\ c+\Delta c)$$

只有在 $(r',c')$ 位於迷宮範圍內、不是牆壁，且尚未拜訪時，才可將其壓入堆疊。

---

（c）是否能使用遞迴解題

核心觀念

本題比較兩種搜尋方法：

1. Binary Search（二分搜尋）：在已排序、可透過索引直接存取的序列中搜尋。
2. Binary Search Tree Search（二元搜尋樹搜尋）：利用二元搜尋樹的鍵值排列性質，沿著根至葉的路徑搜尋。

兩者都利用「每次比較後排除一半搜尋範圍」的概念，但資料結構限制與最壞時間複雜度不同。

---

解題方法

一、Binary Search

假設有一個依遞增順序排列的陣列：

$$A[0] \leq A[1] \leq \cdots \leq A[n-1]$$

搜尋目標值 $x$ 時，設定目前搜尋範圍為 $[low, high]$，每次取中間位置：

$$mid=\left\lfloor\frac{low+high}{2}\right\rfloor$$

比較 $A[mid]$ 與 $x$：

• 若 $A[mid]=x$，搜尋成功。
• 若 $x<A[mid]$，只需搜尋左半部，令 $high=mid-1$。
• 若 $x>A[mid]$，只需搜尋右半部，令 $low=mid+1$。

每次比較都約刪除一半候選資料，因此最多需要比較的次數為：

$$\lfloor \log_2 n \rfloor+1$$

時間複雜度為：

• 最佳情況：$O(1)$，第一次比較即找到。
• 平均情況：$O(\log n)$。
• 最壞情況：$O(\log n)$。

Binary Search 的關鍵限制是：

1. 資料必須已排序。
2. 資料結構必須支援有效率的中間元素存取，通常使用陣列。
3. 若使用 linked list，即使能定位邏輯上的中間節點，尋找該節點仍需走訪節點，無法維持標準的 $O(\log n)$ 效率。

若採用迭代寫法，額外空間為 $O(1)$；若採用遞迴寫法，遞迴深度為 $O(\log n)$。

---

二、Searching on a Binary Search Tree

二元搜尋樹必須符合以下性質。對任一節點 $v$：

• 左子樹所有鍵值小於 $v.key$。
• 右子樹所有鍵值大於 $v.key$。
• 左、右子樹本身也都必須是二元搜尋樹。

搜尋目標值 $x$ 時，從根節點開始：

• 若目前節點為空，搜尋失敗。
• 若目前節點鍵值等於 $x$，搜尋成功。
• 若 $x$ 小於目前節點鍵值，往左子樹搜尋。
• 若 $x$ 大於目前節點鍵值，往右子樹搜尋。

每次比較只沿著一條根至葉路徑前進，因此搜尋時間與樹高 $h$ 成正比：

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

若樹為平衡狀態，樹高約為：

$$h=O(\log n)$$

因此：

• 最佳情況：$O(1)$，根節點即為搜尋目標。
• 平衡樹的平均及最壞情況：$O(\log n)$。
• 未平衡樹的最壞情況：$O(n)$。

例如，依序插入 $1,2,3,4,5$，會形成近似鏈狀結構：

$$1\rightarrow 2\rightarrow 3\rightarrow 4\rightarrow 5$$

此時樹高為 $n-1$，搜尋退化成循序搜尋，時間複雜度為 $O(n)$。

二元搜尋樹不要求資料先以陣列排序，也不要求連續記憶體。它通常以節點與指標表示，因此適合動態插入與刪除。

核心觀念

Heap（堆積）是一棵符合以下條件的完全二元樹：

1. 除最後一層外，每一層皆填滿。
2. 最後一層的節點由左至右排列。
3. 滿足 heap-order property：
   • Max-heap：父節點值 $\geq$ 子節點值。
   • Min-heap：父節點值 $\leq$ 子節點值。

Heap 的重點不在於維護一般二元樹的搜尋結構，而在於快速取得最大值或最小值，並支援插入、刪除根節點等操作。

由於完全二元樹的形狀固定且規則，最適合使用陣列儲存。

---

解題方法

將完全二元樹以層序排列存入陣列。若採用 1-based indexing，節點位於位置 $i$ 時：

$$\text{parent}(i)=\left\lfloor \frac{i}{2}\right\rfloor$$ $$\text{left}(i)=2i$$ $$\text{right}(i)=2i+1$$

例如：

              A
           /     \
          B       C
        /  \     /  \
       D    E   F    G

可存成：

index:  1  2  3  4  5  6  7
value:  A  B  C  D  E  F  G

所有節點都能透過索引直接找到父節點與子節點，不需要額外儲存 left pointer、right pointer 或 parent pointer。

若採用 0-based indexing，則公式改為：

$$\text{parent}(i)=\left\lfloor \frac{i-1}{2}\right\rfloor$$ $$\text{left}(i)=2i+1$$ $$\text{right}(i)=2i+2$$

---

為何使用陣列而非鏈結串列

1. 完全二元樹不需要儲存指標

一般鏈結式二元樹需要為每個節點儲存：

• 資料欄位
• 左子節點指標
• 右子節點指標
• 有時還需要父節點指標

但 heap 的樹形由「完全二元樹」性質決定，子節點位置可以直接由索引公式計算，因此陣列不必額外儲存這些指標。

這能降低記憶體使用量，也讓資料結構更簡潔。

---

2. 陣列能直接取得父子節點

Heap 的核心操作包括：

• 向上調整（percolate up）
• 向下調整（percolate down）
• 插入新元素
• 刪除最小值或最大值

這些操作都必須反覆比較節點與父節點、子節點。

使用陣列時，父子關係只需透過索引計算。例如節點在位置 $i$：

$$\text{parent}(i)=\left\lfloor \frac{i}{2}\right\rfloor$$

因此不需沿著鏈結串列尋找相關節點。

---

核心觀念

本題考查加權無向圖的儲存方式，以及最小生成樹（Minimum Spanning Tree, MST）。生成樹必須連通所有頂點且不含環；若圖有 $V$ 個頂點，生成樹恰有 $V-1$ 條邊。最小生成樹是在所有生成樹中，總權重最小者。

圖一共有 $6$ 個頂點、$9$ 條邊。依圖讀出邊與權重如下：

$$(1,2):3,\ (1,3):2,\ (1,4):1,\ (2,4):4,\ (2,5):2,\ (3,4):2,\ (3,6):1,\ (4,5):3,\ (5,6):4$$

(a) 兩種圖形儲存方式

1. 鄰接矩陣

   使用 $6\times 6$ 矩陣 $A$ 儲存頂點間的邊權重。因為本圖是無向圖，矩陣對稱；沒有邊的位置記為 $\infty$（或以特殊值表示），對角線代表頂點到自身。

   優點是判斷兩頂點是否相鄰、查詢邊權重都只需 $O(1)$，也方便處理稠密圖。缺點是空間需求為 $O(V^2)$；本圖有 $9$ 條邊，但仍需配置 $36$ 個矩陣格子。

2. 鄰接串列

   每個頂點存一串相鄰頂點及邊權重，例如：

   • $1:\ (2,3),(3,2),(4,1)$
   • $2:\ (1,3),(4,4),(5,2)$
   • $3:\ (1,2),(4,2),(6,1)$
   • $4:\ (1,1),(2,4),(3,2),(5,3)$
   • $5:\ (2,2),(4,3),(6,4)$
   • $6:\ (3,1),(5,4)$

核心觀念

二元搜尋樹（BST）插入資料時，較小的鍵往左走，較大的鍵往右走；新鍵會插入搜尋路徑上第一個空位置。因此，樹中每個父節點都必須先於其子節點插入。

圖中的結構是：$28$ 為根；$27$ 是 $28$ 的左子節點，$25$ 是 $27$ 的左子節點；$35$ 是 $28$ 的右子節點，$45$ 是 $35$ 的右子節點。

解題方法

根節點 $28$ 必須第一個插入。接著，$27$ 必須先於 $25$，否則 $25$ 插入時會成為 $28$ 的左子節點；同理，$35$ 必須先於 $45$，否則 $45$ 插入時會成為 $28$ 的右子節點。

因此，除了 $28$ 固定在第一個位置，後續資料只需交錯排列兩個有先後順序的序列：

核心觀念

Shell sort 是「分組插入排序」：

• 每一趟選定增量 $K$。
• 將元素依索引模 $K$ 分成 $K$ 個子序列。
• 對每個子序列進行 insertion sort。
• 增量依序減半：

$$K=\frac{N}{2},\frac{N}{4},\frac{N}{8},\ldots,1$$

因此總趟數為：

$$\log_2 N=O(\log N)$$

關鍵在於：每一趟的排序成本，會隨著增量 $K$ 改變。

解題方法與時間分析

當增量為 $K$ 時，共有 $K$ 個子序列，每個子序列大約包含 $N/K$ 個元素。

Insertion sort 排序長度為 $N/K$ 的序列，最壞時間為：

$$O\left(\left(\frac{N}{K}\right)^2\right)$$

共有 $K$ 個子序列，所以該趟的最壞時間為：

$$K\cdot O\left(\left(\frac{N}{K}\right)^2\right) = O\left(\frac{N^2}{K}\right)$$

將各趟增量代入：

$$\begin{aligned} T(N) &= O\left(\frac{N^2}{N/2}\right) + O\left(\frac{N^2}{N/4}\right) +\cdots+ O\left(\frac{N^2}{1}\right)\\ &= O(2N+4N+\cdots+N^2) \end{aligned}$$

這是一個以 $2$ 為公比的等比級數，其最大項為 $N^2$，因此：

$$T(N)=O(N^2)$$