首页
题库
面试
求职
学习
竞赛
More+
所有博客
搜索面经/职位/试题/公司
搜索
我要招人
去企业版
登录 / 注册
首页
>
试题广场
>
有个长度为12的无重复有序表,按折半查找法进行查找,在表内各
[单选题]
有个长度为12的无重复有序表,按折半查找法进行查找,在表内各元素等概率情况下,查找成功所需的平均比较(三元比较)的次数为()
35/12
37/12
39/12
43/12
查看正确选项
添加笔记
求解答(16)
邀请回答
收藏(694)
分享
9个回答
添加回答
70
前程似锦的垂耳兔很喜欢吃火锅
由题目已知元素序号(即下标)范围为1~12。查找1次成功的结点为:6。查找2次成功的结点为:3,9。查找3次成功的结点为:1,4,7,11。查找4次成功的结点为:2,5,8,10,12。成功查找所有结点的总的比较次数为:1×1+2×2+3×4+4×5=37平均比较次数为37/12。因此选择B。
发表于 2019-04-18 15:15:16
回复(5)
20
LauZyHou
一共12张牌。1费1张,2费2张,3费4张,4费5张(4费最多可以8张)。然后计算总费用就行了,37费。
发表于 2020-05-16 09:57:45
回复(7)
5
来一个西安的offer
发表于 2020-07-03 14:26:15
回复(0)
3
牛客4938kunn
构建了从1——12的搜索树,请指正
发表于 2021-07-22 09:31:54
回复(0)
2
校草王风风的室友
二分查找的次数相同的数字的个数是1,2,4,8,18等2的幂,12个数字的查找1,2,3,4次的个数为1,2,4,5
的比较次数为:1×1+2×2+3×4+4×5=37,平均次数为37/12.
发表于 2019-11-19 22:13:06
回复(0)
1
虚拟小菜鸟
总共12个数,最多查找次数为4次。查找一次找到的数为1个(两点(两个初始端点)则有一个中点(之后总共有3个点));查找2次能找到的为2个(翻倍,3点之间有2个中点(这时总共5个点));查找3次能找到的有4个(翻倍,5个点有4个中点(这时总共为9个点));查找4次的按之前的规律应该能找到8个(翻倍),但是总共只有12个数,前面找到了7个了,因此查找4次能找到剩下的5个值。总结:(1个1次,2个2次,4个3次,5个4次)共37次。
发表于 2021-11-09 12:57:23
回复(0)
0
凤铃
最后一次查找成功到的数据个数根据数据个数不同有不同。
发表于 2022-01-04 16:40:49
回复(0)
0
NightCrow2023
缘来如此,
发表于 2021-12-18 10:58:49
回复(0)
0
米奇伤心屋
等概率下,折半查找的平均查找长度公式为:ASL={[(n+1)/n]*log2^(n+1)}-1
发表于 2021-08-12 12:56:01
回复(0)
这道题你会答吗?花几分钟告诉大家答案吧!
提交观点
问题信息
查找
来自:
小米2019秋招测试开...
上传者:
小小
难度:
9条回答
694收藏
9047浏览
热门推荐
相关试题
以下对logcat 命令描述正确的是:
小米集团
Linux
Java工程师
C++工程师
测试工程师
2019
测试开发工程师
shell
评论
(36)
来自
小米2019秋招测试开发...
使用软件测试工具的目的包括哪些?( )
小米集团
软件测试
Java工程师
C++工程师
测试工程师
2019
测试开发工程师
评论
(21)
来自
小米2019秋招测试开发...
递归是将一个较复杂的(规模较大的)...
递归
评论
(1)
<p> <s...
数组
队列
评论
(1)
在最坏情况下,快速排序耗费 O(N...
排序
复杂度
评论
(2)
扫描二维码,关注牛客网
意见反馈
下载牛客APP,随时随地刷题