搜索
习题9查找9.1单项选择题1.顺序查找法适合于存储结构为____的线性表。A.散列存储B.顺序存储或链接存储C.压缩存储D.索引存储2.对线性表进行二分查找时，要求线性表必须____。A.以顺序方式存储B.以链接方式存储C.以顺序方式存储，且结点按关键字有序排序D.以链接方式存储，且结点按关键字有序排序3.采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为____.A.nB.n/2C.(n+1)/2D.(n-1)/24.采用二分查找方法查找长度为n的线性表时，每个元素的平均查找长度为____。A．O（n2）B.O(nlog2n)C.O(n)D.O(log2n)5.二分查找和二叉排序树的时间性能____。A.相同B.不相同6.有一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当二分查找值82为的结点时，____次比较后查找成功。A.1B.2C.4D.87.设哈希表长m=14，哈希函数H(key)=key%11。表中已有4个结点：addr(15)=4;addr(38)=5;addr(61)=6;addr(84)=7如用二次探测再散列处理冲突，关键字为49的结点的地址是____。A.8B.3C.5D.98.有一个长度为12的有序表，按二分查找法对该表进行查找，在表内各元素等概率情况下查找成功所需的平均比较次数为____。A.35/12B.37/12C.39/12D.43/129．对于静态表的顺序查找法，若在表头设置岗哨，则正确的查找方式为。A.从第0个元素往后查找该数据元素B.从第1个元素往后查找该数据元素C.从第n个元素往开始前查找该数据元素D.与查找顺序无关10．解决散列法中出现的冲突问题常采用的方法是。A.数字分析法、除余法、平方取中法B.数字分析法、除余法、线性探测法C.数字分析法、线性探测法、多重散列法D.线性探测法、多重散列法、链地址法11．采用线性探测法解决冲突问题，所产生的一系列后继散列地址。A.必须大于等于原散列地址B.必须小于等于原散列地址C.可以大于或小于但不能等于原散列地址D.地址大小没有具体限制12．对于查找表的查找过程中，若被查找的数据元素不存在，则把该数据元素插入到集合中。这种方式主要适合于。A.静态查找表B.动态查找表C.静态查找表与动态查找表D两种表都不适合13.散列表的平均查找长度。A.与处理冲突方法有关而与表的长度无关B.与处理冲突方法无关而与表的长度有关C.与处理冲突方法有关而与表的长度有关D.与处理冲突方法无关而与表的长度无关9.2填空题（将正确的答案填在相应的空中）1.顺序查找法的平均查找长度为____；折半查找法的平均查找长度为____；哈希表查找法采用链接法处理冲突时的平均查找长度为____。2.在各种查找方法中，平均查找长度与结点个数n无关的查找方法是____。3.折半查找的存储结构仅限于____，且是____。4.假设在有序线性表A[1..20]上进行折半查找，则比较一次查找成功的结点数为____，则比较二次查找成功的结点数为____，则比较三次查找成功的结点数为____，则比较四次查找成功的结点数为____，则比较五次查找成功的结点数为____，平均查找长度为____。5.对于长度为n的线性表，若进行顺序查找，则时间复杂度为____；若采用折半法查找，则时间复杂度为____；6．已知有序表为（12，18，24，35，47，50，62，83，90，115，134），当用折半查找90时，需进行次查找可确定成功；查找47时，需进行次查找成功；查找100时，需进行次查找才能确定不成功。7．二叉排序树的查找长度不仅与有关，也与二叉排序树的有关。8．一个无序序列可以通过构造一棵树而变成一个有序树，构造树的过程即为对无序序列进行排序的过程。9．平衡二叉排序树上任一结点的平衡因子只可能是、或。10．法构造的哈希函数肯定不会发生冲突。11．在散列函数H(key)=key%p中，p应取____。12．在散列存储中，装填因子的值越大，则____；的值越小，则____。9.3综合练习题:1.画出对长度为10的有序表进行折半查找的判定树，并求其等概率时查找成功的平均查找长度。2.选取哈稀函数H（k）=（3k）MOD11。用开放定址法处理冲突，di=i（（7k）MOD10+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.11．B2．C3．C4．D5．B6．C7．D8．B9．C10．D11．C12．B13．C9.21.（n+1）/2、((n+1)*log2(n+1))/n-1、1+（为装填因子）2.哈希表查找法3.顺序存储结构、有序的4.1、2、4、8、5、3．7（依题意，构造一棵有序二叉树，共12个结点，第一层1个结点，第二层2个结点，第三层4个结点，第四层5个结点，则：ASL=（1*1+2*2+3*4+4*5）/12=37/12）5.O（n）、O(log2n)6．2、4、37．结点个数n、生成过程8．二叉排序树9．0、1、-110．直接定址11．素数12．存取元素时发生冲突的可能性就越大、存取元素时发生冲突的可能性就越小