113 年 國立嘉義大學資訊工程學系碩士班《資料結構》

核心觀念

本題考查遞迴函數的定義與巢狀遞迴的計算。計算時須依序遵守：

• $x=0$ 時，直接使用 $A(0,y)=y+1$。
• $x>0,\ y=0$ 時，使用 $A(x,0)=A(x-1,1)$。
• $x>0,\ y>0$ 時，先計算內層的 $A(x,y-1)$，再代入外層函數。

(a) 計算 $A(1,1)$

因為 $1>0$ 且 $1>0$，使用第三個定義：

$$A(1,1)=A(0,A(1,0))$$

先計算內層的 $A(1,0)$。因為 $1>0$ 且 $y=0$：

$$A(1,0)=A(0,1)$$

再依據 $x=0$ 的定義：

$$A(0,1)=1+1=2$$

因此：

$$A(1,1)=A(0,2)=2+1=3$$

(b) 計算 $A(2,2)$

先整理 $A(1,y)$ 的計算規律：

$$A(1,0)=A(0,1)=2$$

當 $y>0$ 時：

$$A(1,y)=A(0,A(1,y-1))$$

由於 $A(0,z)=z+1$，可得：

$$A(1,y)=A(1,y-1)+1$$

所以：

核心觀念

本題採用資料結構常見定義：

• 二元樹的高度（height）：根節點到最深葉節點之間的最大邊數。
• 高度為 $h$ 的二元樹，第 $i$ 層最多有 $2^i$ 個節點。
• 因此高度為 $h$ 時，最多包含

$$1+2+2^2+\cdots+2^h=2^{h+1}-1$$

個節點。

---

(a) $m$ 個節點的二元樹之最小高度

解題方法

要使高度最小，應使每一層盡量填滿，也就是形成「完全二元樹」或接近完美二元樹的結構。

若高度為 $h$，最多只能容納 $2^{h+1}-1$ 個節點，因此必須滿足

$$m\leq 2^{h+1}-1$$

移項得

$$m+1\leq 2^{h+1}$$

取 $\log_2$：

$$\log_2(m+1)\leq h+1$$

所以

$$h\geq \log_2(m+1)-1$$

由於高度必須是整數，最小高度為

$$h_{\min}=\left\lceil \log_2(m+1)\right\rceil-1$$

此式也可寫成

$$\boxed{h_{\min}=\lfloor \log_2 m\rfloor}$$

為何一定可以達成？

令

$$k=\lfloor \log_2 m\rfloor$$

則

$$2^k\leq m<2^{k+1}$$

將 $m$ 個節點依序由上而下、由左而右排列成完全二元樹，最後一個節點必位於第 $k$ 層，因此其高度為 $k$。所以上述下界確實可以達成。

---

(b) $m$ 個節點的二元樹之最大高度

解題方法

題意釐清

題目中的「10-entry」與 $h(i)=(3i+4)\bmod 12$ 存在規格不一致：10 格表的索引為 $0$～$9$，而模 12 的結果可為 $0$～$11$。本題各鍵的初始雜湊值皆落在 $0$～$9$，以下採用「表格容量為 10 格，碰撞後以 10 格循環進行線性探測」的解讀。

核心觀念

雜湊函數將鍵值映射至初始位置：

$$h(k)=(3k+4)\bmod 12$$

採用線性探測（linear probing）處理碰撞時，若初始位置已被占用，便依序檢查下一格：

$$(h(k)+r)\bmod 10,\qquad r=0,1,2,\ldots$$

直到找到空格為止。插入順序會影響最後的表格配置，因此必須按照題目給出的順序插入。

解題方法

1. 計算各鍵的初始雜湊位置

鍵值 $k$	$3k+4$	初始位置 $h(k)$
13	$43$	$43\bmod12=7$
44	$136$	$136\bmod12=4$
17	$55$	$55\bmod12=7$
88	$268$	$268\bmod12=4$
23	$73$	$73\bmod12=1$
95	$289$	$289\bmod12=1$
20	$64$	$64\bmod12=4$
16	$52$	$52\bmod12=4$
8	$28$	$28\bmod12=4$
67	$205$	$205\bmod12=1$

2. 依序以線性探測插入

插入鍵值	探測位置	最終放置位置
13	$7$	$7$
44	$4$	$4$

核心觀念

本題考查 LSD Radix Sort（最低有效位數基數排序）。

因為所有數字都在 $[0,999]$，每個數字可補成固定的三位數：

$269,\ 184,\ 057,\ 587,\ 004,\ 053,\ 508,\ 263,\ 309,\ 482$

採用十進位基數 $b=10$，依序按照：

1. 個位數
2. 十位數
3. 百位數

進行三次穩定排序。穩定排序表示：當目前位數相同時，保留前一輪的相對順序。

---

(a) Radix Sort 排序過程

第一次：依個位數排序

將數字依個位數放入桶中：

$$\begin{array}{c|l} \text{個位數} & \text{桶內資料}\\ \hline 0 & \varnothing\\ 1 & \varnothing\\ 2 & 482\\ 3 & 053,\ 263\\ 4 & 184,\ 004\\ 5 & \varnothing\\ 6 & \varnothing\\ 7 & 057,\ 587\\ 8 & 508\\ 9 & 269,\ 309 \end{array}$$

由第 $0$ 桶至第 $9$ 桶依序取出：

$482,\ 053,\ 263,\ 184,\ 004,\ 057,\ 587,\ 508,\ 269,\ 309$

---

第二次：依十位數排序

以上一輪結果為輸入，依十位數分桶：

$$\begin{array}{c|l} \text{十位數} & \text{桶內資料}\\ \hline 0 & 004,\ 508,\ 309\\ 1 & \varnothing\\ 2 & \varnothing\\ 3 & \varnothing\\ 4 & \varnothing\\ 5 & 053,\ 057\\ 6 & 263,\ 269\\ 7 & \varnothing\\ 8 & 482,\ 184,\ 587\\ 9 & \varnothing \end{array}$$

依桶號取出：

$004,\ 508,\ 309,\ 053,\ 057,\ 263,\ 269,\ 482,\ 184,\ 587$

例如 $004$、$508$、$309$ 的十位數都為 $0$，其順序必須保留為 $004,508,309$，這正是穩定排序的作用。

---

第三次：依百位數排序

依百位數分桶：

$$\begin{array}{c|l} \text{百位數} & \text{桶內資料}\\ \hline 0 & 004,\ 053,\ 057\\ 1 & 184\\ 2 & 263,\ 269\\ 3 & 309\\ 4 & 482\\ 5 & 508,\ 587\\ 6 & \varnothing\\ 7 & \varnothing\\ 8 & \varnothing\\ 9 & \varnothing \end{array}$$

依桶號取出後得到：

$004,\ 053,\ 057,\ 184,\ 263,\ 269,\ 309,\ 482,\ 508,\ 587$

去除前導零，最後排序結果為：

$\boxed{4,\ 53,\ 57,\ 184,\ 263,\ 269,\ 309,\ 482,\ 508,\ 587}$

---

(b) 時間複雜度與 Quick Sort 的比較

Radix Sort 的時間複雜度

設：

• $n$：資料筆數
• $d$：每個鍵值的位數
• $b$：基數，例如十進位的 $b=10$

每一位通常使用 Counting Sort 或桶排序處理：

核心觀念

中序（Infix）轉後序（Postfix）利用堆疊（Stack）暫存運算子，遵循以下優先權與結合律規則：

1. 運算元（Operand）：直接輸出。
2. 運算子（Operator）：若堆疊頂端運算子之優先權 $\ge$ 讀入運算子，則將堆疊頂端運算子彈出（Pop）至輸出，直到堆疊頂端優先權小於讀入運算子（或遇到左括號 (），再將讀入運算子推入（Push）。
3. 左括號 (：直接 Push 進入堆疊（進入堆疊後視為最低優先權）。
4. 右括號 )：持續 Pop 堆疊內容至輸出，直到遇到 ( 為止（( 與 ) 均丟棄）。
5. 運算子優先權：* $=$ / $>$ + $=$ -（同優先權採左結合，左側先 Pop 輸出）。

---

堆疊追蹤與轉換步驟

讀入字元	堆疊內容（底 $\to$ 頂）	輸出結果（Postfix）
(	(
A	(	A
/	( /	A
B	( /	A B
*	( *	A B /
C	( *	A B / C
+	( +	A B / C *

核心觀念

無向圖為二分圖，等價於頂點可分成兩組，使每條邊的兩端分屬不同組；也等價於圖中沒有奇數長度環。

對鄰接矩陣 $A$，$(A^k)_{ij}$ 計算從頂點 $i$ 到頂點 $j$、長度為 $k$ 的走法數。矩陣乘方允許走法重複經過頂點或邊。

(a) 判斷是否為二分圖

依圖可將頂點分成：

$$\{a,b,e\}\qquad\text{與}\qquad\{c,d,f,g\}$$

圖中的每條邊都連接這兩組，例如 $a$ 分別連到 $c,d,f,g$，$b$ 連到 $d,f,g$，而 $e$ 連到 $d,f,g$；沒有邊的兩端同屬一組。因此此圖是二分圖。

(b) 計算長度為 4 的走法數

以題目標示的頂點順序 $(a,b,c,d,e)$，從 $d$ 出發逐步計數：