下面是小编为大家整理的聊一聊8,,查找,供大家参考。
8
查找 8.1
选择题 1 ． 顺序查找法适合于存储结构为（
）
的线性表。
A）
散列存储
B）
顺序存储或链接存储
C）
压缩存储
D）
索引存储 【答案】
B 2． 下面哪些操作不属于静态查找表（
）
A）
查询某个特定元素是否在表中
B）
检索某个特定元素的属性 C）
插入一个数据元素
D）
建立一个查找表 【答案】
C 3． 下面描述不正确的是（
）
A）
顺序查找对表中元素存放位置无任何要求， 当 n 较大时， 效率低。
B）
静态查找表中关键字有序时， 可用二分查找。
C）
分块查找也是一种静态查找表。
D）
经常进行插入和删除操作时可以采用二分查找。
【答案】
D 4． 散列查找时， 解决冲突的方法有（
）
A）
除留余数法
B）
数字分析法
C）
直接定址法
D）
链地址法 【答案】
D 5． 若表中的记录顺序存放在一个一维数组中， 在等概率情况下顺序查找的平均查找长度为（
）
A）
O（1 ）
B）
O(log2n)
C）
O(n)
D）
O(n2) 【答案】
C 6． 对长度为 4 的顺序表进行查找， 若第一个元素的概率为 1 /8， 第二个元素的概率为 1 /4， 第三个元素的概率为 3/8， 第四个元素的概率为 1 /4， 则查找任一个元素的平均查找长度为（
）
A）
1 1 /8
B）
7/4
C）
9/4
D）
1 1 /4 【答案】
C 【解析】
对顺序表查找， ASL＝ ， 代入题目得：
ASL=4*(1 /8)+3*(1 /4)+2*(3/8)+1*(1 /4)=9/4 7． 静态查找表与动态查找表二者的根本差别在于（
）
A）
它们的逻辑结构不一样
B）
施加在其上的操作不同
C）
所包含的数据元素的类型不一样
D）
存储实现不一样 【答案】
B 8． 若查找表中的记录按关键字的大小顺序存放在一个一维数组中， 在等概率情况下二分法查找的平均检索长度是（
）
A）
O(n)
B）
O(log2n)
C）
O(nlog2n)
D）
O((log2n)2)
【答案】
B 9． 对有 1 4 个数据元素的有序表 R[1 4]（假设下标从 1 开始）
进行二分查找， 搜索到 R[4]的关键码等于给定值， 此时元素比较顺序依次为（
）
。
A）
R[1 ]， R[2]， R[3]， R[4]
B）
R[1 ]， R[1 3]， R[2]， R[3] C）
R[7]， R[3]， R[5]， R[4]
D）
R[7]， R[4]， R[2]， R[3] 【答案】
C 1 0． 设有一个长度为 1 00 的已排好序的表， 用二分查找进行查找， 若查找不成功， 至少比较（
）次。
A）
9
B）
8
C）
7
D）
6
【答案】
B 【解析】
二分查找不成功时和给定值进行比较的关键字个数最多不超过二叉判定树的深度。
1 00 个元素查找表的判定树深为 8（64<1 00<1 28）
。
1 1 ． 请指出在顺序表{2,5,7,1 0,1 4,1 5,1 8,23,35,41 ,52}中， 用二分法查找关键码 1 2 需做（
）
次关键码比较。
A）
2
B）
3
C）
4
D）
5 【答案】
C 1 2． 从具有 n 个结点的二叉排序树中查找一个元素时， 在最坏情况下的时间复杂度为 (
) 。
A )O (n)
B）
O（1 ）
C）
O (log 2 n)
D）
O (n 2 )
【答案】
C 1 3． 分块查找时确定块的查找可以用顺序查找， 也可以用（
）
， 而在块中只能是（
）
A）
静态查找， 顺序查找
B）
二分查找， 顺序查找
C）
二分查找， 二分查找
D）
散列查找， 顺序查找 【答案】
B 1 4． 采用分块查找时， 若线性表中共有 625 个元素， 查找每个元素的概率相同， 假设采用顺序查找来确定结点所在的块时， 每块应分（
）
个结点最佳。
A）
1 0
B）
25
C）
6
D）
625 【答案】
B 1 5． 采用分块查找法（块长为 s， 以二分查找确定块）
查找长度为 n 的线性表时， 每个元素的平均查找长度为（
）
A）
s+n
B）
log2n＋s/2
C）
log2 (n/s+1 )+s/2
D）
(n+s)/2
【答案】
C 1 6． 对一棵二叉排序树根结点而言， 左子树中所有结点与右子树中所有结点的关键字大小关系是 （
）
A）
小于
B）
大于
C）
等于
D）
不小于 【答案】
A
1 7． 若二叉排序树中关键字互不相同， 则下面命题中不正确的是（
）
A）
最小元和最大元一定是叶子 B）
最大元必无右孩子 C）
最小元必无左孩子
D）
新结点总是作为叶结点插入二叉排序树
【答案】
A 1 8． 设二叉排序树中关键字由 1 至 1 000 的整数构成， 现要查找关键字为 363 的结点， 下述关键字序列（
）
不可能是在二叉排序树上查找到的序列?
A）
2,252,401 ,398,330, 344,397,363 B）
924, 220, 91 1 , 244, 898, 258, 362, 363 C）
2, 399, 387, 21 9, 266, 382, 381, 278, 363
D）
925, 202, 91 1 , 240, 91 2, 245, 363 【答案】
D 1 9． 在初始为空的散列表中依次插入关键字序列(MON,TUE,WED,THU,FRI,SAT,SUN),散列函数为H(k)=i MOD 7， 其中， i 为关键字 k 的第一个字母在英文字母表中的序号， 地址值域为 [0:6] ， 采用线性再散列法处理冲突。
插入后的散列表应该如（
）
所示。
A）
0
1
2
3
4
5
6
THU
TUE
WED
FRI
SUN
SAT
MON
B）
0
1
2
3
4
5
6
TUE
THU
WED
FRI
SUN
SAT
MON
C）
0
1
2
3
4
5
6
TUE
THU
WED
FRI
SAT
SUN
MON
D）
0
1
2
3
4
5
6
TUE
THU WED
SUN
SAT
FRI
MON 【答案】
B 20． 若根据查找表建立长度为 m 的散列表， 采用线性探测法处理冲突， 假定对一个元素第一次计算的散列地址为 d ， 则下一次的散列地址为 (
) 。
A）
d
B）
(d+1 )%m
C）
(d+1 )/m
D）
d+1 【答案】
B 21 ． 若根据查找表建立长度为 m 的散列表， 采用二次探测法处理冲突， 假定对一个元素第一次计算的散列地址为 d ， 则第四次计算的散列地址为 (
) 。
A )(d+1 )%m
B）
(d-1 )%m
C）
(d+4)%m
D）
(d-4)%m
【答案】
D 22． 下面有关散列查找的说法中正确的是（
）
A）
直接定址法所得地址集合和关键字集合的大小不一定相同。
B）
除留余数法构造的哈希函数 H(key)=key MOD p， 其中 P 必须选择素数。
C）
构造哈希函数时不需要考虑记录的查找频率。
D）
数字分析法适用于对哈希表中出现的关键字事先知道的情况。
【答案】
D 23． 下面有关散列冲突解决的说法中不正确的是（
）
A）
处理冲突即当某关键字得到的哈希地址已经存在时， 为其寻找另一个空地址。
B）
使用链地址法在链表中插入元素的位置随意， 即可以是表头表尾， 也可以在中间。
C）
二次探测能够保证只要哈希表未填满， 总能找到一个不冲突的地址。
D）
线性探测能够保证只要哈希表未填满， 总能找到一个不冲突的地址。
【答案】
C 24． 设哈希表长 m=1 4， 哈希函数 H(key)=key%1 1 。
表中已有 4 个结点：
addr(1 5)=4， addr(38)=5，addr(61 )=6， addr(84)=7 其余地址为空， 如用二次探测处理冲突， 关键字为 49 的结点的地址是（
）
A）
8
B）
3
C）
5
D）
9 【答案】
D 8.2 填空题 1 ． 在散列函数 H(key)=key%p 中， p 应取_____________。
【答案】
素数 2． 采用分块查找法（块长为 s， 以顺序查找确定块）
查找长度为 n 的线性表时的平均查找长度为_____________。
【答案】
(n/s+1 ) /2+1
3． 己知一个有序表为(1 2,1 8,20,25,29,32,40,62,83,90,95,98)， 当二分查找值为 29 和 90 的元素时， 分别需要_____________次和_____________次比较才能查找成功； 若采用顺序查找时， 分别需要_____________次和_____________次比较才能查找成功。
【答案】
（1 ）
4
（2）
4
（3）
5
（4）
1 0 4． 从一棵二叉排序树中查找一个元素时， 若元素的值等于根结点的值， 则表明
_____________ ，若元素的值小于根结点的值， 则继续向 _____________查找， 若元素的值大于根结点的值， 则继续向 _____________ 查找。
【答案】
（1 ）
查找成功
（2）
左子树
（3）
右子树 5． 二分查找的存储结构仅限于 _____________， 且是_____________。
【答案】
（1 ）
顺序存储结构
（2）
有序
6． 假设在有序线性表 A[1 ..20]上进行二分查找， 则比较一次查找成功的结点数为 _____________个 ，比较二次查找成功的结点数为_____________ ， 比较三次查找成功的结点数为_____________ ， 比较四次查找成功的结点数为_____________ ， 比较五次查找成功的结点数为_____________， 平均查找长度为_____________ 。
【答案】
（1 ）
1
（2）
2
（3）
4
（4）
8
（5）
5
（6）
3.7
7． 在对有 20 个元素的递增有序表作二分查找时， 查找长度为 5 的元素的下标从小到大依次为_____________。
（设下标从 1 开始）
【答案】
4， 9， 1 4， 1 7， 20 8． 对于线性表（70,34,55,23,65,41 ,20,1 00）
进行散列存储时， 若选用 H(K)=K%9 作为散列函数， 则散列地址为 1 的元素有_____________个， 散列地址为 7 的元素有_____________
个。
【答案】
（1 ）
2 （2）
2 9． 索引顺序表上的查找分两个阶段：
_____________、 _____________。
【答案】
（1 ）
确定待查元素所在的块
（2）
在块内查找待查的元素
1 0． 分块查找中， 要得到最好的平均查找长度， 应对 256 个元素的线性查找表分成_____________块，每块的最佳长度是_____________。
若每块的长度为 8， 则等概率下平均查找长度为_____________。
【答案】
（1 ）
1 6
（2）
1 6
（3）
21 【解析】
分块查找的平均查找长度由两部分组成——查找索引表确定所在块的平均查找长度 Lb 和在块中查找元素的平均查找长度 Lw， 即 ASLbs=Lb+Lw=(b+s)/2+1 ， 其 中 s 为每块的长度， b 为所分的快数。由数学知识可知当 s= 时， ASLbs 可取得最小值 ＋1 。
因此， 可得每块的最佳长度是 1 6， 应将查找表分为 1 6 块。
若每块的长度为 8， 则 b=32,因此 ASLbs=Lb+Lw=(b+s)/2+1 =21 。
1 1 ． _____________是一棵二叉树， 如果不为空， 则它必须满足下面的条件：
A）
若左子树不空， 则左子树上所有结点的值均小于根的值。
B）
若右子树不空， 则右子树上所有结点的值均大于根的值。
C）
其左右子树均为二叉排序树。
【答案】
二叉排序树 1 3． 假定有 k 个关键字互为同义词， 若用线性探测法把这些同义词存入散列表中， 至少要进行_____________次探测。
【答案】
1 +2+3...+(k-1 )+k=k(k+1 )/2 【解析】
在散列表的一连串连续空间内， 第一个关键字只需探测一次， 第二个就要探测 2 次， 如此这般， 第 k 个关键字就要探测 k 次才能找到位置存放。
8.3 判断题 1 ． 对查找进行时间分析时， 只需要考虑查找成功的平均情况。
（
）
【答案】
× 【解析】
大多数情况下， 特别查找表中记录数 n 很大时， 查找不成功的概率可以忽略不计。
但是， 当查找不成功的情况不能忽视时， 查找算法的平均查找长度应是查找成功时的平均查找长度与查找不成功时的平均查找长度之和。
2． 在索引顺序表上实现分块查找， 在等概率查找情况下， 其平均查找长度不仅与表的个数有关， 而且与每一块中的元素个数有关。
（
）
【答案】
√
3． 构造一个好的哈希函数必须均匀， 即没有冲突。
（
）
【答案】
× 【解析】
一个好的哈希函数必须均匀， 并不代表完全没有冲突， 而是尽量减少冲突。
4． 在一定情况下， 有可能设计出无冲突的散列函数 H。
（
）
【答案】
√
5. 二分查找只适用于有序表， 包括有序的顺序表和有序的链表。
（
）
【答案】
× 【解析】
二分查找只适用于顺序表， 而不能在链表结构中采用。
因为链表查找都是从头指针开始。
6． 对给定的关键字集合， 以不同的次序插入初始为空的树中， 有可能得到同一棵二叉排序树。
（
）
【答案】
√
7． 分块查找适用于任何有序表或者无序表。
（
）
【答案】
× 【解析】
分块查找适用于任何有序表或者分块有序表， 而不适用于任意的无序表。
8． 在用线性探测法解决冲突所构造的散列表中， 每组同义词中至少有一个元素的地址正好等于其散列地址。
（
）
【答案】
× 【解析】
当存在堆积的冲突时， 可能没有一个元素地址等于其计算所得的散列地址。
9． 对一棵二叉排序树中序遍历一定得到一个关键字的有序序列。
（
）
【答案】
√
1 0． 所谓冲突即是两个关键字的值相同的元素， 其散列地址相同。
（
）
【答案】
× 【解析】
冲突是指两个关键字的值不相同的元素， 计算得到的散列地址相同。
1 1 ． 二叉判定树和二叉排序树一样， 都不是唯一的。
（
）
【答案】
× 【解析】
对于同一组结点， 由于建立二叉排序树时插入结点的先后次序不同， 所构成的二叉排序树的形态及深度也不同， 所以含有 n 个结点的二叉排序树不唯一。
但二叉判定树却是唯一的。
1 2． 若二叉树中每个结点的值均大于其左孩子的值， 小于其右孩子的值， 则该二叉树一定是二叉排序树。
（
）
【答案】
× 【解析】
判定一棵二叉树是否是二叉排序除上面两个条件外， 还必须满足第三个条件， 即其左右子树也是二叉排序树。
1 3． 分块查找中， 每一块的大小是相同的。
（
）
【答案】
× 【解析】
最末一块， 可以不是整块， 前面块的大小必须相同。
1 4． 对一个有序表作二分查找，
查找每个元素所需的查找次数均比用顺序查找所需的查找次数要少。（
）
【答案】
× 【解析】
顺序查找时最少的比较次数为 1 ， 它的比较次数小于位于二叉判定树第二层以上的结点。
二分查找时最多的比较次数为二叉判定树的深度。
1 5． 散列表的查找效率主要取决于所选择的散列函数与处理冲突的方法。
（
）
【答案】
√
8.4 应用题 1 ． 顺序查找...
