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

此題考察 C 語言的格式化輸出與字串處理。

(a) 題目要求以八進位制格式顯示十進位數值 100，並在前面加上 0。在 C 語言中，printf 函數的格式化輸出可以滿足此需求。八進位格式化符為 %o，而要在數字前補零則使用 %0 加上數字的總寬度。由於題目沒有指定總寬度，但要求「前面加 0」，通常是指在數字本身前面加上 0，例如 0144。若要顯示為 0144，則需指定總寬度。然而，標準的八進位格式化輸出，如 printf("%o", 100); 會輸出 144。若要強制前面加上 0，例如 0144，則可以透過指定寬度並補零來達成。例如，如果我們假設總寬度為 4，那麼 printf("%04o", 100); 會輸出 0144。如果題目僅要求「顯示為八進位，且前面加 0」，最直接的理解是直接輸出八進位表示，並在前面加上 0 作為前綴。然而，C 語言標準庫的 printf 函數本身並不會自動為八進位數值添加前綴 0。如果我們需要輸出 0144，則需要自行處理。一種方式是使用 %#o，它會輸出 0 作為八進位前綴，例如 printf("%#o", 100); 會輸出 0144。

此題考察 C 語言指標運算、陣列與 printf 的格式化輸出，特別是前遞增 (++p)、後遞增 (p++) 和解引用 (*p) 的組合使用。

程式碼首先定義了一個字元陣列 s，內容為 "01234"，並初始化一個字元指標 p 指向陣列的起始位置。此時 p 指向 s[0]，即字元 '0'。

讓我們一步一步追蹤 printf 的執行：

1. printf("%c",*p++);

   • p 指向 s[0] ('0')。
   • *p++：這是一個後遞增操作。首先解引用 p，取得 s[0] 的值 '0'。然後 p 再遞增，指向 s[1]。
   • 輸出：'0'
   • p 現在指向 s[1] ('1')。

2. printf("%c",*++p);

   • ++p：這是一個前遞增操作。p 首先遞增，指向 s[2] ('2')。然後解引用 p，取得 s[2] 的值 '2'。
   • 輸出：'2'
   • p 現在指向 s[2] ('2')。

3. printf("%c",*(++p));

   • ++p：這是另一個前遞增操作。p 首先遞增，指向 s[3] ('3')。然後解引用 p，取得 s[3] 的值 '3'。
   • 輸出：'3'
   • p 現在指向 s[3] ('3')。

4. printf("%c",*(p++));

   • *(p++)：這是一個後遞增操作。首先解引用 p，取得 s[3] 的值 '3'。

此題考察 C 語言的巢狀迴圈、條件判斷以及變數的累加。

程式碼初始化 x = 3 和 n = 6。
外層迴圈 for (int i=1; i<=n; i=i+1) 會從 i = 1 執行到 i = 6。
內層迴圈 for (int j=1; j<=n; j=j+1) 會從 j = 1 執行到 j = 6。
因此，內層迴圈會執行 n * n = 6 * 6 = 36 次。

在內層迴圈中，根據 i+j 的值來更新 x：

• 如果 i+j == 2，則 x = x + 3。
• 如果 i+j == 3，則 x = x + 4。
• 如果 i+j == 4，則 x = x + 5。

我們需要計算 i+j 等於 2、3、4 的總次數。
由於 i 和 j 的範圍都是從 1 到 6，i+j 的最小值是 1+1=2，最大值是 6+6=12。

情況 1: i+j == 2

• 唯一組合是 i=1, j=1。
• 此組合會執行 x = x + 3。
• 總共執行 1 次。

核心觀念

這題考察「哨兵值（sentinel value）」與 C 語言陣列結尾標記的限制。

字串以 '\0' 作為結尾，是因為字串內容通常不把空字元視為一般文字內容。若將整數陣列也以特殊值標記結尾，則必須保證該值不會出現在有效資料中，否則程式無法區分：

• 陣列中的有效元素；
• 陣列結束標記。

解題方法

John 將陣列配置成如下形式：

int a[] = {10, 20, 30, 0};

並以整數值 0 作為結尾標記。接收指標的函式可能依序讀取：

while (*p != 0) {
    /* 使用 *p */
    p++;
}

當陣列本身合法包含 0 時，例如：

int a[] = {10, 0, 20, 30, 0};

函式讀到中間的 0 就會誤判陣列已結束，因此只處理 10，漏掉後面的 20 與 30。

核心觀念

本題考查「宣告（declaration）」與「定義（definition）」的區別：

• 宣告：告知編譯器名稱、型別或函式介面，使編譯器知道它的存在。
• 定義：除了宣告之外，還會建立物件、配置儲存空間，或提供函式的實作內容。

函式若只有函式名稱、參數與回傳型別，沒有函式本體 {...}，就是函式宣告，不是函式定義。

typedef 則是建立型別別名的宣告，不會建立變數或函式，也不是物件定義。

解題方法

逐一判斷每個選項是否：

1. 建立變數並配置儲存空間；
2. 提供變數初值；
3. 提供函式本體；
4. 建立型別別名。

符合「只有告知資訊，沒有建立物件或提供實作」者，就是「宣告但不是定義」。

選項分析

(A) int i;

這是整數變數 i 的宣告，同時也是變數定義。

在函式內宣告時，會建立區域變數；在檔案層級時，屬於暫定定義（tentative definition），仍視為物件定義。因此不是本題答案。

(B) int i=1;

這是變數 i 的定義，並且初始化為 $1$。它會建立變數並配置儲存空間，因此不是單純宣告。

(C) int foo(int);

這是函式 foo 的函式原型宣告：

• 回傳型別為 int；
• 接受一個 int 型別的參數；
• 沒有函式本體。

核心觀念

本題考查 C++ 中下列觀念：

1. this 是成員函式內建的指標，指向目前呼叫該成員函式的物件。
2. this 本身不能被重新指定。
3. const 變數必須初始化，且不能透過別名被修改。
4. 參考變數不會建立副本；指標宣告也不會因為指定位址而複製物件。

---

甲、特殊變數 this

解題方法

在非靜態成員函式中，this 代表目前物件的位址。以類別 Thing 為例，非 const 成員函式中的 this 型別可視為：

$$Thing * \operatorname{const}$$

也就是「不可改變的指標」，但指標所指向的物件本身可以被修改。

選項分析

• (A) 錯誤：this 是指標值，不是 reference value。它儲存的是目前物件的位址。

• (B) 錯誤：this 本身不可被重新指定，例如不能寫成：

  this = &anotherObject;
  

• (C) 正確：this 指向呼叫該成員函式的物件，也就是 calling instance。

• (D) 錯誤：因為 (A)、(B) 錯誤，不能選 All of the above。

• (E) 錯誤：至少 (C) 正確，因此不能選 None of the above。

解題技巧

看到 this 時記住：

this 是「指向目前物件的不可重新指定指標」。

因此「指向呼叫實例」正確，「可以改變它指向的物件」錯誤。

【答案】(C)

---

乙、隱含 this 的型別

解題方法

假設類別名稱為 Thing：

• 一般成員函式：

  Thing* const this;
  

• const 成員函式：

  const Thing* const this;
  

this 的最外層指標本身不可改變；若成員函式是 const，則它指向的物件也視為 const。

選項分析

• (A) Thing：錯誤。這是物件型別，不是 this 的指標型別。
• (B) Thing * const：僅適用於非 const 成員函式，不能涵蓋所有成員函式情況。
• (C) const Thing * const：僅適用於 const 成員函式，也不能涵蓋一般成員函式。
• (D) Thing *：錯誤。忽略了 this 指標本身不可重新指定的 const 屬性。
• (E) 正確。this 的完整型別取決於成員函式是否宣告為 const。
• (F) 錯誤：因為 (E) 正確。

解題技巧

本題關鍵是分辨兩個 const：

Thing* const

表示指標不能改指向別處；

const Thing* const

表示指標不能改指向別處，且不能透過它修改 Thing 物件。

【答案】(E)

---

丙、const 變數

核心觀念

const 變數一旦初始化，就不能再被修改：

const int x = 10;

此外，const 是加在被參照型別上，而不是加在 reference 本身。C++ 的 reference 沒有「重新繫結」或「reference 本身為 const」的獨立意義。

選項分析

• (A) 錯誤：不能透過 reference 修改 const 變數：

  const int a = 10;
  const int& r = a;
  

此題組考察 C++ 中的建構子 (Constructor) 的概念。

甲. (3%) 建構子 (Constructors)

建構子是 C++ 中用於初始化物件的特殊成員函數。

• (A) Are called when the instance goes out of scope or is de-allocated.
  • 錯誤。當物件超出作用域或被銷毀時，調用的是解構子 (Destructor)，而不是建構子。
• (B) Can be used to set data members to a known initial value / state.
  • 正確。建構子的主要目的是初始化物件的資料成員，確保物件在創建時處於一個有效的初始狀態。
• (C) Can be overloaded (i.e., multiple constructors with different argument lists)
  • 正確。一個類別可以有多個具有不同參數列表的建構子，這稱為建構子的多載 (overloading)。這允許物件以不同的方式初始化。
• (D) Are called automatically only when the instance is allocated dynamically with 'new and not
  when the instance is declared statically as a local variable.

此題考察資料結構與演算法的基礎概念，包括樹的性質、時間複雜度、圖論以及樹的遍歷。

1. (2%) 具有九個層級的二元樹節點的最大數量

• 觀念: 在二元樹中，層級 (level) 通常從 0 或 1 開始計算。如果層級從 0 開始，則第 k 層最多有 $2^k$ 個節點。樹的高度 (height) 是指從根節點到最深葉節點的最長路徑上的邊數。層數 (number of levels) 是高度 + 1。
• 如果題目中的「九個層級」指的是樹的高度為 8 (即有 9 層，從層 0 到層 8)，那麼總節點數是 $2^0 + 2^1 + \dots + 2^8 = 2^9 - 1 = 512 - 1 = 511$。
• 如果題目中的「九個層級」指的是樹的高度為 9 (即有 10 層，從層 0 到層 9)，那麼總節點數是 $2^{10} - 1 = 1023$。
• 通常，在談論樹的層級時，如果說「有 n 個層級」，通常是指從第 1 層到第 n 層。如果從第 1 層開始，那麼第 k 層最多有 $2^{k-1}$ 個節點。總節點數為 $2^1 + 2^2 + \dots + 2^9 = 2(2^9 - 1) = 2(511) = 1022$。
• 另一種常見定義是：層級 0 根節點，層級 1 子節點...。如果「九個層級」是指最大的層級索引是 8 (即層級 0, 1, ..., 8)，那麼總共有 9 層。最大節點數為滿二元樹，總節點數為 $2^9 - 1 = 511$。
• 如果「九個層級」是指樹的高度為 9 (即從根到最深葉節點的路徑上最多有 9 條邊)，那麼這棵樹最多有 10 層 (層級 0 到 9)。最大節點數為 $2^{10} - 1 = 1023$。
• 基於常見的定義，如果說「有九個層級」，通常是指從第 1 層到第 9 層，或者層級索引從 0 到 8。如果層級從 0 開始，第 9 層的節點數是 $2^8$。總節點數是 $2^9-1=511$。
• 假設「九個層級」是指從層級 0 到層級 8，總共 9 層。 在滿二元樹中，層級 k 最多有 $2^k$ 個節點。總節點數為 $\sum_{k=0}^{8} 2^k = 2^9 - 1 = 511$。
• 結論: 這種情況下，敘述為 True。

2. (2%) $f_1(n) = O(g(n))$ 和 $f_2(n) = O(g(n))$，則 $f_1(n) = f_2(n)$

• 觀念: $O(g(n))$ 表示一個漸進上界。如果 $f_1(n) \in O(g(n))$ 且 $f_2(n) \in O(g(n))$，這意味著 $f_1(n)$ 和 $f_2(n)$ 的成長速度都慢於或等於 $g(n)$ 的成長速度。但這並不意味著 $f_1(n)$ 和 $f_2(n)$ 是相同的函數。
• 反例: 設 $g(n) = n^2$。
  • 令 $f_1(n) = n$。則 $f_1(n) = O(n^2)$ 是正確的。
  • 令 $f_2(n) = n^2$。則 $f_2(n) = O(n^2)$ 是正確的。
  • 但是，$f_1(n) = n \neq n^2 = f_2(n)$。

核心觀念

本題綜合考查：

• Graph 的 Depth-First Search（DFS）
• Max Heap 的 bottom-up heapify
• AVL Tree 插入與旋轉
• Catalan number 與二元樹數量
• Red-Black Tree 插入、重新著色與旋轉

---

(1) DFS

解題方法

從節點 $1$ 開始，每次都選擇尚未拜訪且編號最小的相鄰節點；若目前節點沒有尚未拜訪的鄰點，就回溯到上一層。

依照圖中的連線，DFS 拜訪順序為：

$$1\to5\to9\to2\to6\to7\to8\to12\to10$$

完成 $10$ 的搜尋後回溯，再拜訪 $11$；接著回溯至 $9$，拜訪 $3$ 與 $4$：

$$1,5,9,2,6,7,8,12,10,11,3,4$$

選項分析

• a. 錯誤。從節點 $1$ 出發時，最小的優先鄰點應先走向 $5$，不是 $12$。
• b. 錯誤。走到節點 $5$ 後，依編號應先拜訪 $9$，不是 $8$。
• c. 錯誤。第一步即選擇 $12$，不符合從節點 $1$ 選擇最小編號鄰點的規則。
• d. 正確，符合 DFS 的深入與回溯順序。

解題技巧

DFS 題目要同時注意：

1. 使用堆疊概念深入搜尋。
2. 鄰點選擇順序會影響整個拜訪序列。
3. 已拜訪節點不可重複列入序列。
4. 遇到死路時必須回溯，不能直接跳到任意尚未拜訪節點。

【答案】d

---

(2) Bottom-up Max Heapify

核心觀念

Max Heap 必須滿足：

$$\text{父節點}\geq \text{所有子節點}$$

Bottom-up heapify 從最後一個非葉節點開始調整。陣列共有 $8$ 個元素，因此最後一個非葉節點為：

$$\left\lfloor\frac{8}{2}\right\rfloor=4$$

原陣列：

$$[19,5,27,3,16,11,69,18]$$

解題步驟

從索引 $4$ 開始：

1. 調整節點 $3$，其子節點為 $18$：

$$[19,5,27,18,16,11,69,3]$$

2. 調整節點 $27$，其子節點為 $11,69$，與較大的 $69$ 交換：

$$[19,5,69,18,16,11,27,3]$$

3. 調整節點 $5$，其子節點為 $18,16$，與 $18$ 交換：

$$[19,18,69,5,16,11,27,3]$$

4. 調整根節點 $19$，先與較大的子節點 $69$ 交換：

$$[69,18,19,5,16,11,27,3]$$

接著節點 $19$ 與子節點 $27$ 交換：

$$[69,18,27,5,16,11,19,3]$$

因此 Max Heap 為：

$$\{69,18,27,5,16,11,19,3\}$$

選項分析

• a. 錯誤。雖然符合 Max Heap 的局部大小關係，但不是此陣列使用 bottom-up heapify 後的結果。
• b. 正確，且每個父節點皆不小於其子節點。
• c. 錯誤。節點 $27$ 的子樹排列與實際 sift-down 結果不符。
• d. 錯誤。這是遞增排序結果，不是 Max Heap 的陣列表示。

解題技巧

Heapify 時，每次都要與「較大的子節點」交換，否則無法保證 Max Heap 性質。Bottom-up heapify 的時間複雜度為：

$$O(n)$$

【答案】b

---

(3) AVL Tree 插入

核心觀念

AVL Tree 必須滿足每個節點的平衡因子：

$$BF=\text{左子樹高度}-\text{右子樹高度}$$

且必須滿足：

$$BF\in\{-1,0,1\}$$

當插入造成失衡時，使用 LL、RR、LR 或 RL 旋轉修正。

解題方法

依序插入：

$$89,70,52,4,25,99,59,20,79,62,44,38$$

關鍵旋轉如下：

1. 插入 $52$ 後，$89$ 發生 LL 失衡，右旋。
2. 插入 $25$ 後，節點 $52$ 發生 LR 失衡，先左旋再右旋。
3. 插入 $62$ 後，造成以 $70$ 為根的 LR 失衡，進行雙旋轉，形成以 $59$ 為根的結構。

核心觀念

• 漸近最佳：比較排序的下界為 $\Omega(n\log n)$；若演算法的最壞情況時間也達到 $O(n\log n)$，稱為漸近最佳。
• Decision tree：內部節點代表一次比較（兩種結果），葉節點代表一種輸出排列。它描述的是演算法所有可能的比較結果，與 Quicksort 的遞迴樹是不同的東西。
• Full binary tree：每個節點恰有 0 或 2 個子節點。
• In-place 指額外空間為 $O(1)$（或很小）；stable 指相等鍵值的相對順序保持不變。

選項分析

(a) Quicksort is asymptotically optimal. → False

Quicksort 平均為 $\Theta(n\log n)$，但最壞情況為 $\Theta(n^2)$，沒有達到比較排序的 $\Omega(n\log n)$ 最壞情況下界所對應的 $O(n\log n)$；Merge sort、Heapsort 才是最壞情況也達到的漸近最佳排序。

(b) 每層分割都最不平衡時，對應的 decision tree 是 full binary tree。 → True

不論 pivot 如何選，Quicksort 的每個比較都會產生「小於」與「不小於」兩種結果，decision tree 的每個內部節點因此恰有兩個子節點，葉節點對應各種排列。最不平衡的分割只會讓這棵樹的某些路徑特別長（樹很歪、很深），不會讓內部節點只剩一個子節點。所以它是 full binary tree。把每次分割成 $0$ 與 $n-1$ 兩份的情形當成「degree 1」是把遞迴樹與 decision tree 混為一談。

核心觀念

Dijkstra 演算法的標準適用條件是所有邊權重皆非負；廣度優先搜尋（BFS）可在所有邊權重相同時，依邊數找最短路徑；拓樸排序則只適用於有向無環圖（DAG）。若以頂點勢能重新加權，公式為 $w'(u,v)=w(u,v)+h(u)-h(v)$，可在邊權重變成非負的同時保留最短路徑的相對順序。

解題方法與各小題分析

圖中有向邊及權重為：$a\to c$ 權重 $-1$、$a\to b$ 權重 $4$、$c\to b$ 權重 $1$、$b\to d$ 權重 $-3$、$d\to c$ 權重 $2$。

(a) 否。 圖中有負權邊，違反 Dijkstra 演算法的標準適用條件，因此不能用它保證求得最短路徑。此圖從 $a$ 到 $d$ 的最短路徑為 $a\to c\to b\to d$，權重總和是 $-1+1-3=-3$；但即使某次執行碰巧得到正確結果，也不代表 Dijkstra 對含負權邊的圖適用。

(b) 是。 若每條邊的權重都設為 $1$，路徑權重總和就等於路徑所經過的邊數。BFS 會依距離起點的邊數逐層搜尋，因此可用來找從 $a$ 到 $d$ 的最短路徑。例如 $a\to b\to d$ 經過兩條邊。

核心觀念

Ford–Fulkerson 演算法反覆在殘餘網路中尋找從源點 $s$ 到匯點 $t$ 的增廣路徑。每次沿路徑增加的流量，等於該路徑上最小的剩餘容量；當找不到增廣路徑時，即得到最大流。

解題方法

圖中有四個節點：源點 $s$、右上節點、左下節點及匯點 $t$。有向邊與容量依序為：$s$ 到右上節點容量 $2$、$s$ 到左下節點容量 $4$、$s$ 到 $t$ 容量 $2$、右上節點到左下節點容量 $1$、右上節點到 $t$ 容量 $3$，以及左下節點到 $t$ 容量 $3$。

依序選擇以下增廣路徑：

1. $s\to t$：瓶頸容量為 $2$，增加流量 $2$。
2. $s\to$右上節點$\to t$：瓶頸容量為 $\min(2,3)=2$，增加流量