已知一个长度为16的有序顺序表R[1..16],采用折半查找方法查找一个存在的元素,则比较的次数最多是______。
A. 5
B. 4
C. 7
D. 6
1-16 -》(1+16)/2=8,第一次
1-7-》 (1+7)/2=4 第二次
1-3-》 (1+3)/2=2第三次
1-1-》(1+1)/2 = 1 第四次
admin 回复 小灰机: 有个简单的方法,你这样想4个数折半查找两次能不能找到,很明显最坏情况要比较三次。实际上这题考察二叉排序树的是否理解,16个元素的二叉排序树深度最低为5。
16个二叉排序树的深度为5,查找一个不存在的最多查到最后一层,即5
log2(16)+1=5
对于长度为 nnn 的有序表,比较的次数最多为log2 n,加一次失败比较次数,所以为4+1
秀秀 回复 17679377259: 题目不是查找存在的元素吗
17679377259 回复 秀秀: 是的,我当时搞错了。应该是该二叉判定树高度,而不需要加失败比较次数,所以公式应该是高度公式,log n 取下界+ 1或log (n+1)取上界
A
用户登录可进行刷题及查看答案
登录后提交答案