求数据结构中平均查找长度哪位大侠帮小妹解决一下这个题,假设按下列递归方法进行顺序表的查找,若表长小于等于10,则进行顺序查找,否则进行折半查找,试划出对表长N=50的顺序表进行上述

Question

求数据结构中平均查找长度 哪位大侠帮小妹解决一下这个题,
假设按下列递归方法进行顺序表的查找,若表长小于等于10,则进行顺序查找,否则进行折半查找,试划出对表长N=50的顺序表进行上述查找时描述该查找的判定树,并求出在等概率情况下查找成功的平均查找长度

Answer 1

这个图有点难画啊,按说的还原判定树就可以了,其中从第4层开始的顺序查找方向可以颠倒：
第一层25
第二层12和38
第三层6、18,31、44
第4层5、7,17、19,30、32,43、45
第5层4、8,16、20,29、33,42、46
第6层3、9,15、21,28、34,41、47
第7层2、10,14、22,27、35,40、48
第8层1、11,13、23,26、36,39、49
第9层24,37,50
所以ASL=(1*1 + 2*2 + 3 *4 + 4*8 + 5*8 + 6*8 + 7*8 + 8*8 + 9*3) / 50 = 284/50