有个长度为12的无重复有序表,按折半查找法进行查找,在表内各元素等概率情况下,查找成功所需的平均比较的次数为()

答案:37/12,或者3.1

解析:由题目已知元素序号范围为1~12。查找1次成功的结点为: 6。查找2次成功的结点为:3,9。查找3次成功的结点为: 1, 4, 7, 11。查找4次成功的结点为: 2, 5,8, 10,12。成功查找所有结点的总的比较次数为:1×1+2*2+3×4+4×5=37平均比较次数为37/12。

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注