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

Python编程四级 题库

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

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

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

B体现分治思想

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

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

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

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

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

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

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

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

(1)二分搜索

(2)大整数乘法

(3)Strassen矩阵乘法

(4)棋盘覆盖

(5)合并排序

(6)快速排序

(7)线性时间选择

(8)最接近点对问题

(9)循环赛日程表

(10)汉诺塔

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

A
分解
B
求解
C
合并
D
判断
答案与解析
正确答案:D
这道题暂未补解析。
题目详情
9 单选题 适中 Python编程考级 ·Python编程四级 · 4.2 对分查找

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

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

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

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

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

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

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

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

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

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

A

解析算法

B

枚举算法

C

冒泡排序

D

对分查找

答案与解析
正确答案:D
这道题暂未补解析。
题目详情
13 单选题 适中 Python编程考级 ·Python编程四级 · 4.2 对分查找

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

题目详情