查找-答案

1．2．给定关键字序列11，78，10，1，3，2，4，21，试分别用顺序查找、二分查找、二叉排序树查找、平衡二叉树查找、散列查找(用线性探查法和拉链法)来实现查找，试画出它们的对应存储形式(顺序查找的顺序表，二分查找的判定树，二叉排序树查找的二叉排序树及平衡二叉树查找的平衡二叉树，两种散列查找的散列表)，并求出每一种查找的成功平均查找长度。散列函数H(k)=k%11。顺序查找的顺序表（一维数组）如图所示，117810132421012345678910顺序存储的顺序表顺序存储的顺序表从图可以得到顺序查找的成功平均查找长度为：ASL=(1+2+3+4+5+6+7+8)/8=4.5二分查找的判定树（中序序列为从小到大排列的有序序列）如图8-20所示，421311102178图8-20二分查找的判定树从图8-20可以得到二分查找的成功平均查找长度为：ASL=(1+2*2+3*4+4)/8=2.625线性探查法解决冲突的散列表如图所示，从图可以得到线性探查法的成功平均查找长度为：ASL=（1+1+2+1+3+2+1+8）/8=2.375117813242110012345678910线性探查的散列表012345610117813242110