刷题刷出新高度,偷偷领先!偷偷领先!偷偷领先! 关注我们,悄悄成为最优秀的自己!

单选题

图书馆有1000本按编号排序的书(1-1000),小刚想用分治算法快速找到编号为450的书。分治算法的正确步骤是?( )

A
从第1本开始逐本查找,直到找到450
B
随机抽取100本检查,若未找到则换一批
C
将书分成两堆,依次查找两堆
D
先找中间第500本书,如果书的编号 < 500,则在1-499中重复折半查找
使用微信搜索喵呜刷题,轻松应对考试!

答案:

D

解析:

分治算法的核心思想是将问题分解为更小、更简单的子问题,然后递归地解决这些子问题,最后合并子问题的解以得到原问题的解。在查找排序好的数组或列表中的元素时,可以采用二分查找法,这是一种典型的分治算法。对于小刚想找的书编号为450,正确的分治算法步骤应该是先找到中间编号的书(在本例中是编号为500的书),然后判断目标编号450是在此编号之前还是之后的区间里。如果在之前的区间(编号小于中间值),就在该区间内继续折半查找,直到找到目标编号。因此,选项D是正确的分治算法步骤。

创作类型:
原创

本文链接:图书馆有1000本按编号排序的书(1-1000),小刚想用分治算法快速找到编号为450的书。分治算法

版权声明:本站点所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明文章出处。

让学习像火箭一样快速,微信扫码,获取考试解析、体验刷题服务,开启你的学习加速器!

分享考题
share