NOIP 提高组初赛 · NOIP 2014 提高组初赛试题 第 7 题

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

这题考的是平均检索长度（ASL）的计算。拿到题先别急着套公式，想清楚：顺序检索意味着第 i 个元素必须比较 i 次，等概率就是所有比较次数加起来除以 n，简单求和公式一用就出来了。

最容易掉进的坑是死记硬背结论，忘了推导过程。比如有人会把 n 个元素误以为是 n-1 次比较（以为最后一个不用比），或者把等差数列求和记错成 n^2/2。还有的同学看到是链表就纠结指针移动，其实顺序检索的比较次数跟数组顺序查找完全一样，别被数据结构的表象带偏了，核心就是等差数列求和除以 n。

平均检索长度（ASL）

这道题考查的是数据结构中顺序检索的平均比较次数，也就是平均检索长度（ASL）。虽然题目说的是“有序单链表”，但这里的关键不在于链表的结构特性，而在于检索方式——顺序检索。从表头开始，逐个比较，直到找到目标元素为止。

在等概率假设下（每个元素被检索的概率都是 1/n），我们可以这样思考：

• 第 1 个元素在第 1 次比较时就会被找到，需要 1 次比较；
• 第 2 个元素需要比较 2 次；
• ……
• 第 n 个元素需要比较 n 次。

所以，总的比较次数就是 1 + 2 + 3 + … + n。这是一个经典的等差数列求和问题，和为 n(n+1)/2。

平均检索长度 ASL 就是总比较次数除以元素个数 n： ASL = [n(n+1)/2] / n = (n+1)/2。

这个结果跟数组的顺序查找完全一致，链表只是存储方式不同，不改变顺序检索的比较逻辑。

命题视角与易错点

命题人喜欢在这里挖两个坑：一是让学生误以为链表有某种特殊性质导致比较次数不同，二是让学生记错等差数列求和公式。比如有人会算成 n^2/2（忘了除以 n），或者算成 (n-1)/2（以为最后一个元素不需要比较）。记住，顺序查找的本质就是线性扫描，第 i 个元素必须经过 i 次比较才能确认找到。