数据结构第九章--查找-习题及答案.doc
《数据结构第九章--查找-习题及答案.doc》由会员分享,可在线阅读,更多相关《数据结构第九章--查找-习题及答案.doc(9页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、第九章 查找一、 选择题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个关键字的有序表,折半查找的平均查找长
2、度( ) 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. 对
3、大小均为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的
4、左孩子的平衡因子为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
5、 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
6、 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在散列检索中,“比较”操
7、作一般也是不可避免的。( )3Hash表的平均查找长度与处理冲突的方法无关。 ( )4. 散列法的平均检索长度不随表中结点数目的增加而增加,而是随负载因子的增大而增大。( )5. 在索引顺序表中,实现分块查找,在等概率查找情况下,其平均查找长度不仅与表中元素个数有关,而且与每块中元素个数有关。( )6. 就平均查找长度而言,分块查找最小,折半查找次之,顺序查找最大。( )7 最佳二叉树是AVL树(平衡二叉树)。( )8在查找树(二叉树排序树)中插入一个新结点,总是插入到叶结点下面。 ( )9二叉树中除叶结点外, 任一结点X,其左子树根结点的值小于该结点(X)的值;其右子树根结点的值该结点(X)
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 第九 查找 习题 答案
限制150内