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

核心觀念

本題考查資料檔案中的「次要鍵（secondary key）」用途。

• 主鍵（primary key）：可唯一識別每一筆紀錄，例如學號、身分證字號。
• 次要鍵（secondary key）：通常是非唯一屬性，用來依某個欄位快速查詢紀錄，例如姓名、系所、城市或職稱。同一個次要鍵值可對應多筆紀錄。

因此，次要鍵的重點是：

依照非唯一屬性建立索引，以支援有效率的紀錄檢索。

解題方法

判斷各選項是否符合次要鍵的兩項特徵：

1. 是否用來進行紀錄查詢？
2. 查詢條件是否可能對應多筆紀錄，而非要求唯一識別？

次要鍵通常會搭配**次要索引（secondary index）**使用。索引中的鍵值指向一筆或多筆符合條件的紀錄，例如：

查詢「資訊管理」時，系統可透過次要鍵快速找出多筆紀錄。

選項分析

(A) Uniquely identify each record in a data file

錯誤。唯一識別每筆紀錄是主鍵的功能。次要鍵不要求唯一，同一個鍵值可以對應多筆紀錄。

核心觀念

本題考查 inverted list（倒排表／倒排索引） 的定義與用途。

倒排表不是依照資料紀錄的順序儲存索引，而是建立「索引值 → 包含該值的紀錄清單」的對應關係。其基本形式為：

例如，資料表中有以下紀錄：

針對「科目」欄位建立倒排表後：

因此，搜尋某個屬性值時，可以直接取得對應紀錄清單，不必逐筆掃描所有資料。

解題方法

判斷倒排表的關鍵，是觀察資料的儲存方向：

• 一般索引常由「紀錄」指向索引值。
• 倒排表則由「索引值」反向指向包含該值的多筆紀錄。

題目中的選項若描述「將每個屬性值對應到包含該值的紀錄清單」，即符合倒排表的核心定義。

選項分析

(A) Stores records sequentially according to their primary keys

錯誤。此描述是按照主鍵順序連續儲存紀錄，較接近排序檔案或主鍵索引的概念。倒排表的重點不是依主鍵排列紀錄，而是由屬性值反向找到相關紀錄。

核心觀念

本題考查 reentrant list（可重入串列） 的設計目的。

一般串列節點通常包含一組鏈結欄位，例如：

• 單向串列：next
• 雙向串列：prev 與 next

若同一個節點需要同時隸屬於多個串列，單一組鏈結欄位會互相覆蓋，造成串列結構損壞。因此，reentrant list 會讓節點配置多組鏈結欄位，使同一節點能以不同的鏈結關係加入不同串列。

例如：

Node
 ├── listA_prev, listA_next
 └── listB_prev, listB_next

如此一來，同一個節點可以同時存在於 listA 與 listB，也能用來表達階層式、巢狀式或多重分類的資料結構。

解題方法

判斷本題的關鍵在於辨認「reentrant」所指的功能：

1. 題目談的是資料結構設計，而非多執行緒同步。
2. 若一個節點可以同時屬於多個串列，就必須具備彼此獨立的鏈結欄位。
3. 這種設計特別適合表示巢狀串列或多重串列結構。

因此，符合定義的是「支援巢狀串列，使節點能同時屬於多個串列」的選項。

選項分析

(A) Allow multiple threads to safely access a shared list without synchronization

錯誤。

Reentrant list 的「reentrant」不是指多執行緒安全，也不代表能在沒有同步機制的情況下安全存取共享串列。

多執行緒安全通常需要：

• mutex
• lock
• semaphore
• atomic operation

若多個執行緒同時修改串列，仍可能產生競爭條件，因此 reentrant list 本身不能消除同步需求。

(B) Enable traversal of a list in both forward and backward directions using a single pointer per node

錯誤。

核心觀念

重入串列表示法依節點的出邊，由左至右列出各元素；若出邊連到另一個串列節點，就用括號保留該層子串列；若連到葉節點，則直接寫葉節點標籤。DAG 中共用的子節點可以有多個父節點，沿不同分支表示時仍須保留各自的串列層次。

解題方法

圖中根節點向下連到四個中間圓點。由左至右，四個圓點分別連到 a、a,b,c、c 與共用的子串列節點，以及該共用節點；共用節點再連到 d,e。因此，各中間圓點本身代表的串列層次都要保留。

依序寫出四個分支：

1. 左側中間圓點只連到葉節點 a，所以是 (a)。
2. 第二個中間圓點連到 a,b,c，所以是 (a,b,c)。
3. 第三個中間圓點連到 c，以及包含 d,e 的子串列，所以是 (c,(d,e))。
4. 最右側中間圓點連到包含 d,e 的子串列；它本身也是一層串列，因此是 ((d,e))。

核心觀念

本題考查動態記憶體配置器（dynamic memory allocator）管理 free list 的資料結構選擇，重點包括：

• 空閒區塊的配置與釋放
• 區塊分割（block splitting）
• 立即合併（immediate coalescing）
• 單向鏈結串列與雙向鏈結串列的操作複雜度

配置器通常以鏈結串列記錄所有空閒記憶體區塊。當配置請求發生時，配置器會：

1. 在 free list 中尋找大小足夠的空閒區塊。
2. 若區塊過大，將其分割。
3. 將被使用的區塊從 free list 移除。
4. 釋放區塊時，將其重新插入 free list。
5. 若相鄰區塊也是空閒區塊，立即合併以減少外部碎片。

雙向鏈結串列的每個節點通常包含：

• prev：前一個空閒區塊
• next：下一個空閒區塊

因此，若已經取得某個節點的指標，就能在常數時間內完成移除。

解題方法

判斷本題的關鍵，是區分兩件事：

1. 尋找合適大小區塊的時間
2. 已知區塊位置後，將其從 free list 移除或重新插入的時間

雙向鏈結串列並不會自動讓配置器在 free list 中快速找到合適大小的區塊。若 free list 沒有額外依大小分類，尋找適合區塊仍可能需要逐一走訪，時間複雜度通常是 $O(n)$。

雙向鏈結串列真正的優勢在於：已知節點位置時，可以直接透過 prev 與 next 更新鄰接節點，不必從串列頭開始搜尋該節點的前驅。

假設要移除節點 $x$：

這些操作只涉及固定數量的指標更新，因此時間複雜度為：

若使用單向鏈結串列，即使已知 $x$ 的位置，也通常還需要先找到其前驅節點，才能令前驅節點的 next 指向 $x.next$。此搜尋需要走訪串列，時間複雜度可能為 $O(n)$。

因此，雙向鏈結串列特別適合頻繁進行空閒區塊移除、重新插入與合併管理。

選項分析

(A) A doubly linked list allows the allocator to locate a free block of suitable size in constant time during allocation.

錯誤。

雙向鏈結串列只改善節點之間的前後連結與刪除操作，不代表能在常數時間內找到符合大小的區塊。

若 free list 中有 $n$ 個空閒區塊，配置器使用 first-fit 或 best-fit 搜尋時，通常需要逐一檢查區塊大小，搜尋成本可能為：

要達成較快的大小搜尋，通常需要使用 segregated free lists、平衡樹或其他依區塊大小組織的資料結構，不能只靠雙向鏈結串列。

(B) A doubly linked list guarantees zero external fragmentation by preserving physical adjacency of memory blocks.

錯誤。

外部碎片（external fragmentation）是指記憶體中存在許多分散的小型空閒區塊，雖然空閒總量足夠，卻沒有連續的大區塊可供配置。

核心觀念

本題考查 $k$ 路合併（multi-way merging）的時間複雜度。

給定 $k$ 個已排序序列，總元素數為 $N$。合併過程中，每次都必須從目前各序列的最小候選元素中，選出全域最小值。

若使用大小為 $k$ 的 binary min-heap：

• 建立最小堆：可在 $O(k)$ 時間完成。
• 每輸出一個元素：取出最小值並補入該序列下一個元素，需 $O(\log k)$。
• 共輸出 $N$ 個元素，因此總時間為

在比較模型中，$k$ 路合併的下界為

因此 binary min-heap 方法達到漸近最佳複雜度。

解題方法

比較每個選項所宣稱的時間複雜度，並與標準的 $k$ 路合併演算法及比較模型下界對照。

關鍵判斷是：每次從最多 $k$ 個候選元素中選出最小值，使用堆或 tournament tree 時，單次選擇通常需要 $O(\log k)$，所以整體通常為 $O(N\log k)$，而不是單純的 $O(N)$。

選項分析

(A) 錯誤

每一步掃描所有 $k$ 個序列，尋找目前最小元素，單次需 $O(k)$；總共輸出 $N$ 個元素，因此時間複雜度為

前半段的複雜度敘述正確，但「當 $k=O(N)$ 時漸近最佳」錯誤。

當 $k=\Theta(N)$，每個序列可能只有一個元素，此時問題等同於將 $N$ 個未排序元素排序，比較模型下至少需要

而直接掃描的成本為

顯然不是漸近最佳。

(B) 錯誤

即使所有序列長度相同，使用 divide-and-conquer 兩兩合併：

• 第一層合併總成本為 $O(N)$。
• 第二層仍需處理總共 $N$ 個元素，成本為 $O(N)$。
• 共需 $\log k$ 層。

因此總時間為

核心觀念

本題考查以位元向量（bit vector）表示集合時的空間需求與基本集合運算複雜度。

給定宇宙集合：

集合 $S\subseteq U$ 使用長度為 $n$ 的位元向量 $B$ 表示：

因此，每個宇宙元素都對應到一個固定位置，不論 $S$ 中實際包含多少元素，都必須配置 $n$ 個位元。

解題方法

判斷各選項時，分別檢查：

1. 位元向量需要多少空間；
2. 聯集與交集如何透過位元運算完成；
3. 成員測試是否需要搜尋；
4. 位元向量與平衡搜尋樹在集合運算上的相對效率。

位元向量的優勢在於：集合運算可以直接轉換成逐位元的布林運算。

若 $B_S$ 與 $B_T$ 分別表示集合 $S$ 與 $T$，則：

集合聯集：

集合交集：

這些運算最多需要檢查長度為 $n$ 的整個向量，因此時間複雜度為 $O(n)$。

成員測試則只需直接查看對應位置：

因為陣列索引存取為常數時間，所以成員測試為 $O(1)$。

選項分析

(A) 錯誤

選項稱位元向量需要 $O(|S|)$ 的空間。

實際上，位元向量長度固定為 $n$，每個元素 $0,1,\ldots,n-1$ 都有一個對應位元，因此空間需求為：

而不是 $O(|S|)$。

當集合 $S$ 很稀疏，也就是 $|S|\ll n$ 時，位元向量確實可能浪費空間；但選項將空間複雜度寫成 $O(|S|)$，因此敘述錯誤。

(B) 正確

聯集可用逐位元 OR 運算：

核心觀念

Composite（組合）設計模式的目的，是將「個別物件」與「物件集合」組織成樹狀結構，並讓客戶端透過共同介面，以一致方式操作兩者。

其主要角色如下：

• Component：定義葉節點與組合節點共同使用的介面。
• Leaf：代表樹中的個別物件，不含子物件。
• Composite：代表由多個 Component 組成的集合，可管理子物件並遞迴呼叫其操作。

典型結構如下：

因此，客戶端不必區分目前操作的是單一物件還是由多個物件組成的集合。

解題方法

判斷 Composite 設計模式時，抓住兩個核心特徵：

1. 樹狀遞迴組合：Composite 可以包含其他 Component，因此能形成多層次結構。
2. 共同介面與一致操作：Leaf 與 Composite 都實作 Component 介面，客戶端可以用相同方式呼叫操作。

例如檔案系統中：

• 檔案是 Leaf。
• 資料夾是 Composite。
• 檔案與資料夾都可以提供 display() 操作。
• 客戶端呼叫資料夾的 display() 時，資料夾再遞迴呼叫內部檔案與子資料夾的 display()。

符合上述兩項特徵的敘述，即為正確答案。

選項分析

(A) 錯誤

In the Composite pattern, leaf objects must implement all child-management operations, even if those operations are meaningless.

葉節點本身沒有子物件，因此 addChild()、removeChild()、getChild() 等子物件管理操作，對 Leaf 通常沒有意義。

Composite 模式常見的設計取捨是：

• 將子物件管理操作放在 Component 介面中，使客戶端獲得更透明的統一介面；
• 或只放在 Composite 中，使型別介面更安全。

即使採用前者，也不代表 Leaf「必須實作所有操作且正常具備管理子節點能力」；Leaf 可以拒絕操作、回傳錯誤，或採用預設實作。因此「必須實作所有子物件管理操作」不是 Composite 模式的必要條件。

(B) 正確

The Composite pattern enables recursive composition of objects while allowing clients to interact with both primitive and composite objects through a common interface.

核心觀念

本題考查以 Compressed Sparse Row（CSR） 儲存稀疏矩陣後，進行矩陣與稠密向量乘法的時間複雜度。

令矩陣 $A$ 與向量 $x$ 相乘：

其中：

• $A$ 為 $n \times n$ 矩陣；
• $x$、$y$ 為長度 $n$ 的稠密向量；
• $\mathrm{nnz}$ 表示矩陣 $A$ 中非零元素的數量。

CSR 通常使用三個陣列：

1. values：儲存所有非零元素；
2. colIndex：記錄每個非零元素的欄索引；
3. rowPtr：記錄每一列非零元素在前兩個陣列中的起訖位置。

因此，CSR 不會逐一處理矩陣中的 $n^2$ 個位置，而只處理 $\mathrm{nnz}$ 個非零元素。

解題方法

矩陣向量乘法的第 $i$ 個結果為：

在 CSR 中，第 $i$ 列只會儲存非零元素，因此計算方式可表示為：

for i = 0 to n - 1:
    y[i] = 0
    for k = rowPtr[i] to rowPtr[i+1] - 1:
        y[i] += values[k] * x[colIndex[k]]

內層迴圈每執行一次，就處理一個非零元素。整個矩陣所有列的內層迴圈總執行次數為：

每次執行只包含固定次數的乘法、加法及陣列存取，因此主要計算成本為：

在均勻雜湊下，分離鍊（separate chaining）每個槽的期望鏈長為
$\alpha = \frac{n}{m}$
其中 $\alpha$ 為負載因子。對於一次成功搜尋，須先計算雜湊函式取得槽位，接著在該槽的鏈表中尋找目標鍵。

關鍵概念

• Max‑Heap：對任意父節點 $i$，都有 $A[i]\ge A[2i]$、$A[i]\ge A[2i+1]$（若子節點存在）。
• 逆序 (inversion)：$i<j$ 且 $A[i]>A[j]$。逆序越少，陣列越接近遞增排序。

步驟

1. 逐一檢驗六個陣列是否符合 Max‑Heap 的父子關係。
2. 對每個有效 Heap 計算逆序數 $\displaystyle \sum_{i=1}^{7}\bigl|\{j>i\mid A[i]>A[j]\}\bigr|$。
3. 取逆序最小的陣列即為答案。

驗證與逆序計算

核心觀念

本題考查巢狀迴圈的時間複雜度，主要使用：

• 每次將變數除以 $2$，迴圈次數為對數級：$\Theta(\log n)$。
• 若每次將變數乘以 $2$，從 $1$ 增加到上限 $M$，迴圈次數為 $\Theta(\log M)$。
• 巢狀迴圈的總成本，必須將內層迴圈次數對外層每一輪加總。

解題方法

外層迴圈控制變數為 $a$，初始值為 $n$，每次執行：

因此 $a$ 的變化為：

當 $a\leq 1$ 時停止，所以外層迴圈次數為：

在外層某一輪中，內層迴圈先令 $b=1$，每次執行：

直到 $b>a^2$。因此內層迴圈次數為：

設外層第 $i$ 輪時：

則該輪內層迴圈次數為：

總時間複雜度為：

這是一個從 $\log n$ 遞減至 $1$ 的等差級數，因此：

所以其緊確漸近複雜度為：

選項分析

關鍵概念

• 插入序列產生的 BST 形狀唯一決定於相對次序：根必須最先插入；之後左、右子樹的鍵可以任意交錯，只要各自在子樹內保持能產生該子樹形狀的順序。
• 給定 BST 形狀，產生它的插入序列數量遵循遞迴公式

$N(T)=\binom{n-1}{L}\,N(T_L)\,N(T_R)$

其中 $n$ 為節點總數，$L$ 為左子樹大小，$T_L,T_R$ 為左右子樹。

步驟

1. 高度恰好 2 的唯一形狀是完美平衡樹：根 4，左子樹 $\{1,2,3\}$（根 2，子 1、3），右子樹 $\{5,6,7\}$（根 6，子 5、7）。

2. 根 4 必須是第一個插入的鍵，故固定第一位。剩餘 6 個鍵分為左子樹 3 個、右子樹 3 個，可任意交錯。交錯方式數為

核心觀念

本題考查最小生成樹（Minimum Spanning Tree, MST）以及 Prim 演算法、Kruskal 演算法的選邊規則。

• Prim：從指定起點 $A$ 開始，每次選擇「目前生成樹與外部頂點之間」權重最小的邊。
• Kruskal：將所有邊依權重遞增排序，依序加入不會形成環的邊。
• 若邊權重全部唯一，Prim 與 Kruskal 會得到相同的 MST 邊集合；本題有兩條權重皆為 $3$ 的邊，因此結果會受到 tie-breaking 影響。

解題方法

邊依權重排列如下：

以 Prim 從 $A$ 開始：

1. 從 $A$ 出發，最小邊為 $(A,B)$，加入。
2. 目前樹包含 $\{A,B\}$，最小跨界邊為 $(B,C)$，加入。
3. 目前樹包含 $\{A,B,C\}$，可連接 $D$ 的邊為 $(C,D)$ 與 $(D,A)$，兩者權重同為 $3$。

因此 Prim 的第三條邊可選：

以 Kruskal 演算法：

1. 加入 $(A,B)$，權重 $1$。
2. 加入 $(B,C)$，權重 $2$。
3. 接著處理權重為 $3$ 的兩條邊。兩條邊都能將 $D$ 接入目前的樹，且不形成環，因此先處理的那一條會被加入，另一條不再需要。

若依題目列出的順序處理權重相同的邊，Kruskal 先加入 $(C,D)$，故選項答案為 (C)。若 Kruskal 先處理 $(D,A)$，則會得到另一組同樣合法的 MST。

本題未明確指定權重相同時的 Kruskal tie-breaking 順序；以下採用題目列出的邊順序作為合理假設。

選項分析

核心觀念

本題的核心考點為排序演算法的穩定性（Stability of Sorting Algorithms）。

1. 穩定排序（Stable Sort）的定義：
   若待排序序列中存在鍵值（Key）相同的兩筆資料 $R_i$ 與 $R_j$，且在排序前 $R_i$ 出現在 $R_j$ 之前（即原始位置索引 $i < j$ 且 $\text{Key}(R_i) = \text{Key}(R_j)$），經排序完成後，$R_i$ 依然出現在 $R_j$ 之前，則稱該排序演算法具備「穩定性」。
2. 非穩定排序（Unstable Sort）：
   若排序演算法無法保證鍵值相同的資料在排序後維持原有的相對先後順序（即可能發生順序顛倒），則為非穩定排序。
3. 預設排序方向：
   在電腦科學與研究所入學考試中，若題目未特別說明排序方向，一律預設為遞增排序（Ascending Order）。

解題方法

1. 鎖定相同鍵值的元素與其原始相對位置：
   原始輸入序列為：

   $$[(3, \text{A}), (2, \text{B}), (3, \text{C}), (1, \text{D})]$$

   其中鍵值相同（$\text{Key} = 3$）的項目有兩筆：

   • $(3, \text{A})$ 與 $(3, \text{C})$
   • 原始相對先後順序：$(3, \text{A})$ 在 $(3, \text{C})$ 之前。

2. 推導標準遞增排序結果：
   依鍵值遞增排序後，鍵值順序應為 $1 \le 2 \le 3 \le 3$：

   • 若為穩定排序（Stable）：鍵值為 $3$ 的兩項必須維持原順序，即 $(3, \text{A})$ 在前、$(3, \text{C})$ 在後。 $$[(1, \text{D}), (2, \text{B}), (3, \text{A}), (3, \text{C})]$$
   • 若為非穩定排序（NOT Stable）：鍵值為 $3$ 的兩項相對順序發生翻轉，即 $(3, \text{C})$ 在前、$(3, \text{A})$ 在後。 $$[(1, \text{D}), (2, \text{B}), (3, \text{C}), (3, \text{A})]$$

選項分析

核心觀念

本題考查 NP-complete（NP 完全）問題的定義與多項式時間歸約。

問題 $Q$ 為 NP-complete，必須同時符合：

1. $Q \in NP$：給定一組候選解，可在多項式時間內驗證其正確性。
2. $Q$ 為 NP-hard：對所有問題 $L \in NP$，皆存在多項式時間歸約
   $L \leq_p Q$

題目另給定 $P \neq NP$，因此 NP-complete 問題不可能存在多項式時間演算法。若某個 NP-complete 問題可在多項式時間內解決，便會推出 $P=NP$，與題設矛盾。

解題方法

直接依照 NP-complete 的兩項定義判斷：

• 「所有 NP 問題都能多項式歸約到 $Q$」是 NP-hard 的定義，必然成立。
• 「可在多項式時間驗證」是 $Q \in NP$ 的性質，也必然成立。
• 其餘選項須檢查是否與 $P \neq NP$ 或已知複雜度矛盾。

選項分析

(A) There exists a polynomial-time algorithm to solve Q.

錯誤。

若 $Q$ 存在多項式時間演算法，則 $Q \in P$。由於每個 $L \in NP$ 都可多項式歸約至 $Q$，先將 $L$ 的輸入轉換成 $Q$ 的輸入，再以多項式時間解決 $Q$，即可在多項式時間解決所有 NP 問題。

因此會得到：

$P=NP$

但題目明確假設 $P\neq NP$，所以 $Q$ 不存在多項式時間演算法。

(B) Q cannot be verified in polynomial time.

錯誤。

因為 $Q$ 為 NP-complete，首先必須滿足 $Q\in NP$。這表示給定候選解後，可以在多項式時間內驗證該候選解是否為 $Q$ 的有效解。

因此 $Q$ 可以在多項式時間驗證。

(C) Any problem in NP can be polynomially reduced to Q.

正確。

這正是 $Q$ 為 NP-hard 的定義。形式化表示為：

$\forall L\in NP,\quad L\leq_p Q$

核心觀念

本題比較兩種字典（dictionary）資料結構：

• 平衡二元搜尋樹（balanced binary search tree），如紅黑樹（red-black tree）
• 使用 separate chaining 的雜湊表（hash table）

平衡二元搜尋樹同時維持：

1. 二元搜尋樹性質：左子樹鍵值小於根，右子樹鍵值大於根。
2. 平衡性：樹高維持在 $O(\log n)$。

因此搜尋、插入、刪除在最壞情況下皆為：

雜湊表則透過雜湊函數將鍵值映射至桶（bucket）。在雜湊函數良好且負載因子適當時，搜尋、插入、刪除的平均時間為 $O(1)$；但最壞情況下，大量鍵值碰撞至同一桶，時間可退化為：

兩者的關鍵差異在於：雜湊表不維持鍵值順序，平衡二元搜尋樹則維持排序結構。

解題方法

題目詢問平衡二元搜尋樹相對於雜湊表的「嚴格優勢」（strict advantage），判斷重點是：

哪一項功能是平衡二元搜尋樹自然支援，而雜湊表本身無法有效支援？

範圍查詢，例如找出所有介於 $10$ 與 $50$ 的鍵值，以及依照鍵值排序走訪，都需要資料結構保留鍵值順序。

平衡二元搜尋樹可以利用中序走訪（in-order traversal）取得遞增排序結果。範圍查詢的時間複雜度為：

其中：

• $n$ 是樹中的總鍵數
• $k$ 是符合範圍條件的元素數量

$O(\log n)$ 用於定位範圍起點，$O(k)$ 用於輸出符合條件的鍵。

雜湊表沒有鍵值順序。若要進行範圍查詢，通常必須掃描所有元素，時間為 $O(n)$；若要排序後再走訪，則需額外排序，時間至少為 $O(n\log n)$。

因此正確答案是 (D)。

選項分析

(A) Better average-case time complexity for insertion.

錯誤。

雜湊表在一般假設下，插入的平均時間為：

平衡二元搜尋樹插入時，必須沿樹高尋找適當位置，並可能進行旋轉維持平衡，時間為：

因此平衡二元搜尋樹沒有較佳的平均插入時間複雜度。

(B) Uses less memory for storing integers.

錯誤。

記憶體使用量取決於實作方式，例如：

• 樹節點需要儲存鍵值、左右子指標，以及紅黑樹的顏色或平衡資訊。
• 雜湊表需要配置桶陣列，鏈結串列節點也需要指標與額外欄位。

兩者沒有對所有實作都成立的固定記憶體優勢。單純儲存整數並不能推出平衡二元搜尋樹一定使用較少記憶體，因此這不是嚴格優勢。

核心觀念

Dijkstra’s algorithm 的正確性建立在以下條件：

也就是所有邊的權重都必須是非負數。當節點 $u$ 從優先佇列取出時，Dijkstra 會認定目前的距離 $d(u)$ 已經是最短距離，並且不再允許之後透過其他節點改善它。

若存在負權重邊，例如：

則可能出現「$B$ 已先被取出，但之後經過 $A$ 才發現更短路徑」的情況，破壞 Dijkstra 的貪心假設。

若負權邊屬於從 $S$ 可達的負權環，沿著該環繞行越多次，路徑成本會持續下降：

其中 $C<0$。因此不存在有限的最短路徑。

解題方法

題目問的是「在什麼條件下，Dijkstra 一定無法找到正確最短路徑」。

逐一判斷各選項是否具有「必然失敗」的保證：

• 單純存在負權邊，不代表一定會造成錯誤。
• 必須考慮節點取出順序，以及負權邊是否真的能產生更短路徑。
• 若存在從起點 $S$ 可達的負權環，則某些節點的最短距離不存在，Dijkstra 當然不可能求得正確的有限最短距離。

因此具有必然性的條件是：

選項分析

(A) If the shortest path to B goes through A.

錯誤。

即使 $B$ 的最短路徑經過 $A$，只要 $A$ 在 $B$ 之前被取出，Dijkstra 就能先處理 $A\to B$，正確更新 $B$ 的距離。

此外，選項沒有說明 $B$ 是否在 $A$ 之前被取出，因此不足以保證失敗。

(B) If node B is visited (popped from priority queue) before node A.

錯誤。

$B$ 先於 $A$ 被取出，確實可能導致錯誤，但不一定。

例如：

此時：

• $B$ 目前距離為 $1$
• $A$ 目前距離為 $10$
• 因此 $B$ 會先被取出
• 經過 $A$ 到 $B$ 的路徑長度為 $10-5=5$

因為 $5>1$，負權邊並未形成更短路徑，演算法仍可得到正確答案。

所以「$B$ 先於 $A$ 被取出」只是可能造成失敗，並非一定失敗。

(C) If the shortest path to A is strictly shorter than the shortest path to B.

錯誤。

這只是表示：

核心觀念

1. 插入排序法（Insertion Sort）之迴圈不變性（Loop Invariant）：

   • 插入排序法在處理長度為 $n$ 的陣列時，外層迴圈（Outer loop）索引 $i$ 由 $1$ 遞增至 $n-1$。
   • 每完成第 $k$ 次外層迭代（處理完索引 $k$ 的元素插入），陣列的前綴子陣列 $A[0..k]$ 保證為已排序狀態（Sorted）。
   • 尚未被處理的後續元素 $A[k+1..n-1]$ 則維持原本的相對位置與未排序狀態。

2. 鍵值大小關係（Total Order & Duplicates）：

   • 在標準非遞減（Non-decreasing / 升冪）排序中，已排序前綴滿足相鄰元素 $A[j] \le A[j+1]$。
   • 若題目未特別宣告所有元素相異（Distinct），則元素之間可能相等（即具重複鍵值），故僅能推得 $\le$ 或 $\ge$，不可直接推論嚴格不等式（$<$ 或 $>$）。

解題方法

1. 比對初始狀態與中間狀態：

   • 初始陣列（Initial State）：$[@, \#,$$$, \%, \&, *]$（長度 $n=6$，索引 $0 \sim 5$）
   • 中間狀態（Intermediate State）：$[\&, \#,$$$, @, \%, *]$

2. 分析元素移動與已排序前綴：

   • 原本位於索引 $4$ 的元素 $\&$ 已被移至最前端（索引 $0$），而原本前 $4$ 個元素 $[@, \#,$$$, \%]$ 依序向右位移一格成為索引 $1 \sim 4$。
   • 索引 $5$ 的元素 $*$ 仍停留在原位未動。
   • 這代表演算法已完成索引 $4$（即第 4 個外層迴圈）的插入步驟，使得前 5 個元素所構成的前綴子陣列 $A[0..4]

核心觀念

前序走訪的順序是「根、左子樹、右子樹」；後序走訪的順序是「左子樹、右子樹、根」。兩種走訪都會恰好拜訪每個節點一次。

題目另給每個節點的值都不同。這使我們可以根據走訪序列中的值，辨認每個位置對應的節點。

解題方法

若樹有 $N>1$ 個節點，前序走訪的第一個值是根節點的值；後序走訪的最後一個值也是根節點的值。

兩個走訪序列若完全相同，則這個相同序列的第一個值與最後一個值必須相等。但序列長度大於 $1$，第一個位置與最後一個位置分別對應不同節點；因節點值互異，兩值不可能相等，產生矛盾。

因此樹只能有一個節點：

單一節點的高度為 $H=0$，所以唯一符合條件的情形是 $(N,H)=(1,0)$。

選項分析

• (A) $N=1$，不論 $H$ 為何：正確，且是題目意圖的答案。
  符合條件的樹只能是單一節點，因此 $N=1$。實際上此時高度必為 $0$。

• (B) $N=H+1$：對符合條件的樹也成立。
  唯一符合條件的情形是 $N=1$、$H=0$，代入得 $1=0+1$。因此若把選項解讀為「所有符合條件的樹都滿足此式」，它也正確。

核心觀念

本題考排序演算法的穩定性、資料結構對時間複雜度的影響，以及「交換次數」和「比較次數」的差別。

穩定排序會保留相同鍵值元素原本的相對順序。複雜度記號 $O(g(N))$ 表示漸近上界；$\Theta(g(N))$ 才表示緊確的漸近階。因此，若某數量是 $O(N)$，它也符合 $O(N^2)$。

解題方法

原卷 B-11 題列出六個敘述，內容涉及快速排序、堆積排序、LSD 基數排序、合併排序、插入排序與選擇排序。逐項用各演算法的穩定性、最佳情況，以及最壞情況下的操作次數判斷；特別留意選項 F 使用的是 $O(N^2)$，而不是 $\Theta(N^2)$。

選項分析

• (A) 錯。 Hoare 分割法的快速排序會交換元素，可能改變相同鍵值元素的相對順序，因此不保證穩定。
• (B) 錯。 堆積排序在建堆與取出堆頂時會移動元素，可能打亂相同鍵值元素的相對順序，因此不穩定。
• (C) 對。 LSD 基數排序從低位數字開始逐位排序。每一輪都必須穩定，才能保留前一輪已建立的低位排序次序；計數排序是常見的穩定子排序法。

核心觀念

拓樸排序是將有向圖的頂點排成線性順序，使每條有向邊 $u\to v$ 都符合「$u$ 排在 $v$ 前面」。有向圖存在拓樸排序，若且唯若它是有向無環圖（DAG）。

若圖中有有向環，環上各頂點會形成一連串「必須排在下一頂點之前」的限制，最後又要求回到起點之前，彼此矛盾，因此不存在拓樸排序。

解題方法

原卷頁圖的 B-12 題目與選項和題幹所列相符；圖中沒有另附特定圖形，需判斷的是拓樸排序的定義、唯一性及複雜度。逐一核對各選項，並特別區分標準時間式 $O(V+E)$ 與稠密圖下的最壞情況 $O(V^2)$。

選項分析

• (A) 錯。 拓樸排序用於有向圖，且必須是 DAG；無向圖沒有邊的方向，不能直接套用拓樸排序的定義。
• (B) 對。 含有有向環的圖不存在符合所有邊方向限制的線性順序，因此無法計算出拓樸排序。
• (C) 錯。 拓樸排序不一定唯一。例如兩個頂點間沒有任何邊時，兩種排列都符合條件。
• **(D) 錯。

核心觀念

本題考的是 Kruskal 最小生成樹演算法的時間複雜度分析，以及在使用 Weighted Quick Union with Path Compression（WQU+PC） 的 Union-Find 資料結構時，各個步驟的漸近成本比較。考生須掌握：

1. Kruskal 演算法的流程：排序所有邊 → 依序取最小邊 → 用 Union-Find 判斷是否形成環 → 不成環則加入 MST。
2. 各步驟的時間複雜度。
3. 在稀疏圖（$E \approx V$）的條件下，哪個步驟主導（dominate）整體漸近複雜度。

解題方法

原卷圖（見原卷頁圖）確認題目為 B-13，條件為稀疏圖 $E \approx V$，Union-Find 使用 WQU+PC。以下逐步分析 Kruskal 演算法各組成部分的成本：

Kruskal 演算法的主要步驟與對應複雜度：

其中 $\alpha(V)$ 是 inverse Ackermann function，對所有實際規模的 $V$ 而言 $\alpha(V) \le 5$，視為常數。

在 $E \approx V$ 的條件下：

比較可知 $O(V \log V)$ 嚴格大於 $O(V)$，因此 排序步驟主導整體時間複雜度。

選項分析

(A) The initialization of the union-find data structure.
❌ 初始化 Union-Find 只需 $O(V)$，為線性時間，被排序的 $O(V \log V)$ 所支配。

(B) The sorting of all edges based on their weights.
✅ 排序所有邊的成本為 $O(E \log E)$。因為 $E \approx V$，此為 $O(V \log V)$。又 $\log E = \Theta(\log V)$（因 $E \approx V$），故排序成本為 $O(V \log V)$，是所有步驟中漸近最大的，主導整體複雜度。