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

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

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

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

【考点】数组内存布局｜链表节点结构｜指针开销

1. 考纲定位：GESP五级"数据结构"模块第3章考点。命题人专挖"链表省内存"的常见误区，90%考生误以为动态分配=少占空间，实则忽略了指针开销。

2. 解题思维：逐项验证。A项正确（数组定长，链表可动态增删）；B项正确（数组下标直达O(1)，链表遍历O(n)）；D项正确（数组插入需移动元素O(n)，链表指针定位后插入O(1)）；C项错误——存储n个整数，数组仅占n×sizeof(int)字节，链表每节点多一个指针域（32位系统4字节，64位8字节），总内存反而更多。

3. 陷阱拆解：C项的阴险在于"存储相同数目"的表述。考生易被"动态"二字误导，以为链表更省。实则每节点指针开销是硬成本，且题目未限定指针位数，命题人故意留白制造模糊。若只背"链表灵活"而忽略内存模型，必选错。

4. 反命题思维：若把"整数"换成"无符号整数"，内存仍由指针主导；若改为"数组比链表多占内存"，命题人会要求考生考虑指针大小差异。刷到此类题，先问"命题人想考我什么"。