115年 - 115 關務特種考試_三等_資訊處理（選試英文）：資料結構#138980

(一)（5 分）

(二)（5 分）

(三)若甲、乙二種不同演算法可解決同一問題，甲的時間複雜度為 O(n log n)， 乙的時間複雜度為 O(n²)。將此二演算法以程式語言實作，請列舉一類型測試資料，並說明其會使甲演算法程式實際執行時間不一定比乙演算 法程式實際執行時間快。（10 分）

二、何謂 Complete Binary Tree？假設單一節點的樹其樹高為 1，證明若 Complete Binary Tree 含 n 個節點且樹高為 h，則 2^h-1≤ n ≤2^h-1。（20 分）

(一)請以下圖的 Graph 為例，分別繪出示意圖，說明程式如何以 adjacency matrix 和 adjacency multilist 二種不同資料結構儲存此 Graph。（6 分）

(二)若 Graph 有 n 個節點與 e 個邊，請分別說明並以 Big O 寫出 adjacency matrix 和 adjacency multilist 二種不同資料結構儲存 Graph 時，計算 Graph 中所有節點 Degree 演算法的時間複雜度。（10 分）

(三)若 Graph 有 n 個節點與 e 個邊，請分別以 Big O 寫出以 adjacency matrix 和 adjacency multilist 二種不同資料結構儲存 Graph 空間複雜度。比較 且說明兩者在空間複雜度的優劣。（14 分）

(一)從空集合開始，依下列數字串 1, 2, 3, 4, 5, 6, 7, 8 順序插入節點建立並繪 出 Binary Search Tree。（5 分）

(二)從空集合開始，依下列數字串 1, 2, 3, 4, 5, 6, 7, 8 順序插入節點建立並繪 出 Red Black Tree。（紅色節點請以雙線同心圓表示，例如將紅色節點 5 表示成 ；黑色節點請以單線圓表示，例如將黑色節點 8 表示成 ） 。 （13 分）

(三)請分別說明 Binary Search Tree 與 Red Black Tree 在插入、刪除與搜尋數 字等三操作的時間複雜度。（12 分）