2. 自考
  3. 假设有一个长度为n的有序序列，在进行查找时，可以借助二叉树来进行，请结合二叉树的性质来分析二分查找的最坏性能和平均性能。

假设有一个长度为n的有序序列，在进行查找时，可以借助二叉树来进行，请结合二叉树的性质来分析二分查找的最坏性能和平均性能。

admin2010-04-24  65
问题 假设有一个长度为n的有序序列，在进行查找时，可以借助二叉树来进行，请结合二叉树的性质来分析二分查找的最坏性能和平均性能。
选项
答案假设判定树的内部结点的总数为n=2h-1-1。则判定树是深度为h=lg(n+1)的满二叉树，树中第k层上的结点的个数为2h-1，查找它们所需要比较的次数是k。则在等概率下，二分查找成功时的平均查找长度为：[*]，如果n很大，则可以用如下近似公式：lg(n+1)-1，作为二分查找成功时的平均查找长度。二分查找在查找失败时所需要比较的关键字的个数不超过判定树的深度，在最坏情况下查找成功的比较次数也不超过判定树的深度。因为判定树中度数小于2的结点只可能在最下面的两层上
解析
转载请注明原文地址:https://kaotiyun.com/show/QMAx777K
本试题收录于： 数据结构题库理工类分类
0

数据结构

理工类

相关试题推荐
随机试题
最新回复(0)