首页 › 题库 › Python编程考级 › 4.2 对分查找

Python编程四级 题库

共 21 道题 ,第 1 / 2 页 · 按题型筛选,点「查看答案」核对解析
章节 4.2 对分查找 清除
1 单选题 适中 Python编程考级 ·Python编程四级 · 4.2 对分查找

对元素规模为n的列表进行对分查找时,无论是否找到,至多进行()次查找?

A
n
B
(n+1)/2
C
n-1
D
log2n+1
答案与解析
正确答案:D

对元素规模为n的列表进行对分查找时,无论是否找到,至多进行 log2n+1( log2n+1表示大于或等于 log2n的最小整数)次查找就能得到结果。

题目详情
2 单选题 适中 Python编程考级 ·Python编程四级 · 4.2 对分查找

对于数列3,8,11,15,17,19,25,30,44,采用“二分查找”法查找8,需要查找多少次?( )

A
5
B
4
C
3
D
2
答案与解析
正确答案:D

按二分查找法的规律,每次先查找中间值,进行比较。

题目详情
3 单选题 适中 Python编程考级 ·Python编程四级 · 4.2 对分查找

不超过100个元素的有序数列,使用二分查找能找到指定的元素,可能的查找次数不包括?( )

A
1次
B
6次
C
7次
D
8次
答案与解析
正确答案:D

按照二分查找法的规律,100个元素的有序列表,不管是否找到,至多查找7次。

题目详情
4 单选题 适中 Python编程考级 ·Python编程四级 · 4.2 对分查找

已知有n本按照书名拼音排序好的图书,使用对分查找法搜索其中任何一本书,最多查找次数为6次,则n的值可能为?( )

A
20
B
50
C
80
D
110
答案与解析
正确答案:B

对规模为n的数据进行对分查找时,无论是否查找到,至多进行 |log2n|+1次(|log2n|表示小于等于log2n的最大整数),因此25≤n<26,即32≤n<64。

题目详情
5 单选题 适中 Python编程考级 ·Python编程四级 · 4.2 对分查找

对于序列98,88,76,65,48,24,12,12,8,1,采用“对分查找”法查找8,需要查找多少次? ( )

A
5
B
4
C
3
D
2
答案与解析
正确答案:C

按二分查找法的规律,每次先查找中间值,进行比较。

题目详情
6 单选题 适中 Python编程考级 ·Python编程四级 · 4.2 对分查找

对于数列1,2,8,11,15,17,19,25,30,45,采用“二分查找”法查找11,需要查找多少次?( )

A
5
B
4
C
3
D
2
答案与解析
正确答案:B

按二分查找法的规律,每次先查找中间值,进行比较。

题目详情
7 单选题 适中 Python编程考级 ·Python编程四级 · 4.2 对分查找

有n个按名称排序的商品,使用对分查找法搜索任何一商品,最多查找次数为5次,则n的值可能为?(?)

A
5
B
15
C
30
D
35
答案与解析
正确答案:C

对分查找最多查找次数m与个数之间n的关系是:n对2的对数的取整后加1,现在最多查找次数是5次,因此n的取值范围在[2^4+1,2^5]即[16,31]之间,因此选C。

题目详情
8 单选题 适中 Python编程考级 ·Python编程四级 · 4.2 对分查找

张老师有n(范围在1到15之间)个礼物分给同学们,他请同学们猜礼物的数量,请问同学们猜几次后肯定知道礼物的数量(不算运气成分第1次或第2次就猜到)?( )

A
15
B
7
C
4
D
3
答案与解析
正确答案:C

二分查找特征,15个礼物,每次对半猜,4次后肯定知道结果。

题目详情
9 单选题 适中 Python编程考级 ·Python编程四级 · 4.2 对分查找

二分查找又称折半查找,下列数列中适合二分查找算法的是?

A
11 99 4 25 3 39
B
43 71 78 81 6 55
C
67 62 68 4 1 17
D
85 78 59 53 19 18
答案与解析
正确答案:D

根据二分查找的实现原理,首先数列元素必须是有序的。

题目详情
10 单选题 适中 Python编程考级 ·Python编程四级 · 4.2 对分查找

在32枚崭新的金币中,有一枚外表与真金币完全相同的假币(质量小一点),现在只有一台天平,则应用二分法的思想最多称几次就可以发现这枚假币?

A
4
B
5
C
6
D
7
答案与解析
正确答案:B

二分查找法,每次都通过跟区间的中间元素对比,将待查找的区间缩小为之前的一半,直到找到要查找的元素,或者区间被缩小为 0。

题目详情
11 单选题 适中 Python编程考级 ·Python编程四级 · 4.2 对分查找

某同学用对分查找和顺序查找在数字序列“1,3,5,8,15,21,35,65”中查找数字15,两种方法都能访问到的下列数字是?

A
3
B
5
C
8
D
34
答案与解析
正确答案:C

顺序查找数字15,访问的数字是1,3,5,8,15;使用二分查找数字15,访问到的数字依次是8,21,15;数字8是两种方法都访问到。因此选C。

题目详情
12 单选题 适中 Python编程考级 ·Python编程四级 · 4.2 对分查找

两位同学玩猜数字游戏,规则如下:一方在心里默想一个范围在1-100之间的数,如果另一方猜的数字比对方想的要大,就说大了;如果猜的数字比想的要小,就说小了,直到猜中数字。那么使用二分查找法最多需要猜测的次数是?( )

A
10
B
8
C
7
D

6

答案与解析
正确答案:C

相当于用二分法在1-100之间查找某个数字。

题目详情
13 单选题 适中 Python编程考级 ·Python编程四级 · 4.2 对分查找

不超过 20 个元素的降序数列,使用对分查找能找到指定的元素,可能的查找次数不包括?( )

A
3
B
4
C
5
D
6
答案与解析
正确答案:D
这道题暂未补解析。
题目详情
14 单选题 适中 Python编程考级 ·Python编程四级 · 4.2 对分查找

有6位学生的身高分别为“166、168、169、171、172、175”,其中小王的身高为172,若采用二分查找,则需要找多少次才能够找到小王?( )

A
1
B
2
C
3
D
4
答案与解析
正确答案:B

二分查找思想。

题目详情
15 单选题 适中 Python编程考级 ·Python编程四级 · 4.2 对分查找

一款经典的猜数字游戏:甲先在50以内随意写一个数字,乙开始猜,如果乙猜的比甲写的数大了,甲就说大了,反之,则说小了。请问根据对分查找思想,乙最多用多少次能猜出甲写的正确数字?( )

A
10
B
8
C
6
D

4

答案与解析
正确答案:C

折半查找算法,因为答案所在范围区间为50以内的数字,50介于2^5(32)与2^6(64)之间,所以最大折半查次数是6。

题目详情
16 单选题 适中 Python编程考级 ·Python编程四级 · 4.2 对分查找
在有序列表 [2, 5, 8, 12, 16, 23, 38, 56, 72, 91] 中,用二分查找法寻找元素23,需要查找多少次?( )
A
2
B
3
C
4
D
5
答案与解析
正确答案:B
初始化左边界为列表起始位置,右边界为末尾位置。计算中点位置,取左右边界的中间索引。比较中点元素与目标值:若相等,则查找结束;若目标值小于中点元素,则调整右边界至中点前一位;若目标值大于中点元素,则调整左边界至中点后一位。重复上述过程,每次迭代均重新计算中点并进行比较,直到找到目标值或边界条件不再满足。记录每次比较作为一次查找操作。
题目详情
17 单选题 适中 Python编程考级 ·Python编程四级 · 4.2 对分查找
二分查找又称折半查找,是一种应用于有序数列的高效查找算法。下列数列中适合二分查找算法的是?( )
A
11 99 4 25 3 39
B
43 71 78 81 6 55
C
67 62 68 4 1 17
D
85 78 59 53 19 18
答案与解析
正确答案:D
二分查找要求数据序列在逻辑上保持有序,即元素按非递减或非递增顺序排列。算法通过比较中间元素缩小查找范围,每次将搜索区间减半。若序列无序,则中间元素无法作为划分区间的依据,查找过程失效。因此,适用二分查找的序列必须满足任意位置i,其前后元素符合单调关系。检查给定序列时,需验证整体是否呈现持续非递减或非递增趋势,只要存在破坏单调性的元素对,该序列即不满足二分查找的前提条件。
题目详情
18 单选题 适中 Python编程考级 ·Python编程四级 · 4.2 对分查找

光明小学有128位同学参加夏令营,老师为这些学生从1~128编上号码。现在老师随机抽取一个号码,让小明找到这位同学,小明想用二分查找的方法去查找,请问最差情况下需要查找几次才能找到这位同学?( )

A
5
B
6
C
7
D
8
答案与解析
正确答案:C

128位同学可以这样分解:128->64->32->16->8->4->2->1

即最多查找7次

题目详情
19 单选题 适中 Python编程考级 ·Python编程四级 · 4.2 对分查找

小明班上有50人,数学成绩已经由高到低排列,使用二分查找查找出小明的成绩,至多进行几次查找?( )

A
50次
B
8次
C
7次
D
6次
答案与解析
正确答案:D

考查二分查找法的实施过程,对50人进行6次即可查找到。

题目详情
20 判断题 偏易 Python编程考级 ·Python编程四级 · 4.2 对分查找

二分查找又称对折半查找,例如:在数列34、17、25、9、10、3中查找3,适合采用二分查找法。( )

A
对
B
错
答案与解析
正确答案:错

二分查找是一种应用于有序数列的高效查找算法。

题目详情