问题
单项选择题
具有12个关键字的有序表，折半查找的平均查找长度（）。
A.3.1
B.4
C.2.5
D.5
答案
参考答案：A
解析：
将12个数画成完全二叉树，第一层有1个、第二次2个、第三层4个，第四层只有5个。
二分查找时：
第一层需要比较1次
第二两个数，每个比较2次
第三层四个数，每个比较3次
第四层五个数，每个比较4次
则平均查找长度即为：（1+2*2+3*4+4*5）/12=37/12=3.0833