115年 - 115 高等考試_三級_資訊處理：資料結構#141774

(一)給定一個空的雜湊表，依序插入下列鍵值 22、1、13、24、35、46、7、 18，請畫出所有鍵值插入完成後的雜湊表狀態，並列出插入鍵值 46 時 的完整探查過程。(10 分)

(二)承上題，依序刪除鍵值 24、13，畫出刪除後的雜湊表狀態。並說明為 什麼刪除鍵值時需用 DELETED 標記，而不能將該鍵值所在的儲存格恢復成「從未存放過鍵值」的空狀態。(5 分)

(一)以下列無向圖為例，令起點 s 為 A，終點 t 為 F，依照修改後的演算 法，逐步列出每次選定一個頂點後陣列 d 的變化過程。陣列中的頂點 順序請依字母順序排列。(15 分)

(二)說明修改後演算法之正確性，是基於 d [v] 更新規則具有何種性質。 (5 分)

(三)假設圖以相鄰串列(adjacency list)表示。若要在尚未選定的頂點中找 出 d 值最小者，可使用以下兩種方法：

方法一：每次以線性方式掃描所有尚未選定的頂點找出最小 d 值。 

方法二：使用最小堆積(min-heap)維護目前 d 值最小的頂點。

分別就這兩種方法，分析修改後演算法最壞情況的時間複雜度。 (5 分)

(一)完成下列程式碼的空格。 (20 分)

(二)下圖為一棵包含 5 個節點且滿足 AVL 平衡特性的二元搜尋樹，圖中 顯示每個節點的鍵值。若將鍵值為 70 的新節點插入此樹，為保持 AVL 樹的平衡，會觸發旋轉。請畫出旋轉後的樹狀結構圖。除新插入的節 點 70 外，若原有節點的 size 欄位值在旋轉後發生改變，請在旋轉後 的圖中，於該節點旁標示其新的 size 欄位值。(5 分)

(一)當執行 foo(10)時，一共會呼叫 foo()函式幾次(包含最外層 foo(10)的這一次呼叫)？(10 分)

(二)執行 foo(10)的最終回傳結果為何？(10 分)

(三)以 Big-O 表示 foo(n)的時間複雜度(time complexity)。本題若同一個 「函式與參數」組合被呼叫多次，每次都重新計算，不會儲存先前的計算結果供之後使用。(5 分)