资源描述：
《数据结构域算法设计-第7章++查找+课后习题答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第7章查找1．选择题（1）对n个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为（）。A．(n-1)/2B．n/2C．(n+1)/2D．n（2）适用于折半查找的表的存储方式及元素排列要求为（）。A．链接方式存储，元素无序B．链接方式存储，元素有序C．顺序方式存储，元素无序D．顺序方式存储，元素有序（3）当在一个有序的顺序表上查找一个数据时，既可用折半查找，也可用顺序查找，但前者比后者的查找速度（）。A．必定快B．不一定C．在大部分情况下要快D．取决于表递增还是递减（4）折半查找有序表（4，6，10，12，20，30，50，70，88，10
2、0）。若查找表中元素58，则它将依次与表中（）比较大小，查找结果是失败。A．20，70，30，50B．30，88，70，50C．20，50D．30，88，50（5）对22个记录的有序表作折半查找，当查找失败时，至少需要比较（）次关键字。A．3B．4C．5D．6（6）折半搜索与二叉排序树的时间性能（）。A．相同B．完全不同C．有时不相同D．数量级都是O(log2n)（7）分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是（）。A．（100，80，90，60，120，110，130）B．（100，120，110，130，80，60，90）C．
3、（100，60，80，90，120，110，130）D．(100，80，60，90，120，130，110)（8）在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A，并已知A的左孩子的平衡因子为0右孩子的平衡因子为1，则应作（）型调整以使其平衡。A．LLB．LRC．RLD．RR（9）下列关于m阶B-树的说法错误的是（）。A．根结点至多有m棵子树B．所有叶子都在同一层次上C．非叶结点至少有m/2(m为偶数)或m/2+1（m为奇数）棵子树D．根结点中的数据是有序的（10）下面关于B-和B+树的叙述中，不正确的是（）。A．B-树和B+树都是平衡的
4、多叉树B．B-树和B+树都可用于文件的索引结构C．B-树和B+树都能有效地支持顺序检索D．B-树和B+树都能有效地支持随机检索（11）m阶B-树是一棵（）。A．m叉排序树B．m叉平衡排序树C．m-1叉平衡排序树D．m+1叉平衡排序树（12）下面关于哈希查找的说法，正确的是（）。A．哈希函数构造的越复杂越好，因为这样随机性好，冲突小B．除留余数法是所有哈希函数中最好的C．不存在特别好与坏的哈希函数，要视情况而定D．哈希表的平均查找长度有时也和记录总数有关（13）下面关于哈希查找的说法，不正确的是（）。A．采用链地址法处理冲突时，查找一个元素的时间是相同的B
5、．采用链地址法处理冲突时，若插入规定总是在链首，则插入任一个元素的时间是相同的C．用链地址法处理冲突，不会引起二次聚集现象D．用链地址法处理冲突，适合表长不确定的情况（14）设哈希表长为14，哈希函数是H(key)=key%11，表中已有数据的关键字为15，38，61，84共四个，现要将关键字为49的元素加到表中，用二次探测法解决冲突，则放入的位置是（）。A．8B．3C．5D．9（15）采用线性探测法处理冲突，可能要探测多个位置，在查找成功的情况下，所探测的这些位置上的关键字()。A．不一定都是同义词B．一定都是同义词C．一定都不是同义词D．都相同2．应
6、用题（1）假定对有序表：（3，4，5，7，24，30，42，54，63，72，87，95）进行折半查找，试回答下列问题：①画出描述折半查找过程的判定树；②若查找元素54，需依次与哪些元素比较？③若查找元素90，需依次与哪些元素比较？④假定每个元素的查找概率相等，求查找成功时的平均查找长度。①先画出判定树如下（注：mid=ë(1+12)/2û=6）：30563374287424547295②查找元素54，需依次与30,63,42,54元素比较；③查找元素90，需依次与30,63,87,95元素比较；④求ASL之前，需要统计每个元素的查找次数。判定树的前3层
7、共查找1＋2×2＋4×3=17次；但最后一层未满，不能用8×4，只能用5×4=20次，所以ASL＝1/12（17＋20）＝37/12≈3.08（2）在一棵空的二叉排序树中依次插入关键字序列为12，7，17，11，16，2，13，9，21，4，请画出所得到的二叉排序树。1271721116214913验算方法：用中序遍历应得到排序结果：2,4,7,9,11,12,13,16,17，21（3）已知如下所示长度为12的表：（Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec）①试按表中元素的顺序依次插入一棵初始为
8、空的二叉排序树，画出插入完成之后的二叉排序树，并求其在等概率的情况下查找成功的平
