GESP 五级 · GESP 202412 C++ 五级 第 1 题

下面关于链表和数组的描述，错误的是（ ）。

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

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

【考点】动态内存分配｜指针操作｜插入删除效率

GESP 5 级“数据结构”章节明确要求对比数组与链表的特性。命题人设此题就是为了卡住考生对"动态扩容"与"随机访问"两概念混淆的短板——很多人背结论却分不清何时该用链表、何时该用数组，这正是五级考察的深层理解。

通法：先定位每个选项的考察点（A 考动态分配、B 考随机访问、C 考插入删除、D 考存储方式），再结合数组与链表的核心差异（数组连续、链表离散）逐一验证。本题正确选项是 C，因为链表插入/删除平均时间复杂度为 O(1)（定位后移动指针），并非 O(n)；命题人故意把 O(n) 与 O(1) 混在一起，考察是否真正理解指针操作。

A 正确：数据量不确定时，用链表可动态调整，避免数组预分配浪费空间。 B 正确：链表随机访问需从头遍历，时间复杂度 O(n)。 D 正确：链表节点内存分散，通过指针链接。 C 错误：链表插入/删除只需移动指针，平均 O(1)；只有查找才 O(n)。命题人用"效率较低"诱导考生误以为 O(n)，这是典型的偷换概念陷阱。

如果改成"以下关于栈和队列的描述，错误的是？"答案会完全不同，因为栈/队列的插入删除都有 O(1) 实现。刷到类似题时，先问自己"命题人想考我什么概念差异？"——是动态性、访问方式还是操作效率？