关键词不能为空

当前您在: 主页 > 高中公式大全 >

李绩煮粥:查找练习题(答案)

作者:高考题库网
来源:https://www.bjmy2z.cn/gaokao
2020-11-24 06:37
tags:折半查找的平均查找长度公式

燕山大学是985还是211-普通话水平测试报名

2020年11月24日发(作者:奚业胜)
《查找》练习题
一、单项选择题
1. 若查找每个元素的概率相等,则在长度为n的顺序表上查找任一元素的平均查找长度为
( )。
A. n
为( )。
A. 209
数)的比较次数为( )。
A. 3
26的比较次数为( )。
A. 2
A. O(n)
B. 3
B. O(n)
2
B. n+1 C. (n-1)2 D. (n+1)2
2. 对于长度为9的顺序存储的有序表,若采用折半查找,在等概率情况下的平均查找长度
B. 189 C. 259 D. 229
3. 对于长度为18的顺序存储的有序表,若采用折半查找,则查找第15个元素(从1开始
B. 4 C. 5 D. 6
4. 对于顺序存储的有序表(5,12,20,26,37, 42,46,50,64),若采用折半查找,则查找元素
C. 4
C. O(1)
D. 5
D. O(log
2
n)
5. 对具有n个元素的有序表采用折半查找,则算法的时间复杂度为( )。
6. 在索引查找中,若用 于保存数据元素的主表的长度为144,它被均分为12子表,每个子
表的长度均为12,则索引查找的 平均查找长度为( )。
A. 13
( )。
A. O(n) B. O(1) C. O(log
2
n) D. O(n)
8. 从具有n个结点的二叉排序树中查找一个元素时,在最坏情况下的时间复杂度为( )。
A. O(n) B. O(1) C. O(log
2
n) D. O(n)
9. 若根据查找表(23,44,36 ,48,52,73,64,58)建立哈希表,采用h(K)=K%13计算哈希地址,
则元素64的 哈希地址为( )。
A. 4 B. 8 C. 12 D. 13
10. 若根据查找表建立长度为m的哈希表,采用线性探测法处理冲突,假定对一个元素 第一
次计算的哈希地址为d,则下一次的哈希地址为( )。
A. d B. d+1 C. (d+1)m D. (d+1)%m
二、填空题
1. 以顺序查找方法从长度为n的顺序表或单链表中查找一个元素时,平均查找长度为____
(n+1)2____。
2. 以折半查找方法从长度为n的有序表中查找一个元素时,平均查找长 度约等于
__log
2
n______的向上取整减1,时间复杂度为___O(lo g
2
n) _____。
3. 以折半查找方法在一个查找表上进行查找时,该查找 表必须组织成__顺序______存储的
2
2
B. 24 C. 12 D. 79
7. 从具有n个结点的二叉排序树中查找一个元素时,在平均情况下的时间复杂度大致为
__有序__表。
4. 从有序表(12,18,30,43,56,78,82,95)中分别折半查找43和56元素 时,其比较次数分别为
___1_____和__3______。
5. 在索引查找中,假 定查找表(即主表)的长度为96,被等分为8个子表,则进行索引查
找的平均查找长度为__11__ ___。
6. 在一棵二叉排序树中,每个分支结点的左子树上所有结点的值一定___小于等于__ ___该
结点的值,右子树上所有结点的值一定___大于等于_____该结点的值。
7. 对一棵二叉排序树进行中序遍历时,得到的结点序列是一个__升序__(升序或降序)。
8. 对线性表(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 )
四、应用题
1. 已知一个顺序存储的有序表为(15,26,34,39,45,56,58,63,74,76 ),试画出对应的折半查找判
定树,求出其平均查找长度。
45
26
34< br>39
56
58
63
15
74
76
平均查找长 度=2910
2. 假定一个线性表为(38,52,25,74,68,16,30,54,90, 72),画出按线性表中元素的次序生成的一
棵二叉排序树,求出其平均查找长度。
3825
1630
68
54
72
52
74
90
3. 假定一个待哈希存储的线性表为(32,75,29,63,48,94,25,46,1 8,70),哈希地址空间为
HT[13],若采用除留余数法构造哈希函数H(K)=K % 11和拉链法处理冲突,试画出该
哈希表,并计算该各个元素的平均查找长度。
0

1

2

46
3

25
4

70
5

6


94
7

18
29
8

8
9

75
10
2
32
11

12



48

平均查找长度为1311

中秋佳节-如何挣钱快


吹唢呐为什么寿命短-女生用的笔记本电脑


深职院专业-连贯


完全倒装和部分倒装的区别-大专可以考律师证吗


导函数的基本公式-seem的过去式


rna的功能-有什么词语


上什么学校好-试题答案网


上班族-c是周长还是面积



本文更新与2020-11-24 06:37,由作者提供,不代表本网站立场,转载请注明出处:https://www.bjmy2z.cn/gaokao/459766.html

查找练习题(答案)的相关文章