首页 > 试题广场 >

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

[单选题]
具有12个关键字的有序表,折半查找的平均查找长度() 
  • 3.1
  • 4
  • 2.5
  • 5
查看正确选项
添加回答
Aesthetic92头像 Aesthetic92
答案：选A
假如数组{1,2,3,4,5,6,7,8,9,10,11,12}，先找到中间位置后分两半，{1,2,3,4,5}{6}{7,8,9,10,11,12},然后再把{1,2,3,4,5}和{7,8,9,10,11,12 }做同样操作，继续找到中间位置划分，最终求平均查找长度就是求成功查到的平均长度：(1+2*2+4*3+5*4)/12 = 37/12 = 3.1
编辑于 2021-01-15 12:38:47 回复(1)
时态的空白™头像 时态的空白™
将12个数画成完全二叉树，第一层有1个、第二次2个、第三层4个，第四层只有5个。
二分查找时：
第一层需要比较1次
第二两个数，每个比较2次
第三层四个数，每个比较3次
第四层五个数，每个比较4次
则平均查找长度即为：（1+2*2+3*4+4*5）/12 = 37/12 = 3.0833 即为 A、3.1
发表于 2015-08-27 15:37:36 回复(5)
L.K.头像 L.K.
具体查找如下图所示：
查找一次：6.
查找两次：3、10
查找三次：1、4、8、11
查找四次：2、5、7、9、12



编辑于 2015-07-28 20:54:26 回复(12)
CODEBIRD91头像 CODEBIRD91
为何那么复杂 二分查找时间复杂度log2（N）     log2（2^3）<log2(12)<log2(2^4) 一看 只有A
发表于 2017-08-08 21:07:37 回复(1)
牛客4600784号头像 牛客4600784号
判定树的层数log(n+1)向下取整数等于4，前三层为满二叉树：1-2-4，第四层5，所以平均查找长度=(1*1+2*2+4*3+5*4)/12=3.1
发表于 2017-07-26 16:03:49 回复(0)
友人说201904171536944头像 友人说201904171536944
a
发表于 2019-05-03 16:14:38 回复(0)
我是萌新有人信吗头像 我是萌新有人信吗
平均查找长度还能有小数点吗
发表于 2019-04-03 12:46:26 回复(0)
嗯好啊头像 嗯好啊
建立二叉搜索树
发表于 2018-09-06 10:01:05 回复(0)
我们都是大好青年头像 我们都是大好青年
log2 N
发表于 2018-07-11 08:56:21 回复(0)
这个名有人取了头像 这个名有人取了
本题实际上是就是估计log12的大小
log12=log(4*3)=2log3
1<log3<2，排除B,D
2^1.5 = 2^(3/2) = 2√2 ≈2.8 < 3
所以log3 > 1.5， 排除C，故选A
发表于 2018-04-25 14:58:43 回复(0)
Sc0tt头像 Sc0tt
二叉判定树
发表于 2018-04-24 19:20:34 回复(0)
Sep.wen头像 Sep.wen
具体查找如下图所示： 查找一次：6. 查找两次：3、10 查找三次：1、4、8、11 查找四次：2、5、7、9、12 （1+2*2+3*4+4*5）/12 = 37/12 = 3.0833
编辑于 2018-01-02 18:32:56 回复(2)
哲学老斯基头像 哲学老斯基
查找长度不是底数为2的logn吗，2^3=8,2^4=16，查12个也就是说长度在3~4之间.....
发表于 2017-05-19 10:37:30 回复(1)
wanlanwalan头像 wanlanwalan
12个关键字的有序表，折半查找的判定树如下：
6
/ \
3 9
/ \ / \
1 4 7 11
\ \ \ / \
2 5 8 10 12
平均查找长度=1/12*(1*1+2*2+3*4+4*5)=37/12
发表于 2017-04-26 15:52:24 回复(0)
飞鸟_11头像 飞鸟_11
假定有序表的长度n=2^h-1，则描述这边查找的判定树是深度为h的满二叉树。树中层次为1的结点有1个，层次为2的结点有2个……，层次为h的结点有2^(h-1)个。假设表中每个记录的查找概率相等（Pi=1/n），则查找成功时折半查找的平均查找长度：
ASLbs=Pi*Ci(i从1到n)
   =（1/n）(j*2^(j-1))(j是从1到h)

本题中n=12, h=log(12+1)=4  
因为不是满二叉树（满二叉树时n=15），
所以ALS = (1/12)(1*1+2*2+3*4+4*(8-(15-12))) = 3.0833333 = 3.1
编辑于 2015-06-10 16:47:55 回复(0)
威士忌头像 威士忌
B
发表于 2014-12-30 16:39:29 回复(1)
提交观点

问题信息

复杂度 查找
难度：
16条回答 30344浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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