《数据结构》习题集第9章查找(第1次更新20195).pdf

《《数据结构》习题集第9章查找(第1次更新20195).pdf》由会员分享，可在线阅读，更多相关《《数据结构》习题集第9章查找(第1次更新20195).pdf（7页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、.1 页 第 9 章查找 一、选择题 1.顺序查找一个共有n个元素的线性表，其时间复杂度为（），折半查找一个具有n个元素的有序表，其时间复杂度为（）。【，】A.O(n)B.O(log2n)C.O(n2)D.O(nlog2n)2.在对长度为n的顺序存储的有序表进行折半查找，对应的折半查找判定树的高度为（）。【，】A.n B.C.D.3.采用顺序查找方式查找长度为n的线性表时，平均查找长度为（）。【】A.n B.n/2 C.(n+1)/2 D.(n-1)/2 4.采用折半查找方法检索长度为n的有序表，检索每个元素的平均比较次数（）对应判定树的高度（设高度大于等于2）。【】A.小于 B.大于 C.等

2、于 D.大于等于 5.已知有序表（13，18，24，35，47，50，62，83，90，115，134），当折半查找值为90的元素时，查找成功的比较次数为（）。【】A.1 B.2 C.3 D.4 6.对线性表进行折半查找时，要求线性表必须（）。【】A.以顺序方式存储 B.以链接方式存储 C.以顺序方式存储，且结点按关键字有序排序 D.以链接方式存储，且结点按关键字有序排序 7.顺序查找法适合于存储结构为（）的查找表。【】A.散列存储 B.顺序或链接存储 C.压缩存储 D.索引存储 8.采用分块查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块时，每块

3、应分（）个结点最佳。【】A.10 B.25 C.6 D.625 9.从键盘依次输入关键字的值：t、u、r、b、o、p、a、s、c、l，建立二叉排序树，则其先序遍历序列为（），中序遍历序列为（）。【，】A.abcloprstu B.alcpobsrut C.trbaoclpsu D.trubsaocpl 10.折半查找和二叉排序树的时间性能（）。【】A.相同 B.不相同 11.一棵深度为k的平衡二叉树，其每个非终端结点的平衡因子均为0，则该树共有（）个结点。A.2k-1-1 B.2k-1 C.2k-1+1 D.2k-1 12.利用逐点插入法建立序列50，72，43，85，75，20，35，45，

4、65，30对应的二叉排序树以后，查找元素35要.2 页 进行（）元素间的比较。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/10 B.24/11 C.39/10 D.39/11 15.在表长为n的顺序表中，实施顺序查找，在查找不成功时，与关键字比较的次数为（）A.n+1 B.

5、1 C.n D.n-1 16.设哈希函数为H(key)=key%7，一组关键字为（37，21，9，20，30，19，46），哈希表T的地址空间为06，用线性探测法解决冲突，依次将这组关键字插入T中，得到的哈希表为（）。【，】17.设有一个用线性探测法解决冲突得到的哈希表：哈希函数为H(key)=key%11，若要查找元素14，探测的次数是（）A.3 B.6 C.7 D.9 18.在哈希函数H(key)=key%m中，一般来讲，m应取（）。A.奇数 B.偶数 C.素数 D.充分大的数 19.分块查找的时间性能（）。A.低于二分查找 B.高于顺序查找而低于二分查找 C.高于顺序查找 D.低于顺序查

6、找高于二分查找 20.以下说法错误的是（）。A.哈希法存储的基本思想是由关键字的值决定数据的存储地址 B.哈希表的结点中只包含数据元素自身的信息，不包含任何指针 C.装填因子是哈希法的一个重要参数，它反映哈希表的装填程度 D.哈希表的查找效率主要取决于哈希表造表时选取的散列函数和处理冲突的方法 21.以下说法正确的是（）。A.前序遍历二叉排序树的结点就可以得到排好序的结点序列 B.任一二叉排序树的平均查找时间都小于用顺序查找法查找同样结点的线性表的平均查找时间 C.对具有相同关键字集合的任一插入序列，得到的二叉排序树的形态都是相同的 D.采用分块查找方法，既能实现线性表所希望的较快的查找速度，

7、又能适应动态变化的需要 22.已知采用开放地址法解决哈希表冲突，要从此哈希表中删除一个记录，正确的做法是（）。【，】A.将该元素所在的存储单元清空.3 页 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.3 B.8 C.9 D.10

8、24.有一个长度为12的有序表，按折半查找法对该表进行查找，在表内各元素查找概率相同的情况下，查找成功所需的平均比较次数为（）。【，】A.32/12 B.35/12 C.37/12 D.39/12 25.如果要求一个线性表既能较快的查找，又能适应动太变化的要求，可以采用（）查找方法。【】A.分块 B.顺序 C.折半 D.散列 26.深度为6的AVL树至少有（）个结点。【】A.10 B.12 C.20 D.21 27.哈希表的平均查找长度（）。A.与处理冲突的方法有关而与表的长度无关 B.与处理冲突的方法无关而与表的长度有关 C.与处理冲突的方法有关且与表的长度有关 D.与处理冲突的方法无关且与

9、表的长度无关 28.若为查找表长度为m 的闭散列表采用二次探测再散列处理冲突，对一个元素第1 次计算的哈希地址为d，则第3次计算的哈希地址为（）。【】A.(d+1)%m B.(d-1)%m C.(d+4)%m D.(d-4)%m 29.有数据（49，32，40，6，45，12，56），从空二叉树开始依次插入数据形成二叉排序树，若希望高度最小，则应选择下列哪个输入序列（）。【，】A.45，12，49，6，40，56，32 B.40，12，6，32，49，45，56 C.6，12，32，40，45，49，56 D.32，12，6，40，45，56，49 30.在一棵深度为h的具有n个元素的二叉排序

10、树中，查找所有元素的最长查找长度为（）。【】A.n B.log2n C.(h+1)/2 D.h 二、判断题 1.分块查找方法的平均查找长度低于顺序查找，高于折半查找。（）【】2.采用线性探测再散列法处理散列时的冲突，当从哈希表删除一个记录时，不应将这个记录的所在位置置为空，因为这会影响以后的查找。（）【】3.前序遍历二叉排序树的结点就可以得到排好序的结点序列。（）【】.4 页 4.在任一二叉排序树上查找某个结点都小于用顺序查找法查找同样结点的线性表的查找时间。（）【】5.虽然关键字的序列的顺序不一样，但依次生成的二叉排序树却是一样的。（）【】6.对二棵具有相同关键字集合的形状不同的二叉排序树，

11、按中序遍历它们得到的序列的顺序是一样的。（）【】7.在二叉排序树上插入新的结点时，不必移动其他结点，仅需要改动某个结点的指针，由空变为非空即可。（）【】8.在二叉排序树上删除一个结点时，不必移动其他结点，只要将该结点的父结点的相应指针域置空即可。（）【】三、填空题 1.折半查找效率较高，但要求结点（）并且要求线性表（）；而对于顺序查找，则线性表的存储方式（）。【，】2.假设在有序线性表 A0A9上进行折半查找，则比较一次查找成功的结点数为（），比较二次查找成功的结点数为（），比较三次查找成功的结点数为（），比较四次查找成功的结点数为（），平均查找长度为（）。【】3.在 n 个记录的有序顺序表中

12、进行折半查找，最大的比较次数是（）。【】4.折半查找判定树既是一种（），也是一种（）。【，？】5.顺序查找法的平均查找长度为（）；折半查找法的平均查找长度为（）；分块查找法（以顺序查找确定块）的平均查找长度为（）；分块查找法（以折半查找确定块）的平均查找长度为（）；哈希表查找法采用链接法处理冲突时的平均查找长度为（）。【，】6.对于长度为 n的线性表，若进行顺序查找，则时间复杂度为（）；若进行折半查找，则复杂度为（）；若采用分块查找（假定总块数和每块长度均接近 n的平方），则时间复杂度为（）。【，】7.用二分法查找一个线性表时，该线性表必须具有的特点是（），而分块查找法要求将待查找的表均匀地分

13、成若干块且块中诸记录的顺序可以是任意的，但块与块之间（）。【】8.采用散列技术来实现查找，需要解决的问题有：（）和（）。【】9.在散列存储中，处理冲突有（）和（）两类方法。【】10.（）法构造的哈希函数肯定不会发生冲突。【，？】.5 页 11.在各种查找方法中，平均查找长度与结点个数无关的查找方法为（）。【，？】12.在开散列表上查找健值等于 K 的结点，首先必须计算该健值的（），然后再通过指针查找该结点。13.在索引顺序表上，对于顺序表中的每一块，索引表中有相应的一个“索引项”。每个索引项有两个域：块内最大（）值和块（）位置。【】14.索引顺序表上的查找分两个阶段：一.（）；二.（）。该查找

14、方法称为（）查找。【】15.二叉排序树是一种特殊的、增加了限制条件的二叉树，其限制条件是任一结点的键值（）于其左孩子（及其子孙）的键值且（）于其右孩子（及其子孙）的键值。【】16.在表示一棵二叉排序树的二叉链表上，要找键值比某结点 X的键值（）的结点，只需通过结点 X的右指针到它的右子树中去找。【】17.中序遍历一棵二叉排序树所得的结点访问序列是键值的（）序列。【】18.二叉排序树上的查找长度不仅与（）有关，也与二叉排序树的（）有关。【】19.二叉排序树的查找效率与树的形态有关，当二叉排序树退化为一条单支树时，查找算法退化为（）查找，平均查找长度上升为（）。【，】20.有 n个结点的 AVL树

15、的深度与（）是同数量级的，因而在它上面进行查找的平均查找长度也与（）同数量级。【，？】21.（）查找法的平均查找长度与元素个数 n 个数无关。【】22.在具有 20 个元素的有序表上进行折半查找，则比较一次查找成功的结点数为（），比较二查找成功的结点数为（），比较五次查找成功的结点数为（）。总平均查找长度为（）。【】23.折半查找方法仅适用于这样的表：表中的记录必须（），其存储结构必须是（）。【】24.考虑具有如下性质的二叉树：除叶子结点外，每个结点的值都大于其左子树上的一切结点的值，并小于或等于其右子树上的一切结点的值。现把 9个数 1，2，3，4，5，6，7，8，9填入如图 9.1所示的二

16、叉树中，并使之满足上述性质。（圆圈旁边的数字表示插入结点的序号）【，】25.设线性表 L=（a1，a2，an）（n2），表中元素按值的递增顺序排列。对一个给定的值 k，分别用顺序查找和折半查找与 k 相等的元素，比较次数为 s 和 b，若检索不成功，则 s 和 b 的数据关系是（）。（注：大于、小于或等于）【】26.某顺序存储的表，其中有 10000个元素，已按关键字的值升序排列。现假定对各个元素进行查找的概率是相同的，并且各个元素的关键字都不相同。用顺序查找法查找时，查找成功时的平均比较次数为（），最.6 页 大比较次数为（）。现把 10000个元素按排列顺序划分成若干组，使得每一组中有 g

17、个元素（最后一组可能小于 g）。查找时，先从头一组开始，通过比较各组的最后一个元素的关键项值，找到欲查找的元素所在的组，然后再用顺序查找法找到欲查找的元素。在这种查找法中，使总的比较次数最小的 g是（），此时的平均比较次数是（）。【，】27.长度为 225的表，采用分块查找法，每块的最佳长度是（），应分（）块，若每块的长度为 10，则平均查找长度为（）。【，】28.已知有序表为（13，17，20，32，48，54，65，79，86，91，97），当采用折半查找法查找 86 时需进行（）次比较可确定查找成功。查找 48 时需进行（）次比较可确定查找成功，查找 100时需进行（）次比较才能确定查找

18、不成功。【】四、简答题 1.简述顺序查找、折半查找和分块检索法对被检索表中元素中的要求。若检索表中每个元素概率相同，则对一个长度为 n 的表，用上面三种方法检索时平均查找长度为多少？【，】2.画出长度为 10 的有序表进行折半查找的一棵判定树，并求其等概率下的平均查找长度。【】3.有一个 10000项线性表，若采用分区查找，问分成多少块较理想？平均查找长度为多少？若每块为 40，则平均查找长度为多少？【】4.设有一组关键字19，01，23，14，55，20，84，27，68，11，10，77，采用哈希函数：H(key)=key%13，采用开放地址法的线性探测再散列方法解决冲突，试在 0到 8的

19、 Hash地址空间中对该关键字序列构造 Hash表。【】5.若哈希表的地址范围为 0到 9，Hash函数为 H(key)=(key2+2)mod 9，并采用链地址法处理冲突，画出元素 7，4，5，3，6，2，8，9 依次插入哈希表以后该哈希表的状态。【，】6.假定有 n个关键字，它们具有相同的哈希函数值，用线性探测方法把这 n个关键字存入到哈希表中要做多少次探测？【】7.地址空间为 0-14的散列表中，对关键字序列（JAN，FEB，MAR，APR，MAY，JUN，JUL，AUG，SEP，OCT，NOV，DEC）构造哈希函数：H(key)=floor(i/2)，其中 i为关键字中第一个字母在字母

20、表中的序号。用如下两种处理冲突的方法：（1）线性探测法，（2）链地址法。分别求出这两个哈希表在等概率情况下查找成功和不成功的平均查找长度。【，】8.有一个 400 项的表，欲采用索引顺序查找方法进行查找，问：1)分成多少块最为理想？2)每块的理想长度是什么？3)平均查找长度是多少？【】9.设有一组关键字（19，05，21，24，45，20，68，27，70，11，10），采用哈希函数：H(key)=key%13，采用线性探测再散列方法解决冲突，试在 0到 14 的散列地址空间中对该关键字序列构造哈希函数。并求查找成功和不成功时的平均查找长度。【】10.线性表的关键字集合（47，26，120，0

21、8，39，68，96，23，70，63，57），已知散列函数为：H(key)=key%13，采用拉链法处理冲突。设计出这种链表结构，并计算该表的查找成功和不成功的平均查找长度。【】11.建立一棵具有 13 个结点的判定树，并求其成功和不成功的平均查找长度值各是多少？【】12.分别画出在线性表（06，10，19，24，37，42，50，83）中进行折半查找，查找关键字 10 和 30 的过程。【】13.设二叉排序树中的关键字由 1 到 100内的整数构成，现要查找关键字为 63 的结点，下述关键字序列哪一个是不可能在二叉排序树上查找到的序列？【，】1)12，25，71，68，33，34，37，63 2)92，20，91，24，88，25，36，63.7 页 3)95，22，91，24，94，25，63 4)21，89，77，29，36，38，41，47，63 14.给定表（25，18，48，07，76，52，81，70，92，15）。试按元素在表中的次序将它们依次插入一棵初始为空的二叉排序树，画出插入完成之后的二叉排序树。【】15.二叉树序树中关键字互不相同，则其中最小元无左孩子，最大元无右孩子，此命题是否正确？最小元和最大元一定是叶子吗？一个新结点总是插在二叉排序树的某叶子上吗？【，】