首页 > 试题广场 >

假定对有序表: (3,4,5,7,24, 30,42,54,

[单选题]
假定对有序表: (3,4,5,7,24, 30,42,54,63, 72, 87, 95)进行折半查找,假定每个元素的查找概率相等,则查找成功时的平均查找长度是( )
(要求画出描述折半查找过程的判定树)

  • 37/12
  • 41/12
  • 35/12
  • 以上都不对
推荐
A。由于截至目前对话框插入图片的bug未修复,无法上传折半查找判定树的图
以描述的方式进行判定树图的表述:
  1. 12个元素的折半查找,所以中间位置30为树的根节点,分出左右子树。其左右子树按照中间为根节点的方式继续递归构造判定树。
  2. 遵守左<根<右的规则。
查找成功的平均长度需要统计每个元素的查找次数:
  • 树第一层次数为1,第二场为2*2,第三层为3*4,第四层为5*4,一共为37次
  • 所以平均查找长度为37/12
编辑于 2019-09-20 14:17:56 回复(0)
按规律构造一颗二叉判定树,根据树的结构 第一层1个,第二层2个,第三层4个,第四层5个,然后第几层就表示要查找多少次 规律推出ASL
发表于 2020-05-16 09:22:58 回复(0)
发表于 2019-11-15 16:12:46 回复(4)
12个元素,1费1个,2费2个,3费4个,4费最多8个,但是如果是8个和前面加起来就是15个元素,超过了数组长度12,所以4费是5个。
总费用1*1+2*2+3*4+4*5 =37
发表于 2020-05-16 20:46:01 回复(3)
发表于 2022-11-06 17:31:29 回复(0)
三个索引,left,mid,right,当待查元素比当前mid指向元素小的时候,right等于mid-1,反之,left等于mid+1
发表于 2020-05-03 10:49:45 回复(0)