BCSP-X · 2024 BCSP-X 上半年活动基础知识测评（小学高年级组） 第 13 题

链表不具备的特点是（ ）。

这题考的是链表和数组的核心特性对比。拿到题先想：随机访问靠什么？数组靠下标直接算地址，链表得从头一个个找。抓住这个本质区别，A 选项就露馅了。

最容易栽跟头就是把链表和数组记混，以为链表也能像数组那样 O(1) 随机访问。另外，有些同学看到插入删除不用移动元素，就误以为所有线性表都这样，忽略了数组的插入删除需要挪动后面一堆数据。还有，关于内存地址不连续这点，容易和树、图的非线性存储搞混，其实链表是典型的顺序逻辑、物理存储可断开的结构。

这道题考查的是线性表的两种存储方式——顺序存储（数组）和链式存储（链表）的本质区别，以及由此决定的操作时间复杂度。命题人特别喜欢在‘随机访问’和‘增删效率’这两个对立面出题，让你辨析谁是谁的强项。

先说概念：数组是顺序存储，元素在内存里挨着排，所以只要知道首地址和下标，就能用公式直接算出任意元素的地址，时间复杂度 O(1)，这就是‘随机访问’。链表是链式存储，每个节点存数据和指向下一个节点的指针，物理地址是散的，不要求连续，所以内存利用率灵活，不需要事先估算总大小，随用随申请。但正因为节点分散，要找第 k 个元素，只能从表头顺着指针一步步挪，时间复杂度 O(n)。

再看操作：数组插入或删除某个位置元素，得把后面一堆数据整体挪动，O(n)；链表插入删除只需要改两个指针（前驱和后继），O(1)（前提是已经找到位置）。所以 B 选项‘插入、删除不需要移动元素’是对的，C 选项‘地址可以不连续’也是对的，D 选项‘无需事先估计存储空间’同样正确。

命题坑点就在 A：链表不具备 O(1) 随机访问。很多初学者死记‘链表增删快’，却忘了‘查’是最慢的。树和图属于非线性结构，但本题只问链表，不用扯树边数之类。

考频与趋势：BCSP 近年对数据结构基础概念的考查非常稳定，尤其是数组与链表的对比，几乎年年出现，属于高频考点。从 2021 到 2024 年，这类题在单选题中占比约 25%-30%，且命题角度越来越细，比如结合指针操作、内存分配细节等。

预测：未来大概率还会继续考链表与数组的对比，可能会在更复杂的场景下（如动态规划、分治算法）要求你选择合适的数据结构，或者考查链表的高级操作（如环检测、快慢指针）。但核心依然是抓住‘随机访问 O(1) vs O(n)'这个根本差异。