首页 > 试题广场 >

判断下列说法是否正确：对长度为n的有序表进行折半查找的判定树

[单选题]
判断下列说法是否正确：对长度为n的有序表进行折半查找的判定树的高度为log2n（） 
  • 正确
  • 错误
添加回答
推荐
白驹之过隙头像 白驹之过隙
选B。对有序表的折半查找相当于数据结构中二叉查找树的原理。
如下图所示复杂度最高的一次查询，对长度n为8的有序列表进行折半查找1，树的高度为4
带入题目中⌈log28⌉，结果为3，与实际树的高度相悖。




编辑于 2020-01-21 15:48:15 回复(3)
牛客707235628号头像 牛客707235628号
应该是log2n+1
不是log2(n+1)

发表于 2020-05-21 16:31:34 回复(0)
Jino.头像 Jino.
选B。
此题是考查数据结构二分查找问题。
其判定树的高度，也就是为最坏一次查找时，需要比较的次数，所以为[log2n+1]。因此题中描述有误。
综上，本题选B。
发表于 2020-01-14 17:04:05 回复(0)
大星星和小猩猩头像 大星星和小猩猩
高度是「log2（n+1），不是「log2n。
发表于 2020-04-09 10:54:06 回复(0)
牛客4938kunn头像 牛客4938kunn
准确来说应该是：log2[n+1]，做取整运算。
发表于 2021-01-06 09:00:14 回复(0)
学术废物头像 学术废物
当O选了
发表于 2022-03-18 21:18:41 回复(0)
天尊墨宇头像 天尊墨宇
选B，因为高度是[log2n+1](n>=0)
发表于 2020-06-15 14:57:45 回复(0)
等风来201804271358239头像 等风来201804271358239

应该是以2为底计算出结果再加1

发表于 2020-03-13 00:18:58 回复(0)
提交观点

问题信息

查找
上传者：zsw3
难度：
8条回答 5420浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号