2022年数据结构查找习题 .pdf

《2022年数据结构查找习题 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构查找习题 .pdf（3页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、习题 9 查找9.1 单项选择题1.顺序查找法适合于存储结构为_的线性表。A.散列存储B.顺序存储或链接存储C.压缩存储D.索引存储2.对线性表进行二分查找时，要求线性表必须_。A.以顺序方式存储B.以链接方式存储C.以顺序方式存储，且结点按关键字有序排序D.以链接方式存储，且结点按关键字有序排序3.采用顺序查找方法查找长度为n 的线性表时，每个元素的平均查找长度为_.A.n B.n/2 C.(n+1)/2 D.(n-1)/2 4.采用二分查找方法查找长度为n 的线性表时，每个元素的平均查找长度为_。AO（n2）B.O(nlog2n)C.O(n)D.O(log2n)5.二分查找和二叉排序树的时

2、间性能_。A.相同B.不相同6.有一个有序表为 1，3，9，12，32，41，45，62，75，77，82，95，100，当二分查找值 82为的结点时，_次比较后查找成功。A.1 B.2 C.4 D.8 7.设哈希表长 m=14，哈希函数 H(key)=key%11。表中已有 4 个结点：addr(15)=4;addr(38)=5;addr(61)=6;addr(84)=7 如用二次探测再散列处理冲突，关键字为49 的结点的地址是 _。A.8 B.3 C.5 D.9 8.有一个长度为 12 的有序表，按二分查找法对该表进行查找，在表内各元素等概率情况下查找成功所需的平均比较次数为_。A.35/

3、12 B.37/12 C.39/12 D.43/12 9对于静态表的顺序查找法，若在表头设置岗哨，则正确的查找方式为。A.从第 0 个元素往后查找该数据元素B.从第 1 个元素往后查找该数据元素C.从第 n 个元素往开始前查找该数据元素D.与查找顺序无关10解决散列法中出现的冲突问题常采用的方法是。A.数字分析法、除余法、平方取中法B.数字分析法、除余法、线性探测法C.数字分析法、线性探测法、多重散列法D.线性探测法、多重散列法、链地址法11采用线性探测法解决冲突问题，所产生的一系列后继散列地址。A.必须大于等于原散列地址B.必须小于等于原散列地址C.可以大于或小于但不能等于原散列地址D.地址

4、大小没有具体限制12对于查找表的查找过程中，若被查找的数据元素不存在，则把该数据元素插入到集合中。这种方式主要适合于。A.静态查找表B.动态查找表C.静态查找表与动态查找表D 两种表都不适合名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 3 页 -13.散列表的平均查找长度。A.与处理冲突方法有关而与表的长度无关B.与处理冲突方法无关而与表的长度有关C.与处理冲突方法有关而与表的长度有关D.与处理冲突方法无关而与表的长度无关9.2 填空题（将正确的答案填在相应的空中）1.顺序查找法的平均查找长度为_；折半查找法的平均查找长度为_；哈希表查找法采用链接法处理冲突时的平均查找长度为_

5、。2.在各种查找方法中，平均查找长度与结点个数n 无关的查找方法是 _。3.折半查找的存储结构仅限于_，且是 _。4.假设在有序线性表A1.20 上进行折半查找，则比较一次查找成功的结点数为_，则比较二次查找成功的结点数为_，则比较三次查找成功的结点数为_，则比较四次查找成功的结点数为 _，则比较五次查找成功的结点数为_，平均查找长度为 _。5.对于长度为 n 的线性表，若进行顺序查找，则时间复杂度为 _；若采用折半法查找，则时间复杂度为 _；6已知有序表为（12，18，24，35，47，50，62，83，90，115，134），当用折半查找90 时，需进行次查找可确定成功；查找 47 时，需

6、进行次查找成功；查找 100时，需进行次查找才能确定不成功。7二叉排序树的查找长度不仅与有关，也与二叉排序树的有关。8一个无序序列可以通过构造一棵树而变成一个有序树，构造树的过程即为对无序序列进行排序的过程。9平衡二叉排序树上任一结点的平衡因子只可能是、或。10法构造的哈希函数肯定不会发生冲突。11在散列函数 H(key)=key%p 中，p 应取_。12在散列存储中，装填因子的值越大，则 _；的值越小，则 _。9.3 综合练习题:1.画出对长度为10 的有序表进行折半查找的判定树，并求其等概率时查找成功的平均查找长度。2.选取哈稀函数 H（k）=（3k）MOD 11。用开放定址法处理冲突，d

7、i=i（7k）MOD 10+1）（I=1，2，3，）.试在 0-10 的散列地址空间中对关键字序列（22,41,53,46,30,13,01,67）造哈希表，并求等概率情况下查找成功时的平均查找长度。3.已知一组关键字 49，38，65，97，76，13，27，44，82，35，50，画出由此生成的二叉排序树，注意边插入边平衡。习题答案9.11B 2C 3C 4D 5B 6C 7D 8B 9C 10D 11C 12B 13C 9.2 1.（n+1）/2、(n+1)*log2(n+1)/n-1、1+（为装填因子）2.哈希表查找法3.顺序存储结构、有序的4.1、2、4、8、5、37 名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 3 页 -（依题意，构造一棵有序二叉树，共12个结点，第一层 1 个结点，第二层 2 个结点，第三层4 个结点，第四层 5 个结点，则：ASL=（1*1+2*2+3*4+4*5）/12=37/12）5.O（n）、O(log2n)62、4、3 7结点个数 n、生成过程8二叉排序树90、1、-1 10直接定址11素数12存取元素时发生冲突的可能性就越大、存取元素时发生冲突的可能性就越小名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 3 页 -