首页 › 题库 › Python编程考级 › 4 分治算法

Python编程四级 题库

共 70 道题 ,第 2 / 4 页 · 按题型筛选,点「查看答案」核对解析
章节 4 分治算法 清除
21 单选题 适中 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。

题目详情
22 单选题 适中 Python编程考级 ·Python编程四级 · 4.1 分治思想

下列有关分治算法思想的描述不正确的是?(?)

A
将问题分解成的子问题具有相同的模式
B
当问题足够小时,可以直接求解
C
可以将子问题的结果合并成原问题的解
D
将问题分解出的各个子问题相互包含,相互之间可以有公共子问题
答案与解析
正确答案:D

将问题分解出的各个子问题是相互独立的,即子问题之间不包含公共子子问题

题目详情
23 单选题 适中 Python编程考级 ·Python编程四级 · 4.1 分治思想

下列问题使用分治算法思想的是?(?)

A
求100以内的素数
B
求100个整数之和
C
求斐波那契数列第n项
D
快速排序算法对n个数排序
答案与解析
正确答案:D

快速排序算法使用了分治算法。因此选D。

题目详情
24 单选题 适中 Python编程考级 ·Python编程四级 · 4.1 分治思想

关于分治算法特征的描述中,错误的是?( )

A
当问题的规模缩小到一定的程度就可以容易地解决;
B
问题可以分解为若干个规模较小的相同问题;
C
该问题所分解出的各个子问题是可以相互独立,也可以相互交叉;
D
该问题分解出的子问题的解可以合并为该问题的解。
答案与解析
正确答案:C

该问题所分解出的各个子问题是相互独立,即该问题具有最优子结构性质。

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

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

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

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

题目详情
26 单选题 适中 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

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

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

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

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

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

题目详情
28 单选题 适中 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。

题目详情
29 单选题 适中 Python编程考级 ·Python编程四级 · 4.1 分治思想

《阅微草堂笔记》里描述了槐树果实“响豆”,在夜里爆响,这种豆一棵树只有一粒,难以辨认出。所以古人就等槐树开花结果后,用许多布囊分别贮存豆荚,用来当枕头。夜里如果没有听到声音,便扔掉。如果有爆响声。然后把这一囊的豆荚又分成几个小囊装好,夜里再枕着听……如此这么分下去直到找到响豆。以上故事体现的算法是?( )

A
顺序查找
B
枚举算法
C
解析算法
D
分治算法
答案与解析
正确答案:D

分治算法的特征之一,就是将一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题。

题目详情
30 单选题 适中 Python编程考级 ·Python编程四级 · 4.1 分治思想

下列哪项不是分治算法所具有的特征?( )

A
求解问题的规模缩小到一定的程度就能够容易地解决
B
求解题可以分解为若干个规模较小的不同问题
C
利用求解问题分解出的子问题的解可以合并为该问题的解
D
求解问题所分解出的各个子问题是相互独立的
答案与解析
正确答案:B

求解问题可以分解为若干个规模较小的相同问题。

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

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

A
10
B
8
C
7
D

6

答案与解析
正确答案:C

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

题目详情
32 单选题 适中 Python编程考级 ·Python编程四级 · 4.1 分治思想

下列有关分治算法思想的描述不正确的是?( )

A

将问题分解成的子问题具有相同的模式。

B

将问题分解出的各个子问题相互之间有公共子问题。

C

当问题足够小时,可以直接求解。

D

可以将子问题的求解结果合并成原问题的解。

答案与解析
正确答案:B

将问题分解出的各个子问题相互之间没有公共子问题。

题目详情
33 单选题 适中 Python编程考级 ·Python编程四级 · 4.1 分治思想

以下关于分治算法的描述正确的是?( )

A
各个子问题既相互独立又相互联系
B
问题可以分解成若干个规模较小的相同问题
C
可以直接对问题进行求解
D
子问题的解不能合并成原问题的解
答案与解析
正确答案:B

分治算法的特征,各个子问题相互独立,子问题的求解可以合并成原问题的解。

题目详情
34 单选题 适中 Python编程考级 ·Python编程四级 · 4.1 分治思想

下列选项中哪一项使用了分治算法?( )

A
二分搜索
B
选择搜索
C
插入搜索
D
顺序搜索
答案与解析
正确答案:A

二分查找体现了分治算法。

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

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

A
3
B
4
C
5
D
6
答案与解析
正确答案:D
这道题暂未补解析。
题目详情
36 单选题 适中 Python编程考级 ·Python编程四级 · 4.1 分治思想

下列关于分治算法的描述中,错误的是?( )

A
问题的规模分解到一定的程度,问题容易解决
B
问题可以分解为若干个规模较小相同问题
C
问题所分解出的各个子问题是可以相互交叉
D
问题分解出的子问题的解可以合并为该问题的解
答案与解析
正确答案:C

问题所分解出的各个子问题是相互独立,即该问题具有最优子结构性质。

题目详情
37 单选题 适中 Python编程考级 ·Python编程四级 · 4.1 分治思想

解决下列问题体现分治算法思想的是?( )

A
打印1000以内的完美数(完美数是除了本身之外的因数之和等于本身)
B
输出100以内能被5整除的整数
C
求斐波那契数列第n项
D
用快速排序算法对n个整数升序排序
答案与解析
正确答案:D

快速排序体现分治算法思想。

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

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

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

二分查找思想。

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

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

A
10
B
8
C
6
D

4

答案与解析
正确答案:C

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

题目详情
40 单选题 适中 Python编程考级 ·Python编程四级 · 4.1 分治思想

二分查找法是利用了哪种算法思想?( )

A
动态规划
B
分治算法
C
递推算法
D
递归算法
答案与解析
正确答案:B

分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题,折半查找就是利用分治算法,不断缩小答案所在范围。

题目详情