CSP 模拟 · CSP 2020 第一轮（初赛）模拟 第 10 题

在一个初始长度为 $n$ 的链表中连续进行 $k$ 次操作，每次操作是读入两个数字 $a_i$ 和 $b_i$，在链表中找到元素为 $a_i$ 的结点（假设一定可以找到），然后将 $b_i$ 这个元素插入到这个结点前面。在最理想的情况下，链表访问的结点数量最少可能是多少（不算将要插入的结点）？

别被'链表'二字绕晕了，这题考的是最理想情况下的'命中'概率。要想访问次数最少，命题人肯定让你每次都恰好插在最前面，这样根本不用往后找，每次操作就访问 1 个结点，k 次总共就是 k 次。

最容易掉进'链表默认要从头遍历'的思维定势，下意识觉得每次都要跑 n 步，算出 nk 次；或者被题目里'找到元素'这几个字误导，以为必须遍历整条链表才能定位。

这题考什么

这题披着链表操作的外衣，实则考查的是对'最理想情况'这一限定词的理解，以及基本算术逻辑。它不考链表具体实现，只考你读题时能否抓住'最少可能'这个核心。

命题人怎么挖坑

命题人很狡猾，特意选了'链表'这个数据结构。在链表里，查找一个元素通常意味着从头遍历，最坏情况要跑 n 步。但题目加了'最理想的情况'和'假设一定可以找到'。前者是让你往好处想，后者是告诉你不用考虑'找不到'这种边界情况。很多学生看到'链表'就条件反射地想'遍历'，忽略了'最理想'这个巨大的前提，直接选了 C 选项 nk 次，这就是典型的掉坑。

思考心法

拿到题先想'最少'意味着什么？意味着每一步都尽可能不浪费。在链表里，怎么不浪费？就是不用往后找。怎么不用往后找？就是把新元素插在链表最前面，或者插在已经访问过的节点后面。题目说'找到元素 a_i 的结点'，只要 a_i 就在链表头部，我们读一次就能找到，访问次数就是 1。既然题目问'最少可能'，我们就构造一个场景：每次插入的 a_i 恰好是链表当前的第一个元素。这样每次操作只访问 1 个结点。k 次操作，总共访问 k 个结点。

具体怎么算

每次操作访问 1 个结点（插在头部，直接命中），k 次操作就是 k 次。选项里有 k 次，那就是 B。

避坑

千万别算成 nk。nk 是每次都要从头遍历到尾部才插入，那是'最坏情况'或者'平均情况'（如果插入位置随机）的算法复杂度。题目明确说'最理想'，所以必须按'每次都命中'来算。另外，注意题目括号里说'不算将要插入的结点'，这意味着我们只统计查找过程访问的结点数，插入操作本身不额外计数，这进一步确认了每次只需访问 1 个结点（即 a_i 所在的结点）。