某系統A 使用雜湊表（hash table）儲存不同的正整數鍵值，亦即不允許重
複鍵值，雜湊表有11 個儲存格，索引從0 開始，雜湊函數（hash function）
為
( )
A
h
k
k mod
，其用平方探查法（quadraticprobing）處理碰撞（collision）
問題，探查序列為
( )
(
( )
)
11(
0,1,2,...)
A
A
ih
k
h
k
i
mod
i
，刪除資料時，
被刪除資料的位置標記為特殊符號DELETED。請回答下列問題：
給定一個空的雜湊表，依序插入下列鍵值22、1、13、24、35、46、7、
18，請畫出所有鍵值插入完成後的雜湊表狀態，並列出插入鍵值46 時
的完整探查過程。（10 分）
承上題，依序刪除鍵值24、13，畫出刪除後的雜湊表狀態。並說明為
什麼刪除鍵值時需用DELETED 標記，而不能將該鍵值所在的儲存格
恢復成「從未存放過鍵值」的空狀態。（5 分）
承上題，執行插入鍵值12，請列出插入時的探查過程、操作停止的理
由，並寫出12 最後插入那一個儲存格。插入時，DELETED 標記視為
可放入新鍵值的儲存格。請注意鍵值不能重覆。（5 分）
相較於系統A，考慮另一個採用平方探查法之系統，系統B 的表格大小
為8，索引亦從0 開始，雜湊函數
( )
B
h
k 及探查序列
( )
B
ih
k 分別定義為
( )
B
h
k
k mod
、
( )
(
( )
)
8 (
0,1,2,...)
B
B
ih
k
h
k
i
i
mod
i
。在非均
勻雜湊（non-uniform hashing）的情況下，也就是許多鍵值可能被分配
到相同或少數幾個初始雜湊位置時，那一個系統的雜湊表儲存格利用
率可能較高？並說明理由。（5 分）
參考解答（AI 生成，非官方）
- 一、插入完成後的雜湊表（hash table）狀態：依序插入22、1、13、24、35、46、7、18後，索引0至10的內容為：0:22、1:1、2:13、3:24、4:空、5:18、6:35、7:46、8:7、9:空、10:空。其中24、35、46、18均曾與其他鍵值碰撞，經平方探查法（quadratic probing）後才找到空位。
- 二、插入46的完整探查：h_A(46)=46 mod 11=2。i=0檢查索引2，已有13；i=1檢查2+1=3，已有24；i=2檢查2+4=6，已有35；i=3檢查2+9=11≡0，已有22；i=4檢查2+16=18≡7，索引7為空，故將46放入索引7。探查偏移依序為0、1、4、9、16。
- 三、刪除24與13後：將索引3的24及索引2的13標記為DELETED（刪除標記），表狀態為0:22、1:1、2:DELETED、3:DELETED、4:空、5:18、6:35、7:46、8:7、9:空、10:空。搜尋時DELETED仍須視為曾被占用，不可直接當成空白而跳過。
- 四、必須使用DELETED的理由：平方探查的搜尋會沿著固定探查序列前進；若把刪除格直接改回空白，後續鍵值（例如與13同為初始位置2的35、46）之搜尋可能在空白處提前停止，造成明明存在卻找不到的假陰性（false negative）。DELETED可保留探查鏈，插入時又可重複使用。
- 五、插入12的過程：h_A(12)=12 mod 11=1。i=0檢查索引1，已有1；i=1檢查1+1=2，該格為DELETED且表中無12，故將12放入索引2並停止。停止理由是遇到可重用的DELETED格，且已確認鍵值不重複；12最後插入索引2。
- 六、系統B的利用率比較：系統A較高。系統B大小為8，i^2 mod 8只會循環出現0、1、4，故同一初始位置的鍵值最多只能探查3個儲存格，非均勻雜湊（non-uniform hashing）時容易提前失敗；系統A大小11為質數，i=0至5的平方餘數共6個相異位置0、1、3、4、5、9，且表較大，非均勻時可容納更多同義字，利用率較高。
給定一個無向圖G
(V, E)
，每個頂點代表一個地點，每條邊(
E)
e e
代
表一條道路，邊的正整數權重( )e
表示該道路的塞車程度，數值越大越
壅塞。對於一條從起點s 到終點( ,
V)
t s t
的路徑P，其最大塞車程度C(P)
定義為路徑上所有邊權重的最大值：
C(P)
max
( )
e P
e
本題透過修改Dijkstra 最短路徑演算法中陣列d 的定義與更新方式，求出
從s 到t 可行路徑所能達到的「最大塞車程度的最小值」。修改後的演算法
流程與Dijkstra 最短路徑演算法相同，差異僅在於
(
)
[ ]
V
d v v
的定義與更新
規則，其中，新的[ ]
d v 表示目前已知從s 到v 的路徑中，最大邊權重的最
小值。初始時令[ ]
d s ，其他頂點v 的
)
[
(
]
d v
v
s
。之後依照Dijkstra
演算法，每一輪選出尚未被選定且d 值最小的頂點u，並將原本的更新方
式[ ]
min
[ ],
)
]
(
[
( , )
d v
d v
d u
u v
改為[ ]
min
[ ], ma
)
x
[ ]
, )
(
(
(
)
,
d v
d v
d u
u v
，
其中( , )
u v
為邊(
) (
)
,
,
V
u v
u v
的權重。重複進行，直到終點t 被選定為止。
以下列無向圖為例，令起點s 為A，終點t 為F，依照修改後的演算
法，逐步列出每次選定一個頂點後陣列d 的變化過程。陣列中的頂點
順序請依字母順序排列。（15 分）
說明修改後演算法之正確性，是基於[ ]
d v 更新規則具有何種性質。（5 分）
假設圖以相鄰串列（adjacency list）表示。若要在尚未選定的頂點中找
出d 值最小者，可使用以下兩種方法：
方法一：每次以線性方式掃描所有尚未選定的頂點找出最小d 值。
方法二：使用最小堆積（min-heap）維護目前d 值最小的頂點。
分別就這兩種方法，分析修改後演算法最壞情況的時間複雜度。（5 分）
參考解答（AI 生成，非官方）
- 一、題目資料缺漏之處理：本題圖形的邊集合及各邊權重未隨題文提供，僅知頂點A至F、起點A、終點F，因此無法唯一決定每輪選定的頂點與d值序列；題目資料缺漏，無法得出唯一數值。以下列出可直接套用的公式、表格格式與判定規則，補上原圖後即可逐輪填入。
- 二、初始化與更新公式：令d[A]=0，其餘d[v]=∞。每輪從尚未選定頂點中選d最小者u，對每個相鄰v執行d[v]=min(d[v], max(d[u], w(u,v)))。若t被選定即停止。表格可設欄位：輪次、選定u、d[A]、d[B]、d[C]、d[D]、d[E]、d[F]、本輪鬆弛的邊；d值依A至F字母順序排列。
- 三、逐步記錄要領：第一輪必選A，將A的鄰邊鬆弛；第二輪選當時d最小者，依此類推。每次只更新「經由u」可使瓶頸下降的鄰點；若max(d[u],w)不小於原d[v]則保留。沿路徑延伸時瓶頸值不減，且已選定頂點的d值依序單調不減，最後d[F]即為最大塞車程度的最小值。
- 四、正確性基礎：此演算法屬於瓶頸路徑（bottleneck path）的Dijkstra變形。其更新運算具有單調性與最優子結構（optimal substructure）：任何從s到v的路徑，其瓶頸值等於前一條到u的瓶頸值與邊(u,v)權重的較大者；延伸路徑只會使瓶頸值不減。因此每次選出最小d者時，不可能再經由其他未選點得到更小瓶頸，具備貪心選擇與切割性質（cut property）。
- 五、複雜度：方法一每輪線性掃描未選點，選點共O(V^2)，加上相鄰串列（adjacency list）鬆弛O(E)，總時間O(V^2+E)=O(V^2)。方法二以二元最小堆積（min-heap）維護，每次取出與插入O(log V)，每條邊最多觸發一次鬆弛，總O((V+E)log V)；若用減少鍵值（decrease-key）可達O(E+V log V)。
給定一棵二元搜尋樹（binary search tree），且該樹同時也是一棵AVL 樹。
樹的節點在C 語言中宣告如下：
typedef struct Node {
int key;
// 節點的鍵值，所有節點的鍵值皆互不相同
int size;
// 以該節點為根的子樹節點總數(包含自己)
struct Node *left;
// 指向左子節點
struct Node *right;
// 指向右子節點
} Node;
並定義以下函式：
int size (Node *node)：
若傳入的node 為NULL，則回傳0；否則回傳node -> size。
int count_less_equal (Node *node, int val)：
回傳以node 為根的子樹中，所有鍵值小於等於val 的節點總數。
Node* select (Node *node, int r)：
回傳以node 為根的子樹中，第r 小的節點指標，r 從1 開始算。
Node* greater_k_smallest (Node *root, int val, int k)：
找出以root 為根的整棵樹中，所有鍵值大於val 的節點裡，第k 小的
節點，k 從1 開始算。若第k 小的節點不存在，則回傳NULL。
完成下列程式碼的空格。（20 分）
int count_less_equal(Node *node, int val) {
if (node == NULL) return 0;
if (node->key > val)
return count_less_equal(node->left, val);
else return size(node->left)+
(1)
;
}
Node* select(Node *node, int r) {
int left_size = size(node->left);
if (r ==
(2)
) return node;
else if (r <= left_size)
return select(node->left, r);
else return
(3)
;
}
Node* greater_k_smallest(Node *root, int val, int k){
int x = count_less_equal(root, val);
int y =
(4)
;
if (y > size(root)) return NULL;
return select(root, y);
}
下圖為一棵包含5 個節點且滿足AVL 平衡特性的二元搜尋樹，圖中
顯示每個節點的鍵值。若將鍵值為70 的新節點插入此樹，為保持AVL
樹的平衡，會觸發旋轉。請畫出旋轉後的樹狀結構圖。除新插入的節
點70 外，若原有節點的size 欄位值在旋轉後發生改變，請在旋轉後
的圖中，於該節點旁標示其新的size 欄位值。（5 分）
參考解答（AI 生成，非官方）
- 一、空格答案：（1）1 + count_less_equal(node->right, val)；（2）left_size + 1；（3）select(node->right, r - left_size - 1)；（4）x + k。以上四式即為count_less_equal、select與greater_k_smallest的核心邏輯。
- 二、函式意義與邊界：count_less_equal回傳鍵值小於等於val的節點數；select利用左子樹大小判斷第r小在左子樹、根或右子樹；greater_k_smallest先算小於等於val的數量x，則第k個大於val者之全域排名為x+k，若超過size(root)即不存在，回傳NULL。
- 三、AVL旋轉的判定與限制：題目所述5節點AVL樹之鍵值與連結圖未顯示，無法唯一判定70插入位置、旋轉型態及各節點新size；題目資料缺漏，無法得出唯一樹形。若補上原圖，應先找出插入路徑上最低的不平衡節點，再依其與插入位置的關係判定LL、RR、LR或RL型。
- 四、四種旋轉與繪圖：LL型對最低不平衡節點右旋；RR型左旋；LR型先對左子節點左旋再對根右旋；RL型先對右子節點右旋再對根左旋。繪圖時先標新根，再畫左右子樹，保持二元搜尋樹（binary search tree, BST）中序遞增；新節點70以圓圈標示，並在size變動節點旁寫出新值。
- 五、size更新：旋轉後由下往上計算size(x)=size(x->left)+size(x->right)+1。僅受旋轉影響的子樹根（含新根及其子節點）需要更新，未參與旋轉的子樹size不變；若某節點新size與原值相同則不必特別標示。考場上應先完成旋轉圖，再逐點標size，以免漏算。
考慮以下兩個互相呼叫（mutually recursive）的C 語言函式：
int foo(int n) {
if (n <= 1) return 1;
return foo(n - 1) + bar(n - 1) + 2;
}
int bar(int n) {
if (n <= 1) return 1;
return foo(n - 1) + bar(n - 1);
}
請回答下列問題：（每一小題請寫出推導過程，無推導過程不予計分。）
當執行foo(10)時，一共會呼叫foo()函式幾次（包含最外層foo(10)的
這一次呼叫）？（10 分）
執行foo(10)的最終回傳結果為何？（10 分）
以Big-O 表示foo(n)的時間複雜度（time complexity）。本題若同一個
「函式與參數」組合被呼叫多次，每次都重新計算，不會儲存先前的
計算結果供之後使用。（5 分）
參考解答（AI 生成，非官方）
- 一、定義與基礎值：令F(n)、B(n)分別為foo(n)、bar(n)的回傳值。n≤1時F(n)=B(n)=1；因此F(1)=1、B(1)=1、F(2)=1+1+2=4、B(2)=1+1=2。此為後續推導的初始條件。
- 二、推導通式：n≥3時，B(n)=F(n-1)+B(n-1)，且F(n)=F(n-1)+B(n-1)+2=B(n)+2，故B(n)=F(n)-2。代回F(n)=F(n-1)+(F(n-1)-2)+2=2F(n-1)。由F(2)=4得F(n)=2^n（n≥2），所以F(10)=2^10=1024。
- 三、foo呼叫次數：令f(n)、b(n)分別為執行foo(n)、bar(n)時所呼叫foo的次數（含自身）。f(1)=1、b(1)=0；n≥2時f(n)=1+f(n-1)+b(n-1)，b(n)=f(n-1)+b(n-1)。兩式相減得f(n)=b(n)+1，再代入得b(n)=2b(n-1)+1，故b(n)=2^(n-1)-1、f(n)=2^(n-1)。因此f(10)=2^9=512次。
- 四、時間複雜度：在無記憶化（no memoization）下，每個foo或bar呼叫都會再產生兩個同階的子呼叫，遞迴式為T(n)=2T(n-1)+O(1)，展開得T(n)=O(2^n)，且為Θ(2^n)。本題實際呼叫次數呈指數成長，並非O(n)或O(n^2)；遞迴深度為O(n)，額外空間主要為呼叫堆疊O(n)。