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

核心觀念

Queue 遵循 FIFO（First In, First Out，先進先出）；Stack 遵循 LIFO（Last In, First Out，後進先出）。

使用兩個 stack：

• inStack：負責新元素加入。
• outStack：負責元素移除與查看隊首。

當 outStack 不為空時，其頂端元素就是目前的隊首。若 outStack 為空，便將 inStack 的所有元素逐一移至 outStack，藉由兩次反轉恢復先進先出的順序。

---

解題方法

Enqueue：加入元素

直接將新元素推入 inStack。

enqueue(x):
    inStack.push(x)

例如依序加入 $1,2,3$：

inStack：底部 [1, 2, 3] 頂端
outStack：空

Dequeue：移除隊首

1. 若 outStack 為空，將 inStack 的所有元素移至 outStack。
2. 從 outStack 頂端取出元素。

dequeue():
    if outStack.empty():
        while not inStack.empty():
            outStack.push(inStack.pop())

    if outStack.empty():
        報告 queue underflow

    return outStack.pop()

以上述狀態為例，搬移後：

inStack：空
outStack：底部 [3, 2, 1] 頂端

此時 outStack.pop() 會先取出 $1$，符合 Queue 的 FIFO 規則。

Peek：查看隊首

流程與 dequeue 相同，但不實際移除元素。

front():
    if outStack.empty():
        while not inStack.empty():
            outStack.push(inStack.pop())

    if outStack.empty():
        報告 queue underflow

    return outStack.top()

IsEmpty：判斷是否為空

只有兩個 stack 都為空時，Queue 才為空。

isEmpty():
    return inStack.empty() and outStack.empty()

---

關鍵程式碼

核心觀念

本題考查：

• Prefix expression（前序表示式）：運算子位於運算元之前。
• Infix expression（中序表示式）：運算子位於兩個運算元之間。
• Stack（堆疊）：遵循後進先出（LIFO, Last In First Out）。
• 二元運算子的處理順序：先彈出的元素是右運算元，後彈出的元素是左運算元。

前序表示式為：

$$-+*ABC/EF$$

其中：

• -：減法
• +：加法
• *：乘法
• /：除法
• A,B,C,E,F：運算元

由於前序表示式的運算子在運算元之前，因此使用堆疊時，必須由右至左掃描。

---

解題方法

由右至左讀取每個符號：

1. 遇到運算元：直接推入堆疊。
2. 遇到運算子：
   • 彈出兩個元素。
   • 後彈出的元素為左運算元。
   • 先彈出的元素為右運算元。
   • 組合成中序表示式後，再推回堆疊。
3. 掃描結束後，堆疊頂端即為完整的中序表示式。

為避免運算優先順序造成誤解，組合過程保留括號。

---

堆疊操作紀錄

堆疊表示方式為「底端 → 頂端」。

讀取順序	目前輸入	操作	Stack（底端 → 頂端）	Output
1	F	F 推入堆疊	F	—
2	E	E 推入堆疊	F, E	—
3	/	彈出 E、F，組合成 (E/F)	(E/F)	(E/F)
4	C	C 推入堆疊	(E/F), C	(E/F)

核心觀念

令字串為

$$P=p_1p_2\cdots p_n.$$

題目要求最小的 $m>0$，使得

$$p_1p_2\cdots p_{n-m} = p_{m+1}p_{m+2}\cdots p_n.$$

右側字串長度為 $n-m$，因此此條件表示：

• 字串的前綴 $p_1\cdots p_{n-m}$；
• 字串的後綴 $p_{m+1}\cdots p_n$；

兩者完全相同。

這正是「最長 proper border」問題。若字串存在長度為 $L$ 的最長相同前綴與後綴，則

$$L=n-m,$$

所以

$$m=n-L.$$

其中 $L$ 必須小於 $n$，因為 $m>0$。

對整個字串 $P$，使用 KMP 的 prefix function $\pi[n]$，即可在 $O(n)$ 時間內求出最長 proper border 的長度：

$$L=\pi[n].$$

因此字串的 period 為

$$\boxed{n-\pi[n]}.$$

---

解題方法：使用 KMP Prefix Function

定義 $\pi[i]$ 為子字串 $p_1p_2\cdots p_i$ 的最長 proper border 長度。

也就是最大的 $k<i$，使得

$$p_1p_2\cdots p_k = p_{i-k+1}p_{i-k+2}\cdots p_i.$$

特別地，$\pi[n]$ 就是整個字串的最長 proper border。

Prefix function 的遞推

計算 $\pi[i]$ 時，先令

$$j=\pi[i-1].$$

此時 $j$ 代表前一個前綴的最長 border 長度。

若 $p_{j+1}\neq p_i$，就沿著 KMP 的 failure link 往更短的 border 找：

$$j=\pi[j].$$

重複此步驟，直到：

1. $j=0$；或
2. $p_{j+1}=p_i$。

若最後可以匹配，則

$$j\leftarrow j+1,$$

並令

$$\pi[i]=j.$$

---

關鍵程式碼

以下採用 1-based indexing：

Period(p[1..n]):
    pi[1] = 0

    for i = 2 to n:
        j = pi[i - 1]

        while j > 0 and p[j + 1] != p[i]:
            j = pi[j]

        if p[j + 1] == p[i]:
            j = j + 1

        pi[i] = j

    return n - pi[n]

實作時若需避免存取 $p[1]$ 以外的位置，可將字串改為 0-based indexing，或在程式中明確處理 $j=0$ 的情況。

---

正確性證明

設

核心觀念

本題要求使用 QuickSort 將整數陣列排序成非遞減順序，且每次都選取目前子陣列的最左元素作為 pivot。

QuickSort 的核心步驟如下：

1. 選擇 pivot。
2. 進行 partition，使 pivot 左側元素不大於 pivot，右側元素不小於 pivot。
3. pivot 放到最終正確位置。
4. 對 pivot 左右兩側子陣列遞迴排序。

若 partition 後 pivot 位於索引 $p$，則滿足：

$$a[left \ldots p-1] \leq a[p] \leq a[p+1 \ldots right]$$

因此只需繼續處理：

$$[left,p-1]\quad\text{與}\quad[p+1,right]$$

---

解題方法

由於 pivot 固定為子陣列最左元素，令：

$$pivot=a[left]$$

使用左右兩個指標：

• $i$：由左向右尋找大於 pivot 的元素。
• $j$：由右向左尋找小於 pivot 的元素。

處理流程：

1. 先讓 $j$ 向左移動，跳過所有大於等於 pivot 的元素。
2. 找到小於 pivot 的元素後，將它放到左側空位。
3. 再讓 $i$ 向右移動，跳過所有小於等於 pivot 的元素。
4. 找到大於 pivot 的元素後，將它放到右側空位。
5. 當 $i$ 與 $j$ 相遇時，將 pivot 放入相遇位置。

關鍵程式碼

int partition(int list[], int left, int right) {
    int pivot = list[left];
    int i = left;
    int j = right;

    while (i < j) {
        while (i < j && list[j] >= pivot) {
            j--;
        }

        if (i < j) {
            list[i] = list[j];
            i++;
        }

        while (i < j && list[i] <= pivot) {
            i++;
        }

        if (i < j) {
            list[j] = list[i];
            j--;
        }
    }

    list[i] = pivot;
    return i;
}

void quickSort(int list[], int left, int right) {
    if (left < right) {
        int p = partition(list, left, right);

        quickSort(list, left, p - 1);
        quickSort(list, p + 1, right);
    }
}

呼叫方式：

quickSort(list, 0, n - 1);

Partition 正確性

在 partition 過程中維持以下條件：

核心觀念

本題考查 合併排序（mergesort） 的分治法：

1. 將序列遞迴切成長度更小的子序列。
2. 子序列長度為 $1$ 時視為已排序。
3. 逐層合併兩個已排序序列，產生更大的已排序序列。

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

---

解題方法

採用由上而下的 mergesort，先切割，再由下而上合併。

一、切割階段

原始序列為：

$$\{24,4,35,1,60,12,16,52\}$$

第一次切割：

$$\{24,4,35,1\}\quad \{60,12,16,52\}$$

第二次切割：

$$\{24,4\}\quad \{35,1\}\quad \{60,12\}\quad \{16,52\}$$

第三次切割：

$$\{24\}\ \{4\}\ \{35\}\ \{1\}\ \{60\}\ \{12\}\ \{16\}\ \{52\}$$

每個單一元素序列皆視為已排序。

---

二、第一次合併

合併 $\{24\}$ 與 $\{4\}$

比較 $24$ 與 $4$：

$$4<24$$

因此得到：

$$\{4,24\}$$

合併 $\{35\}$ 與 $\{1\}$

比較 $35$ 與 $1$：

$$1<35$$

因此得到：

$$\{1,35\}$$

合併 $\{60\}$ 與 $\{12\}$

比較 $60$ 與 $12$：

$$12<60$$

因此得到：

$$\{12,60\}$$

合併 $\{16\}$ 與 $\{52\}$

比較 $16$ 與 $52$：

$$16<52$$

因此得到：

$$\{16,52\}$$

此時序列變為：

$$\{4,24\}\quad \{1,35\}\quad \{12,60\}\quad \{16,52\}$$

---

三、第二次合併

合併 $\{4,24\}$ 與 $\{1,35\}$

依序比較：

• $4$ 與 $1$：取 $1$
• $4$ 與 $35$：取 $4$
• $24$ 與 $35$：取 $24$
• 左側用完，接上 $35$

因此：

$$\{4,24\}+\{1,35\} \longrightarrow \{1,4,24,35\}$$

合併 $\{12,60\}$ 與 $\{16,52\}$

依序比較：

• $12$ 與 $16$：取 $12$
• $60$ 與 $16$：取 $16$
• $60$ 與 $52$：取 $52$
• 右側用完，接上 $60$

因此：

核心觀念

本題考查雜湊（hashing）與開放定址法（open addressing）。

每筆紀錄的雜湊值定義為所有字元 ASCII 碼的總和：

$$H(\text{record})=\sum \text{ASCII(character)}$$

雜湊表共有 $37$ 個 bucket，因此初始 bucket index 為：

$$h(\text{record})=H(\text{record})\bmod 37$$

題目未明示碰撞後的探查方式，以下採用開放定址法中最基本的線性探查（linear probing）：

$$h_i(k)=(h(k)+i)\bmod 37,\quad i=0,1,2,\ldots$$

也就是發生碰撞時，依序檢查下一個 bucket。

解題方法與計算

1. Aarom

$$65+97+114+111+109=496$$ $$496\bmod 37=15$$

因此放入第 $15$ 號 bucket。

2. Ana

$$65+110+97=272$$ $$272\bmod 37=13$$

第 $13$ 號 bucket 尚未使用，因此放入第 $13$ 號 bucket。

3. Donnie

$$68+111+110+110+105+101=605$$ $$605\bmod 37=13$$

第 $13$ 號 bucket 已有 Ana，發生碰撞。採線性探查：

• 第 $13$ 號：已使用
• 第 $14$ 號：空置

因此 Donnie 放入第 $14$ 號 bucket。

4. Tyriom

$$84+121+114+105+111+109=644$$ $$644\bmod 37=15$$

第 $15$ 號 bucket 已有 Aarom，發生碰撞。採線性探查：

• 第 $15$ 號：已使用
• 第 $16$ 號：空置

(a) 插入順序 8, 8, 12, 6, 9 的修正步驟

插入值	主要違規	修正方式	變更後樹形（顏色）
8	–	直接成為根，置黑	8B
8	–	為右子，置紅	8B → 8R
12	父節點為紅 (8R) 且為右子 → 右‑右	左旋於祖父 (8B)，父黑、祖父紅	8B 為根，左子 8R，右子 12R
6	父節點 (8R) 為紅，叔節點 (12R) 為紅	重新著色：父、叔變黑，祖父變紅，根再置黑	8B 為根，左子 8B、右子 12B，6R 為左子 8B 的左子
9	– (父為黑)	直接插入左紅子	9R 為 12B 的左子

最終樹形 (a)

        8(B)
       /   \
    8(B)   12(B)
    /       /
  6(R)    9(R)

---

(b) 在 (a) 基礎上再插入 3, 4, 6, 5, 11, 10 的修正步驟

插入值	主要違規	修正方式	變更後關鍵子樹
3	父 (6R) 為紅，屬左‑左	右旋於祖父 (8B)，父黑、祖父紅，根再置黑	6B 成為左子，左子 3R，右子 8R

核心觀念

有向圖的鄰接矩陣 $A=[a_{ij}]$ 定義為：

$$a_{ij}= \begin{cases} 1, & \text{若存在由頂點 }v_i\text{ 指向 }v_j\text{ 的邊}\\ 0, & \text{否則} \end{cases}$$

矩陣的「列」代表出發頂點，矩陣的「行」代表抵達頂點。因此，有向邊 $v_i\to v_j$ 應記錄在第 $i$ 列、第 $j$ 行的位置。

解題方法

1. 先依題圖標示的順序排列所有頂點，例如 $v_1,v_2,\ldots,v_n$。
2. 建立一個 $n\times n$ 的零矩陣。
3. 逐一檢查圖中的每條有向邊：
   • 若有 $v_i\to v_j$，則令 $a_{ij}=1$。
   • 若沒有反向邊 $v_j\to v_i$，則 $a_{ji}$ 仍為 $0$。

核心觀念

本題考查下列定義與性質：

• 二分圖（bipartite graph）：頂點集合可分成兩個互斥集合 $U$、$W$，且每條邊的兩端分別位於 $U$ 與 $W$；因此 $U$ 內部與 $W$ 內部都沒有邊。
• 無環圖（acyclic graph）：圖中不存在任何 cycle。無向無環圖的每個連通分量都是一棵樹，因此整個圖稱為 forest。
• 樹中任兩個頂點之間存在唯一簡單路徑。

證明目標是：將所有頂點分成兩組，使每條邊都連接兩組中的不同組別。

---

解題方法：依與根頂點距離的奇偶性分組

先處理圖中的每個連通分量。對每個連通分量任選一個根頂點 $r$，依各頂點到 $r$ 的距離分組：

$$U=\{v\in V:\operatorname{dist}(r,v)\text{ 為偶數}\},$$ $$W=\{v\in V:\operatorname{dist}(r,v)\text{ 為奇數}\}.$$

每個頂點到根頂點的距離必為整數，因此每個頂點恰好屬於 $U$ 或 $W$ 其中一組，且兩組互斥。

---

關鍵性質：相鄰頂點的距離奇偶性必不同

設 $x$ 與 $y$ 相鄰。因為圖是樹，從根頂點 $r$ 到 $x$、$y$ 的路徑皆唯一。

若 $x$ 位於從 $r$ 到 $y$ 的唯一路徑上，則

$$\operatorname{dist}(r,y)=\operatorname{dist}(r,x)+1.$$

若 $y$ 位於從 $r$ 到 $x$ 的唯一路徑上，則

$$\operatorname{dist}(r,x)=\operatorname{dist}(r,y)+1.$$

兩種情況皆表示相鄰頂點到根的距離相差 $1$，所以一個距離為偶數，另一個距離必為奇數。

核心觀念

最小生成樹是在連通圖中選出恰好 $|V|-1$ 條邊，使所有頂點連通且總權重最小。此圖有 $9$ 個頂點，因此生成樹需選 $8$ 條邊。

使用 Kruskal 演算法：依邊權重由小到大檢查，只有在加入該邊不會形成環時才納入。

解題方法

依權重排序，逐步選取不會形成環的邊：

權重	邊	判斷
1	$AB$	納入
1	$CG$	納入
2	$BF$	納入
2	$DG$	納入
2	$HC$	納入
3	$AF$	略過；$A$、$F$ 已由 $A-B-F$ 連通
3	$GH$	略過；$G$、$H$ 已連通