数据结构第9章查找习题

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)/24.采用二分查找方法查找长度为n的线性表时，每个元素的平均查找长度为_。AO（n2） B. O(nlog2n) C. O(n) D. O(log

2、2n)5.二分查找和二叉排序树的时间性能_。A. 相同 B. 不相同6.有一个有序表为1，3，9，12，32，41，45，62，75，77，82，95，100，当二分查找值82为的结点时，_次比较后查找成功。A. 1 B. 2 C. 4 D. 87.设哈希表长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. 98.有一个长度为12的有序表，按二分查找法对该表进行查找，在表内各元素等概率情况

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

4、.可以大于或小于但不能等于原散列地址D.地址大小没有具体限制12对于查找表的查找过程中，若被查找的数据元素不存在，则把该数据元素插入到集合中。这种方式主要适合于 。A.静态查找表B.动态查找表C.静态查找表与动态查找表D两种表都不适合13.散列表的平均查找长度 。A.与处理冲突方法有关而与表的长度无关B.与处理冲突方法无关而与表的长度有关C.与处理冲突方法有关而与表的长度有关D.与处理冲突方法无关而与表的长度无关9.2 填空题（将正确的答案填在相应的空中）1.顺序查找法的平均查找长度为_；折半查找法的平均查找长度为_；哈希表查找法采用链接法处理冲突时的平均查找长度为_。2.在各种查找方法中，平

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

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

7、，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.1 1B 2C 3C 4D 5B 6C 7D 8B 9C 10D 11C 12B 13C9.2 1. （n+1）/2 、(n+1)*log2(n+1)/n-1 、1+（为装填因子） 2. 哈希表查找法 3. 顺序存储结构、有序的 4. 1、2、4、8、5、37（依题意，构造一棵有序二叉树，共12个结点，第一层1个结点，第二层2个结点，第三层4个结点，第四层5个结点，则：ASL=（1*1+2*2+3*