【正确答案】 D

【答案解析】在查找成功的情况下，平均查找长度为(1+n)/2；在查找不成功时，每次都需要查找n次，即平均查找长度为n，而题目告诉我们查找成功与查找不成功各占一半，故平均查找长度为：（（l+n)/2)/2+n/2=0.75n+0.25 0
注：一般如果题中不加特别说明，都可以认为每个结点的查找概率相等。