第9章查找一、选择题1.顺序查找一个共有n个元素的线性表，其时间复杂度为（），折半查找一个具有n个元素的有序表，其时间复杂度为（）。
【＊，★】A.O(n)B. O(log2n)C. O(n2)D. O(nlog2n)2.在对长度为n的顺序存储的有序表进行折半查找，对应的折半查找判定树的高度为（）。
【＊，★】A.nB.C.D.3.采用顺序查找方式查找长度为n的线性表时，平均查找长度为（）。
【＊】A.nB. n/2C. (n+1)/2D. (n-1)/24.采用折半查找方法检索长度为n的有序表，检索每个元素的平均比较次数（）对应判定树的高度（设高度大于等于2）。
【＊＊】A.小于B. 大于C. 等于D. 大于等于5.已知有序表（13，18，24，35，47，50，62，83，90，115，134），当折半查找值为90的元素时，查找成功的比较次数为（）。
【＊】A. 1B. 2C. 3D. 46.对线性表进行折半查找时，要求线性表必须（）。
【＊】A.以顺序方式存储B. 以链接方式存储C.以顺序方式存储，且结点按关键字有序排序D. 以链接方式存储，且结点按关键字有序排序7.顺序查找法适合于存储结构为（）的查找表。
【＊】A.散列存储B. 顺序或链接存储C. 压缩存储D. 索引存储8.采用分块查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块时，每块应分（）个结点最佳。
【＊＊】A.10B. 25C. 6D. 6259.从键盘依次输入关键字的值：t、u、r、b、o、p、a、s、c、l，建立二叉排序树，则其先序遍历序列为（），中序遍历序列为（）。
【＊＊，★】A.abcloprstuB. alcpobsrutC. trbaoclpsuD. trubsaocpl10.折半查找和二叉排序树的时间性能（）。
【＊】A.相同B. 不相同11.一棵深度为k的平衡二叉树，其每个非终端结点的平衡因子均为0，则该树共有（）个结点。
A.2k-1-1B. 2k-1C. 2k-1+1D. 2k-112.利用逐点插入法建立序列{50，72，43，85，75，20，35，45，65，30}对应的二叉排序树以后，查找元素35要进行（）元素间的比较。
A.4次B. 5次C. 7次D. 10次13.设Hash地址空间为0到m-1，哈希函数为h(k)=k%p，为了减少发生冲突的可能性，一般取p为（）。
A.小于m的最大奇数B. 小于m的最大素数C. 小于m的最大偶数D. 小于m的最大合数14.长度为10的按关键字有序的查找表采用顺序组织方式。
若采用折半查找方法，则在等概率情况下，查找失败时的ASL值是（）。
A.24/10B. 24/11C. 39/10D. 39/1115.在表长为n的顺序表中，实施顺序查找，在查找不成功时，与关键字比较的次数为（）A.n+1B. 1C. nD. n-116.设哈希函数为H(key)=key%7，一组关键字为（37，21，9，20，30，19，46），哈希表T的地址空间为0…6，用线性探测法解决冲突，依次将这组关键字插入T中，得到的哈希表为（）。
【＊，★】17.设有一个用线性探测法解决冲突得到的哈希表：哈希函数为H(key)=key%11，若要查找元素14，探测的次数是（）A. 3B. 6C. 7D. 918.在哈希函数H(key)=key%m中，一般来讲，m应取（）。
A.奇数B. 偶数C. 素数D. 充分大的数19.分块查找的时间性能（）。
A.低于二分查找B. 高于顺序查找而低于二分查找C.高于顺序查找D. 低于顺序查找高于二分查找20.以下说法错误的是（）。
A.哈希法存储的基本思想是由关键字的值决定数据的存储地址B.哈希表的结点中只包含数据元素自身的信息，不包含任何指针C.装填因子是哈希法的一个重要参数，它反映哈希表的装填程度D.哈希表的查找效率主要取决于哈希表造表时选取的散列函数和处理冲突的方法21.以下说法正确的是（）。
A.前序遍历二叉排序树的结点就可以得到排好序的结点序列B.任一二叉排序树的平均查找时间都小于用顺序查找法查找同样结点的线性表的平均查找时间C.对具有相同关键字集合的任一插入序列，得到的二叉排序树的形态都是相同的D.采用分块查找方法，既能实现线性表所希望的较快的查找速度，又能适应动态变化的需要22.已知采用开放地址法解决哈希表冲突，要从此哈希表中删除一个记录，正确的做法是（）。
【＊，★】A.将该元素所在的存储单元清空B.将该元素用一个特殊的符号代替C.将与该元素有相同Hash地址的后继元素顺次前移一个位置D.用与该元素有相同Hash地址的最后插入表中的元素替代23.设哈希表长为M=14，哈希函数H(key)=key%11，表中已有4个结点：ADDR(15)=4、ADDR(38)=5、ADDR(61)=6、ADDR(84)=7，其余地址为空，如用二次探测再散列处理冲突，现插入关键字为50的结点的地址应是（）。
【＊，★】A. 3B. 8C. 9D. 1024.有一个长度为12的有序表，按折半查找法对该表进行查找，在表内各元素查找概率相同的情况下，查找成功所需的平均比较次数为（）。
【＊＊，★】A.32/12B. 35/12C. 37/12D. 39/1225.如果要求一个线性表既能较快的查找，又能适应动太变化的要求，可以采用（）查找方法。
【＊】A.分块B. 顺序C. 折半D. 散列26.深度为6的AVL树至少有（）个结点。
【＊＊】A.10B. 12C. 20D. 2127.哈希表的平均查找长度（）。
A.与处理冲突的方法有关而与表的长度无关B.与处理冲突的方法无关而与表的长度有关C.与处理冲突的方法有关且与表的长度有关D.与处理冲突的方法无关且与表的长度无关28.若为查找表长度为m的闭散列表采用二次探测再散列处理冲突，对一个元素第1次计算的哈希地址为d，则第3次计算的哈希地址为（）。
【＊＊】A.(d+1)%mB. (d-1)%mC. (d+4)%mD. (d-4)%m29.有数据（49，32，40，6，45，12，56），从空二叉树开始依次插入数据形成二叉排序树，若希望高度最小，则应选择下列哪个输入序列（）。
【＊，★】A.45，12，49，6，40，56，32B. 40，12，6，32，49，45，56C.6，12，32，40，45，49，56D. 32，12，6，40，45，56，4930.在一棵深度为h的具有n个元素的二叉排序树中，查找所有元素的最长查找长度为（）。
【＊】A.nB. log2nC. (h+1)/2D. h二、判断题1.分块查找方法的平均查找长度低于顺序查找，高于折半查找。
（）【＊＊】2.采用线性探测再散列法处理散列时的冲突，当从哈希表删除一个记录时，不应将这个记录的所在位置置为空，因为这会影响以后的查找。
（）【＊】3.前序遍历二叉排序树的结点就可以得到排好序的结点序列。
（）【＊】4.在任一二叉排序树上查找某个结点都小于用顺序查找法查找同样结点的线性表的查找时间。
（）【＊】5.虽然关键字的序列的顺序不一样，但依次生成的二叉排序树却是一样的。
（）【＊】6.对二棵具有相同关键字集合的形状不同的二叉排序树，按中序遍历它们得到的序列的顺序是一样的。
（）【＊】7.在二叉排序树上插入新的结点时，不必移动其他结点，仅需要改动某个结点的指针，由空变为非空即可。
（）【＊】8.在二叉排序树上删除一个结点时，不必移动其他结点，只要将该结点的父结点的相应指针域置空即可。
（）【＊】三、填空题1.折半查找效率较高，但要求结点（）并且要求线性表（）；而对于顺序查找，则线性表的存储方式（）。
【＊，★】2.假设在有序线性表A[0]—A[9]上进行折半查找，则比较一次查找成功的结点数为（），比较二次查找成功的结点数为（），比较三次查找成功的结点数为（），比较四次查找成功的结点数为（），平均查找长度为（）。
【＊】3.在n个记录的有序顺序表中进行折半查找，最大的比较次数是（）。
【＊】4.折半查找判定树既是一种（），也是一种（）。
【＊，？】5.顺序查找法的平均查找长度为（）；折半查找法的平均查找长度为（）；分块查找法（以顺序查找确定块）的平均查找长度为（）；分块查找法（以折半查找确定块）的平均查找长度为（）；哈希表查找法采用链接法处理冲突时的平均查找长度为（）。
【＊＊，★】6.对于长度为n的线性表，若进行顺序查找，则时间复杂度为（）；若进行折半查找，则复杂度为（）；若采用分块查找（假定总块数和每块长度均接近n的平方），则时间复杂度为（）。
【＊＊，★】7.用二分法查找一个线性表时，该线性表必须具有的特点是（），而分块查找法要求将待查找的表均匀地分成若干块且块中诸记录的顺序可以是任意的，但块与块之间（）。
【＊】8.采用散列技术来实现查找，需要解决的问题有：（）和（）。
【＊】9.在散列存储中，处理冲突有（）和（）两类方法。
【＊】10.（）法构造的哈希函数肯定不会发生冲突。
【＊，？】11.在各种查找方法中，平均查找长度与结点个数无关的查找方法为（）。
【＊，？】12.在开散列表上查找健值等于K的结点，首先必须计算该健值的（），然后再通过指针查找该结点。
13.在索引顺序表上，对于顺序表中的每一块，索引表中有相应的一个“索引项”。
每个索引项有两个域：块内最大（）值和块（）位置。
【＊】14.索引顺序表上的查找分两个阶段：一.（）；二.（）。
该查找方法称为（）查找。
【＊】15.二叉排序树是一种特殊的、增加了限制条件的二叉树，其限制条件是任一结点的键值（）于其左孩子（及其子孙）的键值且（）于其右孩子（及其子孙）的键值。
【＊】16.在表示一棵二叉排序树的二叉链表上，要找键值比某结点X的键值（）的结点，只需通过结点X的右指针到它的右子树中去找。
【＊】17.中序遍历一棵二叉排序树所得的结点访问序列是键值的（）序列。
【＊】18.二叉排序树上的查找长度不仅与（）有关，也与二叉排序树的（）有关。
【＊】19.二叉排序树的查找效率与树的形态有关，当二叉排序树退化为一条单支树时，查找算法退化为（）查找，平均查找长度上升为（）。
【＊，★】20.有n个结点的AVL树的深度与（）是同数量级的，因而在它上面进行查找的平均查找长度也与（）同数量级。
【＊，？】21.（）查找法的平均查找长度与元素个数n个数无关。
【＊】22.在具有20个元素的有序表上进行折半查找，则比较一次查找成功的结点数为（），比较二查找成功的结点数为（），比较五次查找成功的结点数为（）。
总平均查找长度为（）。
【＊＊】23.折半查找方法仅适用于这样的表：表中的记录必须（），其存储结构必须是（）。
【＊】24.考虑具有如下性质的二叉树：除叶子结点外，每个结点的值都大于其左子树上的一切结点的值，并小于或等于其右子树上的一切结点的值。