GESP 五级 · GESP 202603 C++ 五级 第 16 题

有一个存储了 $n$ 个整数的线性表，分别用数组和单链表两种方式实现。在已知下标（或结点指针）的前提下，数组的随机访问是 $O(1)$，而在链表中已知某结点的指针时，在该结点之后插入一个新结点的操作也是 $O(1)$。

分析时间复杂度时关注循环层数和每层迭代次数，递归算法则分析递归树。注意最坏/最好/平均情况的区别。

分析复杂度时注意外层循环和内层循环的关联。例如内外两层都到n的循环不一定是O(n²)，要看内层是否每次都在缩小。

【考点】数组随机访问｜链表插入操作｜时间复杂度分析

① 考纲定位（考点定位） 本题考查"线性表基本操作的时间复杂度"（GESP 五级 数据结构模块）。命题人想卡住那些只背结论的考生：数组随机访问 O(1) 和链表已知指针插入 O(1) 是两条独立事实，但很多人会混淆"访问"和"插入"的复杂度，或者忽略"已知指针"这个前提。

② 解题思维（拆解与通法） 看到题先想：数组下标已知→直接读内存；链表指针已知→直接改 next。关键观察是"已知"二字，意味着不需要遍历。通法：对于线性表，已知位置或指针时，访问/插入均为 O(1)；否则需遍历，复杂度 O(n)。

③ 陷阱拆解（命题人的套路） 选项 B 的错误在于偷换概念：把"插入 O(n)"的结论套用到"已知指针插入"的情境，或把"访问 O(n)"的结论套用到"已知下标访问"的情境。最阴险的细节是"已知下标（或结点指针）的前提下"——如果忽略这个前提，就掉进"必须遍历"的陷阱。只背结论、不理解本质，就会误判。

④ 反命题思维（教练升华） 如果把"已知"改成"未知"，数组访问和链表插入都会变成 O(n)；若把"插入"改成"删除"，在已知指针下仍为 O(1)。刷到类似题时，先问自己：命题人想考我什么？——是考察对"已知条件"的敏感度，还是对数据结构操作复杂度的准确记忆。