109 年 國立成功大學資訊管理研究所乙組《資料結構》

a. $n^{1.5}=n^{3/2}$ 的增長速率比 $n\log n$ 快，因為 $\displaystyle\lim_{n\to\infty}\frac{n^{3/2}}{n\log n}= \lim_{n\to\infty}\frac{\sqrt n}{\log n}= \infty$。故 $n^{1.5}\neq O(n\log n)$。
答案：False

b. 完全二元樹（complete binary tree）在每層除了最底層外皆滿，且最底層的節點盡可能靠左；滿二元樹（full binary tree）要求每個節點要么是葉子要么有兩個子節點。給定相同高度 $h$，滿二元樹的節點數恰好是 $2^{h+1}-1$，而完全二元樹的節點數上限同樣是 $2^{h+1}-1$，下限則為 $2^{h}$。

核心觀念

Priority queue（優先佇列）與一般 queue 的差異在於：

• 一般 queue 依照先進先出（FIFO）。
• Priority queue 依照 priority 決定服務順序，priority 較高者優先 dequeue。
• 本題要求 enqueue 與 dequeue 都有效率，且不能使用 STL，因此適合使用二元最大堆積（max heap）。

以最大堆積儲存資料時，必須滿足：

$$\text{parent.priority} \geq \text{child.priority}$$

因此根節點永遠是最高優先權元素，可在 $O(1)$ 時間找到；enqueue 與 dequeue 透過調整堆積維持結構，時間複雜度皆為 $O(\log n)$。

---

解題方法

每個元素包含兩個整數：

data      // 資料
priority  // 優先權

採用陣列儲存二元最大堆積。若節點位於索引 $i$：

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

陣列容量不足時，配置一個容量加倍的新陣列，將原資料複製過去，因此佇列大小只受可用記憶體限制。

---

a. 資料結構設計

class PriorityQueue {
private:
    struct Node {
        int data;
        int priority;
    };

    Node* heap;
    int size;
    int capacity;

    void resize();
    void swap(Node& a, Node& b);

public:
    PriorityQueue();
    ~PriorityQueue();

    void enqueue(int data, int priority);
    bool dequeue(int& data, int& priority);

    bool empty() const;
};

其中：

• heap：存放最大堆積的陣列。
• size：目前元素數量。
• capacity：目前陣列容量。
• 根節點 heap[0] 的 priority 最大。
• dequeue 回傳 false 表示佇列為空。

---

b. enqueue 與 dequeue 實作

enqueue

新元素先放在陣列最後，接著向上調整：

1. 將新元素放到索引 size。
2. 與父節點比較 priority。
3. 若新元素 priority 較高，便與父節點交換。
4. 持續向上直到符合最大堆積性質。

dequeue

刪除根節點：

1. 取出根節點作為 dequeue 結果。
2. 將最後一個元素移到根節點。
3. 將此元素向下調整：
   • 找出左右子節點中 priority 較高者。
   • 若子節點 priority 高於目前節點，便交換。
   • 持續向下直到符合最大堆積性質。

a. 定義
紅黑樹（Red‑Black Tree）是一種滿足以下五條性質的二元搜尋樹：

1. 每個節點皆為紅色 (R) 或黑色 (B)。
2. 根節點為黑色。
3. 所有葉子 NIL（外部空節點）皆為黑色。
4. 若一個節點為紅色，則其兩個子節點皆為黑色（紅色節點不可相鄰）。
5. 任一節點到其各子孫葉子 NIL 的所有簡單路徑上，黑色節點數目相同（稱為 黑高）。

---

b. 時間複雜度（以節點數 $n$ 計）

操作	最佳情況	最差情況
Find	$O(\log n)$（樹高受限於 $2\log_2(n+1)$）	$O(\log n)$
Insert	$O(\log n)$（搜尋 + 最多 $2$ 次旋轉 + 重新著色）	$O(\log n)$
Remove	$O(\log n)$（搜尋 + 最多 $3$ 次旋轉 + 重新著色）	$O(\log n)$

---

c. 插入序列 $2,1,4,5,9,3,6,7$ 的逐步結果
節點顯示格式：value(color)；黑色 B、紅色 R。

1. 插入 2 → 只剩根節點，重新著色為黑色。

   2B
   

2. 插入 1 → 1 為左子，顏色 R；根 2 仍 B。

     2B
    /
   1R
   

3. 插入 4 → 4 為右子，顏色 R。

     2B
    / \
   1R 4R
   

4. 插入 5 → 插入為 4 的右子 (5R)，違反連續紅色 (4R‑5R)。
   重新著色：4 變 B，5 變 R，根 2 仍 B。

核心觀念

本題考查「堆疊（Stack）」在括號配對與巢狀結構檢查上的應用。

括號必須同時滿足兩項條件：

1. 每個右括號都要有對應的左括號。
2. 括號的配對順序必須正確，先開啟的括號要最後關閉。

例如：

• {[2 × (a + b)] - c}：正確
• ([ ])：正確
• ([)]：錯誤，( 尚未關閉就遇到 ]
• ((a+b)：錯誤，最後仍有左括號未配對
• (a+b))：錯誤，多出一個右括號

這種「後開先關」的特性正好符合堆疊的後進先出（Last In, First Out, LIFO）原則。

---

解題方法

由左至右掃描整個運算式：

1. 遇到左括號 (、[、{：推入堆疊。
2. 遇到右括號 )、]、}：
   • 若堆疊為空，表示沒有可配對的左括號，直接判定錯誤。
   • 取出堆疊頂端的左括號。
   • 檢查兩者是否為同一種類型；不相符則判定錯誤。
3. 掃描結束後：
   • 堆疊為空，表示所有括號均已配對，運算式正確。
   • 堆疊不為空，表示仍有左括號未關閉，運算式錯誤。

以題目中的片段為例：

{ [ 2 × ( a + b ) ] - c }

括號處理順序如下：

掃描到的符號	堆疊內容	動作
{	{	推入
[	{ [	推入
(	{ [ (	推入
)	{ [	與 ( 配對並移除
]	{	與 [ 配對並移除
}	空	與 { 配對並移除

掃描結束時堆疊為空，因此括號排列正確。

---

C++ 參考實作

核心觀念

本題綜合考查：

• 隨機排列與排序複雜度
• 多項式加法、乘法與稀疏表示法
• Binary Search Tree（BST）的插入與刪除
• Dijkstra 最短路徑與 Hamiltonian path
• 零權重 cycle 的判定
• 圖的平均 degree
• Min-heap 建構方法

---

a. 隨機排序整數

答案：F

產生 $B[1],\ldots,B[n]$ 後依照 $B$ 的大小排序，再用此順序排列 $A$，排序本身確實可在 $O(n\log n)$ 時間完成；但這不代表一定能產生均勻的隨機排列。

原因是 $B[i]$ 是整數，可能出現相同值。例如：

$$B[1]=B[2]$$

此時兩個元素的先後順序必須依賴排序法的 tie-breaking 規則。若相同值時維持原順序，則部分排列的機率會不同，無法保證每個排列都等機率出現。

雖然取值範圍 $[-n^3,n^3]$ 很大，使碰撞機率很低，但碰撞機率仍不等於 $0$。因此這個方法不能嚴格保證隨機化排列。

此外，正確的 Fisher–Yates shuffle 可在 $O(n)$ 時間完成，因此「隨機化需要 $O(n\log n)$」也不是最佳複雜度。

---

b. 稠密多項式的加法與乘法

答案：T

多項式加法為：

$$f(x)+g(x)=\sum_{k=0}^{\max(m,n)}C_kx^k$$

其中

$$C_k=A_k+B_k$$

缺少的係數可視為 $0$。需要逐項處理至次數 $\max(m,n)$，所以時間複雜度為：

$$O(\max\{m,n\})$$

多項式乘法中：

$$D_l=\sum_{i+j=l}A_iB_j$$

每個 $A_i$ 都必須與每個 $B_j$ 相乘，共有：

$$(m+1)(n+1)=O(mn)$$

個乘積，因此直接計算的時間複雜度為：

$$O(mn)$$

所以敘述正確。

---

c. 稀疏多項式的加法與乘法

答案：T

設第一個多項式有 $p$ 個非零項，第二個多項式有 $q$ 個非零項，且兩者都依指數遞增排列。

多項式加法

兩個有序 linked list 可以使用類似 merge 的方法：

1. 比較目前兩個節點的指數。
2. 指數較小者直接放入結果。
3. 指數相同時，將兩個係數相加。
4. 移動相應的指標。

每個節點最多被走訪一次，因此：

$$T_{\text{addition}}=O(p+q)$$

多項式乘法

每個非零項都要與另一個多項式的每個非零項相乘：

$$p\times q$$

個乘積。每個乘積會產生一項：

$$A_iB_jx^{i+j}$$

將指數相同的項合併後，總處理量仍受 $pq$ 個非零項乘積所限制，因此：

$$T_{\text{multiplication}}=O(pq)$$

稀疏表示的重點是複雜度依非零項數 $p,q$ 計算，而不是依最大次數 $m,n$ 計算。

---

d. BST 插入後立即刪除

答案：F

在 BST 中插入一個「新值」時，由於該值原本不存在，最後一定會被插入成葉節點。

例如原本有：

$$\begin{array}{c} 10\\ /\quad \backslash\\ 5\quad 15 \end{array}$$

插入新值 $12$ 後：

$$\begin{array}{c} 10\\ /\quad \backslash\\ 5\quad 15\\ \quad /\quad \backslash\\ \quad 12 \end{array}$$

新節點 $12$ 沒有子樹，因此刪除它只需直接移除該葉節點，原本的樹形會完全恢復。

所以「插入新值後立即刪除，樹結構可能改變」是錯誤的。

---

e. 使用 Dijkstra 找出通過所有節點的最短路徑

答案：F

Dijkstra 演算法解決的是：

從單一起點到各節點的最短路徑問題。

核心觀念

本題主要考查三個觀念：

1. 單一來源—單一目的地的最大流（maximum flow）。
2. 最短路徑網路（shortest-path subnetwork）的建構。
3. 多商品流（multicommodity flow）與不同流量間的容量競爭。

對任一弧 $(i,j)\in A$，容量限制為

$$0\le x_{ij}\le u_{ij}.$$

若要從來源 $o$ 傳送 $F$ 單位流量至目的地 $d$，只要最大流值滿足

$$\operatorname{maxflow}(o,d)\ge F,$$

即可判定能否成功傳送。

---

(a) 判定從節點 $1$ 傳送至節點 $1+n/2$

解題方法

令

$$o_1=1,\qquad d_1=1+\frac n2.$$

將原網路 $G=(N,A)$ 視為一個容量網路，對每條弧設定容量 $u_{ij}$，接著執行最大流演算法，例如 Ford–Fulkerson 演算法：

1. 初始流量設為 $0$。

2. 在殘餘網路中尋找一條由 $o_1$ 到 $d_1$ 的增廣路徑。

3. 沿增廣路徑增加可行流量：

   $$\Delta=\min_{(i,j)\text{ 在增廣路徑上}} r_{ij},$$

   其中 $r_{ij}$ 為弧 $(i,j)$ 的殘餘容量。

4. 重複上述步驟，直到：

   • 最大流值達到 $F$；或
   • 殘餘網路中不存在從 $o_1$ 到 $d_1$ 的路徑。

若最大流值至少為 $F$，則可以成功傳送；否則無法成功傳送。

根據最大流最小割定理，也可以改以判斷是否存在一個 $o_1$–$d_1$ 割，其容量小於 $F$。若最小割容量小於 $F$，必然無法傳送 $F$ 單位流量。

複雜度

若採用 Ford–Fulkerson，且容量為整數，每次增廣至少增加 $1$ 單位流量，因此時間複雜度為

$$O(mF_{\max}),$$

其中 $F_{\max}$ 為最大流量。

因為每條弧容量至多為

$$U=\max_{(i,j)\in A}u_{ij},$$

且網路中最多有 $n$ 個節點，所以可使用較寬鬆的上界

$$F_{\max}\le nU.$$

因此複雜度可寫為

$$O(nmU).$$

若使用 Edmonds–Karp 等較穩定的最大流演算法，則可得到與容量數值無關的複雜度，例如

$$O(nm^2).$$

---

(b) 建構包含所有最短路徑的子網路 $G_1$

核心想法

要找出所有由來源 $o_1$ 到目的地 $d_1$ 的最短路徑，可分別計算：

• $D_o[v]$：從 $o_1$ 到節點 $v$ 的最短距離；
• $D_d[v]$：從節點 $v$ 到 $d_1$ 的最短距離。

由於題目給定 $c_{ij}\ge 0$，可使用 Dijkstra 演算法。

計算步驟

第一步：從來源節點計算距離

在原圖 $G$ 上以 $o_1$ 為起點執行 Dijkstra，得到

$$D_o[v]=\operatorname{dist}(o_1,v).$$

第二步：從目的地反向計算距離

將所有弧反向，對反向網路以 $d_1$ 為起點執行 Dijkstra，得到

$$D_d[v]=\operatorname{dist}(v,d_1).$$

令

$$D=D_o[d_1]$$

為 $o_1$ 到 $d_1$ 的最短距離。

第三步：保留位於最短路徑上的弧

對每條弧 $(i,j)\in A$，若滿足

$$D_o[i]+c_{ij}+D_d[j]=D,$$

則弧 $(i,j)$ 位於至少一條最短路徑上，因此保留該弧。

所以子網路可定義為

$$A_1= \left\{ (i,j)\in A: D_o[i]+c_{ij}+D_d[j]=D \right\},$$

並令

$$G_1=(N_1,A_1),$$

其中 $N_1$ 只包含被保留弧連接到的節點，以及來源 $o_1$ 和目的地 $d_1$。

為什麼這個條件正確？

若弧 $(i,j)$ 位於某條最短路徑上，則該路徑必可分成三段：

$$o_1\leadsto i,\qquad (i,j),\qquad j\leadsto d_1.$$

三段長度相加必須等於整體最短距離，因此