108 年 國立中正大學資訊工程學系碩士班《軟體設計》

cout 是 C++ 標準函式庫 iostream 中定義的一個物件 (object)，它的型別是 ostream 的一個實例。

C++11 標準引入了 bool 型別來表示布林值 (true/false)。
選項 (a) 嘗試將字串 "true" 賦值給 char 型別，這是錯誤的。
選項 (b) 正確地宣告了一個 bool 型別的變數 errorFlag 並賦值為 true。

在 C++ 中，private 成員（變數或函數）只能在宣告該成員的類別 (class) 內部被存取。

我們要判斷哪個函數能真正增加傳入的 double 變數的值。

• incl(double &a): 參數 a 是 double 的參考 (reference)。參考相當於給原來的變數取了別名。因此，a++ 會直接修改傳入的變數。此函數會增加傳入的 double 值。

• inc2(double *p): 參數 p 是 double 的指標 (pointer)。p++ 是指標的算術運算，它會將指標 p 本身移動到下一個 double 的記憶體位置，而不是改變 p 所指向的 double 的值。因此，此函數不會增加傳入的 double 值。

當使用 new 來配置一個陣列時 (例如 new int[100])，必須使用 delete[] 來釋放該陣列的記憶體。delete[] 告訴系統這是一個陣列的刪除操作，需要釋放所有陣列元素所佔用的記憶體。

我們來逐一分析每個函數宣告的正確性：

1. int sum1 (int a=1, int b=2; int c=3);
   在 C++ 中，函數宣告時，預設參數 (default arguments) 必須從右邊開始，也就是說，如果一個參數有預設值，那麼它右邊的所有參數也必須有預設值。在這個宣告中，b 有預設值，但 c 也有預設值，這本身沒問題。然而，參數列表中的分號 ; 是不應該出現在這裡的。參數之間應該用逗號 , 分隔。因此，sum1 的宣告是錯誤的。

複製建構子 (Copy Constructor) 在 C++ 中有幾種常見的觸發時機：

1. 物件的初始化 (Initialization of objects)：當一個物件使用同型別的另一個物件來初始化時。這包括：

   • MyClass obj2 = obj1;
   • MyClass obj2(obj1);
   • MyClass obj2{obj1}; (C++11 onwards)

2. 參數傳遞時以傳值方式 (Passing objects by value to functions)：當一個物件被作為參數傳遞給一個函數，而該函數的參數是傳值方式時，會呼叫複製建構子來建立一個參數的副本。

3. 函數傳回物件時以傳值方式 (Returning objects by value from functions)：當一個函數傳回一個物件，並且該物件是以傳值方式傳回時，會呼叫複製建構子來建立傳回值的副本。

純虛函數 (Pure Virtual Function) 是 C++ 中用來定義抽象基底類別 (Abstract Base Class) 的一種機制。純虛函數的宣告方式是在函數宣告的末尾加上 = 0;。

選項分析：
(a) virtual void f() = 0 {};：這是錯誤的語法。= 0; 表示純虛函數，但函數體 {} 則表示函數有定義。純虛函數不應該有函數體。
(b) void virtual f() = 0 {};：virtual 關鍵字應該放在返回型別之前，而不是之後。所以語法錯誤。
(c) virtual void f() { } = 0;：這個選項的語法是錯誤的。

程式碼使用 cin >> i >> d >> c >> str; 來從標準輸入讀取資料。cin 在讀取時，預設會跳過空白字元（空格、Tab、換行等），直到遇到第一個非空白字元為止。

輸入是 30 40 King Dome。

1. cin >> i;：讀取整數 30。i 的值為 30。輸入緩衝區中剩餘： 40 King Dome。
2. cin >> d;：跳過前面的空格，讀取下一個數字 40。d 的值為 40.0。輸入緩衝區中剩餘： King Dome。

我們逐行追蹤程式碼的執行：

1. #include <iostream>：包含輸入輸出函式庫。
2. void f (int& p1, int& p2) { p1 = p2 + 7 * 2; }：定義一個函數 f，它接受兩個整數的參考作為參數。函數體內，p1 被賦值為 p2 加上 7 * 2 (也就是 14)。因為參數是參考，所以對 p1 的修改會影響到傳遞給它的原始變數。
3. int main (void) { ... }：主函數開始。
4. int x, y;：宣告兩個整數變數 x 和 y。
5. x = 2;：將 x 初始化為 2。此時 x = 2。
6. f (x, x);：呼叫函數 f，傳入 x 作為 p1 和 p2。
   • 在 f 函數內部，p1 和 p2 都引用 x。
   • 計算 p2 + 7 * 2：x + 14，即 2 + 14 = 16。
   • 將結果賦值給 p1：x = 16。
   • 所以，呼叫 f(x, x) 後，x 的值變為 16。
7. y = x;：將 x 的當前值 (16) 賦值給 y。

當使用輸入串流 (如 ifstream 或 cin) 讀取資料時，如果讀取失敗（例如，檔案內容不是預期的格式，或者到達檔案結尾），串流物件本身會進入一個錯誤狀態。C++ 的串流物件可以被轉換為布林值，來檢查其狀態。

• 當串流處於正常狀態時，轉換為 bool 結果為 true。
• 當串流發生錯誤（如讀取失敗）時，轉換為 bool 結果為 false。

在這個情境下，iFile >> count; 嘗試將檔案中的內容讀入整數變數 count。如果檔案內容是 'x' 而不是一個有效的整數，這個讀取操作會失敗，導致 iFile 進入錯誤狀態。

選項分析：
(a) if (iFile) { ... } else { ... }：這是檢查串流狀態的標準 C++ 方法。如果 iFile 處於錯誤狀態，if (iFile) 會評估為 false，從而進入 else 區塊，表示錯誤發生。這正是我們需要的。

(b) if (iFile[0] != int) { ... }：ifstream 物件不能使用 [] 運算符來存取特定位置的字元，更不用說與 int 進行比較。語法錯誤。

(c) char chCount = char (count); if (isalpha(chCount)) { ... }：這嘗試將讀取到的整數 count 轉換為 char，然後檢查 char 是否是字母。

核心觀念

本題考查：

1. 二元搜尋樹（Binary Search Tree, BST）的建立。

2. leftSize 欄位的意義：
   $\text{leftSize}(u)=\text{左子樹節點數}+1$

   其中額外的 $1$ 代表節點 $u$ 自己。

3. 利用左子樹大小，在 BST 中尋找第 $k$ 小元素。

4. BST 的中序走訪結果會按照遞增順序排列。

解題方法

依照題目給定順序插入：

$65,\ 50,\ 80,\ 70,\ 60,\ 62,\ 90,\ 10$

BST 的插入規則為：

• 小於目前節點：往左子樹走。
• 大於目前節點：往右子樹走。

逐一插入

• $65$：成為根節點。
• $50<65$：放在 $65$ 左側。
• $80>65$：放在 $65$ 右側。
• $70>65$ 且 $70<80$：放在 $80$ 左側。
• $60<65$ 且 $60>50$：放在 $50$ 右側。
• $62<65$、$62>50$、$62>60$：放在 $60$ 右側。
• $90>65$、$90>80$：放在 $80$ 右側。
• $10<65$、$10<50$：放在 $50$ 左側。

（a）二元搜尋樹與 leftSize

各節點的左子樹節點數如下：

因此二元搜尋樹為：

              65 (leftSize=5)
             /              \
      50 (leftSize=2)    80 (leftSize=2)
       /          \          /          \
10 (1)       60 (1)    70 (1)       90 (1)
                  \
                   62 (1)

其中括號內的數字為該節點的 leftSize。

（b）尋找第 $k$ 小元素

判斷原理

對目前節點 $u$ 而言：

leftSize(u)

就是「目前節點的排名」，因為：

• 左子樹中的所有元素都比 $u$ 小；
• 左子樹有 leftSize(u)-1 個節點；
• 因此 $u$ 在以自己為根的子樹中，是第 leftSize(u) 小的元素。

設目前節點為 $u$，令：

$r=u.\text{leftSize}$

則有三種情況：

1. 若 $k=r$，目前節點就是第 $k$ 小元素。
2. 若 $k<r$，第 $k$ 小元素位於左子樹，令 $u$ 移至左子節點。
3. 若 $k>r$，第 $k$ 小元素位於右子樹。右移後需扣除左子樹與目前節點所包含的 $r$ 個元素：
   $k\leftarrow k-r$
   然後令 $u$ 移至右子節點。

演算法

這是一道關於最大堆積 (Max Heap) 和堆積排序 (Heap Sort) 的題目。

核心觀念：

• 最大堆積性質：父節點的值總是 >= 其子節點的值。
• 堆積插入：新元素插入到堆積的最後一個位置，然後向上調整 (heapify-up)，直到滿足堆積性質。
• 堆積排序：
  1. 將輸入陣列建成最大堆積。
  2. 重複以下步驟 n-1 次：
     a. 將堆積的根節點（最大元素）與堆積的最後一個元素交換。
     b. 將堆積的大小減一（即將已排序的元素從堆積中移除）。
     c. 對新的根節點執行向下調整 (heapify-down)，以恢復堆積性質。

(a) (3%) 請寫下所有值插入到最大堆積後，最大堆積的狀態。

插入順序：7, 16, 49, 82, 5, 31, 6, 2, 44。

我們將使用陣列來表示堆積，其中索引 i 的節點，其左子節點是 2*i + 1，右子節點是 2*i + 2。父節點是 (i-1)/2 (整數除法)。

1. 插入 7: [7]
2. 插入 16: [7, 16]。16 > 7，交換。[16, 7]
3. 插入 49: [16, 7, 49]。49 > 16，交換。[49, 7, 16]
4. 插入 82: [49, 7, 16, 82]。82 > 49，交換。[82, 49, 16, 7]
5. 插入 5: [82, 49, 16, 7, 5]。5 < 49，不交換。[82, 49, 16, 7, 5]
6. 插入 31: [82, 49, 16, 7, 5, 31]。31 > 16，交換。[82, 49, 31, 7, 5, 16]。31 < 49，不交換。[82, 49, 31, 7, 5, 16]
7. 插入 6: [82, 49, 31, 7, 5, 16, 6]。6 < 31，不交換。[82, 49, 31, 7, 5, 16, 6]
8. 插入 2: [82, 49, 31, 7, 5, 16, 6, 2]。2 < 7，不交換。[82, 49, 31, 7, 5, 16, 6, 2]
9. 插入 44: [82, 49, 31, 7, 5, 16, 6, 2, 44]。44 > 5，交換。[82, 49, 31, 7, 44, 16, 6, 2, 5]。44 > 49，交換。[82, 44, 31, 7, 49, 16, 6, 2, 5]。44 < 82，不交換。[82, 44, 31, 7, 49, 16, 6, 2, 5]

最終最大堆積狀態 (陣列表示)：
[82, 44, 31, 7, 49, 16, 6, 2, 5]

對應的樹狀結構：

          82
       /      \
      44       31
     /  \     /  \
    7    49   16   6
   / \
  2   5

(b) (3%) 從 (a) 中建立的最大堆積開始，寫下堆積排序過程中，第 5 次迭代後的 maximum heap 和 sorted array 狀態。

初始堆積 (n=9)：[82, 44, 31, 7, 49, 16, 6, 2, 5]
已排序部分 (Sorted Array): [] (空)

第 1 次迭代：

• 最大值是根節點 82。
• 交換堆積頂部 (82) 和最後一個元素 (5)。
  堆積變為：[5, 44, 31, 7, 49, 16, 6, 2, 82]
• 堆積大小減 1。現在堆積是 [5, 44, 31, 7, 49, 16, 6, 2] (大小 n=8)。
• 對新的根節點 5 進行向下調整 (heapify-down)。
  • 5 的子節點是 44 和 31。44 是最大的。
  • 交換 5 和 44：[44, 5, 31, 7, 49, 16, 6, 2]
  • 現在檢查 5 (索引 1)。它的子節點是 7 和 49。49 是最大的。

核心觀念

本題考查兩種圖形演算法：

• Dijkstra’s algorithm：在邊權重皆為非負數時，求單一起點到其他頂點的最短路徑。
• Breadth-First Search（BFS）：以佇列逐層拜訪頂點；本題要求同一頂點有多條可走邊時，依邊權重由小到大處理。

依圖可讀得主要有向邊如下：

解題方法一：Dijkstra 演算法

令 $d(v)$ 表示目前從頂點 $0$ 到頂點 $v$ 的最短距離。初始值為：

每次選擇尚未處理且 $d(v)$ 最小的頂點，並鬆弛其所有出邊。

第一步：處理頂點 $0$

由 $0$ 可到達：

• $0\to1$，距離為 $2$
• $0\to2$，距離為 $15$

因此：

目前最小的是頂點 $1$。

第二步：處理頂點 $1$

更新：

$1\to0$ 不會產生更短路徑。

目前未處理頂點中，$d(4)=12$ 最小。

第三步：處理頂點 $4$

由 $4\to3$：

目前未處理頂點中，$d(2)=15$ 最小。

第四步：處理頂點 $2$

更新：

目前最小的是頂點 $3$。

第五步：處理頂點 $3$

頂點 $3$ 沒有能產生更短距離的出邊。

第六步：處理頂點 $5$

由 $5$ 出發也無法改善已知距離，演算法結束。

Dijkstra 處理順序與最短路徑

這是一道關於雜湊表 (Hash Table) 的題目，使用除法雜湊函數和線性探測法 (Linear Probing) 處理碰撞。

核心觀念：

• 雜湊表：一種數據結構，用鍵 (key) 來儲存和檢索值。
• 除法雜湊函數：h(key) = key % table_size。
• 線性探測法 (Linear Probing)：當發生碰撞（即計算出的雜湊索引已被佔用）時，按順序檢查下一個可用的位置（索引 + 1, 索引 + 2, ...，並循環）。
• 雜湊表大小：table_size = 17。
• 雜湊函數：h(key) = key % 17。

要插入的鍵 (keys) 順序： 6, 12, 34, 29, 28, 11, 23, 7, 0, 33。

插入過程：

1. 插入 6:

   • h(6) = 6 % 17 = 6。
   • 雜湊表索引 6 為空。
   • Table: [_, _, _, _, _, _, 6, _, _, _, _, _, _, _, _, _, _] (索引 0-16)

2. 插入 12:

   • h(12) = 12 % 17 = 12。
   • 雜湊表索引 12 為空。
   • Table: [_, _, _, _, _, _, 6, _, _, _, _, _, 12, _, _, _, _]

3. 插入 34:

   • h(34) = 34 % 17 = 0。
   • 雜湊表索引 0 為空。
   • Table: [34, _, _, _, _, _, 6, _, _, _, _, _, 12, _, _, _, _]

4. 插入 29:

   • h(29) = 29 % 17 = 12。
   • 索引 12 已被 12 佔用。
   • 線性探測：檢查 13。索引 13 為空。
   • Table: [34, _, _, _, _, _, 6, _, _, _, _, _, 12, 29, _, _, _]

5. 插入 28:

   • h(28) = 28 % 17 = 11。
   • 雜湊表索引 11 為空。
   • Table: [34, _, _, _, _, _, 6, _, _, _, _, 28, 12, 29, _, _, _]

6. 插入 11:

   • h(11) = 11 % 17 = 11。
   • 索引 11 已被 28 佔用。
   • 線性探測：檢查 12。

這是一道關於樹結構的題目，關於 k-ary tree 的節點數量。

核心觀念：

• k-ary tree：一種樹結構，其中每個節點最多可以有 k 個子節點。
• 樹的高度 (height)：從根節點到最深葉節點的最長路徑上的邊數。如果定義高度為節點數，則與通常定義不同。題目中通常指邊數。如果根節點是高度 0，則高度 h 表示樹有 h+1 層。

定義：

• 我們採用樹的高度定義為：從根節點到最深葉節點的最長路徑上的邊數。
• 高度為 0 的樹只有一個節點（根節點）。
• 高度為 1 的樹，根節點有子節點，最深節點在第二層。

(a) (2%) 高度為 h 的 k-ary tree 中最多有多少個節點？

為了使節點數最多，我們需要讓每一層都達到其最大容量。

• 第 0 層 (根節點)：有 1 個節點。
• 第 1 層：最多有 k 個子節點。
• 第 2 層：上一層的每個節點最多有 k 個子節點，所以這一層最多有 $k \times k = k^2$ 個節點。
• 第 i 層：最多有 $k^i$ 個節點。

如果樹的高度定義為 h，並且這表示樹的深度（從根算起，根是第 0 層，最深葉子在第 h 層），那麼總共有 h+1 層（第 0 層到第 h 層）。
總節點數是所有層節點數的總和：
$\text{Total Nodes} = \sum_{i=0}^{h} k^i$
這是一個等比級數。

公式：
對於一個等比級數 $\sum_{i=0}^{h} r^i = 1 + r + r^2 + \dots + r^h$，其總和為 $\frac{r^{h+1} - 1}{r - 1}$ （當 $r \neq 1$）。
在這裡，$r = k$。
所以，最多節點數為：
$\frac{k^{h+1} - 1}{k - 1}$

特殊情況：

• 如果 $k = 1$ (即一個鏈表)，則總節點數是 $h+1$。公式 $\frac{1^{h+1} - 1}{1 - 1}$ 是不定型，需要單獨考慮。當 k=1 時，每層只有 1 個節點，總共 h+1 層，所以是 h+1 個節點。
• 如果 $h = 0$，則總節點數為 $k^0 = 1$。公式為 $\frac{k^{0+1} - 1}{k - 1} = \frac{k - 1}{k - 1} = 1$。

結論：
高度為 h 的 k-ary tree 中最多有 $\frac{k^{h+1} - 1}{k - 1}$ 個節點（當 $k \neq 1$）。
如果 $k=1$，則最多有 $h+1$ 個節點。

(b) (3%) 證明你的答案。

證明：
我們將使用數學歸納法來證明。

基本情況 (Base Case):
令 $h=0$。一個高度為 0 的 k-ary tree 只有一個節點（根節點）。
根據公式，最多節點數為 $\frac{k^{0+1} - 1}{k - 1} = \frac{k - 1}{k - 1} = 1$ (當 $k \neq 1$)。
如果 $k=1$，公式不適用，但對於高度為 0 的鏈表，節點數也是 1。
基本情況成立。

歸納假設 (Inductive Hypothesis):
假設對於任意高度為 $h'$ 的 k-ary tree，最多節點數為 $\frac{k^{h'+1} - 1}{k - 1}$。
我們要證明對於高度為 $h'+1$ 的 k-ary tree，最多節點數為 $\frac{k^{(h'+1)+1} - 1}{k - 1} = \frac{k^{h'+2} - 1}{k - 1}$。

歸納步驟 (Inductive Step):
考慮一個高度為 $h'+1$ 的 k-ary tree，要使其節點數最多，我們需要讓每一層的節點數都達到最大。
這棵樹的根節點是第 0 層。它的 k 個子節點（如果存在）構成的子樹，其高度為 $h'$。
為了使總節點數最多，每個子節點都必須是高度為 $h'$ 的 k-ary tree 的根，並且這些子樹的節點數也必須達到最多。

根據歸納假設，每個高度為 $h'$ 的子樹最多有 $\frac{k^{h'+1} - 1}{k - 1}$ 個節點。
由於根節點有 k 個子節點，每個子節點都作為一個高度為 $h'$ 的 k-ary tree 的根。

核心觀念

本題考查三個演算法與複雜度觀念：

1. 多序列最長共同子序列（Longest Common Subsequence, LCS）的複雜度。
2. 最長簡單路徑（Longest Simple Path）與 NP-hard 問題的關係。
3. Breadth-First Search（BFS）對圖的走訪與邊分類。

解題方法

判斷是非題時，應檢查：

• 題目所述問題是否具有已知的多項式時間演算法。
• 能否由已知的 NP-hard 或 NP-complete 問題進行歸約。
• 演算法是否能保證走訪所有頂點與邊，以及如何分類邊。

選項分析

(a) Finding a longest common subsequence from an arbitrary number of input sequences is a P problem.

答案：錯誤。

對兩個序列，LCS 可以使用動態規劃求解。若兩序列長度分別為 $m$ 與 $n$，時間複雜度為：

若輸入序列數量固定為 $k$，也可以建立 $k$ 維動態規劃表，時間複雜度約為：

當 $k$ 是固定常數時，這仍可視為輸入長度的多項式時間。

然而題目使用 arbitrary number，表示序列數量 $k$ 也是輸入的一部分，而非固定常數。此時 $k$ 維動態規劃的狀態數量會隨序列數量增加而呈指數成長；一般序列的多序列 LCS 問題已知為 NP-hard，其決策版本為 NP-complete。

因此，不能宣稱它是 P problem，除非 $P=NP$。

正確修正：

Finding a longest common subsequence from an arbitrary number of input sequences is an NP-hard problem.

(b) Given a non-negatively weighted graph G and two vertices u and v, finding the longest simple path from u to v is a NP-hard problem.

答案：正確。

可由 Hamiltonian Path 問題進行歸約。

給定一個圖 $H$，要判斷是否存在一條從 $u$ 到 $v$、通過所有頂點恰好一次的 Hamiltonian path。將 $H$ 中每一條邊的權重設為 $1$，形成圖 $G$。

這是一道關於排序演算法穩定性的題目。

核心觀念：

• 排序演算法的穩定性 (Stability)：如果一個排序演算法是穩定的，那麼對於兩個具有相同鍵值的元素，它們在排序後的相對順序與它們在排序前的相對順序相同。

我們來逐一分析選項中的排序演算法：

• (a) Counting sort (計數排序)：
  計數排序是一種穩定的排序演算法。它通過計算每個元素出現的次數，然後確定它們在排序數組中的位置。在構建輸出數組時，它通常會按照原始順序處理元素，從而保持相同鍵值的相對順序。

• (b) Quicksort (快速排序)：
  快速排序是一種不穩定的排序演算法。它的分區 (partition) 操作可能會改變相同鍵值的元素的相對順序。例如，如果一個基準元素 (pivot) 被選中，並且有兩個相同的元素，一個在基準點左邊，一個在右邊，分區過程可能會將它們交換到不符合原始順序的位置。

這是一道關於排序演算法漸進優化性 (Asymptotic Optimality) 的題目。

核心觀念：

• 漸進優化性 (Asymptotic Optimality)：一個排序演算法被認為是漸進優化的，如果它的時間複雜度在最壞情況下達到了比較排序 (comparison-based sorting) 的理論下限。
• 比較排序的理論下限：對於任意一個依賴於比較操作的排序演算法，其在最壞情況下的時間複雜度至少為 $\Omega(n \log n)$，其中 n 是待排序元素的數量。這是因為需要通過一系列比較來確定 n 個元素的順序，而確定 n 個元素的順序共有 $n!$ 種可能性，每次比較最多將可能性空間縮小一半，因此需要至少 $\log_2(n!)$ 次比較，而 $\log_2(n!) \approx n \log_2 n$。

我們來分析每個選項：

• (a) Bubble sort (氣泡排序)：

  • 最壞情況時間複雜度：$O(n^2)$。
  • 最佳情況時間複雜度：$O(n)$（如果數組已經排序，並且使用一個標誌來檢測是否發生交換）。
  • 平均情況時間複雜度：$O(n^2)$。
  • 與理論下限 $\Omega(n \log n)$ 相比，$O(n^2)$ 顯然更高。因此，氣泡排序不是漸進優化的。

• (b) Quicksort (快速排序)：

  • 最壞情況時間複雜度：$O(n^2)$（例如，當輸入數組已經排序或逆序排序，並且選擇的基準點總是最邊緣元素時）。
  • 最佳情況和平均情況時間複雜度：$O(n \log n)$。

這是一道關於圖的表示方法的題目。

題目給出了一個表格，其中列和行都標示了頂點的編號 (1, 2, 3)。表格中的值代表了從列頂點指向行頂點的邊的權重。

例如：

• 表格中的 (2, 1) 位置的值是 20，表示從頂點 2 到頂點 1 有一條權重為 20 的邊 (2→1)。
• 表格中的 (2, 3) 位置的值是 -30，表示從頂點 2 到頂點 3 有一條權重為 -30 的邊 (2→3)。
• 值為 0 的表示沒有邊（或者說權重為 0 的邊，但通常沒有邊表示為 0 或無值）。
• 表格中的 (1, 1), (1, 2), (1, 3), (2, 2), (3, 1), (3, 2), (3, 3) 位置的值為 0，表示這些方向的邊不存在或權重為 0。

這是一道關於圖演算法 Johnson's Algorithm 的題目。它建立在上一題的鄰接矩陣表示的圖的基礎上。

核心觀念：

• Johnson's Algorithm：這個演算法用於在帶有負權重的邊的圖中，計算所有頂點對之間的最短路徑 (All-Pairs Shortest Paths)。
• 挑戰：標準的 Dijkstra 演算法不能處理負權重邊。Bellman-Ford 演算法可以處理負權重邊，但計算所有頂點對最短路徑的複雜度是 $O(V^3 E)$，這對於稠密圖 (E≈V^2) 會非常高。
• Johnson's Algorithm 的方法：
  1. 重新加權 (Reweighting)：Johnson 演算法通過引入一個新的源點 s，並為所有頂點定義一個新的權重函數，使得所有邊的權重變成非負數，同時保持最短路徑的相對關係不變。
  2. 使用 Bellman-Ford：首先，使用 Bellman-Ford 演算法從新的源點 s 開始，計算到所有頂點的最短路徑，記為 $h(v)$。如果 Bellman-Ford 檢測到負權重的環，則演算法終止，因為最短路徑是無窮小的。
  3. 計算新的權重：對於圖中的每條邊 $(u, v)$，計算新的權重 $w'(u, v) = w(u, v) + h(u) - h(v)$。可以證明，所有新的權重 $w'$ 都是非負的。
  4. 使用 Dijkstra：對所有頂點，使用修改後的權重 $w'$，從每個頂點運行 Dijkstra 演算法，計算所有頂點對的最短路徑。
  5. 恢復原始權重：最後，將 Dijkstra 計算出的最短路徑值 $d'(u, v)$ 轉換回原始圖中的最短路徑 $d(u, v)$，計算方法是 $d(u, v) = d'(u, v) - h(u) + h(v)$。

應用於題目中的圖：

上一題給出的鄰接矩陣表示的圖：
頂點：{1, 2, 3}
邊及其權重：

• 2 → 1 (20)
• 2 → 3 (-30)
• 3 → 1 (40)

步驟 1：引入新的源點 s (我們稱之為頂點 0)，並為所有頂點 (0, 1, 2, 3) 添加到 s 的邊，權重為 0。
新的圖 G' 包含頂點 {0, 1, 2, 3}。
邊：

• 0 → 1 (0)
• 0 → 2 (0)
• 0 → 3 (0)
• 2 → 1 (20)
• 2 → 3 (-30)
• 3 → 1 (40)

步驟 2：使用 Bellman-Ford 演算法從源點 0 計算最短路徑 $h(v)$。
頂點數 V' = 4。需要進行 V'-1 = 3 次迭代。

• 初始化：
  h = {0: 0, 1: inf, 2: inf, 3: inf}

• 迭代 1：

  • 0 → 1 (0): h[1] = min(inf, h[0] + 0) = 0
  • 0 → 2 (0): h[2] = min(inf, h[0] + 0) = 0
  • 0 → 3 (0): h[3] = min(inf, h[0] + 0) = 0
  • 2 → 1 (20): h[1] = min(0, h[2] + 20) = 0
  • 2 → 3 (-30): h[3] = min(0, h[2] - 30) = -30
  • 3 → 1 (40): h[1] = min(0, h[3] + 40) = min(0, -30 + 40) = 0
  • h = {0: 0, 1: 0, 2: 0, 3: -30}

• 迭代 2：

  • 0 → 1 (0): h[1] = min(0, h[0] + 0) = 0
  • 0 → 2 (0): h[2] = min(0, h[0] + 0) = 0
  • 0 → 3 (0): h[3] = min(-30, h[0] + 0) = -30
  • 2 → 1 (20): h[1] = min(0, h[2] + 20) = 0
  • 2 → 3 (-30): h[3] = min(-30, h[2] - 30) = -30
  • 3 → 1 (40): h[1] = min(0, h[3] + 40) = min(0, -30 + 40) = 0
  • h = {0: 0, 1: 0, 2: 0, 3: -30} (沒有變化)

• 迭代 3：

  • 再次檢查，值沒有變化。
  • h = {0: 0, 1: 0, 2: 0, 3: -30}

• 負權重環檢測：
  在第 4 次迭代（V' 次迭代）中，我們檢查是否有邊的距離可以被縮短。

  • 2 → 3 (-30): h[3] (-30) vs h[2] + (-30) (0 - 30 = -30)。沒有縮短。
  • 3 → 1 (40): h[1] (0) vs h[3] + 40 (-30 + 40 = 10)。沒有縮短。
  • 2 → 1 (20): h[1] (0) vs h[2] + 20 (0 + 20 = 20)。沒有縮短。
    沒有發現負權重環。

步驟 3：計算新的非負權重 $w'(u, v) = w(u, v) + h(u) - h(v)$。
我們只關心原始圖 (頂點 1, 2, 3) 的邊。

• 邊 2 → 1 (權重 20):
  $w'(2, 1) = w(2, 1) + h(2) - h(1) = 20 + 0 - 0 = 20$
• 邊 2 → 3 (權重 -30):
  $w'(2, 3) = w(2, 3) + h(2) - h(3) = -30 + 0 - (-30) = -30 + 30 = 0$
• 邊 3 → 1 (權重 40):
  $w'(3, 1) = w(3, 1) + h(3) - h(1) = 40 + (-30) - 0 = 10$

新的權重圖 G'' (只包含原始頂點)：

• 2 → 1 (20)
• 2 → 3 (0)
• 3 → 1 (10)
  所有權重都是非負的。

步驟 4：對每個頂點，使用 Dijkstra 演算法計算所有頂點對的最短路徑 $d'(u, v)$。

• 從頂點 1 開始 (Dijkstra on G''):

  • d'(1, v)：
  • 1 沒有出邊。
  • d'(1, 1)=0, d'(1, 2)=inf, d'(1, 3)=inf

• 從頂點 2 開始 (Dijkstra on G''):

  • d'(2, v)：
  • 2 → 3 (0): d'(2, 3) = 0
  • 3 → 1 (10): d'(2, 1) = min(inf, d'(2, 3) + 10) = 0 + 10 = 10
  • d'(2, 1)=10, d'(2, 2)=0, d'(2, 3)=0

核心觀念

本題考查：

1. if-else 的「懸空 else」配對規則。
2. 條件判斷未成立時，後續獨立敘述是否仍會執行。
3. struct 的大小、成員大小與記憶體對齊（alignment）。
4. 指標遞增、字元陣列與字串結尾字元 '\0'。
5. sizeof 的結果與平台實作有關。

(a) if-else 配對與輸出

解題方法

程式可整理為：

if (x > y) {
    if (y > 0)
        printf("B");
    else
        printf("H");
}

printf(" or C");

在 C 語言中，else 會自動與「最近且尚未配對的 if」配對，因此原程式的結構是：

if (x > y)
    if (y > 0)
        printf("B");
    else
        printf("H");

printf(" or C");

變數值為：

因此：

外層 if 不成立，所以內層 if、else 都不會執行，B 與 H 均不會輸出。

最後的：

printf(" or C");

不屬於任何 if，因此一定會執行。

解題技巧

遇到巢狀 if 時，先將程式加上大括號，再判斷每個敘述的實際歸屬。特別注意：

if (條件1)
    if (條件2)
        敘述A;
    else
        敘述B;

其中 else 配對的是 條件2，不是 條件1。

(b) struct 大小、指標操作與字串輸出

1. text 初始狀態

char text[100];
memset(text, 0, 100);

這會將陣列全部設為 '\0'：

text = "\0\0\0\0\0\0..."

接著：

p = text;
for (i=0; i<10; i++) {
    *p++ = 'a' + i;
}

每次執行後，p 向後移動一格，依序寫入：

此時：

p == text + 10

2. 複製 d、e、f

q = text + 3;

因此 q 指向 text[3]，也就是字元 'd'。

接著：

for (i=0; i<3; i++) {
    *p++ = *q++;
}

逐次執行如下：

核心觀念

本題考查 C 語言的字串表示、字元陣列與指標，以及字串複製和串接：

• C 字串以 '\0' 作為結尾。目的陣列必須有足夠空間存放字串內容和結尾字元。
• strcpy(dest, src) 會把來源字串複製到目的地，並覆蓋目的地原有內容。
• strcat(dest, src) 會把來源字串接到目的字串結尾；目的陣列必須已包含合法的結尾字元，且有足夠剩餘空間。
• 陣列名稱不能像一般指標變數一樣重新指定，因此不能寫 text += ...。

解題方法

要連續輸出三個 "Apple"，先準備來源字串 q，再將目的字串 text 初始化為空字串，最後用迴圈串接三次。

#include <stdio.h>
#include <string.h>

int main(void) {
    char q[] = "Apple";
    char text[100] = "";

    for (int i = 0; i < 3; i++) {
        strcat(text, q);
    }

    printf("%s\n", text);
    return 0;
}

逐項修正如下：

1. q 原本未初始化，卻直接傳給 strcpy，來源內容不確定。改以 char q[] = "Apple"; 初始化。
2. text 原本未初始化，不是合法的空字串。

核心觀念

本題考查：

1. C 語言陣列初始化使用大括號 {}。
2. 陣列名稱在運算式中會轉換成指向第 0 個元素的指標。
3. 指標運算：
   • p + k 表示向後移動 $k$ 個「所指向型別」的元素。
   • *(p + k) 取得第 $k$ 個元素的值。
4. 指標遞增 p++ 會移動到下一個陣列元素。
5. 陣列元素必須使用相容的指標型別存取。

解題方法

a) 陣列宣告錯誤

原程式為：

int A[] = (0, 1, 2, 3, 4, 5);

C 語言的陣列初始化值列表必須使用大括號，而非小括號：

int A[] = {0, 1, 2, 3, 4, 5};

因此，陣列 A 的正確宣告為：

int A[] = {0, 1, 2, 3, 4, 5};

此外，原程式另有一個指標型別錯誤：

char *p;
p = A;

A 在運算式中會轉換成 int *，因此不能指定給 char *。若要逐一存取 int 陣列元素，應宣告為：

int *p;

完整的合理修正版為：

int A[] = {0, 1, 2, 3, 4, 5};
int *p;

p = A;
p = &A[*(p + 2)];

b) 迴圈執行後的陣列內容

初始陣列為：

先執行：

p = A;

此時：

接著：

p = &A[*(p+2)];

因為 $p$ 是 int *，所以：

因此：

代回後：

指標 p 從 A[2] 開始，迴圈如下：