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

单选题

在有序表{7, 15, 18, 21, 27, 36, 42, 48, 51, 54, 60, 72}中,采用折半查找算法寻找值为15和38,分别需要进行多少次元素之间的比较?

A
3和1 
B
3和2
C
4和1
D
4和3
使用微信搜索喵呜刷题,轻松应对考试!

答案:

D

解析:

折半查找算法是一种在有序数组中查找特定值的算法。对于给定的有序表{7,15,18,21,27,36,42,48,51,54,60,72},寻找值为15和38的过程需要进行比较的次数分别是4次和3次。

对于值15,首次比较中间元素36(第6个元素),因为15小于36,所以搜索范围缩小到数组的前半部分。接着比较中间元素18(第3个元素),因为15仍然小于18,搜索范围进一步缩小到数组的前半部分的前半部分,即前三个元素。最终在第一个元素处找到值等于15的元素,所以总共需要比较4次。

对于值38,首次比较中间元素36(第6个元素),因为38大于36,所以搜索范围缩小到数组的后半部分。接着比较中间元素(第7个元素)即第(6+(6-1)/ 2 = 6.5)个元素(注意这里取上界),即第7个元素是下一个中间元素的位置。由于数组中没有找到值为38的元素,所以在第3次比较后结束搜索。因此总共需要比较3次。所以答案是选项D。

创作类型:
原创

本文链接:在有序表{7, 15, 18, 21, 27, 36, 42, 48, 51, 54, 60, 72

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

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

分享考题
share