数据结构第7章答案(已核)_第1页
数据结构第7章答案(已核)_第2页
数据结构第7章答案(已核)_第3页
数据结构第7章答案(已核)_第4页
数据结构第7章答案(已核)_第5页
已阅读5页，还剩2页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

习题一、名词解释 (1)主关键字 (2)平均查找长度 (3)静态查找表 (4)动态查找表 (5)二叉查找树 (6)哈希表二、填空题 (1)静态查找表的存储结构主要采用顺序存储结构，如果需要，也可以采用链式存储结构， 但当使用二分(折半)查找算法或(斐波那契数列)查找算法来查找时，要求查找表 只能是顺序存储结构，并且查找表中的数据序列必须有序。 (2)通过中根序遍历一棵二叉查找树得到的数据序列必然是一个非降序(有序)序 (3)各种查找方法中，平均查找长度与结点个数n无关的查找方法是哈希查找。 *(4)如果对一个有序查找表SST进行折半查找，在最坏时要比较10次，那么对该查找表 进行顺序查找时，在最坏时要比较210-1次。 解析：最坏情况要比较10次，说明树的高度是10。而一棵深度为10的二叉树，最多*(5)深度为7的平衡二叉树至少有33个结点。解析：在节点最少的情况下，左右子树的高度差为1，则总节点数S(n)=S(n-1)+S(n-2)+1。已知，初始值S(1)=1，S(2)=2，所以，高度为7的平制衡二百叉树最少结点数是33。三、简答题 (1)请画出长度为8的有序查找表的折半查找判定树。 (2)折半查找的前提：顺序存储、查找表有序。 (3)已知关键字序列为{45，28，67，33，29，50}，二叉排序树初始为空，要求：①画出按正向(从关键字45开始)顺序插入结点建立的二叉排序树。②画出按反向(从关键字50开始)顺序插入结点建立的二叉排序树。 (4)二叉排序树的平均查找长度：与结点个数和树的形态有关。 (5)设哈希表的地址空间为0~6，哈希函数H(key)=key%7。请对关键字序列{32，13，成功 (6)设哈希表的地址空间为0~12，哈希函数H(key)=key%11。请对关键字序列{30，15，49，61，22，50，23，41，18}按二次探测再哈希法解决冲突的办法构造哈希表。并求出在等概并查找成功时的平均查找长度。关于关键字18的说明：H(18)=18%11=7,冲突；H1=(H(key)+d1)%m=(7+1)%13=8，冲突；H2=(H(key)+d1)%m=(7-1)%13=6，冲突；号存储单元中。备注：公式Hi=(H(key)+di)%m详见课本第164页，其中m是表长。 (7)设哈希表的地址空间为0~12，哈希函数H(key)=key%11。请对关键字序列{30，

人人文库> 全部分类> 行业资料 > 信息产业

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论