设查找表有n个数据元素，则二分查找算法的平均查找长度为______。
log2(n+1)-1[考点] 二分查找的平均查找长度[解析] 可参见考点的定义。
举一反三
- 查找类算法中，基本操作运算是（），设要查找的数据表元素的个数为n，则查找成功的顺序查找的平均检索长度是（）。
- 设查找表各元素的查找概率都相等,则分块查找的平均查找长度不仅与要查找的元素个数有关,而且与每块中的元素个数有关。（)
- 在各种查找算法中，平均查找长度（与关键字比较次数的期望值）与查找表中元素个数n无关的查找方式是什么排序？
- 在n个数中查找指定数据，使用顺序查找法，平均查找长度为（）。
- 一个查找表{13，4，5，9，10，6}，从前向后顺序查找5，5需要依次与13、、4、5进行一次比较，找到了，查找成功。该查找表的平均查找长度是。 知识补充：一个查找算法的评价，常常用平均查找长度来评价，平均查找长度就是找到每个元素的平均比较次数。如果查找每个元素的概率相等，N个元素的查找表，每个元素的查找概率为1/N，则查找表的平均查找长度ASL=(1/n * c1+1/n *c2+1/n *c3+……+1/n *Cn),ci是找到第i个元素需要比较的次数
内容
- 0
采用二分查找的算法,当n较大时,其平均查找长度ASL近乎为____
- 1
关于平均查找长度不正确的描述是？（ ） A: 平均查找长度为对关键字需要进行的平均比较次数 B: 对于含有n个数据元素的查找表，查找成功的平均查找长度为：ASL=∑PiCi (i=1,2,3,…,n)，其中：Pi 为查找表中第i个数据元素的概率，Ci为找到第i个数据元素时已经比较过的次数 C: 平均查找长度为衡量一个查找算法效率优劣的标准 D: 在等概率的情况下，ASL=n∑Ci
- 2
对N个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为_______
- 3
设有序顺序表中有n个数据元素，则利用二分查找法查找数据元素X的最多比较次数不超过（ ）。
- 4
采用折半查找方法查找长度为n的查找表，平均查找长度为（）。