电子文档交易市场
安卓APP | ios版本
电子文档交易市场
安卓APP | ios版本
换一换
首页 金锄头文库 > 资源分类 > DOC文档下载
分享到微信 分享到微博 分享到QQ空间

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

  • 资源ID:90116020       资源大小:137.50KB        全文页数:9页
  • 资源格式: DOC        下载积分:12金贝
快捷下载 游客一键下载
账号登录下载
微信登录下载
三方登录下载: 微信开放平台登录   支付宝登录   QQ登录  
二维码
微信扫一扫登录
下载资源需要12金贝
邮箱/手机:
温馨提示:
快捷下载时,用户名和密码都是您填写的邮箱或者手机号,方便查询和重复下载(系统自动生成)。
如填写123,账号就是123,密码也是123。
支付方式: 支付宝    微信支付   
验证码:   换一换

 
账号:
密码:
验证码:   换一换
  忘记密码?
    
1、金锄头文库是“C2C”交易模式,即卖家上传的文档直接由买家下载,本站只是中间服务平台,本站所有文档下载所得的收益全部归上传人(卖家)所有,作为网络服务商,若您的权利被侵害请及时联系右侧客服;
2、如你看到网页展示的文档有jinchutou.com水印,是因预览和防盗链等技术需要对部份页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有jinchutou.com水印标识,下载后原文更清晰;
3、所有的PPT和DOC文档都被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;下载前须认真查看,确认无误后再购买;
4、文档大部份都是可以预览的,金锄头文库作为内容存储提供商,无法对各卖家所售文档的真实性、完整性、准确性以及专业性等问题提供审核和保证,请慎重购买;
5、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据;
6、如果您还有什么不清楚的或需要我们协助,可以点击右侧栏的客服。
下载须知 | 常见问题汇总

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

第九章 查找一、 选择题1.若查找每个记录的概率均等,则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录,其平均查找长度ASL为( )。 A (n-1)/2 B. n/2 C. (n+1)/2 D. n2. 下面关于二分查找的叙述正确的是 ( ) A. 表必须有序,表可以顺序方式存储,也可以链表方式存储 C. 表必须有序,而且只能从小到大排列B. 表必须有序且表中数据必须是整型,实型或字符型 D. 表必须有序,且表只能以顺序方式存储3. 用二分(对半)查找表的元素的速度比用顺序法( )A必然快 B. 必然慢 C. 相等 D. 不能确定4. 具有12个关键字的有序表,折半查找的平均查找长度( ) A. 3.1 B. 4 C. 2.5 D. 55当采用分块查找时,数据的组织方式为 ( ) A数据分成若干块,每块内数据有序B数据分成若干块,每块内数据不必有序,但块间必须有序,每块内最大(或最小)的数据组成索引块C. 数据分成若干块,每块内数据有序,每块内最大(或最小)的数据组成索引块D. 数据分成若干块,每块(除最后一块外)中数据个数需相同6. 二叉查找树的查找效率与二叉树的( (1))有关, 在 ((2))时其查找效率最低 (1): A. 高度 B. 结点的多少 C. 树型 D. 结点的位置 (2): A. 结点太多 B. 完全二叉树 C. 呈单枝树 D. 结点太复杂。7. 对大小均为n的有序表和无序表分别进行顺序查找,在等概率查找的情况下,对于查找失败,它们的平均查找长度是(1) ,对于查找成功,他们的平均查找长度是(2)供选择的答案: A. 相同的 B.不同的9分别以下列序列构造二叉排序树,与用其它三个序列所构造的结果不同的是( ) A(100,80, 90, 60, 120,110,130) B.(100,120,110,130,80, 60, 90)C.(100,60, 80, 90, 120,110,130) D. (100,80, 60, 90, 120,130,110)10. 在平衡二叉树中插入一个结点后造成了不平衡,设最低的不平衡结点为A,并已知A的左孩子的平衡因子为0右孩子的平衡因子为1,则应作( ) 型调整以使其平衡。A. LL B. LR C. RL D. RR11. 下面关于m阶B-树说法正确的是( ) 每个结点至少有两棵非空子树; 树中每个结点至多有m一1个关键字; 所有叶子在同一层上; 当插入一个数据项引起B树结点分裂后,树长高一层。A B. C. D. 12. m阶B-树是一棵( ) A. m叉排序树 B. m叉平衡排序树 C. m-1叉平衡排序树 D. m+1叉平衡排序树15. 设有一组记录的关键字为19,14,23,1,68,20,84,27,55,11,10,79,用链 地址法构造散列表,散列函数为H(key)=key MOD 13,散列地址为1的链中有( ) 个记录。A1 B. 2 C. 3 D. 416. 关于哈希查找说法不正确的有几个( ) (1)采用链地址法解决冲突时,查找一个元素的时间是相同的 (2)采用链地址法解决冲突时,若插入规定总是在链首,则插入任一个元素的时间是相同的 (3)用链地址法解决冲突易引起聚集现象 (4)再哈希法不易产生聚集A. 1 B. 2 C. 3 D. 417. 设哈希表长为14,哈希函数是H(key)=key%11,表中已有数据的关键字为15,38,61,84共四个,现要将关键字为49的结点加到表中,用二次探测再散列法解决冲突,则放入的位置是( ) A8 B3 C5 D9 18. 假定哈希查找中k个关键字具有同一哈希值,若用线性探测法把这k个关键字存入散列表中,至少要进行多少次探测?( ) Ak-1次 B. k次 C. k+1次 D. k(k+1)/2次19. 好的哈希函数有一个共同的性质,即函数值应当以( )取其值域的每个值。A. 最大概率 B. 最小概率 C. 平均概率 D. 同等概率20. 将10个元素散列到100000个单元的哈希表中,则( )产生冲突。A. 一定会 B. 一定不会 C. 仍可能会二、 判断题1采用线性探测法处理散列时的冲突,当从哈希表删除一个记录时,不应将这个记录的所在位置置空,因为这会影响以后的查找。( )2在散列检索中,“比较”操作一般也是不可避免的。( )3Hash表的平均查找长度与处理冲突的方法无关。 ( )4. 散列法的平均检索长度不随表中结点数目的增加而增加,而是随负载因子的增大而增大。( )5. 在索引顺序表中,实现分块查找,在等概率查找情况下,其平均查找长度不仅与表中元素个数有关,而且与每块中元素个数有关。( )6. 就平均查找长度而言,分块查找最小,折半查找次之,顺序查找最大。( )7 最佳二叉树是AVL树(平衡二叉树)。( )8在查找树(二叉树排序树)中插入一个新结点,总是插入到叶结点下面。 ( )9二叉树中除叶结点外, 任一结点X,其左子树根结点的值小于该结点(X)的值;其右子树根结点的值该结点(X)的值,则此二叉树一定是二叉排序树。( )10有n个数存放在一维数组A1.n中,在进行顺序查找时,这n个数的排列有序或无序其平均查找长度不同。( )11. N个结点的二叉排序树有多种,其中树高最小的二叉排序树是最佳的。 ( )12. 在任意一棵非空二叉排序树中,删除某结点后又将其插入,则所得二排序叉树与原二排序叉树相同。( )13. B-树中所有结点的平衡因子都为零。 ( )14. 在平衡二叉树中,向某个平衡因子不为零的结点的树中插入一新结点,必引起平衡旋转。( )三、填空题1. 顺序查找n个元素的顺序表,若查找成功,则比较关键字的次数最多为_ _次;当使用监视哨时,若查找失败,则比较关键字的次数为_ _。2在有序表A1.12中,采用二分查找算法查等于A12的元素,所比较的元素下标依次为_。3. 在有序表A1.20中,按二分查找方法进行查找,查找长度为5的元素个数是_4. 高度为4(含叶子结点层)的3阶b-树中,最多有_个关键字。5. 在一棵m阶B-树中,若在某结点中插入一个新关键字而引起该结点分裂,则此结点中原有的关键字的个数是_;若在某结点中删除一个关键字而导致结点合并,则该结点中原有的关键字的个数是_。6. 在哈希函数H(key)=key%p中,p值最好取_。8. 如果按关键码值递增的顺序依次将关键码值插入到二叉排序树中,则对这样的二叉排序 树检索时,平均比较次数为_。 9. 如果关键码按值排序,而后用二分法依次检索这些关键码,并把检索中遇到的在二叉树中没有出现的关键码依次插入到二叉排序树中,则对这样的二叉排序树检索时,平均比较次数为_。(提示:此时二叉排序树与折半查找的二叉判定树一样了)10. 平衡因子的定义是_ _11. 查找是非数值程序设计的一个重要技术问题,基本上分成_(1)_查找,_(2)_查找和_(3)_查找。处理哈希冲突的方法有_(4)_、_(5)_、_(6)_和_(7)_。12. 具有N个关键字的B树的查找路径长度不会大于_。在一棵有N 个结点的非平衡二叉树中进行查找,平均时间复杂度的上限(即最坏情况平均时间复杂度)为_13. 高度为5(除叶子层之外)的三阶B-树至少有_个结点。14. 可以唯一的标识一个记录的关键字称为_。15. 动态查找表和静态查找表的重要区别在于前者包含有_和_运算,而后者不包含这两种运算。16. 已知N元整型数组a存放N个学生的成绩,已按由大到小排序,以下算法是用对分(折半)查找方法统计成绩大于或等于X分的学生人数,请填空使之完善。( 提示:这时需要找的是最后一个大于等于X的下标,若查找成功其下标若为m,则有m个学生成绩大于或等于X,若查找不成功,若这时low所指向的值小于X,则有low-1个学生成绩大于或等于X,注意这时表中可能不止一个数值为X的值,这时我们要查找的是下标最大的)#define N /*学生人数*/int uprx(int aN,int x ) /*函数返回大于等于X分的学生人数*/ int low=1,mid,high=N; do mid=(low+high)/2;if(x<=amid) _(1)_ else _(2)_;while(_(3)_);if (alow<x) return low-1;return low; 四、应用题1. 名词解释:哈希表叙述B-树定义,主要用途是什么? 平衡二叉树(AVL树)平衡因子 平均查找长度(ASL)3. 设有一组关键字9,01,23,14,55,20,84,27,采用哈希函数:H(key)=key mod 7 ,表长为10,用开放地址法的二次探测再散列方法解决冲突Hi=(H(key)+di) mod 10(di=12,22,32,)。要求:对该关键字序列构造哈希表,并确定其装填因子,查找成功所需的平均探查次数。4. 设一组数据为1,14,27,29,55,68,10,11,23,现采用的哈希函数是H(key)=key MOD 13, 即关键字对13取模,冲突用链地址法解决,设哈希表的大小为13(0.12),试画出插入上述数据后的哈希表。7. 设有一棵空的阶B-树,依次插入关键字30,20,10,40,80,58,47,50,29,22,56,98,99,请画出该树。9. 已知2棵2-3 B-树如下(省略外结点): (1) 对树(a),请分别画出先后插入26,85两个新结点后的树形;(2) 对树(b),请分别画出先后删除53,37两个结点后的树形。(a) (b) 10. 输入一个正整数

注意事项

本文(数据结构第九章 查找 习题及答案)为本站会员(小**)主动上传,金锄头文库仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即阅读金锄头文库的“版权提示”【网址:https://www.jinchutou.com/h-59.html】,按提示上传提交保证函及证明材料,经审查核实后我们立即给予删除!

温馨提示:如果因为网速或其他原因下载失败请重新下载,重复下载不扣分。




关于金锄头网 - 版权申诉 - 免责声明 - 诚邀英才 - 联系我们
手机版 | 川公网安备 51140202000112号 | 经营许可证(蜀ICP备13022795号)
©2008-2016 by Sichuan Goldhoe Inc. All Rights Reserved.