对有序表R[0.29]进行二分查找的平均查找长度为(55)。A.4B.62／15C.64／15D.6／25

Question

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

A．4

B．62/15

C．64/15

D．6/25

Answer 1

正确答案：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。