数据结构第九章查找习题集及其答案解析

《数据结构第九章查找习题集及其答案解析》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、-/第九章查找一、选择题1.若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为()。A．(n-1)/2B.n/2C.(n+1)/2D.n2.下面关于二分查找的叙述正确的是()A.表必须有序，表可以顺序方式存储，也可以链表方式存储C.表必须有序，而且只能从小到大排列B.表必须有序且表中数据必须是整型，实型或字符型D.表必须有序，且表只能以顺序方式存储3.用二分（对半）查找表的元素的速度比用顺序法()A．必然快B.必然慢C.相等D.不能确定4.具有12个关键字的有序表，折半查

2、找的平均查找长度（）A.3.1B.4C.2.5D.55．当采用分块查找时，数据的组织方式为()A．数据分成若干块，每块内数据有序B．数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块C.数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块D.数据分成若干块，每块（除最后一块外）中数据个数需相同6.二叉查找树的查找效率与二叉树的(（1）)有关,在(（2）)时其查找效率最低(1):A.高度B.结点的多少C.树型D.结点的位置(2):A.结点太多B.完全二叉树C.呈单枝树D.结点太

3、复杂。7.对大小均为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.在平衡二叉树中插入一个结点后

4、造成了不平衡，设最低的不平衡结点为A,并已知A的左孩子的平衡因子为0右孩子的平衡因子为1,则应作()型调整以使其平衡。A.LLB.LRC.RLD.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，

5、27，55，11，10，79}，用链地址法构造散列表，散列函数为H（key）=keyMOD13,散列地址为1的链中有（）个记录。A．1B.2C.3D.416.关于哈希查找说法不正确的有几个()（1）采用链地址法解决冲突时，查找一个元素的时间是相同的（2）采用链地址法解决冲突时，若插入规定总是在链首，则插入任一个元素的时间是相同的（3）用链地址法解决冲突易引起聚集现象-/（4）再哈希法不易产生聚集A.1B.2C.3D.417.设哈希表长为14，哈希函数是H(key)=key%11,表中已有数据的关键字为15，38，61，84共四个

6、，现要将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是()A．8B．3C．5D．918.假定哈希查找中k个关键字具有同一哈希值，若用线性探测法把这k个关键字存入散列表中，至少要进行多少次探测？()A．k-1次B.k次C.k+1次D.k（k+1）/2次19.好的哈希函数有一个共同的性质，即函数值应当以()取其值域的每个值。A.最大概率B.最小概率C.平均概率D.同等概率20.将10个元素散列到100000个单元的哈希表中，则（）产生冲突。A.一定会B.一定不会C.仍可能会二、判断题1．采用线性探测法处理散列

7、时的冲突，当从哈希表删除一个记录时，不应将这个记录的所在位置置空，因为这会影响以后的查找。（）2．在散列检索中，“比较”操作一般也是不可避免的。（）3．Hash表的平均查找长度与处理冲突的方法无关。（）4.散列法的平均检索长度不随表中结点数目的增加而增加，而是随负载因子的增大而增大。（）5.在索引顺序表中，实现分块查找，在等概率查找情况下，其平均查找长度不仅与表中元素个数有关，而且与每块中元素个数有关。（）6.就平均查找长度而言，分块查找最小，折半查找次之，顺序查找最大。（）7．最佳二叉树是AVL树（平衡二叉树）。（）8．在查找

8、树（二叉树排序树）中插入一个新结点，总是插入到叶结点下面。（）9．二叉树中除叶结点外,任一结点X，其左子树根结点的值小于该结点（X）的值；其右子树根结点的值≥该结点（X）的值,则此二叉树一定是二叉排序树。（）10．有n个数存放在一维数组A[1..n]中，在进行顺