111 年 國立中正大學資訊工程學系碩士班乙組《計算機概論》

核心觀念

本題考查：

• 漸進符號 $O$ 與 $\Omega$ 的定義
• 比較式排序的時間下限
• 二元樹的最大節點數
• 中序運算式與後序運算式的轉換
• C++ 函式多載（function overloading）

---

解題方法與選項分析

(a) The worst-case time complexity of any sorting algorithm is $\Omega(n \log n)$.

答案：F

$\Omega$ 表示漸進下界。對於「基於比較」的排序演算法，最壞情況時間複雜度確實具有下界：

$$\Omega(n\log n)$$

原因是比較排序可表示成決策樹。要排列 $n$ 個不同元素，至少要區分 $n!$ 種排列，因此決策樹高度至少為：

$$\log_2(n!)=\Omega(n\log n)$$

但題目說的是 任何排序演算法，範圍包含非比較排序，例如 counting sort、radix sort。當鍵值範圍適當時，counting sort 的時間複雜度可為：

$$O(n+k)$$

其中 $k$ 是鍵值範圍；當 $k=O(n)$ 時，整體為 $O(n)$，低於 $n\log n$。

因此，$\Omega(n\log n)$ 只適用於比較排序，不能套用到所有排序演算法。

---

(b) If $f_1(n) = O(g(n))$ and $f_2(n) = O(g(n))$, then $f_1(n) = f_2(n)$.

答案：F

$O(g(n))$ 只表示函數的漸進上界，不代表兩個函數完全相等。

例如：

$$f_1(n)=n,\qquad f_2(n)=1,\qquad g(n)=n$$

可得：

$$f_1(n)=O(n)$$

且：

$$f_2(n)=O(n)$$

但顯然：

$$n\ne 1$$

所以兩個函數同屬於 $O(g(n))$，不代表兩者相等。

---

(c) The maximum number of nodes in a binary tree of depth $k$ is $2^k-1$.

答案：T

本題採用二元樹深度以「層數」計算的常見定義，根節點位於第 $1$ 層。

二元樹每一個節點最多有兩個子節點，因此：

• 第 $1$ 層最多有 $2^0=1$ 個節點
• 第 $2$ 層最多有 $2^1=2$ 個節點
• 第 $3$ 層最多有 $2^2=4$ 個節點
• 第 $k$ 層最多有 $2^{k-1}$ 個節點

總節點數為等比級數：

$$1+2+4+\cdots+2^{k-1}$$

其和為：

這題考察 C++ 的繼承、多型、虛函數、建構子與解構子的調用順序，以及 dynamic_cast 的使用。

核心觀念：

• 繼承與建構子調用：當創建一個派生類別物件時，會先調用基底類別的建構子，然後再調用派生類別自身的建構子。
• 解構子調用順序：當物件被銷毀時，會先調用派生類別的解構子，然後再依序調用基底類別的解構子。
• 虛函數與多型：virtual 關鍵字確保在運行時調用正確的函數版本（特別是解構子）。
• dynamic_cast：用於在繼承體系中進行運行時的類型轉換。它會檢查轉換是否安全。如果轉換失敗（目標類型不是來源物件的實際類型或其基底類型），則返回 nullptr。

解題過程：

1. B* b_ptr = new D;

   • 這行程式碼創建了一個 D 類別的物件，並將其指標賦值給一個 B* 型別的指標 b_ptr。
   • 創建 D 物件時，調用順序如下：
     • B 的建構子被調用：輸出 "hi B"。
     • D 的建構子被調用：輸出 "hi D"。
   • 目前為止的輸出：hi B 換行, hi D 換行。

2. D* d_ptr = dynamic_cast<D*>(b_ptr);

   • b_ptr 指向一個實際為 D 型別的物件。
   • dynamic_cast<D*>(b_ptr) 嘗試將 b_ptr（類型為 B*）轉換為 D*。
   • 由於 b_ptr 實際指向的物件確實是 D 類別（或者 D 的派生類別），這個轉換是安全的。
   • d_ptr 將會成功指向該 D 物件。

3. if (d_ptr == nullptr) cout << "no d_ptr" << endl;

   • d_ptr 不是 nullptr，所以這段 if 語句不會執行。

這題考察 C++ 的類別定義、建構子、運算符重載，特別是二元運算符 + 的重載和隱含類型轉換。

核心觀念：

• 類別定義：Money 類別有私有成員 dollar，以及公有的建構子和運算符重載。
• 建構子：
  • Money()：預設建構子，將 dollar 初始化為 0。
  • Money(int _dollar)：接受一個整數參數，用於初始化 dollar。
• 運算符重載 operator+：
  • const Money operator+(const Money& amount) const：這是一個成員函數，用於重載 + 運算符。
  • 它接收一個 const Money& 類型的右操作數 amount。
  • 它返回一個新的 Money 物件，其 dollar 值為 this->dollar + amount.dollar。
  • const 關鍵字表示該函數不會修改物件本身的 dollar 成員，並且返回的 Money 物件也是 const 的。
• 隱含類型轉換 (Implicit Type Conversion)：C++ 允許在某些情況下自動將一種資料類型轉換為另一種。當一個函數接受一個參數，但該參數的類型與傳入的類型不同時，如果存在一個從傳入類型到函數參數類型的轉換建構子（或轉換函數），則會發生隱含轉換。

解題過程：

1. Money baseAmount(100), fullAmount;

   • 創建 baseAmount 物件，調用 Money(int _dollar) 建構子，baseAmount.dollar 初始化為 100。
   • 創建 fullAmount 物件，調用預設建構子 Money()，fullAmount.dollar 初始化為 0。

2. fullAmount = baseAmount + 25;

   • 這裡發生了一個運算。左操作數是 baseAmount (類型 Money)，右操作數是 25 (類型 int)。
   • Money 類別定義了一個成員函數 operator+，它期望右操作數是 const Money&。
   • 由於右操作數 25 是 int 型別，與 const Money& 不符，編譯器會嘗試進行隱含類型轉換。
   • Money 類別有一個接受 int 參數的建構子 Money(int _dollar)。編譯器會利用這個建構子，將整數 25 轉換成一個臨時的 Money 物件，例如 Money(25)。
   • 現在，運算變成了 baseAmount + Money(25)。
   • 調用 baseAmount.operator+(Money(25))。
   • 在 operator+ 內部：
     • this->dollar 是 baseAmount.dollar，即 100。
     • amount.dollar 是臨時 Money(25) 物件的 dollar，即 25。
     • 返回一個新的 Money 物件，其 dollar 值為 $100 + 25 = 125$。
   • 這個返回的 Money 物件（值為 125）被賦值給 fullAmount。
   • fullAmount.dollar 被更新為 125。

3. fullAmount = 25 + baseAmount;

   • 這裡發生了另一個運算。左操作數是 25 (類型 int)，右操作數是 baseAmount (類型 Money)。
   • Money 類別定義的 operator+ 是作為一個 成員函數，它隱含地將左操作數設為 this 指標。因此，只有 Money + Money 或 Money + int（通過隱含轉換）的組合能直接調用。
   • 對於 int + Money 的形式，編譯器會嘗試查找一個 非成員函數 的 operator+，或者一個可以將左操作數轉換為 Money 的建構子（這在左操作數是基本類型時不太常見，除非有轉換函數）。
   • 然而，由於 Money(int _dollar) 是 單參數建構子，它可以被用來進行隱含轉換。編譯器會嘗試將 25 轉換為一個臨時 Money 物件，然後再進行運算。
   • 但是，這個轉換必須發生在「需要 Money 型別」的地方。在這裡，25 是左操作數，而 operator+ 是作為 Money 的成員函數來查找的。
   • 編譯器會尋找一個 operator+，其第一個參數是 Money（或可以轉換為 Money），第二個參數是 int，或者反之。
   • 由於 Money 類別中定義的 operator+ 是成員函數，它默認左操作數是 Money 物件。所以 baseAmount + 25 可以通過將 25 轉換為 Money 來實現。
   • 但是 25 + baseAmount，編譯器會查找一個非成員的 operator+，其簽名類似於 Money operator+(int, Money) 或 Money operator+(const Money&, int)。
   • 由於 Money 類別中 沒有 定義非成員的 operator+，也沒有定義接受 int 作為第一個參數的 operator+，並且 int 不能通過轉換函數轉換為 Money 的「第一個」參數（它需要是 Money 的成員函數或非成員函數的參數），所以 25 + baseAmount 這一行代碼 將會導致編譯錯誤。
   • 編譯器無法找到一個合適的 operator+ 來處理 int 和 Money 的相加。

   再次確認：
   C++ 中，如果一個類別有一個單參數的建構子（並且該建構子不是 explicit 聲明的），這個建構子就可以用來進行隱含類型轉換。

   • 對於 baseAmount + 25：baseAmount 是 Money。25 是 int。Money 有一個單參數建構子 Money(int)。編譯器會將 25 轉換為臨時 Money 物件，然後調用 baseAmount.operator+(Money(25))。這個是有效的。
   • 對於 25 + baseAmount：25 是 int。baseAmount 是 Money。編譯器會嘗試以下兩種方式之一來處理：
     1. 尋找一個 非成員 的 operator+，其簽名是 Money operator+(int, const Money&)。如果存在，則調用它。
     2. 嘗試將左操作數 25 轉換為 Money 物件，然後調用 Money 的成員函數 operator+。但是，25 是一個 int 字面量，它不能直接通過成員函數的方式被「轉換」成一個可以作為左操作數調用 operator+ 的 Money 物件，除非 Money 有一個轉換函數（如 operator int()）。
   • 因為 Money 類別 沒有 定義非成員的 operator+ 來處理 int + Money，也沒有定義 explicit 以外的單參數建構子來隱含轉換 int 為 Money 的左操作數，所以 25 + baseAmount 是無效的。

   結論：程式碼會在 fullAmount = 25 + baseAmount; 這一行編譯失敗。

   如果題目要求的是「執行結果」而不是「編譯結果」，那麼我們必須假設程式能夠編譯通過。在這種情況下，題目可能預設了某種方式讓 25 + baseAmount 也能工作。通常，這需要定義一個非成員的 operator+。
   例如，如果我們添加：

   Money operator+(int lhs, const Money& rhs) {
     return Money(lhs + rhs.dollar);
   }
   

   那麼 25 + baseAmount 就可以工作，並且 fullAmount.dollar 會被更新為 $25 + 100 = 125$。

   根據考古題的慣例，通常會問「輸出結果」或「程式執行結果」。如果程式無法編譯，則沒有執行結果。
   但是，這是一個選擇題，通常會要求輸出。我們假設編譯器足夠聰明，或者題目有隱含的假設。
   最常見的解釋是，題目是想測試 operator+ 的成員函數形式，以及如何處理 int 與 Money 的混合運算。

   • baseAmount + 25 -> baseAmount.operator+(Money(25)) -> Money(125) -> fullAmount 變成 125。
   • 25 + baseAmount -> 這裡需要編譯器將 25 轉換成 Money 才能調用 baseAmount.operator+，但這是一個左值，不能直接轉換。或者尋找非成員 operator+。
   • 如果 Money 類別有 explicit Money(int)，那麼 baseAmount + 25 也會編譯錯誤。

這題考察定點數表示法（Fixed-Point Representation），包括二進位轉換、二補數表示法以及定點數的優缺點。

核心觀念：

• 定點數表示法：將一個數字分為整數部分和小數部分，並固定小數點的位置。
• 二進位表示法：將十進位數字轉換為二進位。
• 二補數（Two's Complement）：用於表示帶符號的二進位數，通常用於整數部分。
• 位權：二進位數字的每一位都有一個對應的權重。對於小數部分，權重是 $2^{-1}, 2^{-2}, \dots$。對於整數部分，權重是 $2^0, 2^1, \dots$。

解題過程：

題目設定：

• 總共 8 bits。
• 整數部分 4 bits。
• 小數部分 4 bits。
• 採用二補數表示帶符號數。

位權分析：

• 整數部分（從左到右）：$2^3, 2^2, 2^1, 2^0$。
• 小數部分（從左到右）：$2^{-1}, 2^{-2}, 2^{-3}, 2^{-4}$。

(a) 將 00100110$_2$ 轉換為十進位
* 這是帶符號數，最高位 (MSB) 是符號位。0 表示正數。
* 二進位數：0010 0110
* 整數部分：0010
* 小數部分：0110
* 整數部分轉換：
* 0010 = $0 \times 2^3 + 0 \times 2^2 + 1 \times 2^1 + 0 \times 2^0 = 0 + 0 + 2 + 0 = 2$。
* 小數部分轉換：
* 0110 = $0 \times 2^{-1} + 1 \times 2^{-2} + 1 \times 2^{-3} + 0 \times 2^{-4}$
* = $0 \times \frac{1}{2} + 1 \times \frac{1}{4} + 1 \times \frac{1}{8} + 0 \times \frac{1}{16}$
* = $0 + 0.25 + 0.125 + 0 = 0.375$。
* 總計：整數部分 + 小數部分 = $2 + 0.375 = 2.375$。

【答案】2.375

(b) 將 -6.3125$_{10}$ 轉換為定點數表示
* 步驟 1：將 -6.3125 轉換為二進位
* 整數部分 -6：
* 先轉換 6 為二進位：$6 = 4 + 2 = 1 \times 2^2 + 1 \times 2^1 + 0 \times 2^0 = 110_2$。
* 由於整數部分是 4 bits，需要補足：0110。
* 由於是負數，需要轉換成二補數。
* 先取正數 0110 的反碼：1001。
* 反碼加 1：1001 + 1 = 1010。
* 所以，-6 的 4 bits 二補數表示是 1010。
* 小數部分 -0.3125：
* 將 0.3125 轉換為二進位：
* $0.3125 \times 2 = 0.625$ (取整數部分 0)
* $0.625 \times 2 = 1.25$ (取整數部分 1)
* $0.25 \times 2 = 0.5$ (取整數部分 0)
* $0.5 \times 2 = 1.0$ (取整數部分 1)
* 將取出的整數部分由上到下排列：$0.0101_2$。
* 所以，0.3125 的二進位是 $0.0101_2$。
* 我們要表示 -0.3125。由於小數部分通常不直接用二補數表示（小數點後最高位是符號位，這會使計算複雜），而是直接轉換其絕對值，然後再根據符號位決定。
* 這裡的題目設定是「Two's complement is used for signed values」，這通常是指整個數值，特別是整數部分。小數部分通常是轉換絕對值後，再由整數部分的符號決定。
* 然而，更常見的定點數表示法是，整個固定位元寬度的數字都採用二補數。如果我們將整個 8 bits 都視為二補數：
* 整數部分：4 bits，小數部分：4 bits。
* 二進位表示是 S IIII . FFFF，其中 S 是符號位，IIII 是整數部分，FFFF 是小數部分。
* 位權：$2^3, 2^2, 2^1, 2^0$ | $2^{-1}, 2^{-2}, 2^{-3}, 2^{-4}$。
* 對於 -6.3125：
* 絕對值是 6.3125。
* 整數部分 6 是 0110。
* 小數部分 0.3125 是 0101。
* 組合起來是 0110.0101。
* 現在要轉換成 8 bits 的二補數。最高位是符號位。
* 如果最高位是符號位，且其他位是值，這不是標準的二補數。
* 標準的二補數表示法：
* 對於一個 N bits 的數，最高位是符號位，其權重是 $-2^{N-1}$。
* 在這裡，我們有 8 bits，其中 4 bits 是整數，4 bits 是小數。
* 最左邊的 bit (第 7 位，索引從 0 開始) 是符號位，其權重是 $-2^{4-1} = -2^3 = -8$。

這題考察軟體開發過程中，編譯器、直譯器、組合器和連結器的基本概念與功能。

核心觀念：

• 程式語言翻譯：將人類可讀的高階語言或組合語言轉換為機器可執行的機器碼的過程。
• 編譯器 (Compiler)：將整個高階語言原始碼一次性翻譯成機器碼或另一種低階語言。
• 直譯器 (Interpreter)：逐行（或逐句）讀取並執行高階語言程式碼，通常不產生獨立的可執行檔。
• 組合器 (Assembler)：將組合語言（Assembly Language）翻譯成機器碼。
• 連結器 (Linker)：將多個目標檔案（Object Files）和函式庫合併成一個可執行檔。

解題過程：

(a) Compiler (編譯器)
* 定義：編譯器是一種軟體工具，它將用高階程式語言（如 C, C++, Java）編寫的原始程式碼（Source Code）一次性地翻譯成低階語言，通常是機器碼（Machine Code）或彙編語言（Assembly Language）。
* 工作流程：編譯器通常包含幾個階段，如詞法分析（Lexical Analysis）、語法分析（Syntax Analysis）、語義分析（Semantic Analysis）、中間碼生成（Intermediate Code Generation）、程式碼優化（Code Optimization）和目標碼生成（Target Code Generation）。
* 輸出：生成一個獨立的可執行檔（Executable File）或目標檔案（Object File），使用者可以在之後執行。
* 優點：執行速度通常比直譯器快，因為程式碼在執行前已被完全翻譯和優化。
* 缺點：編譯過程可能比較耗時，且修改程式碼後需要重新編譯整個程式。

(b) Interpreter (直譯器)
* 定義：直譯器是一種軟體工具，它直接執行用高階程式語言編寫的程式碼，而無需事先將其翻譯成機器碼。它逐行（或逐語句）讀取原始碼，並立即執行相應的操作。
* 工作流程：直譯器會解析原始碼中的每一條指令，並將其轉換成一系列機器指令來執行。
* 輸出：通常不生成獨立的可執行檔。程式碼的執行是即時的。
* 優點：開發和除錯方便，因為修改程式碼後可以立即看到結果，無需編譯。適合腳本語言和快速原型開發。

這題考察對寄存器操作指令的理解，包括位元操作（AND, OR）、算術操作（ADD）和位移操作（SHR, SHL）。

核心觀念：

• 寄存器 (Register)：CPU 內部用於暫存數據的高速儲存單元。
• 位元操作 (Bitwise Operations)：AND, OR, XOR 等操作直接作用於二進位位的邏輯運算。
• 位移操作 (Shift Operations)：SHR (Shift Right) 和 SHL (Shift Left) 將位元向左或向右移動。
• 二補數與符號位：SHR 操作在處理有符號數時，可能會有算術右移（保持符號位）或邏輯右移（用 0 填充）。題目中描述的 SHR 是邏輯右移（左邊補 0）。
• 位元遮罩 (Bitmask)：使用特定的位元模式來選擇性地讀取、修改或清除某些位元。

解題過程：

寄存器資訊：

• 有 8 個寄存器：d0 到 d7。
• 每個寄存器是 16 bits，位元編號從 0 到 15。
• 位元 15 是最高位（MSB），位元 0 是最低位（LSB）。

(a) 將寄存器 d1 的所有位元清除為零
* 目標：讓 d1 的 16 個位元都變成 0。
* 方法：
1. 使用 AND 操作：將 d1 與一個全零的 16 位元值進行 AND 操作。任何數與 0 AND 結果都是 0。
* 我們需要一個全零的 16 位元值。可以通過將 d1 與自身 AND（但這不會改變 d1，除非結果存入 d1），或者與一個明確為零的值進行 AND。
* 最直接的方法是將 d1 與另一個寄存器（例如 d0）進行 AND 操作，假設 d0 已經被設置為零，或者將 d1 與一個立即數 0x0000 進行 AND。
* 指令格式是 AND dst, srcl, src2。
* 我們可以讓 dst 和 srcl 都是 d1，然後 src2 是 0。
* 如何得到 0？題目說 src2 可以是寄存器或立即值。一個立即值 0 可以用 0x0000 表示。
* 指令：AND d1, d1, 0x0000
* 或者，如果我們有一個寄存器，假設 d0 已經是 0 (或者我們可以先將 d0 設置為 0，例如 XOR d0, d0, d0，如果存在 XOR 指令的話；但題目沒有 XOR)。
* 另一種常見方法是，如果存在 MOV dst, immediate 指令，可以直接將 0 載入 d1。
* 但是，根據提供的指令集，我們只有 AND, OR, ADD, SHR, SHL。
* 最直接的方法是使用 AND 操作。
* 我們需要一個全零的 16 位元值作為 src2。如果 src2 可以是立即值，那麼 0x0000 就是我們要的。
* 指令：AND d1, d1, 0x0000
* 這個指令將 d1 的內容與 0x0000（即全零）進行位元 AND 操作，結果存回 d1。
2. 使用 OR 操作：將 d1 與一個全一的 16 位元值進行 OR 操作，然後再與全零值 AND。這比較複雜。
3. 使用 SHR/SHL 操作：
* 例如，將 d1 右移 16 位，右邊補 0，結果存回 d1。
* SHR d1, d1, 16。這會將 d1 的所有位元右移 16 位，左邊補 0。由於寄存器只有 16 位，右移 16 位會將所有原始位元移出，左邊補 16 個 0，最終結果是 0。
* 這也是一個有效的方法。

*   選擇最簡潔或最直接的方法。`SHR d1, d1, 16` 是一個非常簡潔的方法。`AND d1, d1, 0x0000` 也很直接，但需要知道立即數的表示法。假設 `0x0000` 是合法的立即值。

*   **選項**：
    *   `SHR d1, d1, 16`
    *   `AND d1, d1, 0x0000` (假設 0x0000 是合法的立即值)

*   我們給出其中一個。`SHR d1, d1, 16` 利用了位移操作的特性，並且不需要額外的立即值。

【答案】
`SHR d1, d1, 16`
或者
`AND d1, d1, 0x0000` (如果 0x0000 是合法的立即數)

(b) 提取 d1 的位元 5-10，放入 d2 的位元 0-5，d2 其他位元不變，d1 不變
* 目標：
* 讀取 d1 的位元 5, 6, 7, 8, 9, 10。
* 將這些位元存入 d2 的位元 0, 1, 2, 3, 4, 5。
* d2 的位元 6 到 15 保持不變。
* d1 保持不變。
* 步驟 1：提取 d1 的位元 5-10
* 我們需要創建一個「遮罩」（mask），只保留位元 5 到 10。
* 位元 5 到 10 總共有 6 個位元。
* 遮罩的模式應為：...0000111111000000 (16 bits)。
* 其中，位元 10 到 5 是 1，其他位是 0。
* 這個模式是 0000 1111 1100 0000。
* 轉換為十六進位：00C0。

這題考察電腦的位元組順序（Byte Order），即 Little-Endian 和 Big-Endian 的區別，以及 C 語言中的指標轉換和記憶體佈局。

核心觀念：

• 位元組順序 (Byte Order)：在電腦記憶體中，多位元組數據（如 int, long）的儲存順序。
  • Big-Endian：最高有效位元組 (Most Significant Byte, MSB) 儲存在最低記憶體位址。
  • Little-Endian：最低有效位元組 (Least Significant Byte, LSB) 儲存在最低記憶體位址。
• 指標轉換：將一個指標類型轉換為另一個類型，會影響程式如何解釋記憶體中的數據。將 int* 轉換為 unsigned char*，可以逐位元組地訪問 int 的內容。
• 記憶體佈局：一個 int 型別的變數在記憶體中佔用連續的位元組。

解題過程：

程式碼分析：

• int a = 0x12345678;：宣告一個 32 位元（4 位元組）的整數 a，並初始化為十六進位值 12345678。
• unsigned char *c = (unsigned char*)(&a);：獲取 a 的記憶體位址，並將其轉換為 unsigned char* 型別的指標 c。這意味著 c 現在指向 a 的第一個位元組，並且我們可以通過 c 及其偏移量（c+1, c+2, c+3）來逐個位元組地訪問 a 的內容。
• printf("%d\n", *c); // S1：
  • *c 讀取 c 指向的第一個位元組的值。
  • 根據 printf 的格式符號 %d，這個位元組的值將被解釋為一個十進位整數並輸出。
• printf("%d\n", *(c+3)); // S2：
  • c+3 指向 a 的第四個位元組（即 a 的最高位元組）。
  • *(c+3) 讀取這個位元組的值，並以十進位輸出。

已知資訊：

• a 的值是 0x12345678。
• a 在記憶體中的位元組順序是未知的。
• S1 的輸出是 18。

分析 S1 的輸出：

• a = 0x12345678。這個 32 位元的值可以分解為四個 8 位元組：
  • 0x12 (最高有效位元組, MSB)
  • 0x34
  • 0x56
  • 0x78 (最低有效位元組, LSB)

核心觀念

本題考查三種基本資料結構與排序方法：

1. Quicksort

   • 以子陣列第一個元素作為 pivot。
   • 指標 $i$ 從左向右尋找第一個不小於 pivot 的元素。
   • 指標 $j$ 從右向左尋找第一個不大於 pivot 的元素。
   • 若 $i<j$，交換 $a[i]$ 與 $a[j]$。
   • 最後交換 pivot 與 $a[j]$，使 pivot 位於排序後的正確位置。

2. Binary Search Tree, BST

   • 小於節點值的資料放左子樹。
   • 大於節點值的資料放右子樹。
   • 按照輸入順序逐一插入，且不做旋轉。

3. Max Heap

   • 每個父節點皆滿足
     $\text{parent} \geq \text{children}$
   • 新元素一律加入目前最下層最左側的空位，再向上與父節點比較交換。
   • 本題要求逐一插入，不能直接對全部資料執行 heapify。

---

(a) 依指定 Quicksort 排序

原始資料如下，以下以陣列索引 $0$ 至 $9$ 表示：

$$[37,5,26,1,61,11,59,15,48,19]$$

第一次分割：quicksort(0,9)

pivot 為第一個元素：

$$pivot=37$$

指標掃描：

• $i$ 往右越過 $5,26,1$，停在 $61$。
• $j$ 往左停在 $19$。
• 交換 $61$ 與 $19$：

$$[37,5,26,1,19,11,59,15,48,61]$$

繼續掃描：

• $i$ 越過 $11$，停在 $59$。
• $j$ 往左越過 $61,48$，停在 $15$。
• 交換 $59$ 與 $15$：

$$[37,5,26,1,19,11,15,59,48,61]$$

此時 $i$ 已不小於 $j$，交換 pivot $37$ 與 $a[j]=15$：

$$[15,5,26,1,19,11,37,59,48,61]$$

因此 pivot $37$ 位於索引 $6$，分成：

$$[15,5,26,1,19,11]\quad 37\quad [59,48,61]$$

題目程式會先遞迴處理較小的右半部，再以 while 處理左半部。

---

第二次分割：quicksort(7,9)

目前右半部為：

$$[59,48,61]$$

pivot 為 $59$。

• $i$ 越過 $48$，停在 $61$。
• $j$ 從右側越過 $61$，停在 $48$。
• 此時 $i>j$，直接將 pivot $59$ 與 $a[j]=48$ 交換：

$$[48,59,61]$$

pivot $59$ 位於索引 $8$，左右子陣列皆只有一個元素，完成此部分排序。

---

第三次分割：quicksort(0,5)

目前左半部為：

$$[15,5,26,1,19,11]$$

pivot 為 $15$。

• $i$ 越過 $5$，停在 $26$。
• $j$ 從右側停在 $11$。
• 交換 $26$ 與 $11$：

$$[15,5,11,1,19,26]$$

繼續掃描：

• $i$ 越過 $1$，停在 $19$。
• $j$ 從右側越過 $26,19$，停在 $1$。
• 此時 $i>j$，交換 pivot $15$ 與 $a[j]=1$：

$$[1,5,11,15,19,26]$$

pivot $15$ 位於索引 $3$，分成：

$$[1,5,11]\quad 15\quad [19,26]$$

---

第四次分割：quicksort(4,5)

子陣列為：

$$[19,26]$$

pivot 為 $19$。由於 $26>19$，pivot 不需移動，結果仍為：

$$[19,26]$$

---

第五次分割：quicksort(0,2)

子陣列為：

$$[1,5,11]$$

pivot 為 $1$。其餘元素皆大於 $1$，pivot 保持在最左側：

$$[1,5,11]$$

---

Quicksort 最終結果

合併各分割結果：

$$\boxed{[1,5,11,15,19,26,37,48,59,61]}$$

複雜度

• 平均時間複雜度：
  $O(n\log n)$
• 最壞時間複雜度：
  $O(n^2)$
• 本程式每次遞迴處理較小子陣列，較大子陣列交由 while 迴圈處理，因此遞迴堆疊空間約為：
  $O(\log n)$

---

(b) 依序建立 Binary Search Tree

輸入順序為：

$$37,5,26,1,61,11,59,15,48,19$$

逐一插入

1. 插入 $37$：成為根節點。
2. 插入 $5$：$5<37$，放在 $37$ 左側。
3. 插入 $26$：$26<37$，再因 $26>5$，放在 $5$ 右側。
4. 插入 $1$：$1<37$、$1<5$，放在 $5$ 左側。
5. 插入 $61$：$61>37$，放在 $37$ 右側。
6. 插入 $11$：$11<37$、$11>5$、$11<26$，放在 $26$ 左側。
7. 插入 $59$：$59>37$、$59<61$，放在 $61$ 左側。
8. 插入 $15$：$15<37$、$15>5$、$15<26$、$15>11$，放在 $11$ 右側。
9. 插入 $48$：$48>37$、$48<61$、$48<59$，放在 $59$ 左側。

這題考察 C 語言的函數參數傳遞機制，特別是「傳址呼叫」（Call by Reference）的實現方式，以及函數原型（Function Prototype）和函數定義的語法。

核心觀念：

• 函數參數傳遞：C 語言預設是「傳值呼叫」（Call by Value），即函數接收的是參數的副本。若要實現「傳址呼叫」（相當於 C++ 的 Call by Reference），需要傳遞參數的指標。
• 指標 (Pointer)：變數的記憶體位址。
• 解引用 (Dereference)：通過指標訪問其指向的值（使用 * 操作符）。
• 函數原型與定義：函數定義提供了函數的實現，而函數原型（或函數頭）則聲明了函數的名稱、返回類型和參數類型。

解題過程：

題目要求函數 func 能夠交換兩個整數變數的值，並且程式執行的輸出結果是 "200 100"。
在 main 函數中，a 的初始值是 100，b 的初始值是 200。
printf("%d %d\n", a, b); 輸出 a 和 b 的值。
如果輸出是 "200 100"，這意味著在 func 函數被呼叫後，a 的值變成了 200，而 b 的值變成了 100。
這表明 func 函數成功地交換了 a 和 b 的值。

由於 C 語言是傳值呼叫，直接傳遞 a 和 b 的值給 func 無法修改 main 中的 a 和 b。
為了讓 func 能夠修改 main 中的變數，我們必須傳遞 a 和 b 的 位址（指標）。

(1) 函數參數列表：void func((1))
* func 函數需要接收兩個整數的指標，以便能夠修改它們指向的變數。
* 因此，參數類型應該是 int *。
* 為了能夠在函數內部訪問和修改指標指向的值，我們需要為這兩個指標命名，例如 ptr_a 和 ptr_b。
* 所以，(1) 應該是 int *ptr_a, int *ptr_b。

(2) 函數體：(2)
* 在函數體內部，我們需要交換 ptr_a 和 ptr_b 所指向的值。
* 假設 ptr_a 指向 a，ptr_b 指向 b。