2. 计算机
  3. 对具有n个元素的有序序列进行二分查找时，(40)。

对具有n个元素的有序序列进行二分查找时，(40)。

admin2021-01-13  4
问题 对具有n个元素的有序序列进行二分查找时，(40)。
选项 A、查找元素所需的比较次数与元素的位置无关
B、查找序列中任何一个元素所需要的比较次数不超过[log2(n+1)]
C、元素位置越靠近序列后端，查找该元素所需的比较次数越少
D、元素位置越靠近序列前端，查找该元素所需的比较次数越少
答案B
解析 本题考查查找方法中的二分方法。二分查找过程是：以处于中间位置记录的关键字和给定值比较，若相等，则查找成功；若不等，则缩小范围，直至新的区间中间位置记录的关键字等于给定值或查找区间的大小为零时(表明查找不成功)为止。对于有11个元素的有序表进行二分查找的过程可用一个二叉树表示，如下所示(结点中的数字表示元素在序列中的序号)：

该二叉树表明，若需要查找序列中的第6个元素，则仅需一次元素间的比较。若需查找第3个或第9个元素，则分别需要两次比较。依此类推，查找第1、4、7、10个元素时，分别需要三次比较，查找第2、5、8、11个元素时，分别需要四次比较。因此，查找元素所需的比较次数与元素在序列中的位置是有关的。显然，选项C或D的说法也是错误的。若序列中有n个元素，则根据二分查找法构造的二叉树的高度不会超过[log2(n+1)]，因此选项B是正确的。
转载请注明原文地址:https://kaotiyun.com/show/9INZ777K
本试题收录于： 程序员上午基础知识考试题库软考初级分类
0

程序员上午基础知识考试

软考初级

相关试题推荐
随机试题
最新回复(0)