108 年 國立清華大學資訊工程學系碩士班《基礎計算機科學》

(A) 遞迴關係式求解

核心觀念

本題考查**普通生成函數（Ordinary Generating Function, OGF）**解非齊次線性遞迴關係式。
主要使用以下基本公式與級數展開：

1. 若序列為 $\{a_n\}$，其生成函數定義為 $A(x) = \sum_{n=0}^{\infty} a_n x^n$。
2. 常用幾何級數與閉合形式：
   • $\sum_{n=0}^{\infty} x^n = \frac{1}{1-x}$
   • $\sum_{n=0}^{\infty} r^n x^n = \frac{1}{1-rx}$
   • $\sum_{n=0}^{\infty} n x^n = \frac{x}{(1-x)^2}$
3. 利用部分分式分解（Partial Fraction Decomposition）將 $A(x)$ 拆解為標準項後，藉由二項式定理展開取各項係數即為閉合解 $a_n$。

---

解題方法

題目給定遞迴關係式為：

$$a_n - 4a_{n-1} + 3a_{n-2} = 2^n + n + 3 \quad (n \ge 2)$$

初始條件：$a_0 = 1$，$a_1 = 4$。

步驟一：設定生成函數並列出方程式
令 $A(x) = \sum_{n=0}^{\infty} a_n x^n$。
在遞迴關係式兩端同乘 $x^n$ 並對 $n \ge 2$ 取和：

$$\sum_{n=2}^{\infty} a_n x^n - 4 \sum_{n=2}^{\infty} a_{n-1} x^n + 3 \sum_{n=2}^{\infty} a_{n-2} x^n = \sum_{n=2}^{\infty} 2^n x^n + \sum_{n=2}^{\infty} n x^n + 3 \sum_{n=2}^{\infty} x^n$$

步驟二：將左式化為 $A(x)$ 的形式

• $\sum_{n=2}^{\infty} a_n x^n = A(x) - a_0 - a_1 x = A(x) - 1 - 4x$
• $\sum_{n=2}^{\infty} a_{n-1} x^n = x \sum_{n=2}^{\infty} a_{n-1} x^{n-1} = x [A(x) - a_0] = x(A(x) - 1)$
• $\sum_{n=2}^{\infty} a_{n-2} x^n = x^2 \sum_{n=2}^{\infty} a_{n-2} x^{n-2} = x^2 A(x)$

代入左式可得：

$$[A(x) - 1 - 4x] - 4x[A(x) - 1] + 3x^2 A(x) = (1 - 4x + 3x^2)A(x) - 1$$

步驟三：將右式非齊次項轉換為封閉形式

• $\sum_{n=2}^{\infty} 2^n x^n = \frac{1}{1-2x} - 1 - 2x = \frac{4x^2}{1-2x}$
• $\sum_{n=2}^{\infty} n x^n = \frac{x}{(1-x)^2} - x = \frac{x - x(1-2x+x^2)}{(1-x)^2} = \frac{2x^2 - x^3}{(1-x)^2}$
• $3 \sum_{n=2}^{\infty} x^n = 3 \left( \frac{1}{1-x} - 1 - x \right) = \frac{3x^2}{1-x}$

將左式與右式統整，並將左式的常數項 $-1$ 移至右側（注意到 $1 + \sum_{n=2}^{\infty} (2^n + n + 3)x^n$ 等同於將右側補回 $n=0$ 的項，但需調整 $n=1$ 的缺項）：
直接在等號兩側還原為完整的無窮級數形式更不易出錯：

$$(1 - 4x + 3x^2)A(x) - 1 = \left( \frac{1}{1-2x} - 1 - 2x \right) + \left( \frac{x}{(1-x)^2} - x \right) + 3\left( \frac{1}{1-x} - 1 - x \right)$$

將右側的常數項合併並移項整理：

$$(1 - 4x + 3x^2)A(x) = \frac{1}{1-2x} + \frac{x}{(1-x)^2} + \frac{3}{1-x} - 6x - 3$$

通分右側：

$$\frac{1}{1-2x} + \frac{3(1-x) + x}{(1-x)^2} - (6x+3) = \frac{1}{1-2x} + \frac{3-2x}{(1-x)^2} - (6x+3)$$ $$= \frac{(1-x)^2 + (3-2x)(1-2x) - (6x+3)(1-2x)(1-x)^2}{(1-2x)(1-x)^2}$$

分子展開後計算得：

$$\text{分子} = -12x^4 + 30x^3 - 22x^2 + 5x + 1$$

因此：

$$(1-x)(1-3x) A(x) = \frac{-12x^4 + 30x^3 - 22x^2 + 5x + 1}{(1-2x)(1-x)^2}$$

兩側同除以 $(1-x)(1-3x)$：

$$A(x) = \frac{-12x^4 + 30x^3 - 22x^2 + 5x + 1}{(1-3x)(1-2x)(1-x)^3}$$

步驟四：部分分式分解（Partial Fraction Decomposition）
設：

$$A(x) = \frac{A}{1-3x} + \frac{B}{1-2x} + \frac{C}{1-x} + \frac{D}{(1-x)^2} + \frac{E}{(1-x)^3}$$

利用遮蔽法（Heaviside cover-up method）與比較係數求解各係數：

1. 求 $A$：兩端同乘 $(1-3x)$ 並令 $x = \frac{1}{3}$：

   $$A = \left. \frac{-12x^4 + 30x^3 - 22x^2 + 5x + 1}{(1-2x)(1-x)^3} \right|_{x=1/3} = \frac{-\frac{12}{81} + \frac{30}{27} - \frac{22}{9} + \frac{5}{3} + 1}{\left(1-\frac{2}{3}\right)\left(1-\frac{1}{3}\right)^3} = \frac{\frac{29}{27}}{\frac{1}{3} \cdot \frac{8}{27}} = \frac{29}{8}$$

2. 求 $B$：兩端同乘 $(1-2x)$ 並令 $x = \frac{1}{2}$：

   $$B = \left. \frac{-12x^4 + 30x^3 - 22x^2 + 5x + 1}{(1-3x)(1-x)^3} \right|_{x=1/2} = \frac{-\frac{12}{16} + \frac{30}{8} - \frac{22}{4} + \frac{5}{2} + 1}{\left(1-\frac{3}{2}\right)\left(1-\frac{1}{2}\right)^3} = \frac{1}{\left(-\frac{1}{2}\right)\left(\frac{1}{8}\right)} = -16$$

3. 求 $E$：兩端同乘 $(1-x)^3$ 並令 $x = 1$：

   $$E = \left. \frac{-12x^4 + 30x^3 - 22x^2 + 5x + 1}{(1-3x)(1-2x)} \right|_{x=1} = \frac{-12 + 30 - 22 + 5 + 1}{(1-3)(1-2)} = \frac{2}{(-2)(-1)} = 1$$

4. 求 $D$ 與 $C$：
   將已求得的各項帶入或藉由特徵根法對應非齊次解形式。
   本題之常微分/差分特徵方程為 $(r-3)(r-1) = 0$。非齊次項包含 $2^n$ 與一次多項式 $n+3$。由於 $r=1$ 為單重特徵根，對應非齊次多項式的特解形式為 $n(c_1 n + c_2) = c_1 n^2 + c_2 n$。
   因此，閉合形式之通用解為：

核心觀念

本題評量離散數學中二元關係（Binary Relations）的計數問題。設集合 $A$ 的元素個數為 $|A| = n$，則其笛卡兒積（Cartesian product）$A \times A$ 共有 $n^2$ 個有序對（ordered pairs）。$A$ 上的任意關係 $R$ 即為 $A \times A$ 的一個子集合，亦可以 $n \times n$ 的布林關聯矩陣（Relation Matrix）$M_R = [m_{ij}]$ 表示：

• 主對角線元素（Diagonal elements）：共 $n$ 個有序對 $(a_i, a_i)$，對應矩陣主對角線 $m_{ii}$。
• 非對角線對稱元素對（Off-diagonal symmetric pairs）：$(a_i, a_j)$ 與 $(a_j, a_i)$（其中 $i < j$），共有 $\binom{n}{2} = \frac{n(n-1)}{2}$ 組無序對，每組包含 2 個互為反向的有序對，合計 $n(n-1) = n^2 - n$ 個元素。

各類關係的定義如下：

1. 反身性（Reflexive）：對所有 $a \in A$，皆有 $(a, a) \in R$。亦即主對角線 $n$ 個元素必須全為 1。
2. 對稱性（Symmetric）：對所有 $a, b \in A$，若 $(a, b) \in R$，則 $(b, a) \in R$。亦即關聯矩陣為對稱矩陣（$m_{ij} = m_{ji}$）。
3. 反自反性／非反身性（Irreflexive）：對所有 $a \in A$，皆有 $(a, a) \notin R$。亦即主對角線 $n$ 個元素必須全為 0。

---

解題方法

解決關係計數問題的最佳切入點為**「矩陣位置獨立性分析」與「乘法原理／排容原理」**：

1. (A) 同時滿足反身與對稱：

   • 關係的計數可拆解為主對角線元素與非對角線元素的選取方法數之乘積。
   • 反身性鎖定主對角線元素；對稱性則限制非對角線對稱元素對必須同進同出。

2. (B) 既非反身亦非反自反（Neither reflexive nor irreflexive）：

   • 可直接分析主對角線的狀態：反身性要求主對角線「全為 1」，反自反性要求主對角線「全為 0」。
   • 因此「既非反身亦非反自反」等價於主對角線元素「不全為 1 且不全為 0」，其餘非對角線元素則可自由選取。
   • 亦可採用餘集與排容原理（Principle of Inclusion-Exclusion）從所有可能關係中扣除反身關係與反自反關係。

---

小題詳細推導與分析

(A) Both reflexive and symmetric（既反身又對稱）

1. 主對角線元素：
   • 因 $R$ 具反身性，對所有 $1 \le i \le n$，$(a_i, a_i)$ 必定屬於 $R$。
   • 每個主對角線位置只有 1 種選擇（必須存在），共 $n$ 個位置，可能情形數為：

$$1^n = 1$$

2. 非對角線元素：
   • 因 $R$ 具對稱性，對於每一對相異元素形成的對稱對 $\{(a_i, a_j), (a_j, a_i)\}$（$1 \le i < j \le n$）：
     • 兩者同時屬於 $R$
     • 兩者同時不屬於 $R$
   • 共有 $\binom{n}{2} = \frac{n(n-1)}{2}$ 組對稱對，每一組恰有 2 種選法。
   • 非對角線部分的可能情形數為：

$$2^{\frac{n(n-1)}{2}}$$

3. 綜合計算：
   • 依乘法原理，既反身又對稱的關係總數為：

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

---

(B) Neither reflexive nor irreflexive（既非反身亦非反自反）

假設集合元素個數 $n \ge 1$：

方法一：對角線獨立狀態分析法（最直觀法）

1. 主對角線限制：
   • 主對角線上共有 $n$ 個位置，每個位置可選入或不選入關係中，總配置數為 $2^n$ 種。

核心觀念

本題考查「樹」與「圖同構」的基本分類。

• 樹是連通且不含循環的無向圖。
• 具有 $n$ 個頂點的樹必有 $n-1$ 條邊，因此本題的樹有 $4$ 條邊。
• 「非同構」表示不考慮頂點標籤；只要兩個圖的鄰接結構相同，就視為同一種。
• 「非根樹」表示沒有指定特殊的根頂點。

樹中所有頂點的度數總和為

$$2|E|=2(4)=8.$$

解題方法

依照樹的最大度數分類。五個頂點的樹，其最大度數介於 $2$ 與 $4$ 之間。

情況一：最大度數為 $4$

某一頂點與其他四個頂點全部相連，形成星狀樹 $K_{1,4}$：

$$\deg=(4,1,1,1,1).$$

此結構只有一種非同構形式。

情況二：最大度數為 $3$

設度數為 $3$ 的頂點為中心。它必須連接三個分支，而總共還有四個其他頂點。

為了使用完全部五個頂點，其中一個分支必須再延伸一個頂點，形成度數序列

$$\deg=(3,2,1,1,1).$$

核心觀念

本題評量開放定址法（Open Addressing）中的線性探測（Linear Probing）碰撞處理機制，以及各鍵值（Key）在插入過程中的先後相依關係（Dependency / Partial Order）。

1. 雜湊函數與初始位置（Home Slot）：
   依題意，長度 $m = 10$，雜湊函數為 $h(k) = k \bmod 10$。鍵值 $k$ 首先嘗試放入其初始位置 $h(k)$。

2. 線性探測（Linear Probing）：
   若位置 $h(k)$ 已被佔據（發生碰撞 Overflow），則依序檢查相鄰的下一個位置：

   $h_i(k) = (h(k) + i) \bmod 10, \quad i = 0, 1, 2, \dots$

   直到找到第一個空的槽位（Empty Slot）將其存入。

3. 插入順序的偏序限制：
   如果鍵值 $k$ 最終落在位置 $p$，且 $p \ne h(k)$，表示在 $k$ 被插入的當下，從初始位置 $h(k)$ 到 $p - 1$ 的連續區間內所有槽位都必須已被其他鍵值佔據。因此，佔據這些槽位的鍵值必須在 $k$ 之前被插入。

---

解題方法

首先比對各鍵值的初始雜湊值與最終所在位置：

鍵值 $k$	初始雜湊值 $h(k) = k \bmod 10$	最終位置（Actual Index）	是否發生探測位移
42	$42 \bmod 10 = 2$	2	否（直接落在初始位置）
23	$23 \bmod 10 = 3$	3	否（直接落在初始位置）
34	$34 \bmod 10 = 4$	4	否（直接落在初始位置）
52	$52 \bmod 10 = 2$	5	是（由 2 位移至 5）
46	$46 \bmod 10 = 6$	6	否（直接落在初始位置）
33	$33 \bmod 10 = 3$	7	是（由 3 位移至 7）

關鍵推導（偏序條件建立）：

1. 針對鍵值 52：

   • 初始位置為 $2$，最終存放在 $5$。

   • 這表示在插入 $52$ 時，槽位 $2, 3, 4$ 必須都已經有資料。

   • 目前佔據這三個槽位的是 $42$（槽位 2）、$23$（槽位 3）、$34$（槽位 4）。

   • 條件一：$42, 23, 34$ 均必須在 $52$ 之前被插入，即：

     $\{42, 23, 34\} \prec 52$

2. 針對鍵值 33：

   • 初始位置為 $3$，最終存放在 $7$。

   • 這表示在插入 $33$ 時，槽位 $3, 4, 5, 6$ 必須都已經有資料。

   • 目前佔據這四個槽位的是 $23$（槽位 3）、$34$（槽位 4）、$52$（槽位 5）、$46$（槽位 6）。

   • 條件二：$23, 34, 52, 46$ 均必須在 $33$ 之前被插入，即：

     $\{23, 34, 52, 46\} \prec 33$

3. 綜合傳遞關係：

   • 由於 $42 \prec 52$，且 $52 \prec 33$，因此 $42$ 也必須在 $33$ 之前插入。
   • 綜合所有限制，其餘 5 個鍵值 $\{42, 23, 34, 46, 52\}$ 全部都必須在 $33$ 之前被插入。換言之，$33$ 必須是這 6 個元素中最後一個被插入的鍵值。

---

選項分析

核心觀念

本題考查資料結構中以兩個**堆疊（Stack）實作佇列（Queue）**的經典演算法：

1. 佇列（Queue）：遵循「先進先出」（FIFO, First-In-First-Out）原則。
2. 堆疊（Stack）：遵循「後進先出」（LIFO, Last-In-First-Out）原則。
3. 兩次反轉等於同序：堆疊的彈出順序會將資料反轉一次；若將元素從第一個堆疊逐一彈出並壓入第二個堆疊，資料順序會經歷第二次反轉，剛好還原成先進先出（FIFO）的順序。因此通常配置：
   • stack1：作為輸入端（Inbox Stack），負責接收所有 enqueue 的新元素。
   • stack2：作為輸出端（Outbox Stack），負責供應 dequeue 的取值。

---

解題方法

由類別成員與建構子可知，內部維護了 stack1 與 stack2：

1. enqueue(e) 流程：
   題目程式碼已給定：

   void enqueue(T e) {
       stack1.push(e);
   }
   

   這確立了 stack1 為輸入端堆疊。

2. dequeue() 流程：
   欲取出佇列前端元素（最早進入的元素）：

   • 若 stack2 內尚有元素，則 stack2 的頂端即為當前最先進入佇列的元素，可直接彈出。
   • 若 stack2 為空，必須將 stack1 內現存的所有元素依序彈出並壓入 stack2。此動作將 stack1 內的元素順序完全顛倒，使最早進入的元素移動至 stack2 的頂端。
   • 傾倒完成後，若 stack2 非空，則自 stack2 頂端彈出元素回傳；若 stack2 仍為空（代表原本佇列內無任何元素），則回傳 null。

對應程式碼結構推導各空格：

• 第一步：檢查 stack2 是否為空。若空，才需要將 stack1 的元素倒過來。

  if( (__I__).isEmpty() )
  

  故 I 為 stack2。
• 第二步：當 stack1 還有元素時，將其逐一轉移至 stack2。

  while( !(__II__).isEmpty() )
      (__III__).push( (__IV__).pop() );
  

  故 II 為 stack1、III 為 stack2、IV 為 stack1。
• 第三步：檢查轉移後的 stack2 是否非空，若是則從 stack2 取出頂端元素。

核心觀念

1. AVL 樹定義與平衡因子（Balance Factor, BF）：

   • AVL 樹為一種自平衡二元搜尋樹（Self-Balancing Binary Search Tree）。
   • 對於樹中任一節點 $x$，其平衡因子定義為左子樹高度減去右子樹高度：
     $BF(x) = h_L(x) - h_R(x)$
     （空樹高度定義為 $0$，單一節點樹高度定義為 $1$）。
   • AVL 樹的平衡條件為：所有節點的平衡因子皆滿足 $|BF(x)| \le 1$（即 $BF(x) \in \{-1, 0, 1\}$）。

2. 失衡判斷與旋轉調整（Rotations）：

   • 當新節點插入後，從插入位置沿著路徑向上回溯，找到第一個（深度最深、離插入點最近）滿足 $|BF| > 1$ 的失衡節點 $A$。
   • 根據由 $A$ 往插入節點路徑上的前兩步方向，分為四種旋轉型態：
     • LL 型（路徑為左 $\to$ 左）：對節點 $A$ 進行單次右旋（Right Rotation）。
     • RR 型（路徑為右 $\to$ 右）：對節點 $A$ 進行單次左旋（Left Rotation）。
     • LR 型（路徑為左 $\to$ 右）：先對左小孩進行左旋，再對節點 $A$ 進行右旋（Double Rotation）。
     • RL 型（路徑為右 $\to$ 左）：先對右小孩進行右旋，再對節點 $A$ 進行左旋（Double Rotation）。

---

解題方法

子題 (A)：依序插入 100, 200, 50, 300, 400

1. 插入 100：作為根節點。
2. 插入 200：$200 > 100$，置於 100 之右小孩。全樹平衡。
3. 插入 50：$50 < 100$，置於 100 之左小孩。此時根節點 100 的 $BF = 1 - 1 = 0$，全樹平衡。
4. 插入 300：$300 > 100 \to 300 > 200$，置於 200 之右小孩。
   • 節點 200 的 $BF = 0 - 1 = -1$。
   • 節點 100 的 $BF = 1 - 2 = -1$。全樹平衡。
5. 插入 400：$400 > 100 \to 400 > 200 \to 400 > 300$，置於 300 之右小孩。
   • 向上檢查平衡因子：
     • 節點 300：$BF = 0 - 1 = -1$
     • 節點 200：$BF = 0 - 2 = -2$ $\implies$ 第一個失衡節點為 200。
   • 判定型態：路徑為 $200 \to 300$（右）$\to 400$（右），屬於 RR 型。
   • 執行旋轉：以 200 為軸進行左旋（Left Rotation），使 300 成為局部子樹的根節點，200 降為 300 的左小孩，400 為 300 的右小孩。
   • 調整後，根節點 100 的左子樹高度為 1（節點 50），右子樹高度為 2（節點 300），$BF(100) = 1 - 2 = -1$；節點 300 的 $BF = 1 - 1 = 0$。全樹恢復平衡。

---

子題 (B)：承接 (A)，繼續依序插入 25, 250, 225, 500, 240, 260

1. 插入 25：$25 < 100 \to 25 < 50$，置於 50 之左小孩。

   • 節點 50 的 $BF = 1 - 0 = 1$。
   • 節點 100 的左子樹高 2，右子樹高 2，$BF(100) = 2 - 2 = 0$。全樹平衡。

2. 插入 250：$250 > 100 \to 250 < 300 \to 250 > 200$，置於 200 之右小孩。

   • 節點 200 的 $BF = 0 - 1 = -1$。
   • 節點 300 的左高 2、右高 1，$BF(300) = 2 - 1 = 1$。
   • 節點 100 的左高 2、右高 3，$BF(100) = 2 - 3 = -1$。全樹平衡。

3. 插入 225：$225 > 100 \to 225 < 300 \to 225 > 200 \to 225 < 250$，置於 250 之左小孩。

   • 向上回溯檢查平衡因子：
     • 節點 250：$BF = 1 - 0 = 1$
     • 節點 200：$BF = 0 - 2 = -2$ $\implies$ 第一個失衡節點為 200。
   • 判定型態：路徑為 $200 \to 250$（右）$\to 225$（左），屬於 RL 型。
   • 執行雙旋轉：

核心觀念

本題評量對 二元堆積（Binary Heap） 與 樹的走訪（Tree Traversal） 結構特性的掌握：

1. Max Heap 定義：
   • 結構性（Structural Property）：必須是一棵完全二元樹（Complete Binary Tree, CBT）。若節點總數為 $n$，其形狀（樹狀骨架）是唯一確定的；若以陣列（1-based）表示，節點 $i$ 的左子節點為 $2i$，右子節點為 $2i+1$。
   • 堆積性（Heap-Order Property）：每個非根節點的值均不大於其父節點的值（$A[\text{parent}(i)] \ge A[i]$），因此任何子樹的根節點必為該子樹中的最大值。
2. 中序走訪（In-order Traversal）：
   • 遍歷順序為：左子樹 $\to$ 當前節點 $\to$ 右子樹。
3. 笛卡兒樹（Cartesian Tree）視角：
   • 給定一棵樹的「中序走訪序列」，同時要求滿足「父節點 $\ge$ 子節點（Max Heap 特性）」，則整棵樹的根節點必然是該序列中的全域最大值。最大值左側的元素構成左子樹，右側元素構成右子樹，對各子樹亦遞迴適用此性質。
   • 本題結合了「完全二元樹（CBT）形狀約束」與「In-order 序列」，兩者能互相印證並唯一確定每個節點的位置。

---

解題方法

給定節點數 $n = 10$，中序走訪序列為：
$\text{In-order: } [2, 16, 7, 62, 5, 9, 188, 14, 78, 10]$

步驟一：確定完全二元樹（CBT）的骨架與中序訪問順序

具有 10 個節點的 CBT，其 1-based 陣列索引對應的樹狀結構如下（編號 $1 \sim 10$）：

• Level 1: 節點 1（Root）
• Level 2: 節點 2、3
• Level 3: 節點 4、5、6、7
• Level 4: 節點 8、9、10（節點 8、9 為節點 4 之子，節點 10 為節點 5 之左子）

              1
          /       \
        2           3
      /   \       /   \
     4     5     6     7
    / \   /
   8   9 10

對此骨架進行中序走訪（左 $\to$ 根 $\to$ 右），求出每個陣列位置被訪問的先後順序：

1. 走訪左子樹（以 2 為根）：
   • 走訪 2 的左子樹（以 4 為根）：先走訪 8 $\to$ 再走訪 4 $\to$ 再走訪 9。
   • 走訪根 2。
   • 走訪 2 的右子樹（以 5 為根）：先走訪 10 $\to$ 再走訪 5。
   • 至此左子樹訪問順序為：$8 \to 4 \to 9 \to 2 \to 10 \to 5$。
2. 走訪整棵樹的根：$1$。
3. 走訪右子樹（以 3 為根）：
   • 走訪 3 的左子樹：$6$。
   • 走訪根：$3$。
   • 走訪 3 的右子樹：$7$。
   • 至此右子樹訪問順序為：$6 \to 3 \to 7$。

核心觀念

本題探討「資料結構對演算法時間複雜度之影響」，主要評量考生對集合（Set）操作在不同底層資料結構下的時間複雜度分析能力。
演算法包含一個處理 $n$ 個元素的迴圈，在每次迭代中對集合 $S$ 進行成員查詢（member，即搜尋）與插入（insert）。演算法的總時間複雜度取決於：

1. 迴圈執行次數：共執行 $n$ 次。
2. 動態陣列加入元素（append）：均攤時間複雜度為 $O(1)$。
3. 集合操作的單次花費：在不同資料結構（Hash Table、BST、AVL Tree）下，集合內元素至多為 $n$ 個時，單次 member 與 insert 的時間複雜度差異。

---

解題方法

設輸入陣列長度為 $n$。迴圈共執行 $n$ 次，在第 $i$ 次迭代時，集合 $S$ 中的元素個數至多為 $i-1$ 個（最大不超過 $n$）。

• 每次迭代的操作包含：
  1. S.member(x)：搜尋操作。
  2. 若不存在，執行 S.insert(x)：插入操作。
  3. A.append(x)：動態陣列尾端插入，均攤花費 $O(1)$。

因此，每次迴圈的核心花費為集合的「搜尋」與「插入」。總時間複雜度為：

$$T(n) = \sum_{i=1}^{n} \left( T_{\text{search}}(i) + T_{\text{insert}}(i) + O(1) \right)$$

根據 Big-O 記號的定義，通常分析演算法的最壞情況（Worst-case complexity）。若題目有特殊假設（如 Hash Table 無溢位），則依假設推導。

---

各小題分析與推導

(A) a hash table (with the assumption that overflow does not occur)?

• 分析：
  題目明確假設「overflow does not occur」（不發生溢位／碰撞衝突），表示雜湊函數能完美或無衝突地配置，因此每次雜湊表的搜尋（member）與插入（insert）操作時間複雜度皆為 $O(1)$。
• 推導：
  迴圈共執行 $n$ 次，每次迭代皆花費 $O(1)$： $$T(n) = n \times O(1) = O(n)$$
• 複雜度：$O(n)$。

---

(B) a binary search tree?

• 分析：
  若集合 $S$ 採用一般二元搜尋樹（Binary Search Tree, BST），未保證樹的平衡性。

核心觀念

本題的核心為主定理（Master Theorem）求解分治遞迴關係式（Divide-and-Conquer Recurrence），以及漸近時間複雜度的嚴格比較（Asymptotically Faster）。

1. 主定理（Master Theorem）：
   對於遞迴式 $T(n) = a T\left(\frac{n}{b}\right) + f(n)$，其中 $a \ge 1, b > 1$：

   • Case 1：若存在 $\epsilon > 0$，使得 $f(n) = O(n^{\log_b a - \epsilon})$，則 $T(n) = \Theta(n^{\log_b a})$。
   • Case 2：若 $f(n) = \Theta(n^{\log_b a})$，則 $T(n) = \Theta(n^{\log_b a} \log n)$。
   • Case 3：若存在 $\epsilon > 0$，使得 $f(n) = \Omega(n^{\log_b a + \epsilon})$，且滿足正規條件（regularity condition，即存在 $c < 1$ 使得 $a f(n/b) \le c f(n)$），則 $T(n) = \Theta(f(n))$。

2. 漸近更快的定義（Asymptotically Faster）：
   演算法 $\text{A}'$ 比演算法 $\text{A}$ 漸近更快（asymptotically faster），代表當 $n \to \infty$ 時，$\text{A}'$ 的執行時間增長階數嚴格小於 $\text{A}$，即：

   $$T'(n) = o(T(n)) \iff \lim_{n \to \infty} \frac{T'(n)}{T(n)} = 0$$

---

解題方法

步驟一：求演算法 A 的時間複雜度 $T(n)$

演算法 $\text{A}$ 的遞迴式為：

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

• 參數為 $a = 7, b = 2, f(n) = n^2$。
• 臨界次方為 $\log_b a = \log_2 7$。
• 由於 $2^2 = 4 < 7 < 2^3 = 8$，可知 $2 < \log_2 7 < 3$。
• 比較 $f(n) = n^2$ 與 $n^{\log_2 7}$：
  取 $\epsilon = \log_2 7 - 2 > 0$，可得 $f(n) = n^2 = O(n^{\log_2 7 - \epsilon})$。
• 根據主定理 Case 1： $$T(n) = \Theta(n^{\log_2 7})$$

步驟二：分析演算法 A' 的時間複雜度 $T'(n)$

演算法 $\text{A}'$ 的遞迴式為：

$$T'(n) = aT'\left(\frac{n}{4}\right) + n^2$$

• 參數為分治次數 $a$（正整數）、縮小倍數 $b = 4$、$f(n) = n^2$。
• 臨界次方為 $\log_b a = \log_4 a$。

根據 $a$ 的數值大小，可分為三種情況：

1. 當 $1 \le a < 16$ 時：
   $\log_4 a < \log_4 16 = 2$。
   此時 $f(n) = n^2 = \Omega(n^{\log_4 a + \epsilon})$，且 $a\left(\frac{n}{4}\right)^2 = \frac{a}{16}n^2 \le c n^2$（取 $c = \frac{a}{16} < 1$ 滿足正規條件）。
   由主定理 Case 3 可得： $$T'(n) = \Theta(n^2)$$

核心觀念

• Kruskal 演算法：將邊依權重由小到大檢查；若加入某邊不會形成環，就納入最小生成樹，直到選出 $|V|-1=5$ 條邊。
• Dijkstra 演算法：從來源點 $n1$ 出發，每次確定目前暫定距離最小的未處理頂點，再用該頂點更新鄰點距離：
  $d(v)\leftarrow\min\bigl(d(v),\,d(u)+w(u,v)\bigr)$
• 深度優先搜尋（DFS）：沿著尚未拜訪的鄰點深入；題目指定邊權重愈小，鄰點優先級愈高，因此每一步按相連邊權重由小到大選擇。

（A）Kruskal 最小生成樹

將所有邊依權重排序：

$$(n2,n3):5,\ (n5,n6):10,\ (n3,n6):15,\ (n2,n5):20,\ (n1,n4):25,\ (n1,n2):30,\ (n3,n5):35,\ (n4,n6):40,\ (n3,n4):50$$

依序檢查：

邊	權重	處理
$n2-n3$	5	納入
$n5-n6$	10	納入
$n3-n6$	15	納入，連接兩個連通分量
$n2-n5$	20	捨棄；加入會形成環
$n1-n4$	25	納入
$n1-n2$	30	納入，連接兩個連通分量，已選滿 5 條
$n3-n5$、$n4-n6$、$n3-n4$	35、40、50	不需再檢查；若加入皆會形成環

因此最小生成樹的邊為：

$$\{n2-n3,\ n5-n6,\ n3-n6,\ n1-n4,\ n1-n2\}$$

總權重為 $5+10+15+25+30=85$。

（B）以 $n1$ 為來源的 Dijkstra 演算法

初始距離為 $d(n1)=0$，其他頂點距離皆為無限大。每次確定暫定距離最小的未處理頂點，並更新其鄰點：

確定頂點	更新結果
$n1$（距離 0）	$d(n2)=30$，前驅為 $n1$；$d(n4)=25$，前驅為 $n1$
$n4$（距離 25）	$d(n6)=65$，前驅暫為 $n4$
$n2$（距離 30）	$d(n3)=35$，前驅為 $n2$；$d(n5)=50$，前驅為 $n2$

核心觀念

本題評量**二元搜尋（Binary Search）與費氏搜尋（Fibonacci Search）**在有序陣列中的搜尋追蹤（Trace）與鍵值比較次數（Key Comparisons）。

1. 二元搜尋（Binary Search）的標準定義（依經典教科書 Horowitz / Sahni 規範）：

   • 給定排序好的陣列 $A[1 \dots n]$，區間為 $[left, right]$，初始時 $left = 1, right = n$。
   • 中間索引計算公式為： $$mid = \left\lfloor \frac{left + right}{2} \right\rfloor$$
   • 每次比較：
     • 若 $K = A[mid]$：搜尋成功，結束。
     • 若 $K < A[mid]$：往左半部搜尋，更新 $right = mid - 1$。
     • 若 $K > A[mid]$：往右半部搜尋，更新 $left = mid + 1$。
   • 每次檢查 $K$ 與 $A[mid]$ 的關係計為 1 次關鍵鍵值比較（Key Comparison）。

2. 費氏搜尋（Fibonacci Search）的標準定義（依經典教科書 Horowitz / Knuth 規範）：

   • 費氏數列定義為：$F_0 = 0, F_1 = 1, F_2 = 1, F_3 = 2, F_4 = 3, F_5 = 5, F_6 = 8, F_7 = 13, F_8 = 21, \dots$
   • 尋找最小的費氏數 $F_m$，使得 $F_m - 1 \ge n$。
     本題 $n = 16$，而 $F_7 - 1 = 13 - 1 = 12 < 16$，$F_8 - 1 = 21 - 1 = 20 \ge 16$，故選取 $m = 8$（$F_m = 21, F_{m-1} = 13, F_{m-2} = 8$）。
   • 令目前檢驗位置為： $$i = left + F_{m-2} - 1$$ 若使用累積偏移量偏移記法（Horowitz 標準演算法），設基準偏移量 $offset = 0$（即有效區間左界前一位），索引設為 $i = \min(offset + F_{m-2}, n)$：
     • 若 $K < A[i]$：往左區間搜尋，費氏指標降 1 級（$m \leftarrow m - 1$），即新區間長度由 $F_{m-1}$ 主導，下一步檢驗位移量改用 $F_{m-3}$。
     • 若 $K > A[i]$：往右區間搜尋，費氏指標降 2 級（$m \leftarrow m - 2$），基準偏移量更新為 $offset \leftarrow i$。
     • 若 $K = A[i]$：搜尋成功，結束。

---

解題方法與詳細步驟

題目給定鍵值集合為有序數列 $A[1 \dots 16] = [1, 2, 3, \dots, 16]$，因此陣列索引與鍵值恰好相同，即 $A[x] = x$。

(A)～(C) 二元搜尋（Binary Search）

初始狀態：$left = 1, right = 16$。

• (A) 搜尋 $K = 2$：

  1. 第 1 次比較： $$mid = \left\lfloor \frac{1 + 16}{2} \right\rfloor = 8$$ 比較 $K$ 與 $A[8] = 8$。因 $2 < 8$，更新 $right = 8 - 1 = 7$。
  2. 第 2 次比較： $$mid = \left\lfloor \frac{1 + 7}{2} \right\rfloor = 4$$ 比較 $K$ 與 $A[4] = 4$。因 $2 < 4$，更新 $right = 4 - 1 = 3$。
  3. 第 3 次比較： $$mid = \left\lfloor \frac{1 + 3}{2} \right\rfloor = 2$$ 比較 $K$ 與 $A[2] = 2$。因 $2 = 2$，搜尋成功，停止。
  • 總比較次數：3 次。

• (B) 搜尋 $K = 10$：

  1. 第 1 次比較： $$mid = \left\lfloor \frac{1 + 16}{2} \right\rfloor = 8$$ 比較 $K$ 與 $A[8] = 8$。因 $10 > 8$，更新 $left = 8 + 1 = 9$。
  2. 第 2 次比較： $$mid = \left\lfloor \frac{9 + 16}{2} \right\rfloor = 12$$ 比較 $K$ 與 $A[12] = 12$。因 $10 < 12$，更新 $right = 12 - 1 = 11$。
  3. 第 3 次比較： $$mid = \left\lfloor \frac{9 + 11}{2} \right\rfloor = 10$$ 比較 $K$ 與 $A[10] = 10$。因 $10 = 10$，搜尋成功，停止。
  • 總比較次數：3 次。

• (C) 搜尋 $K = 15$：

  1. 第 1 次比較： $$mid = \left\lfloor \frac{1 + 16}{2} \right\rfloor = 8$$ 比較 $K$ 與 $A[8] = 8$。因 $15 > 8$，更新 $left = 8 + 1 = 9$。
  2. 第 2 次比較： $$mid = \left\lfloor \frac{9 + 16}{2} \right\rfloor = 12$$ 比較 $K$ 與 $A[12] = 12$。因 $15 > 12$，更新 $left = 12 + 1 = 13$。
  3. 第 3 次比較： $$mid = \left\lfloor \frac{13 + 16}{2} \right\rfloor = 14$$ 比較 $K$ 與 $A[14] = 14$。因 $15 > 14$，更新 $left = 14 + 1 = 15$。
  4. 第 4 次比較： $$mid = \left\lfloor \frac{15 + 16}{2} \right\rfloor = 15$$ 比較 $K$ 與 $A[15] = 15$。因 $15 = 15$，搜尋成功，停止。
  • 總比較次數：4 次。

---

(D)～(F) 費氏搜尋（Fibonacci Search）

設定費氏數列：$F = [0, 1, 1, 2, 3, 5, 8, 13, 21]$，索引分別對應 $F_0 \sim F_8$。
陣列長度 $n = 16$，最小滿足以 $F_m - 1 \ge 16$ 之費氏數為 $F_8 = 21$（$21 - 1 = 20 \ge 16$），故起始設定：
$offset = 0$，$m = 8$，三個費氏數變數為 $(F_m, F_{m-1}, F_{m-2}) = (21, 13, 8)$。

• (D) 搜尋 $K = 2$：
  1. 第 1 次比較： $$i = \min(offset + F_{m-2}, n) = \min(0 + 8, 16) = 8$$ 比較 $K$ 與 $A[8] = 8$。因 $2 < 8$，往左走：
     更新 $m \leftarrow m - 1 = 7$，費氏數降為 $(F_7, F_6, F_5) = (13, 8, 5)$，$offset$ 保持 0。
  2. 第 2 次比較： $$i = \min(offset + F_{m-2}, n) = \min(0 + 5, 16) = 5$$ 比較 $K$ 與 $A[5] = 5$。因 $2 < 5$，往左走：
     更新 $m \leftarrow m - 1 = 6$，費氏數降為 $(F_6, F_5, F_4) = (8, 5, 3)$，$offset$ 保持 0。
  3. 第 3 次比較： $$i = \min(offset + F_{m-2}, n) = \min(0 + 3, 16) = 3$$ 比較 $K$ 與 $A[3] = 3$。因 $2 < 3$，往左走：
     更新 $m \leftarrow m - 1 = 5$，費氏數降為 $(F_5, F_4, F_3) = (5, 3, 2)$，$offset$ 保持 0。
  4. 第 4 次比較：