112 年 國立中正大學資訊管理學系碩士班乙組《資料結構》

核心觀念

假設輸入規模小於某個固定常數時，$T(n)=\Theta(1)$。各遞迴式的緊確漸近界以 $\Theta$ 表示。

對標準形式

$$T(n)=aT\left(\frac{n}{b}\right)+f(n)$$

令臨界函數為

$$n^{\log_b a}.$$

比較 $f(n)$ 與此臨界函數即可使用主定理。當子問題比例不同，例如 $n/2$ 與 $n/4$，使用 Akra–Bazzi 定理：

$$T(n)=\Theta\left( n^p\left(1+\int_1^n\frac{g(u)}{u^{p+1}}\,du\right) \right),$$

其中 $p$ 滿足

$$\sum_i a_i b_i^p=1.$$

---

（1）$T(n)=2T\left(\frac n2\right)+n$

解題方法

這是標準主定理形式，其中

$$a=2,\qquad b=2,\qquad f(n)=n.$$

臨界函數為

$$n^{\log_2 2}=n.$$

因此遞迴額外成本 $f(n)=n$ 與臨界函數相同，屬於主定理第二種情況：

$$T(n)=\Theta(n\log n).$$

遞迴樹驗算

第 $k$ 層有 $2^k$ 個子問題，每個子問題規模為 $n/2^k，因此該層總成本為

$$2^k\cdot \frac{n}{2^k}=n.$$

遞迴深度為 $\Theta(\log n)$，所以總成本為

$$n\cdot \Theta(\log n)=\Theta(n\log n).$$

---

（2）$T(n)=T\left(\frac n2\right)+T\left(\frac n4\right)+n$

解題方法

兩個子問題的縮小比例不同，直接套用標準主定理不適合，使用 Akra–Bazzi 定理。

令 $p$ 滿足

$$\left(\frac12\right)^p+\left(\frac14\right)^p=1.$$

設 $x=2^{-p}$，則

$$x+x^2=1.$$

取正根：

$$x=\frac{\sqrt5-1}{2}.$$

因此

$$p=\log_2\frac{1+\sqrt5}{2}<1.$$

本題的非遞迴成本為 $g(n)=n$，所以

$$\begin{aligned} T(n) &=\Theta\left( n^p\left( 1+\int_1^n\frac{u}{u^{p+1}}\,du \right)\right)\\ &=\Theta\left( n^p\left( 1+\int_1^n u^{-p}\,du \right)\right). \end{aligned}$$

因為 $p<1$，

$$\int_1^n u^{-p}\,du=\Theta(n^{1-p}).$$

因此

$$T(n)=\Theta\left(n^p\cdot n^{1-p}\right)=\Theta(n).$$

遞迴樹直觀理解

規模為 $m$ 的節點會產生總規模

$$\frac m2+\frac m4=\frac{3m}{4}$$

的子問題，因此每層由非遞迴成本產生的總工作量至少按照幾何級數遞減：

$$n+\frac{3n}{4}+\left(\frac34\right)^2n+\cdots=\Theta(n).$$

根節點本身已經提供 $\Omega(n)$ 的成本，故總複雜度為

$$\boxed{\Theta(n)}.$$

---

（3）$T(n)=2T\left(\frac{3n}{4}\right)+n$

解題方法

將子問題寫成標準形式：

$$\frac{3n}{4}=\frac{n}{4/3}.$$

因此

$$a=2,\qquad b=\frac43,\qquad f(n)=n.$$

臨界函數為

$$n^{\log_{4/3}2}.$$

由於

$$\log_{4/3}2>1,$$

所以 $f(n)=n$ 比臨界函數低一個多項式階，符合主定理第一種情況：

$$T(n)=\Theta\left(n^{\log_{4/3}2}\right).$$

遞迴樹驗算

第 $k$ 層有 $2^k$ 個節點，每個節點的問題規模為

$$n\left(\frac34\right)^k.$$

因此第 $k

核心觀念

三維陣列 $A[3][5][7]$ 的索引範圍為：

• 第一維：$0 \leq i < 3$
• 第二维：$0 \leq j < 5$
• 第三維：$0 \leq k < 7$

每個整數占 $4$ bytes，因此只要先計算 $A[0][0][0]$ 到 $A[1][2][4]$ 之前共有多少個元素，再乘以 $4$，即可得到位元組位移量。

已知：

$$\operatorname{Addr}(A[0][0][0])=1000$$

---

列優先儲存（row-major order）

列優先是指最右側的索引變化最快，因此第三維索引 $k$ 先連續排列。

三維陣列的線性元素位移公式為：

$$\text{Offset} =i(d_2d_3)+j(d_3)+k$$

代入 $d_1=3$、$d_2=5$、$d_3=7$ 以及 $(i,j,k)=(1,2,4)$：

$$\text{Offset} =1(5\times 7)+2(7)+4$$ $$=35+14+4=53$$

表示 $A[1][2][4]$ 位於起始元素之後第 $53$ 個元素的位置。

換算成位元組位移：

$$53\times 4=212\text{ bytes}$$

因此其位址為：

$$1000+212=\boxed{1212}$$

(1) 中置式

$\frac{a+\displaystyle\frac{b}{c}-(d-e)}{f+g}$

(2) 計算過程

核心觀念

本題考查遞迴函式的「基本情況」與「遞迴情況」。

函式可表示為：

$$f(x)= \begin{cases} 0, & x=1\\ x\cdot f(x-1)+x^3, & x\ne 1 \end{cases}$$

計算時，必須先依序遞迴到 $f(1)$，再由最底層往上代回。基本情況 $f(1)=0$ 是遞迴停止的條件。

解題方法

先計算 $f(2)$：

$$\begin{aligned} f(2) &=2\cdot f(1)+2^3\\ &=2\cdot 0+8\\ &=8 \end{aligned}$$

接著計算 $f(3)$，因為 $f(4)$ 會用到 $f(3)$：

$$\begin{aligned} f(3) &=3\cdot f(2)+3^3\\ &=3\cdot 8+27\\ &=51 \end{aligned}$$

最後計算 $f(4)$：

核心觀念

最大堆（max-heap）必須同時滿足兩個條件：

1. 完全二元樹：除最後一層外，每一層都必須填滿；最後一層的節點必須由左至右連續排列。
2. 最大堆序：每個父節點的值都必須大於或等於其子節點的值。

因此，只符合父子節點的大小關係，還不足以構成最大堆。

解題方法

依原卷附圖，根節點為 $50$，只有左子節點 $20$，沒有右子節點；$20$ 的左、右子節點分別為 $8$ 與 $3$，全樹共有四個節點。

先檢查最大堆序，各父子關係為：

$$50 \ge 20,\qquad 20 \ge 8,\qquad 20 \ge 3.$$

核心觀念

本題考查二元樹的走訪順序與由走訪結果還原樹形。

• Inorder（中序）：左子樹 → 根節點 → 右子樹。
• Postorder（後序）：左子樹 → 右子樹 → 根節點。

因此，後序走訪的最後一個節點必定是整棵樹的根。取得根節點後，再利用中序序列將其左右子樹分開，遞迴處理即可。由於節點 $A$ 至 $F$ 均不重複，兩種走訪結果可以唯一決定樹形。

解題方法

已知：

• Inorder：BADECF
• Postorder：BDEFCA

1. 後序序列最後一個節點為 $A$，所以根節點是 $A$。

2. 在中序序列 BADECF 中找到 $A$：

   • $A$ 左側為 B，代表左子樹。
   • $A$ 右側為 DECF，代表右子樹。

   對應的後序序列依子樹節點數量切分：

   • 左子樹有 1 個節點，因此為 B。
   • 右子樹為 DEFC。

3. 還原左子樹：

   左子樹的中序與後序皆為 B，所以 $B$ 是 $A$ 的左子節點。

4. 還原右子樹：

   • 中序：DECF
   • 後序：DEFC

   後序最後一個節點為 $C$，因此 $C$ 是右子樹的根。

   在中序 DECF 中：

   • $C$ 左側為 DE，是 $C$ 的左子樹。
   • $C$ 右側為 F，是 $C$ 的右子樹。

5. 還原 $C$ 的左子樹：

   • 中序：DE
   • 後序：DE

核心觀念

有向圖若對任意兩個頂點 $u$、$v$，都存在從 $u$ 到 $v$ 的有向路徑，且也存在從 $v$ 到 $u$ 的有向路徑，便稱為強連通。判斷時須確認每個頂點都能沿箭頭到達其他所有頂點；只看圖形相連並不足夠。

解題方法與選項分析

逐一沿箭頭檢查頂點間是否能互相到達：

• （1）不是強連通圖。 圖中只有左側頂點指向右側頂點，右側頂點沒有路徑回到左側頂點，因此兩者不能互相到達。
• （2）不是強連通圖。 中間與右側頂點之間有往返路徑，但左側頂點只有通往中間頂點的箭頭，沒有任何路徑能回到左側頂點。

核心觀念

Floyd-Warshall 演算法以允許的中間頂點集合逐步擴大，計算任意兩頂點間的最短路徑。

題目定義 $d_{ij}^{(k)}$ 為從頂點 $i$ 到頂點 $j$ 的最短路徑權重，且所有中間頂點都必須屬於 $\{1,2,\ldots,k\}$。

當加入頂點 $k$ 作為新的候選中間頂點時，最短路徑只有兩種情形：

1. 路徑不經過頂點 $k$。
2. 路徑經過頂點 $k$，可拆成 $i\to k$ 與 $k\to j$ 兩段。

解題方法

若最短路徑不經過 $k$，其權重為：

$$d_{ij}^{(k-1)}$$

若最短路徑經過 $k$，則前半段 $i\to k$ 與後半段 $k\to j$ 的中間頂點只能來自 $\{1,\ldots,k-1\}$，因此總權重為：

$$d_{ik}^{(k-1)}+d_{kj}^{(k-1)}$$

取兩種情形中的較小值，得到 Floyd-Warshall 的更新公式：

$$\boxed{ d_{ij}^{(k)} = \min\left\{ d_{ij}^{(k-1)}, \ d_{ik}^{(k-1)}+d_{kj}^{(k-1)} \right\} }$$

初始條件為：

核心觀念

二分搜尋法適用於已排序的資料。每次取目前搜尋範圍的中間元素與目標值比較：

• 若目標值小於中間元素，搜尋左半部。
• 若目標值大於中間元素，搜尋右半部。
• 若相等，表示找到目標。

以位置 $1$ 到 $12$ 表示此串列，採用下中位數：

$$middle=\left\lfloor\frac{top+bottom}{2}\right\rfloor$$

解題方法

目標值為 $21$，串列如下：

$$1,\ 3,\ 5,\ 7,\ 9,\ 11,\ 13,\ 15,\ 17,\ 19,\ 21,\ 23$$

步驟	top（位置／元素）	bottom（位置／元素）	middle 計算	middle（位置／元素）	比較結果
1	$1/1$	$12/23$	$\lfloor(1+12)/2\rfloor=6$	$6/11$	$21>11$，往右半部搜尋
2	$7/13$	$12/23$	$\lfloor(7+12)/2\rfloor=9$	$9/17$	$21>17$，往右半部搜尋

核心觀念

Huffman coding 用來建立「總加權碼長最小」的最佳前綴碼（prefix code）。若符號 $x_i$ 的頻率為 $f_i$，其碼長為 $\ell_i$，則總成本為

$$C=\sum_i f_i\ell_i$$

Huffman 演算法的步驟是：

1. 每次選出頻率最小的兩個節點。
2. 將兩者合併成頻率總和的新節點。
3. 重複合併，直到形成完整二元樹。
4. 從根節點往葉節點標示 $0$、$1$，根到葉的路徑即為該符號的編碼。

Huffman 演算法可保證得到總加權碼長最小的前綴碼。

解題方法

原始頻率如下：

元素	頻率
$a$	15
$b$	20
$c$	25
$d$	10
$e$	30

依頻率由小到大合併：

1. 合併最小的 $d$ 與 $a$：

$$10+15=25$$

形成節點 $(da,25)$。

2. 合併 $b$ 與 $c$：

$$20+25=45$$

形成節點 $(bc,45)$。

3. 合併 $(da,25)$ 與 $e$：

$$25+30=55$$

形成節點 $(dae,55)$。

4. 合併最後兩個節點：

$$45+55=100$$

形成根節點。

指定左分支為 $0$、右分支為 $1$，可得：

插入順序 2、3、5、1、4、6、7、8，依序維持 AVL 性質：

1. 插入 2

   • 成為根節點，$BF=0$。

2. 插入 3

   • 2 的右子節點；$BF_{2}=-1$，仍平衡。

3. 插入 5

   • 2 → 3 → 5，形成 RR 不平衡於節點 2。
   • 左旋 於 2，得到

       3
      / \
     2   5
   

   • 所有節點 $BF$ 為 $0$。

4. 插入 1

   • 1 成為 2 的左子節點。
   • $BF_{2}=+1,\; BF_{3}=+1$，仍平衡。

5. 插入 4

   • 4 成為 5 的左子節點。
   • $BF_{5}=+1,\; BF_{3}=0$，仍平衡。

核心觀念

本題考查「矩陣鏈乘法的最佳括號化」與動態規劃。

矩陣乘法具有結合律，因此：

$$(M_1M_2)M_3=M_1(M_2M_3)$$

但不同括號化會造成不同的矩陣相乘成本。若將一個 $a\times b$ 矩陣與一個 $b\times c$ 矩陣相乘，需要進行：

$$abc$$

次純量乘法。

令矩陣尺寸向量為：

$$p_0=25,\quad p_1=30,\quad p_2=15,\quad p_3=40,\quad p_4=20$$

其中 $M_i$ 的尺寸為 $p_{i-1}\times p_i$。

定義 $m[i,j]$ 為計算 $M_iM_{i+1}\cdots M_j$ 所需的最少純量乘法次數，則：

$$m[i,j]=\min_{i\leq k<j} \left\{ m[i,k]+m[k+1,j]+p_{i-1}p_kp_j \right\}$$

其中 $k$ 表示最後一次切割的位置，且：

$$m[i,i]=0$$

---

解題方法：區間動態規劃

1. 計算兩個相鄰矩陣

$$m[1,2]=25\times30\times15=11250$$ $$m[2,3]=30\times15\times40=18000$$ $$m[3,4]=15\times40\times20=12000$$

---

2. 計算三個矩陣

計算 $M_1M_2M_3$

有兩種切法。

切在 $k=1$：

$$M_1(M_2M_3)$$

成本為：

$$0+18000+(25\times30\times40) =18000+30000 =48000$$

切在 $k=2$：

$$(M_1M_2)M_3$$

成本為：

$$11250+0+(25\times15\times40) =11250+15000 =26250$$

因此：

$$m[1,3]=26250$$

最佳括號化為：

$$(M_1M_2)M_3$$

---

計算 $M_2M_3M_4$

切在 $k=2$：

$$M_2(M_3M_4)$$

成本為：

$$0+12000+(30\times15\times20) =12000+9000 =21000$$

切在 $k=3$：

$$(M_2M_3)M_4$$

成本為：

$$18000+0+(30\times40\times20) =18000+24000 =42000$$

因此：

$$m[2,4]=21000$$

最佳括號化為：

$$M_2(M_3M_4)$$

---

3. 計算四個矩陣

考慮最後一次相乘的位置。

切在 $k=1$

括號化形式為：