107 高考三级资料结构题解(一)
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 |
相近 |