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

核心觀念

圖形的 edge list representation（邊串列表示法），是將圖中的每一條邊依序存放在一個串列中。每個串列節點通常記錄一條邊的兩個端點：

$$(u,v)$$

因此，若圖有 $8$ 個節點與 $10$ 條邊，edge list 會包含 $10$ 個元素，但這些元素屬於同一個 linked list。

$$\text{linked lists 數量}=1$$

題目問的是 linked lists 的數量，不是串列節點的數量。

解題方法

先辨認表示法：

• Edge list：使用一個串列，逐筆記錄所有邊。
• Adjacency list（鄰接串列）：通常每個圖形節點各配置一個串列，因此 $8$ 個節點會有 $8$ 個 linked lists。
• Adjacency matrix（鄰接矩陣）：使用二維陣列，不以 linked list 為主要結構。

本題採用 edge list，因此不論圖中有幾個節點、幾條邊，標準表示法都是使用一個 linked list：

$$(v_1,v_2), (v_3,v_4), \ldots, (v_i,v_j)$$

$10$ 條邊會形成串列中的 $10$ 個資料節點，但 linked list 本身仍只有 $1$ 個。

選項分析

核心觀念

雜湊函數

$$\mathrm{Hash}(X)=X\bmod 1000$$

所產生的結果是除以 $1000$ 後的餘數。對於非負整數 $X$，餘數必定滿足：

$$0\leq X\bmod 1000<1000$$

因此，可能的雜湊值為：

$$0,1,2,\ldots,999$$

總共有 $1000$ 種結果。

解題方法

直接依據餘數的定義判斷範圍：

• $X=1000k$ 時，餘數為 $0$。
• $X=1000k+999$ 時，餘數為 $999$。
• 餘數不可能等於 $1000$，因為餘數必須小於除數 $1000$。

所以：

$$\mathrm{Hash}(X)\in\{0,1,2,\ldots,999\}$$

選項分析

• (a) 0 to 1000：錯誤

  雖然包含下限 $0$，但餘數不可能等於 $1000$。餘數最大只能是 $999$。

核心觀念

Heapsort 的時間複雜度為：

• 平均情況：$O(n\log n)$
• 最壞情況：$O(n\log n)$

因此，本題要找的是「平均與最壞情況皆為 $O(n\log n)$」的排序演算法。

其中：

• $n$：待排序資料筆數
• $\log n$：堆積操作或分治層數所造成的成本

解題方法

比較各排序法的平均與最壞時間複雜度：

排序法	平均時間	最壞時間
Insertion sort	$O(n^2)$	$O(n^2)$
Mergesort	$O(n\log n)$	$O(n\log n)$
Quicksort	$O(n\log n)$	$O(n^2)$
Shellsort	依遞增序列而定	依遞增序列而定
Heapsort	$O(n\log n)$	$O(n\log n)$

只有 Mergesort 與 Heapsort 同時具有平均與最壞情況 $O(n\log n)$ 的時間界限。

Mergesort 每次將資料切成兩半，遞迴深度為 $O(\log n)$；每一層合併所有元素的成本為 $O(n)$，因此：

$$T(n)=2T\left(\frac{n}{2}\right)+O(n)$$

由主定理可得：

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

切割是否平均、資料原本是否已排序，都不會改變 Mergesort 的分治層數與每層合併成本，因此平均與最壞情況皆為 $O(n\log n)$。

選項分析

(a) Insertion sort

錯誤。Insertion sort 在平均情況下需要大量元素位移與比較，時間複雜度為：

核心觀念

Binary heap（二元堆積）是一種具備下列特性的完全二元樹：

1. 完整性（complete binary tree）：除最底層外，每層皆填滿，最底層由左至右排列。
2. 堆積順序（heap order）：
   • Max-heap：父節點值大於或等於子節點值。
   • Min-heap：父節點值小於或等於子節點值。

Binary heap 的根節點永遠是目前的最大值或最小值，因此適合快速取得「優先權最高」的元素。

常見操作複雜度如下：

• 取得最高優先權元素：$O(1)$
• 插入元素：$O(\log n)$
• 移除最高優先權元素：$O(\log n)$

這正符合 priority queue（優先佇列） 的需求。

解題方法

判斷資料結構的實作方式，應比較其核心操作：

• 優先佇列：每次取出優先權最高的元素。
• Binary heap：根節點可直接提供最大值或最小值，並能以 $O(\log n)$ 維持堆積性質。

因此，binary heap 可以有效實作 priority queue。

選項分析

(a) binary search tree

錯誤。Binary search tree（BST）要求：

$$\text{左子樹所有鍵值} < \text{根節點鍵值} < \text{右子樹所有鍵值}$$

Binary heap 只保證父節點與子節點之間的大小關係，不保證左子樹與右子樹之間的全域排序。例如在 min-heap 中，只知道父節點小於子節點，無法判斷左子樹元素是否小於右子樹元素，因此不具備 BST 的搜尋性質。

(b) priority queue

正確。優先佇列的核心是依優先權取出元素，而非依照先進先出順序處理。Binary heap 的根節點永遠是最高優先權元素：

核心觀念

樹的高度定義為「根到最深葉節點路徑上的邊數」。

因此：

• 高度 $h$ 的樹，根節點位於第 $0$ 層，最深葉節點位於第 $h$ 層。
• 二元樹每個節點最多有 $2$ 個子節點。
• 高度為 $h$ 的二元樹最多包含 $h+1$ 層。
• 高度為 $h$ 的二元樹至少需要一條包含 $h$ 條邊的根到葉路徑。

---

解題方法

（1）高度為 $8$ 的二元樹最多有多少個節點？

要使節點數最大，每一層都必須完全填滿：

• 第 $0$ 層：$2^0$ 個節點
• 第 $1$ 層：$2^1$ 個節點
• $\cdots$
• 第 $8$ 層：$2^8$ 個節點

因此節點總數為等比級數：

$$1+2+2^2+\cdots+2^8$$

利用公式：

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

代入 $h=8$：

$$2^{8+1}-1=2^9-1=512-1=511$$

所以，高度為 $8$ 的二元樹最多有 $511$ 個節點。

---

核心觀念

二元搜尋樹（Binary Search Tree, BST）遵守以下性質：

• 節點左子樹的所有鍵值小於該節點。
• 節點右子樹的所有鍵值大於該節點。
• 插入資料時，從根節點開始逐一比較，較小者往左，較大者往右，直到找到空位置插入。
• 「最深節點」是距離根節點最遠、所在層數最大的節點。

題目中的「8179」依考古題數列格式應解讀為兩個數字 $81$、$79$。

解題方法

依序插入 $52,43,81,79$：

1. 插入 $52$：成為根節點。
2. 插入 $43$：$43<52$，放在 $52$ 的左子樹。
3. 插入 $81$：$81>52$，放在 $52$ 的右子樹。
4. 插入 $79$：
   • $79>52$，往右走到 $81$；

核心觀念

本題綜合考查：

• 有向多重圖的邊數計算。
• Adjacency matrix 與 Adjacency list 的適用情況。
• Single-source shortest path、Minimum-spanning tree 與 Traveling Salesman Problem（TSP）的差異。
• 當造訪國家數量為固定常數時，利用暴力枚舉解決受限制的路徑問題。

設共有 $n$ 個國家，每一個有序國家對 $(i,j)$，其中 $i\ne j$，存在 $K$ 條成本與飛行時間各不相同的直飛航班。

---

（1）有向弧的數量

解題方法

因為是有向圖，從國家 $i$ 飛往國家 $j$，與從國家 $j$ 飛往國家 $i$ 是兩組不同的有向弧。

對每一個起點國家 $i$：

• 不能飛回自己，因此有 $n-1$ 個目的地；
• 每個目的地有 $K$ 條不同航班。

因此，每個國家發出的弧數為：

$$(n-1)K$$

共有 $n$ 個起點國家，所以總弧數為：

$$|E|=n(n-1)K$$

解題技巧

不要使用無向完全圖的公式 $\frac{n(n-1)}{2}$，因為本題明確使用 directed arc，方向必須分開計算。

---

（2）圖的儲存方式

解題方法

本題的圖是有向多重圖。對每一組有序國家 $(i,j)$，有 $K$ 條航班，而且每條航班的成本與飛行時間不同，因此不能只存一個數值。

可以使用 Adjacency matrix 儲存：

$$A[i][j]= \begin{cases} \text{由 }i\text{ 飛往 }j\text{ 的 }K\text{ 條航班資料}, & i\ne j\\ \varnothing, & i=j \end{cases}$$

其中每一筆航班資料至少包含：

$$(\text{cost},\text{time})$$

因此，每個矩陣元素可設計成一個大小為 $K$ 的陣列或串列：

A[i][j] = [
    (cost1, time1),
    (cost2, time2),
    ...
    (costK, timeK)
]

矩陣中共有 $n^2$ 個位置，但只有 $n(n-1)$ 個位置存放實際航班資料；對角線 $A[i][i]$ 為空。

為何選擇 Adjacency matrix

本題中每一對不同國家之間都有 $K$ 條航班，因此圖非常稠密：

$$|E|=n(n-1)K=\Theta(n^2K)$$

使用 Adjacency matrix 的優點是：

1. 可在 $O(1)$ 時間判斷國家 $i$ 與 $j$ 之間是否有航班。
2. 可直接取得兩國之間的全部 $K$ 條航班資料。
3. 圖是稠密圖，使用 Adjacency list 並不能節省太多空間。
4. 矩陣形式較適合進行全體國家兩兩關係的處理。

為何不選擇 Adjacency list

若使用 Adjacency list，每個國家都必須列出前往其餘 $n-1$ 個國家的 $K$ 條航班，因此仍須儲存：

$$n(n-1)K$$

筆航班資料，空間複雜度同樣為：

$$\Theta(n^2K)$$

而且若要查詢 $i$ 到 $j$ 是否有航班，通常必須在 $i$ 的鄰接串列中搜尋，查詢效率不如矩陣直接。

因此，本題應選擇「每個矩陣格子存放 $K$ 筆航班資料」的 Adjacency matrix。

複雜度

• 空間複雜度：$\Theta(n^2K)$。
• 查詢 $i\to j$ 的航班集合：$O(1)$ 取得矩陣位置；若需逐一檢視 $K$ 條航班，則為 $O(K)$。

---

（3）應使用 1-ALL shortest path 或 Minimum-spanning tree？

結論

兩者皆不適合直接解決本題。

若 Tom 的目標是「從一個起點出發，分別求到所有國家的最短成本」，才是 1-ALL shortest path 問題；但題目描述的是要實際安排一趟行程，拜訪所有國家，使總成本最小。

這屬於 Traveling Salesman Problem（TSP）的概念。

為何不是 1-ALL shortest path

1-ALL shortest path 的目標是：

$$\text{從固定起點 }s\text{ 到每個國家 }v\text{ 的最短路徑}$$

它會分別求出：

$$d(s,v)$$

但這些最短路徑彼此可能重複經過相同國家，也不會自然形成一條「每個國家都拜訪一次」的單一路線。

例如：

核心觀念

本題綜合考查：

• 均勻分布下的 Bucket Sort 與比較式排序下界。
• BST 的走訪、Heap 的線性建堆。
• Dijkstra 演算法的非負邊權限制，以及 DAG 最長路徑。
• 有向環與路徑的等價轉換。
• Red-Black Tree 走訪與線性時間的中位數選取。

---

(a) 均勻分布實數的排序

判定：F（錯誤）

題目聲稱排序需要 $\Theta(n\log n)$ 時間，這是錯的。

解題方法

若數值獨立且均勻分布於 $[0,1000]$，可使用 Bucket Sort：

1. 建立 $n$ 個 buckets。

2. 對每個數字 $x$，依照

   $\left\lfloor \frac{nx}{1000} \right\rfloor$

   將其放入對應 bucket。

3. 分別排序各 bucket。

4. 按 bucket 順序輸出。

由於數值均勻分布，每個 bucket 的期望元素數量為常數。若使用 Insertion Sort 排序各 bucket，所有 bucket 內部排序的期望成本為

$$E\left[\sum_{i=1}^{n} k_i^2\right]=O(n),$$

其中 $k_i$ 為第 $i$ 個 bucket 中的元素數量。因此整體期望時間為

$$O(n)+O(n)=O(n).$$

為何比較排序下界不適用

$\Omega(n\log n)$ 是一般比較式排序的下界；本題已額外提供「均勻分布於固定區間」的資訊，因此可以利用分布進行 Bucket Sort，不受一般比較排序下界限制。

解題技巧

看到「已知均勻分布」時，優先想到 Bucket Sort。題目若只說「任意實數」，才通常考慮比較排序的 $\Theta(n\log n)$ 下界。

---

(b) BST 輸出並建立 Min-Heap

判定：F（錯誤）

題目聲稱需要 $w(n\log n)$ 時間，並非必要。

解題方法

可分成兩個步驟：

1. 輸出 BST 中的所有元素

對 BST 做中序走訪：

Inorder(node):
    Inorder(node.left)
    output node.key
    Inorder(node.right)

每個節點只拜訪一次，因此時間為

$$O(n).$$

中序走訪會按照遞增順序輸出所有 distinct integers。

2. 建立 Min-Heap

將走訪所得的 $n$ 個元素放入陣列後，使用 Bottom-Up Build-Heap，而非逐一插入：

for i = floor(n/2) downto 1:
    MinHeapify(A, i)

Bottom-Up Build-Heap 的總時間為

$$O(n),$$

因為高度為 $h$ 的節點數量快速減少，總成本可表示為

$$\sum_{h\ge 0}\frac{n}{2^{h+1}}O(h)=O(n).$$

因此總時間為

$$O(n)+O(n)=O(n).$$

反例

即使 BST 形狀極度不平衡，仍可中序走訪 $n$ 個節點，再以陣列線性建堆，總時間仍為 $O(n)$。所以不需要 $w(n\log n)$ 時間。

解題技巧

「逐一將元素插入 Heap」才會得到 $O(n\log n)$；「已經有全部元素，直接建 Heap」則可用 Bottom-Up Build-Heap，在 $O(n)$ 時間完成。

---

(c) 將邊權乘以 $-1$ 後使用 Dijkstra 求最長路徑

判定：F（錯誤）

核心觀念

對任意路徑 $P$，若將每條邊權乘以 $-1$，則

$$w'(P)=-w(P).$$

因此原圖中的最長路徑會對應到新圖中的最短路徑。然而，Dijkstra 演算法要求所有邊權必須滿足

$$w'(u,v)\ge 0.$$

題目只保證原圖「含有負邊」，並未保證所有原始邊權皆為負。若原圖同時含有正邊，乘以 $-1$ 後就會產生負邊，Dijkstra 不適用。

反例

考慮 DAG：

核心觀念

本題分為兩部分：

1. 軸對齊矩形的幾何判定

   • 檢查每台機器是否完全位於工廠內。
   • 檢查任兩台機器在水平方向與垂直方向是否均保持安全距離 $d$。

2. 圖論最佳化

   • 機器視為頂點。
   • 機器 $i,j$ 間的連線成本為邊權重 $c_{ij}=c_{ji}$。
   • 要使所有機器連通且總成本最小，是 Minimum Spanning Tree（最小生成樹，MST）。
   • 若要求所有機器形成一個環，則是 Traveling Salesperson Problem（旅行商問題，TSP）。

以下採用水平座標為 $x$、垂直座標為 $y$ 的慣例，因此工廠範圍為：

$$0\le x\le V,\qquad 0\le y\le U.$$

若依題目角點排列將兩座標軸對調，只需將 $U,V$ 以及 $x,y$ 對調，判定方法不變。

---

(a) 判斷給定座標是否符合限制

機器的邊界

機器 $i$ 的水平長度為 $v_i$，垂直長度為 $u_i$，中心為 $(x_i,y_i)$。

因此其邊界為：

• 左邊界：$x_i-\dfrac{v_i}{2}$
• 右邊界：$x_i+\dfrac{v_i}{2}$
• 上邊界：$y_i-\dfrac{u_i}{2}$
• 下邊界：$y_i+\dfrac{u_i}{2}$

---

(i) 檢查所有機器是否位於工廠內

機器 $i$ 完全位於工廠內，必須滿足：

$$x_i-\frac{v_i}{2}\ge 0$$ $$x_i+\frac{v_i}{2}\le V$$ $$y_i-\frac{u_i}{2}\ge 0$$ $$y_i+\frac{u_i}{2}\le U$$

等價地寫成中心座標限制：

$$\frac{v_i}{2}\le x_i\le V-\frac{v_i}{2}$$ $$\frac{u_i}{2}\le y_i\le U-\frac{u_i}{2}$$

對每台機器逐一檢查即可。

虛擬碼

for i = 1 to n:
    if xi - vi/2 < 0 or xi + vi/2 > V:
        return false
    if yi - ui/2 < 0 or yi + ui/2 > U:
        return false

return true

複雜度

每台機器只需進行固定次數的比較，因此：

$$\boxed{O(n)}$$

額外空間為：

$$\boxed{O(1)}$$

---

(ii) 檢查任兩台機器是否保持安全距離

題目要求任兩台機器的邊界：

• 水平方向至少相距 $d$；
• 垂直方向至少相距 $d$。

對機器 $i,j$ 而言，水平方向中心距離為 $|x_i-x_j|$。兩台機器在水平方向的半長度總和為：

$$\frac{v_i}{2}+\frac{v_j}{2}$$

因此，水平方向的安全條件為：

$$|x_i-x_j| \ge \frac{v_i+v_j}{2}+d$$

同理，垂直方向的安全條件為：

$$|y_i-y_j| \ge \frac{u_i+u_j}{2}+d$$

所以對任意 $i\ne j$，必須同時滿足：

$$|x_i-x_j| \ge \frac{v_i+v_j}{2}+d$$

且

$$|y_i-y_j| \ge \frac{u_i+u_j}{2}+d$$

若任一方向不符合，便判定違反安全距離。

虛擬碼

for i = 1 to n:
    for j = i + 1 to n:
        horizontalGap = |xi - xj| - (vi + vj)/2
        verticalGap   = |yi - yj| - (ui + uj)/2

        if horizontalGap < d:
            return false

        if verticalGap < d:
            return false

return true

其中：

$$\text{horizontalGap} = |x_i-x_j|-\frac{v_i+v_j}{2}$$

代表兩台機器邊界在水平方向的實際間隔；垂直方向同理。

複雜度

機器對數為：

$$\binom{n}{2}=\frac{n(n-1)}{2}$$

每一對只需固定時間檢查，因此：

$$\boxed{O(n^2)}$$

額外空間為：

$$\boxed{O(1)}$$

---

整體判定流程

先執行工廠內部檢查，再執行兩兩安全距離檢查：

1. 對所有機器檢查是否在工廠內，時間 $O(n)$。
2. 對所有機器對檢查安全距離，時間 $O(n^2)$。

因此整體時間複雜度為：

$$\boxed{O(n^2)}$$