NOIP 提高 2014 第一轮 第 7 题：对长度为 n 的有序单链表，若检索每个元素的概率相等，则顺序检索到表中任一元素的

题目

对长度为 $n$ 的有序单链表，若检索每个元素的概率相等，则顺序检索到表中任一元素的平均检索长度为(  ).

选项

• A. $\dfrac{n}{2}$
• B. $\dfrac{n+1}{2}$
• C. $\dfrac{n-1}{2}$
• D. $\dfrac{n}{4}$

答案

B

题解

考点定位

本题考「顺序检索平均长度」,对应大纲 3.2.3 链表（难度【2】）。

解题过程

等概率检索第 i 个元素需 i 次：平均 = (1+2+…+n)/n = (n+1)/2。

选 B。

易错提醒

① 等差平均；② 有序无序不影响顺序检索的复杂度量级。