首页 > 试题广场 >

有个长度为12的无重复有序表,按折半查找法进行查找,在表内各

[单选题]
有个长度为12的无重复有序表,按折半查找法进行查找,在表内各元素等概率情况下,查找成功所需的平均比较(三元比较)的次数为()
  • 35/12
  • 37/12
  • 39/12
  • 43/12
由题目已知元素序号(即下标)范围为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)
一共12张牌。1费1张,2费2张,3费4张,4费5张(4费最多可以8张)。然后计算总费用就行了,37费。
发表于 2020-05-16 09:57:45 回复(7)
发表于 2020-07-03 14:26:15 回复(0)

构建了从1——12的搜索树,请指正图片说明

发表于 2021-07-22 09:31:54 回复(0)
二分查找的次数相同的数字的个数是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)
总共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)
最后一次查找成功到的数据个数根据数据个数不同有不同。
发表于 2022-01-04 16:40:49 回复(0)
缘来如此,
发表于 2021-12-18 10:58:49 回复(0)
等概率下,折半查找的平均查找长度公式为:ASL={[(n+1)/n]*log2^(n+1)}-1
发表于 2021-08-12 12:56:01 回复(0)