单选题
如下图所示的一棵二叉排序树，其查找成功的平均查找长度是______，查找不成功的平均查找长度是21/7。
【正确答案】
C
【答案解析】[解析] 该二叉排序树的查找成功的平均查找长度为ASL=(1×1+2×2+3×2+4×1)/6=15/6。为了计算查找不成功的平均查找长度需要构造判定树，如下图所示。每次查找不成功，一定是从根结点走到了一个空指针位置，等于从根到空指针的路径长度，因此查找不成功的平均查找长度为ASL=(2×2+3×3+4×2)/7=21/7。
[*]