Question

c语言数据结构。长度为11的有序表，采用折半查找，在等概率情况下查找成功的平均查找长度为？请给出详

c语言数据结构。长度为11的有序表，采用折半查找，在等概率情况下查找成功的平均查找长度为？请给出详细过程

Answer 1

5.

一命击中的长度为1

两次击中的长度为2

三次击中的长度为4

四次击中的长度为8

五次击中的长度为16

所以，长度为11的有序表的平均查找次数约为5。

扩展资料：

首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。

参考资料来源：百度百科-二分查找

Answer 2

画出有11个结点的完全二叉树

上面的相加除以11就是33/11了这是查找成功的评价查找长度

Answer 3

一命击中的长度为1
两次击中的长度为2
三次击中的长度为4
四次击中的长度为8
五次击中的长度为16
所以，你的长度为11的有序表的平均查找次数约为5

Answer 4

最快的办法是将有序表转成二叉树
最慢的办法是一个个列举
1 3
2 4
3 2
4 3
5 4
6 1
7 3
8 4
9 2
10 3
11 4
共1*1+2*2+3*4+4*4=33
33/11=3

Answer 5

我不会我不会