设查找表为(7,15,21,22,40,58,68,80,88,89,120) ,元素的下标依次为1,2,3,……, 11.(1)画出对上述查找表进行折半查找所对应的判定树(树中结点用下标表示)(2)说明成功查找到元素40需要经过多少次比较?(3)求在等概率条件下,成功查找的平均比较次数?

题目
设查找表为(7,15,21,22,40,58,68,80,88,89,120) ,元素的下标依次为1,2,3,……, 11.(1)画出对上述查找表进行折半查找所对应的判定树(树中结点用下标表示)(2)说明成功查找到元素40需要经过多少次比较?(3)求在等概率条件下,成功查找的平均比较次数?


相似考题
参考答案和解析
参考答案:(1)(2)4次
(3)ASL=(1+2*2+3*4+4*4)/11=3
更多“设查找表为(7,15,21,22,40,58,68,80,88,89,120) ,元素的下标依次为1,2,3,……, 11.(1)画出对上述查找表进行折半查找所对应的判定树(树中结点用下标表示)(2)说明成功查找到元素40需要经过多少次比较?(3)求在等概率条件下,成功查找的平均比较次数? ”相关问题
  • 第1题:

    画出对长度为10的有序表进行折半查找的判定树(以序号1,2,……10表示树结点),并对上述序列进行折半查找,求等概率条件下,成功查找的平均查找长度。
    (1)

    (2)ASL=(1x1+2x2+3x4+4x3)/10=29/10

  • 第2题:

    画出长度为10的折半查找判定树,并求等概率时查找成功和不成功的平均查找长度。


    (1) (2)ASL=(1x1+2x2+3x4+4x3)/10=29/10

  • 第3题:

    1. 假定对有序表:(6,10,15,17,24,35,46,57,66,73,85,90)进行折半查找,试回答下列问题: (1)画出描述折半查找过程的判定树;(4分) (2)若查找元素24,需依次与哪些元素比较?(2分) (3)若查找元素92,需依次与哪些元素比较?(2分) (4)假定每个元素的查找概率相等,求查找成功时的平均查找长度。(2分)


    19

  • 第4题:

    设有序列{10,12,15,19,22,25,100,130,150,200}画出对上述序列进行折半查找的判定树(以序列中的元素作为树的结点)。为了成功查找到100需要进行多少次元素间的比较?为了查找9,经过多少次元素间的比较可知道查找失败?
    (1)

    (2)4次;3次

  • 第5题:

    画出对长度为10的有序表进行折半查找的判定树,并求其等概率时查找成功的平均查找长度。


    (1) (2)ASL=(1x1+2x2+3x4+4x3)/10=29/10