申論 1某系統A 使用雜湊表（hash table）儲存不同的正整數鍵值，亦即不允許重複鍵值，雜湊表有11 個儲存格，索引從0 開始，雜湊函數（hash function）為hA( k)k mod11，其用平方探查法（quadraticprobing）處理碰撞（collision）問題，探查序列為hA( k)(hA( k)i2)mod11(i0,1,2,...)，刪除資料時，i被刪除資料的位置標記為特殊符號DELETED。請回答下列問題：㈠給定一個空的雜湊表，依序插入下列鍵值22、1、13、24、35、46、7、18，請畫出所有鍵值插入完成後的雜湊表狀態，並列出插入鍵值46 時的完整探查過程。（10 分）㈡承上題，依序刪除鍵值24、13，畫出刪除後的雜湊表狀態。並說明為什麼刪除鍵值時需用DELETED 標記，而不能將該鍵值所在的儲存格恢復成「從未存放過鍵值」的空狀態。（5 分）㈢承上題，執行插入鍵值12，請列出插入時的探查過程、操作停止的理由，並寫出12 最後插入那一個儲存格。插入時，DELETED 標記視為可放入新鍵值的儲存格。請注意鍵值不能重覆。（5 分）㈣相較於系統A，考慮另一個採用平方探查法之系統，系統B 的表格大小為8，索引亦從0 開始，雜湊函數hB( k )及探查序列hB( k )分別定義為ihB( k)k mod8、hB( k)(hB( k)i2i2)mod8 (i0,1,2,...)。在非均i勻雜湊（non-uniform hashing）的情況下，也就是許多鍵值可能被分配到相同或少數幾個初始雜湊位置時，那一個系統的雜湊表儲存格利用率可能較高？並說明理由。（5 分）
本卷皆為申論題，點「看答案與解析」查看擬答。
弱點分析
未作答的題目不計分。看我的紀錄
申論 2給定一個無向圖G(V, E)，每個頂點代表一個地點，每條邊e (eE)代表一條道路，邊的正整數權重( e)表示該道路的塞車程度，數值越大越壅塞。對於一條從起點s 到終點t ( s ,t V)的路徑P，其最大塞車程度C(P)定義為路徑上所有邊權重的最大值：C(P)max(e )e P本題透過修改Dijkstra 最短路徑演算法中陣列d 的定義與更新方式，求出從s 到t 可行路徑所能達到的「最大塞車程度的最小值」。修改後的演算法流程與Dijkstra 最短路徑演算法相同，差異僅在於d [v ](vV)的定義與更新規則，其中，新的d [ v ]表示目前已知從s 到v 的路徑中，最大邊權重的最小值。初始時令d [ s ]0，其他頂點v 的d [v](vs)。之後依照Dijkstra演算法，每一輪選出尚未被選定且d 值最小的頂點u，並將原本的更新方式d [ v]min(d [ v],d [u](u , v))改為d [ v]min(d [ v], max(d [u ],(u , v)))，其中(u , v)為邊(u ,v) (u ,vV)的權重。重複進行，直到終點t 被選定為止。㈠以下列無向圖為例，令起點s 為A，終點t 為F，依照修改後的演算法，逐步列出每次選定一個頂點後陣列d 的變化過程。陣列中的頂點順序請依字母順序排列。（15 分）㈡說明修改後演算法之正確性，是基於d [ v ]更新規則具有何種性質。（5 分）㈢假設圖以相鄰串列（adjacency list）表示。若要在尚未選定的頂點中找出d 值最小者，可使用以下兩種方法：方法一：每次以線性方式掃描所有尚未選定的頂點找出最小d 值。方法二：使用最小堆積（min-heap）維護目前d 值最小的頂點。分別就這兩種方法，分析修改後演算法最壞情況的時間複雜度。（5 分）
申論 3給定一棵二元搜尋樹（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 分）
申論 4考慮以下兩個互相呼叫（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 分）