Python编程四级 题库
分治,"分而治之"。从字面上理解就是分---治,把大的问题分成小问题,解决一个一个小问题,之后把问题的答案合并起来,就得到大问题的结果。历史上也有很多故事属于分治思想,以下属于分治思想的是?( )
B体现分治思想
以下不可以使用分治法求解的是?( )
可使用分治法求解的一些经典问题
(1)二分搜索
(2)大整数乘法
(3)Strassen矩阵乘法
(4)棋盘覆盖
(5)合并排序
(6)快速排序
(7)线性时间选择
(8)最接近点对问题
(9)循环赛日程表
(10)汉诺塔
应用分治算法的前提是?( )
问题的可分性和解的可归并性是应用分治算法的前提。
下列哪项不是分治算法所具有的特征?( )
有100枚金币,其中有1枚轻1克的假金币,现在要找出这枚假金币,但身边只有1个没有刻度的天秤。小明先是将金币分成50枚一堆,共两堆称重,在轻的那一堆中又分成两堆,接着在轻的25枚中分成12,12,1三堆称重,若两堆12枚的重量相同,则假币为单独剩下的那一枚,否则在轻的那一堆中继续按照之前的办法称下去,直到找到假金币。请问小明采用的办法与哪个算法有着相似之处?( )
分治算法就是对一个问题采取各个击破的方法,将一个规模为N的问题分解为K个规模较小的子问题,这些子问题相互独立且与原问题性质相同。只要求出子问题的解,就可得到原问题的解。
分治法所能解决的问题一般具有以下几项特征,下列哪一项描述不正确? ( )
使用分治算法的基本步骤是?( )
使用分治算法的基本步骤是分解、解决、合并。
二分查找法是运用哪种策略实现的算法?( )
二分查找法,也叫折半查找法。每次都通过跟区间的中间元素对比,将待查找的区间缩小为之前的一半,直到找到要查找的元素。属于分治算法的思想。
下列选项中,哪一项不是分治算法的特征?( )
子问题分解到什么程度需要视具体问题而定,并不一定要分解到不能分解为止。其余三个选项都是分治算法的特征。
下列有关分治算法思想的描述不正确的是?(?)
将问题分解出的各个子问题是相互独立的,即子问题之间不包含公共子子问题
下列问题使用分治算法思想的是?(?)
快速排序算法使用了分治算法。因此选D。
关于分治算法特征的描述中,错误的是?( )
该问题所分解出的各个子问题是相互独立,即该问题具有最优子结构性质。
《阅微草堂笔记》里描述了槐树果实“响豆”,在夜里爆响,这种豆一棵树只有一粒,难以辨认出。所以古人就等槐树开花结果后,用许多布囊分别贮存豆荚,用来当枕头。夜里如果没有听到声音,便扔掉。如果有爆响声。然后把这一囊的豆荚又分成几个小囊装好,夜里再枕着听……如此这么分下去直到找到响豆。以上故事体现的算法是?( )
分治算法的特征之一,就是将一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题。
下列哪项不是分治算法所具有的特征?( )
求解问题可以分解为若干个规模较小的相同问题。
下列有关分治算法思想的描述不正确的是?( )
将问题分解成的子问题具有相同的模式。
将问题分解出的各个子问题相互之间有公共子问题。
当问题足够小时,可以直接求解。
可以将子问题的求解结果合并成原问题的解。
将问题分解出的各个子问题相互之间没有公共子问题。