無敵小草

107 高考三級資料結構

(一)請說明並比較二分搜尋（binary search）與一般二元搜尋樹（binary search tree）兩者在儲存鍵值並應用來進行搜尋鍵值功能時，在'建置'與'搜尋'程序上作法與效能的差異。

(二)若有n個鍵值，以下列甲和乙兩種資料結構策略儲存：

策略甲：由小到大依序儲存在一陣列中

策略乙：以AVL tree架構儲存

請以Big-O觀念比較後續六種不同功能獨立運作時，這兩種策略何者效能較優或兩者效能相近：1.尋找特定鍵值k；2.尋找排序為j的鍵值；3.刪除特定鍵值k；4.刪除排序為j的鍵值；5.插入新鍵值；6.依序輸出所有鍵值。

[參考解答]

(一)

(二)

一非空的二元樹（binary tree），如果有N0個葉節點（leaf node）且N2個節點之分支度（degree）為2，請證明N0 = N2+1。 【107高考】

證明如下：

1、從節點數來看，分支度為2的節點數N2個，分支度為1的節點數N1個，分支度為0的節點數N0個，則節點總數 = N2 + N1 + N0

2、從分支度來看，一非空二元樹，分支度為2的節點會有2個子節點，分支度為1的節點會有1個子節點，因此，節點總數 = 2N2 + N1 + 1( 根節點 )

由1及2可得

N2+N1+N0 = 2N2 +N1 +1

=> N0 = N2 + 1

二元樹(binary tree)

【簡單說明】

節點：A,B,C,D皆稱為節點

根節點(root)：A

父節點：A為B和C的父節點，B為D的父節點

子節點：B, C為A的子節點

葉節點：紅色的部分皆為葉節點

分支度(d)：每個節點分支個數，A, B的分支度為2，C的分支度為1，D的分支度為0

高度(h)：二元樹的階層數，上圖的高度為4( 若根節點為階層0時，則高度為3 )

【國家考試曾經考過的類型】