Python编程四级 题库
分治,"分而治之"。从字面上理解就是分---治,把大的问题分成小问题,解决一个一个小问题,之后把问题的答案合并起来,就得到大问题的结果。历史上也有很多故事属于分治思想,以下属于分治思想的是?( )
B体现分治思想
对元素规模为n的列表进行对分查找时,无论是否找到,至多进行()次查找?
对元素规模为n的列表进行对分查找时,无论是否找到,至多进行 log2n+1( log2n+1表示大于或等于 log2n的最小整数)次查找就能得到结果。
以下不可以使用分治法求解的是?( )
可使用分治法求解的一些经典问题
(1)二分搜索
(2)大整数乘法
(3)Strassen矩阵乘法
(4)棋盘覆盖
(5)合并排序
(6)快速排序
(7)线性时间选择
(8)最接近点对问题
(9)循环赛日程表
(10)汉诺塔
对于数列3,8,11,15,17,19,25,30,44,采用“二分查找”法查找8,需要查找多少次?( )
按二分查找法的规律,每次先查找中间值,进行比较。
应用分治算法的前提是?( )
问题的可分性和解的可归并性是应用分治算法的前提。
下列哪项不是分治算法所具有的特征?( )
不超过100个元素的有序数列,使用二分查找能找到指定的元素,可能的查找次数不包括?( )
按照二分查找法的规律,100个元素的有序列表,不管是否找到,至多查找7次。
有100枚金币,其中有1枚轻1克的假金币,现在要找出这枚假金币,但身边只有1个没有刻度的天秤。小明先是将金币分成50枚一堆,共两堆称重,在轻的那一堆中又分成两堆,接着在轻的25枚中分成12,12,1三堆称重,若两堆12枚的重量相同,则假币为单独剩下的那一枚,否则在轻的那一堆中继续按照之前的办法称下去,直到找到假金币。请问小明采用的办法与哪个算法有着相似之处?( )
分治算法就是对一个问题采取各个击破的方法,将一个规模为N的问题分解为K个规模较小的子问题,这些子问题相互独立且与原问题性质相同。只要求出子问题的解,就可得到原问题的解。
已知有n本按照书名拼音排序好的图书,使用对分查找法搜索其中任何一本书,最多查找次数为6次,则n的值可能为?( )
对规模为n的数据进行对分查找时,无论是否查找到,至多进行 |log2n|+1次(|log2n|表示小于等于log2n的最大整数),因此25≤n<26,即32≤n<64。
对于序列98,88,76,65,48,24,12,12,8,1,采用“对分查找”法查找8,需要查找多少次? ( )
按二分查找法的规律,每次先查找中间值,进行比较。
分治法所能解决的问题一般具有以下几项特征,下列哪一项描述不正确? ( )
对于数列1,2,8,11,15,17,19,25,30,45,采用“二分查找”法查找11,需要查找多少次?( )
按二分查找法的规律,每次先查找中间值,进行比较。
使用分治算法的基本步骤是?( )
使用分治算法的基本步骤是分解、解决、合并。
二分查找法是运用哪种策略实现的算法?( )
二分查找法,也叫折半查找法。每次都通过跟区间的中间元素对比,将待查找的区间缩小为之前的一半,直到找到要查找的元素。属于分治算法的思想。
下列选项中,哪一项不是分治算法的特征?( )
子问题分解到什么程度需要视具体问题而定,并不一定要分解到不能分解为止。其余三个选项都是分治算法的特征。