查找和排序(6)

习题习题习题习题习题习题习题习题习题

2．假定对有序表(3,4,5,7,24,30,42,54,63,72,87,95)进行折半查找，试回答下列问题：

（1）画出描述折半查找过程的判定树。

（2）若查找元素54，需依次与那些元素比较。

（2）若查找元素90，需依次与那些元素比较。

（3）求查找成功时的平均查找长度。

3、对下面的关键字集{30，15，21，40，25，26，36，37}若查找表的装填因子为0.8，采用线性探测再散列方法解决冲突，哈希函数为H（key）＝key％ 7，画出该哈希表，并计算查找成功的平均查找长度。

4．设有一组关键字{ 9，1，23，14，55，20，84，27 }．采用哈希函数：H(key)＝key％7。 采用开放地址法的二次探测再散列方法解决冲突Hi (H(key) di)mod10(di 12,22, )，试对该关键字序列构造哈希表，并计算查找成功的平均查找长度。

5．输入一个正整数序列（17，31，13，11，20，35，25，8，4，11，24，40，27）画出该二叉排序树。依此二叉排序树，如何得到一个递增序列？

6．一棵二叉排序树结构如下图所示，各结点的值分别为1，2，3,...9,请在图中标出各结点的值。

6

7．已知插入结点的序列为（17，31，13，11，20，35，25，8，4，11，24，40，27）,请画出该二叉排序树，并分别给出下列操作后的二叉排序树：

(1)插入数据9；

（2）删除数据17；

（3）再删除结点13；

8．按下列次序输入关键字：（E,F,P,K,M,L,B）,请画出AVL树的构造和调整过程。要求画出每插入一个关键字后查找树的形状及调整后的结果，并标明调整类型。