《《数据结构》习题集：第9章 查找(第1次更新2012-5)》由会员分享，可在线阅读，更多相关《《数据结构》习题集：第9章 查找(第1次更新2012-5)（7页珍藏版）》请在金锄头文库上搜索。
1、数据数据结结构构课课后后练习题练习题 第第 9 章章 查查找找第 1 页 共 6 页 北京理工大学珠海学院计算机学院 “数据结构”课程组编制 2011-3-1第第 9 章章 查找查找一、一、选择题选择题1.顺序查找一个共有n个元素的线性表，其时间复杂度为（ ），折半查找一个具有n个元素的有序表，其时 间复杂度为（ ）。【，】 A.O(n) B. O(log2n) C. O(n2) D. O(nlog2n)2.在对长度为n的顺序存储的有序表进行折半查找，对应的折半查找判定树的高度为（ ）。【，】A.n B. C. D. 22( + 1)2( + 1)3.采用顺序查找方式查找长度为n的线性表时，平
2、均查找长度为（ ）。【】 A.n B. n/2 C. (n+1)/2 D. (n-1)/24.采用折半查找方法检索长度为n的有序表，检索每个元素的平均比较次数（ ）对应判定树的高度（设高 度大于等于2）。【】 A.小于 B. 大于 C. 等于 D. 大于等于 5.已知有序表（13，18，24，35，47，50，62，83，90，115，134），当折半查找值为90的元素时，查找成功 的比较次数为（ ）。【】 A.1 B. 2 C. 3 D. 46.对线性表进行折半查找时，要求线性表必须（ ）。【】 A.以顺序方式存储 B. 以链接方式存储 C.以顺序方式存储，且结点按关键字有序排序 D. 以链
3、接方式存储，且结点按关键字有序排序 7.顺序查找法适合于存储结构为（ ）的查找表。【】 A.散列存储 B. 顺序或链接存储 C. 压缩存储 D. 索引存储 8.采用分块查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在 的块时，每块应分（ ）个结点最佳。【】 A.10 B. 25 C. 6 D. 6259.从键盘依次输入关键字的值：t、u、r、b、o、p、a、s、c、l，建立二叉排序树，则其先序遍历序列为（ ），中序遍历序列为（ ）。【，】 A.abcloprstu B. alcpobsrut C. trbaoclpsu D. trubsaocpl 10
4、. 折半查找和二叉排序树的时间性能（ ）。【】 A.相同 B. 不相同 11. 一棵深度为k的平衡二叉树，其每个非终端结点的平衡因子均为0，则该树共有（ ）个结点。 A.2k-1-1 B. 2k-1 C. 2k-1+1 D. 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.
5、小于m的最大偶数 D. 小于m的最大合数 14. 长度为10的按关键字有序的查找表采用顺序组织方式。若采用折半查找方法，则在等概率情况下，查找失败 时的ASL值是（ ）。 A.24/10 B. 24/11 C. 39/10 D. 39/1115. 在表长为n的顺序表中，实施顺序查找，在查找不成功时，与关键字比较的次数为（ ） A.n+1 B. 1 C. n D. n-1数据数据结结构构课课后后练习题练习题 第第 9 章章 查查找找第 2 页 共 6 页 北京理工大学珠海学院计算机学院 “数据结构”课程组编制 2011-3-116. 设哈希函数为H(key)=key%7，一组关键字为（37，21
6、，9，20，30，19，46），哈希表T的地址空间为06， 用线性探测法解决冲突，依次将这组关键字插入T中，得到的哈希表为（ ）。【，】17. 设有一个用线性探测法解决冲突得到的哈希表：哈希函数为H(key)=key%11，若要查找元素14，探测的次数是（ ） A.3 B. 6 C. 7 D. 918. 在哈希函数H(key)=key%m中，一般来讲，m应取（ ）。 A.奇数 B. 偶数 C. 素数 D. 充分大的数 19. 分块查找的时间性能（ ）。 A.低于二分查找B. 高于顺序查找而低于二分查找 C.高于顺序查找D. 低于顺序查找高于二分查找 20. 以下说法错误的是（ ）。 A.哈希法
7、存储的基本思想是由关键字的值决定数据的存储地址 B.哈希表的结点中只包含数据元素自身的信息，不包含任何指针 C.装填因子是哈希法的一个重要参数，它反映哈希表的装填程度 D.哈希表的查找效率主要取决于哈希表造表时选取的散列函数和处理冲突的方法 21. 以下说法正确的是（ ）。 A.前序遍历二叉排序树的结点就可以得到排好序的结点序列 B.任一二叉排序树的平均查找时间都小于用顺序查找法查找同样结点的线性表的平均查找时间 C.对具有相同关键字集合的任一插入序列，得到的二叉排序树的形态都是相同的 D.采用分块查找方法，既能实现线性表所希望的较快的查找速度，又能适应动态变化的需要 22. 已知采用开放地址
8、法解决哈希表冲突，要从此哈希表中删除一个记录，正确的做法是（ ）。【，】 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.3 B. 8 C. 9 D. 1024. 有一个长度为12的有序表，按折
9、半查找法对该表进行查找，在表内各元素查找概率相同的情况下，查找成功 所需的平均比较次数为（ ）。【，】 A.32/12 B. 35/12 C. 37/12 D. 39/12数据数据结结构构课课后后练习题练习题 第第 9 章章 查查找找第 3 页 共 6 页 北京理工大学珠海学院计算机学院 “数据结构”课程组编制 2011-3-125. 如果要求一个线性表既能较快的查找，又能适应动太变化的要求，可以采用（ ）查找方法。【】 A.分块 B. 顺序C. 折半 D. 散列 26. 深度为6的AVL树至少有（ ）个结点。【】A.10 B. 12C. 20 D. 21 27. 哈希表的平均查找长度（ ）。
10、 A.与处理冲突的方法有关而与表的长度无关 B.与处理冲突的方法无关而与表的长度有关 C.与处理冲突的方法有关且与表的长度有关 D.与处理冲突的方法无关且与表的长度无关 28. 若为查找表长度为m的闭散列表采用二次探测再散列处理冲突，对一个元素第1次计算的哈希地址为d，则第3 次计算的哈希地址为（ ）。【】 A.(d+1)%m B. (d-1)%mC. (d+4)%m D. (d-4)%m29. 有数据（49，32，40，6，45，12，56），从空二叉树开始依次插入数据形成二叉排序树，若希望高度最小， 则应选择下列哪个输入序列（ ）。【，】 A.45，12，49，6，40，56，32B. 4
11、0，12，6，32，49，45，56 C.6，12，32，40，45，49，56D. 32，12，6，40，45，56，49 30. 在一棵深度为h的具有n个元素的二叉排序树中，查找所有元素的最长查找长度为（ ）。【】 A.n B. log2nC. (h+1)/2 D. h二、二、判断题判断题1.分块查找方法的平均查找长度低于顺序查找，高于折半查找。 （ ） 【】 2.采用线性探测再散列法处理散列时的冲突，当从哈希表删除一个记录时，不应将这个记录的所在位置置为空， 因为这会影响以后的查找。 （ ） 【】 3.前序遍历二叉排序树的结点就可以得到排好序的结点序列。 （ ） 【】 4.在任一二叉排序
12、树上查找某个结点都小于用顺序查找法查找同样结点的线性表的查找时间。（ ）【】 5.虽然关键字的序列的顺序不一样，但依次生成的二叉排序树却是一样的。（ ）【】 6.对二棵具有相同关键字集合的形状不同的二叉排序树，按中序遍历它们得到的序列的顺序是一样的。（ ）【】 7.在二叉排序树上插入新的结点时，不必移动其他结点，仅需要改动某个结点的指针，由空变为非空即可。（ ）【】 8.在二叉排序树上删除一个结点时，不必移动其他结点，只要将该结点的父结点的相应指针域置空即可。（ ）【】三、三、填空题填空题1.折半查找效率较高，但要求结点（ ）并且要求线性表（ ） ；而对于顺序查找，则线性表的存储方式 （ ） 。 【，】 2.假设在有序线性表 A0A9上进行折半查找，则比较一次查找成功的结点数为（ ），比较二次查找成 功的结点数为（ ），比较三次查找成功的结点数为（ ），比较四次查找成功的结点数为（ ）， 平均查找长度为（ ）。【】 3.在 n 个记录的有序顺序表中进行折半查
