Question

数据结构查找技术假设在有序线性表a[20]上进行折半查找,则比较一次查找成功的节点数为1；比较两次查找成功的结点数为（

Answer 1

二次为2个

四次的为8个

平均查找长度为（1x1+2x2+3x4+4x8+5x5)/20=74/20

先构造长度为20的折半查找判定树,其他的就OK了,判定树如下

10

/

5 15

/ /

2 7 12 18

/ / / /

1 3 6 8 11 13 16 19

4 9 14 17 20