数据结构第九章 查找 习题及答案(5)

数据结构课件

n 1

12．log m/2 (

2

)+1 ，(n+1)/2（最坏情况是每个结点只要一个孩子结点的情况，这时的

平均时间复杂度为（n+1）/2,而log (5(n 1)) 2是通常情况下的ASL） 13．31 14．主关键字 15．插入 删除

16(1)low=mid+1 (2)high=mid-1 (3)high>=low

四．应用题

1．概念是基本知识的主要部分，要牢固掌握。这里只列出一部分，目的是引起重视，解答略。 3．

查找成功平均查找长度：ASLsucc=（1+1+1+2+3+4+1+2）/8=15/8

以关键字27为例：H（27）=27%7=6（冲突） H1=（6+1）%10=7（冲突）

23

H2=（6+2）%10=0（冲突） H3=（6+3）%10=5 所以比较了4次。

注意：计算查找失败时的平均查找长度，必须计算不在表中的关键字，当其哈希地址为i（0≤i≤m-1）时的查找次数。如下例中m=10。对于关键字集{30,15,21,40,25,26,36,37}若查找表的装填因子为0.8，哈希函数为H（key）=key % 7采用线性探测再散列方法解决冲突，

4.

unsuccASL查找成功=18/13 7.如下图： 9．（1）当插入26后的树形为：