NOIP 普及组初赛 · NOIP 2015 普及组初赛试题 第 13 题

链表不具备的特点是( )。

这题考内存管理基础，拿到题先想：数组和链表在底层存储上最大的区别是什么？数组是连续块，链表是离散节点，这个本质差异直接决定了能否随机访问。

最容易掉进命题人的陷阱是混淆‘优点’和‘缺点’。学生往往把‘插入删除快’‘不需预估空间’这些链表的优势当成错误选项，因为题目问的是‘不具备的特点’。另外，有些同学会纠结‘空间与元素数成正比’这句话，觉得链表有额外指针开销所以不成正比，其实只要忽略常系数，线性关系是成立的，命题人特意把这点放在D选项就是看你是否真正理解‘成正比’的数学含义。

考点与概念

这道题考查的是线性存储结构中最基础的对比：数组与链表。命题人挖坑的点在于，它不问你具体怎么写代码，而是问你“链表不具备什么特点”，本质是让你辨析两种结构的底层差异。

命题视角与思考心法

拿到这种概念题，不要急着背口诀，先想两个核心问题： 1. 数据在内存里是怎么摆的？ 2. 如果要找第 k 个元素，我该怎么走？

数组在内存里是连续的一块，地址可以直接算出来：第 i 个元素的地址 = 首地址 + i * 元素大小。所以只要知道首地址和 i，就能 O(1) 直接跳到它，这叫随机访问。

链表呢？每个节点里存着数据和指向下一个节点的指针。内存里节点是离散分布的，它们之间没有固定的地址关系。要找第 k 个元素，只能从表头开始，顺着指针一个个往后跳：第 1 个、第 2 个……直到第 k 个。时间复杂度是 O(k)，无法随机访问。