2. 计算机
  3. 对有序表R[0.29]进行二分查找的平均查找长度为(55)。

对有序表R[0.29]进行二分查找的平均查找长度为(55)。

admin2010-01-23  9
问题 对有序表R[0.29]进行二分查找的平均查找长度为(55)。
选项 A、4
B、62/15
C、64/15
D、6/25
答案B
解析 有序表A[0..29]的长度n为30，它的判定树的深度与具有30个结点的完全二叉树的深度相同，为[log2n]+1=5。深度为5的判定树，前面4层是满的，只有第5层有可能不满。由二叉树的性质1可知，第1到第4层的结点数依次为20，21，22，23，24，即依次为1，2，4，　8，因而第5层上有30-(1+2+4+8)=15个结点。这些元素所在的层数即为成功查找它们所需比较的次数。故其平均查找长度为：(1×　1+2×2+3×4+4×8+5×15)/30=124/30=62/15。
转载请注明原文地址:https://kaotiyun.com/show/dlxZ777K
本试题收录于： 软件设计师上午基础知识考试题库软考中级分类
0

软件设计师上午基础知识考试

软考中级

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