close
107 高考三級資料結構
(一)請說明並比較二分搜尋（binary search）與一般二元搜尋樹（binary search tree）兩者在儲存鍵值並應用來進行搜尋鍵值功能時，在'建置'與'搜尋'程序上作法與效能的差異。
(二)若有n個鍵值，以下列甲和乙兩種資料結構策略儲存：
策略甲：由小到大依序儲存在一陣列中
策略乙：以AVL tree架構儲存
請以Big-O觀念比較後續六種不同功能獨立運作時，這兩種策略何者效能較優或兩者效能相近：1.尋找特定鍵值k；2.尋找排序為j的鍵值；3.刪除特定鍵值k；4.刪除排序為j的鍵值；5.插入新鍵值；6.依序輸出所有鍵值。
[參考解答]
(一)
|
|
binary search |
binary search tree |
|
建置的資料結構 |
陣列 |
鏈結串列 |
|
建置的方法 |
一次性儲存所有鍵值後進行排序，排序方法： 1. 氣泡排序 2. 快速排序 3. 插入排序 4. 選擇排序 |
1、根據左子節點的鍵值<=父節點，右子節點的鍵值>父節點的規則，建立二元樹
|
|
建置時的平均時間複雜度(Big-O) |
1. 氣泡排序：N2 2. 快速排序：N log N 3. 插入排序：N2 4. 選擇排序：N2 |
log N |
|
搜尋方法 |
二分搜尋法 |
二元樹走訪 |
|
搜尋時間複雜度 |
log N |
log N |
(二)
|
|
時間複雜度 |
結果 |
|
|
binary search |
binary search tree |
||
|
尋找特定鍵值k |
log N |
log N |
相近 |
|
尋找排序為j的鍵值 |
N |
N |
相近 |
|
刪除特定鍵值k |
N log N |
log N |
binary search tree 優 |
|
刪除排序為j的鍵值 |
N |
N log N |
binary search 優 |
|
插入新鍵值 |
N |
log N |
binary search tree 優 |
|
依序輸出所有鍵值 |
N |
N |
相近 |
文章標籤
全站熱搜
留言列表
