首页 > 试题广场 >

具有12个关键字的有序表，折半查找的平均查找长度（ )

[单选题]

具有12个关键字的有序表，折半查找的平均查找长度（ ) 

  • 3.1
  • 4
  • 2.5
  • 5
查看正确选项
添加回答
sunlight_run头像 sunlight_run

如图标红节点，查找到标红节点需要3次比较，这样的节点有4个，由此类推。。。。比较4次节点有5个。。。。
所以平均查找长度为  总长度/总结点数=（1+2*2+4*3+5*4）/12=3.1  (公式自己想的，并非参考权威资料)
发表于 2017-07-01 14:27:39 回复(4)
Z4Knight头像 Z4Knight
将12个数画成完全二叉树，第一层有1个、第二次2个、第三层4个，第四层只有5个。
二分查找时：
第一层需要比较1次
第二两个数，每个比较2次
第三层四个数，每个比较3次
第四层五个数，每个比较4次
则平均查找长度即为：（1+2*2+3*4+4*5）/12 = 37/12 = 3.0833 即为 A、3.1
解析来源于@时态的空白™
编辑于 2017-05-22 19:46:21 回复(0)
理想低通滤波器头像 理想低通滤波器
log 12 约等于 3.1
发表于 2017-07-05 01:04:08 回复(2)
平头哥plus头像 平头哥plus
画个完全2插树
发表于 2019-09-14 00:31:24 回复(0)
Gumufff头像 Gumufff

将折半查找转成完全二叉树，然后计算平均查找长度

发表于 2019-07-07 10:21:14 回复(0)
planet起风了头像 planet起风了
那么平均查找长度为 1/n*（1*2^0+2*2^1+3*2^2+……+j*2^(j-1)） 则经过化简计算，得平均查找长度为：(（n+1）/n ) *log2(n+1)-1 (其中对数中的2为底数：即log以2为底（n+1)的对数） 注 : 当n很大时 ，可近似为 log2(n+1)-1
编辑于 2018-04-04 08:35:59 回复(0)
智能车俱乐部看门大叔头像 智能车俱乐部看门大叔 
log2[12]=lg12/lg2
= lg(2²×3)/lg2
= (2lg2+lg3)/lg2
= 2 + lg3/lg2
≈ 2 + 0.4771/0.301
≈ 3.5850
发表于 2018-01-26 10:14:43 回复(0)
牛客4898397号头像 牛客4898397号
嗯
发表于 2017-09-11 08:44:02 回复(0)
上善若水58头像 上善若水58
平均查找长度，其实可以理解平均，就是说各种情况下都要算进去，所以，要各种情况的总长度除以节点数，这样求得每个节点下的查找长度了
发表于 2017-09-07 15:17:04 回复(0)
提交观点

问题信息

查找
上传者：阿奻_
难度：
9条回答 3974浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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