首页 › 题库 › Python编程考级 › 4.1 分治思想

Python编程四级 题库

共 49 道题 ,第 1 / 3 页 · 按题型筛选,点「查看答案」核对解析
章节 4.1 分治思想 清除
1 单选题 适中 Python编程考级 ·Python编程四级 · 4.1 分治思想

分治,"分而治之"。从字面上理解就是分---治,把大的问题分成小问题,解决一个一个小问题,之后把问题的答案合并起来,就得到大问题的结果。历史上也有很多故事属于分治思想,以下属于分治思想的是?( )

A
三国时,曹操带兵长途行军,士兵们都很口喝,曹操便说:“前面就是一大片梅林,结了许多梅子,又甜又酸,可以解渴。” 士兵们听了,嘴里都流口水,一时也就不渴了。
B
战国时期,秦国通过远交近攻的策略,逐个击破,最后统一六国。
C
汉末刘备三次到诸葛亮住的茅屋去邀请他出来帮助自己打天下,最后诸葛亮才答应出来。
D
三个臭皮匠顶个诸葛亮是一个文化术语。指的是三个副将的智慧能顶一个诸葛亮。
答案与解析
正确答案:B

B体现分治思想

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

以下不可以使用分治法求解的是?( )

A
棋盘覆盖问题
B
选择问题
C
归并排序
D
0/1背包问题
答案与解析
正确答案:D

可使用分治法求解的一些经典问题

(1)二分搜索

(2)大整数乘法

(3)Strassen矩阵乘法

(4)棋盘覆盖

(5)合并排序

(6)快速排序

(7)线性时间选择

(8)最接近点对问题

(9)循环赛日程表

(10)汉诺塔

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

应用分治算法的前提是?( )

A
问题的可分性和解的可归并性
B
问题的复杂性和解的简单性
C
问题的可分性和解的存在性
D
问题的复杂性和解的可归并性
答案与解析
正确答案:A

问题的可分性和解的可归并性是应用分治算法的前提。

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

下面哪种算法使用了分治的方法?( )

A
插入排序
B
快速排序
C
选择排序
D
冒泡排序
答案与解析
正确答案:B

只有B使用了分治的方法。

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

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

A
该问题的规模缩小到一定的程度就可以容易地解决
B
该问题可以分解为若干个规模较小的不同问题
C
利用该问题分解出的子问题的解可以合并为该问题的解
D
该问题所分解出的各个子问题是相互独立的
答案与解析
正确答案:B
这道题暂未补解析。
题目详情
6 单选题 适中 Python编程考级 ·Python编程四级 · 4.1 分治思想

以下哪项不是使用分治法解决问题的步骤?( )

A
分解
B
求解
C
合并
D
判断
答案与解析
正确答案:D
这道题暂未补解析。
题目详情
7 单选题 适中 Python编程考级 ·Python编程四级 · 4.1 分治思想

有100枚金币,其中有1枚轻1克的假金币,现在要找出这枚假金币,但身边只有1个没有刻度的天秤。小明先是将金币分成50枚一堆,共两堆称重,在轻的那一堆中又分成两堆,接着在轻的25枚中分成12,12,1三堆称重,若两堆12枚的重量相同,则假币为单独剩下的那一枚,否则在轻的那一堆中继续按照之前的办法称下去,直到找到假金币。请问小明采用的办法与哪个算法有着相似之处?( )

A
递归
B
分治
C
枚举
D
贪心
答案与解析
正确答案:B

分治算法就是对一个问题采取各个击破的方法,将一个规模为N的问题分解为K个规模较小的子问题,这些子问题相互独立且与原问题性质相同。只要求出子问题的解,就可得到原问题的解。

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

以下常见算法中,体现分治思想的是? ( )

A

解析算法

B

枚举算法

C

冒泡排序

D

对分查找

答案与解析
正确答案:D
这道题暂未补解析。
题目详情
9 单选题 适中 Python编程考级 ·Python编程四级 · 4.1 分治思想

分治法所能解决的问题一般具有以下几项特征,下列哪一项描述不正确? ( )

A
该问题的规模缩小到一定的程度就可以容易地解决
B
该问题可以分解为若干个规模较小的相同问题,即该问题具有最优子结构性质
C
利用该问题分解出的子问题的解可以合并为该问题的解
D
该问题所分解出的各个子问题之间包含公共的子子问题
答案与解析
正确答案:D
这道题暂未补解析。
题目详情
10 单选题 适中 Python编程考级 ·Python编程四级 · 4.1 分治思想

下面哪种算法使用了分治的方法?( )

A
冒泡排序
B
选择排序
C
插入排序
D
对分查找
答案与解析
正确答案:D
这道题暂未补解析。
题目详情
11 单选题 适中 Python编程考级 ·Python编程四级 · 4.1 分治思想

使用分治算法的基本步骤是?( )

A
分解、解决、合并
B
分解、解决
C
合并、解决
D
合并、解决、分解
答案与解析
正确答案:A

使用分治算法的基本步骤是分解、解决、合并。

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

二分查找法是运用哪种策略实现的算法?( )

A
分治法
B
贪心法
C
回溯法
D
动态规划法
答案与解析
正确答案:A

二分查找法,也叫折半查找法。每次都通过跟区间的中间元素对比,将待查找的区间缩小为之前的一半,直到找到要查找的元素。属于分治算法的思想。

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

下列选项中,哪一项不是分治算法的特征?( )

A
问题的规模缩小到一定程度就可以容易解决。
B
该问题分解出的子问题的解可以合并为该问题的解。
C
各个子问题必须分解到不能分解为止。
D
该问题具有最优子结构性质。
答案与解析
正确答案:C

子问题分解到什么程度需要视具体问题而定,并不一定要分解到不能分解为止。其余三个选项都是分治算法的特征。

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

下列排序算法中利用了分治算法思想的是?( )

A
冒泡排序
B
插入排序
C
选择排序
D
快速排序
答案与解析
正确答案:D

快速排序利用了分治算法思想。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

A

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

B

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

C

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

D

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

答案与解析
正确答案:B

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

题目详情