《查找练习题(答案).docx》由会员分享，可在线阅读，更多相关《查找练习题(答案).docx（4页珍藏版）》请在三一文库上搜索。
1、精选资料，欢迎下载查找练习题、单项选择题1. 若查找每个元素的概率相等， 则在长度为 n 的顺序表上查找任一元素的平均查找长度为()。A. nB. n+1C. (n-1)/2D. (n+1)/22. 对于长度为 9 的顺序存储的有序表，若采用折半查找，在等概率情况下的平均查找长度为()。A. 20/9B. 18/9C. 25/9D. 22/93. 对于长度为 18 的顺序存储的有序表，若采用折半查找，则查找第15 个元素 ( 从 1 开始数) 的比较次数为 () 。A. 3B. 4C. 5D. 64. 对于顺序存储的有序表(5,12,20,26,37,42,46,50,64) ，若采用折半查找
2、，则查找元素26 的比较次数为 () 。A. 2B. 3C. 4D. 55. 对具有 n 个元素的有序表采用折半查找，则算法的时间复杂度为 () 。A. O(n)B. O(n 2)C. O(1)D. O(log 2n)6. 在索引查找中， 若用于保存数据元素的主表的长度为 144， 它被均分为12子表， 每个子表的长度均为12，则索引查找的平均查找长度为() 。A. 13B. 24C. 12D. 797. 从具有 n 个结点的二叉排序树中查找一个元素时，在平均情况下的时间复杂度大致为()。A. O(n)B. O(1)C. O(log 2n) D. O(n 2)8. 从具有 n 个结点的二叉排序
3、树中查找一个元素时， 在最坏情况下的时间复杂度为 () 。A. O(n)B. O(1)9. 若根据查找表(23,44,36,48,52,73,64,58)则元素 64 的哈希地址为 () 。A. 4B. 8C. O(log 2n)D. O(n 2)建立哈希表，采用h(K尸K%13计算哈希地址,C. 12D. 1310. 若根据查找表建立长度为 m 的哈希表，采用线性探测法处理冲突，假定对一个元素第一次计算的哈希地址为d,则下一次的哈希地址为()。A. dB. d+1C. (d+1)/mD. (d+1)%m、填空题1 . 以顺序查找方法从长度为 n 的顺序表或单链表中查找一个元素时， 平均查找长
4、度为 _ (n+1) /2 。2 . 以折半查找方法从长度为 n 的有序表中查找一个元素时，平均查找长度约等于_log 2n 的向上取整减1 ，时间复杂度为_O(log 2n) 。3 . 以折半查找方法在一个查找表上进行查找时， 该查找表必须组织成_ 顺序 存储的有序表。4 .从有序表(12,18,30,43,56,78,82,95)中分别折半查找 43和56元素时，其比较次数分另 为 1 和 _3。5 .在索引查找中，假定查找表(即主表)的长度为 96,被等分为8个子表，则进行索引查 找的平均查找长度为_11。6 .在一棵二叉排序树中，每个分支结点的左子树上所有结点的值一定一小于等于 该结点
5、的值，右子树上所有结点的值一定大于等于 该结点的值。7 .对一棵二叉排序树进行中序遍历时，得到的结点序列是一个升序_(升序或降序)。8 .对线T表(18,25,63,50,42,32,90)进行哈希存储时，若选用 H(K尸K % 9作为哈希函数，则哈希地址为0的元素有 2 个，哈希地址为 5的元素有_2 个。三、判断题1 .在索引顺序结构的搜索中，对索引表既可以采取顺序搜索，也可以采用折半搜索。(1)2 .对二叉排序树的中序遍历结果是结点的升序排列。(1)3 .执行折半查找法要求查找表必须为顺序结构。(1)4 . 100个元素的有序表中，折半查找成功的最大查找长度为8。( 1 )四、应用题，试
6、画出对应的折半1 .已知一个顺序存储的有序表为(15,26,34,39,45,56,58,63,74,76)查找判定树，求出其平均查找长度。平均查找长度=29/102 .假定一个线性表为 (38,52,25,74,68,16,30,54,90,72),画出按线性表中元素的次序生成的一棵二叉排序树，求出其平均查找长度。3 .假定一个待哈希存储的线性表为(32,75,29,63,48,94,25,46,18,70),哈希地址空间为HT13,若采用除留余数法构造哈希函数H(K)=K %11和拉链法处理冲突，试画出该哈希表，并计算该各个元素的平均查找长度。012345678910111222570754829平均查找长度为13/11Welcome !欢迎您的下载,资料仅供参考!