Python编程四级 题库
有n个按名称排序的商品,使用对分查找法搜索任何一商品,最多查找次数为5次,则n的值可能为?(?)
对分查找最多查找次数m与个数之间n的关系是:n对2的对数的取整后加1,现在最多查找次数是5次,因此n的取值范围在[2^4+1,2^5]即[16,31]之间,因此选C。
下列有关分治算法思想的描述不正确的是?(?)
将问题分解出的各个子问题是相互独立的,即子问题之间不包含公共子子问题
下列问题使用分治算法思想的是?(?)
快速排序算法使用了分治算法。因此选D。
关于分治算法特征的描述中,错误的是?( )
该问题所分解出的各个子问题是相互独立,即该问题具有最优子结构性质。
张老师有n(范围在1到15之间)个礼物分给同学们,他请同学们猜礼物的数量,请问同学们猜几次后肯定知道礼物的数量(不算运气成分第1次或第2次就猜到)?( )
二分查找特征,15个礼物,每次对半猜,4次后肯定知道结果。
二分查找又称折半查找,下列数列中适合二分查找算法的是?
根据二分查找的实现原理,首先数列元素必须是有序的。
在32枚崭新的金币中,有一枚外表与真金币完全相同的假币(质量小一点),现在只有一台天平,则应用二分法的思想最多称几次就可以发现这枚假币?
二分查找法,每次都通过跟区间的中间元素对比,将待查找的区间缩小为之前的一半,直到找到要查找的元素,或者区间被缩小为 0。
某同学用对分查找和顺序查找在数字序列“1,3,5,8,15,21,35,65”中查找数字15,两种方法都能访问到的下列数字是?
顺序查找数字15,访问的数字是1,3,5,8,15;使用二分查找数字15,访问到的数字依次是8,21,15;数字8是两种方法都访问到。因此选C。
《阅微草堂笔记》里描述了槐树果实“响豆”,在夜里爆响,这种豆一棵树只有一粒,难以辨认出。所以古人就等槐树开花结果后,用许多布囊分别贮存豆荚,用来当枕头。夜里如果没有听到声音,便扔掉。如果有爆响声。然后把这一囊的豆荚又分成几个小囊装好,夜里再枕着听……如此这么分下去直到找到响豆。以上故事体现的算法是?( )
分治算法的特征之一,就是将一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题。
下列哪项不是分治算法所具有的特征?( )
求解问题可以分解为若干个规模较小的相同问题。
两位同学玩猜数字游戏,规则如下:一方在心里默想一个范围在1-100之间的数,如果另一方猜的数字比对方想的要大,就说大了;如果猜的数字比想的要小,就说小了,直到猜中数字。那么使用二分查找法最多需要猜测的次数是?( )
6
相当于用二分法在1-100之间查找某个数字。
下列有关分治算法思想的描述不正确的是?( )
将问题分解成的子问题具有相同的模式。
将问题分解出的各个子问题相互之间有公共子问题。
当问题足够小时,可以直接求解。
可以将子问题的求解结果合并成原问题的解。
将问题分解出的各个子问题相互之间没有公共子问题。
以下关于分治算法的描述正确的是?( )
分治算法的特征,各个子问题相互独立,子问题的求解可以合并成原问题的解。
下列关于分治算法的描述中,错误的是?( )
问题所分解出的各个子问题是相互独立,即该问题具有最优子结构性质。
解决下列问题体现分治算法思想的是?( )
快速排序体现分治算法思想。
有6位学生的身高分别为“166、168、169、171、172、175”,其中小王的身高为172,若采用二分查找,则需要找多少次才能够找到小王?( )
二分查找思想。
一款经典的猜数字游戏:甲先在50以内随意写一个数字,乙开始猜,如果乙猜的比甲写的数大了,甲就说大了,反之,则说小了。请问根据对分查找思想,乙最多用多少次能猜出甲写的正确数字?( )
4
折半查找算法,因为答案所在范围区间为50以内的数字,50介于2^5(32)与2^6(64)之间,所以最大折半查次数是6。
二分查找法是利用了哪种算法思想?( )
分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题,折半查找就是利用分治算法,不断缩小答案所在范围。