数据结构（查找）习题及答案
3星 · 超过75%的资源 需积分: 50 66 浏览量
2008-12-21
00:34:36
上传
评论 1
收藏 128KB DOC 举报 
第八章 查找
一、填空
１、顺序查找法等概率下查找成功时的平均查找长度为（），查找不成功时的比较次数为
（）。
２、对线性表进行折半查找时，要求线性表必须（）。
３ 、 设 哈 希 表 L 长 m=14 ， 哈 希 函 数 H(key)=key%11 ， 表 中 已 有 ４ 个 结 点 ：
L[4]=15，L[5]=38，L[6]=61，L[7]=84，其余地址为空，若用二次探测再散列法处理冲突，
关键字值为４９的结点在Ｌ中下标为（）。
４、哈希表查找法中仍需进行关键字间比较的原因是（）的存在。
５、在各种查找方法中，平均查找长度与结点个数无关的查找方法是（）。
二、画出对长度为１７的有序表进行折半查找的判定树，并求等概率下查找成功时的平均查
找长度。
三、按给定关键字序列（３３、６２、７６、４５、５２、５８）构造二叉排序树，并求等
概率下查找成功时的平均查找长度。
四、按给定关键字序列（３３、６２、７６、４５、５２、５８）构造平衡的二叉排序树，
并求等概率下查找成功时的平均查找长度。
五、设有３阶Ｂ－树如下，画出删除关键字值１７的过程。
六、设哈希函数 H(key)=key%13，用公共溢出区法处理冲突。试在０～１９的散列地址空间
中对关键字序列（１９，０１，２３，１４，５５，２０，８４，２７，６８，１１，１０
７７）造哈希表，并求等概率下查找成功时的平均查找长度。
七、设计递归算法，从大到小输出给定二叉排序树中所有关键字值不小于ｘ的数据元素。要
求算法时间复杂度为 O(log
2
n+m)，其中ｎ为排序树中所含结点数，ｍ为输出的关键字个数。
【参考答案】
资源评论
jisitang2013-05-21对我上课挺有用的。
