GESP 七级 · GESP 202312 C++ 七级 第 21 题

简单有向图有 $n$ 个顶点和 $e$ 条弧，可以用邻接矩阵或邻接表来存储，二者求节点 $u$ 的度的时间复杂度一样。（ ）

这道题考的是图论基础里邻接矩阵和邻接表两种存储方式在求节点度时的时间复杂度对比。拿到题先明确有向图中‘度’的定义，再看两种结构怎么存边，最后对比遍历代价。

学生容易把‘时间复杂度一样’当成默认结论，或者混淆‘平均情况’和‘最坏情况’。邻接表在稀疏图上快很多，但大O只看最坏情况；还有人把‘度’误以为入度，导致分析方向全偏。

考点定位

题目落在GESP七级数据结构模块，核心是图的两种存储结构（邻接矩阵 vs 邻接表）以及时间复杂度分析。命题人专门挖了‘度’的定义歧义和‘平均快≠复杂度一样’这两个坑。

概念澄清

先说人话：有向图里，从节点u出发的边叫出度，指向u的边叫入度。题目只写‘度’，默认指出度（否则会说‘入度’或‘总度’）。邻接矩阵是n×n的方阵，matrix[u][v]=1表示u→v有边；邻接表里每个节点u挂一条链表，链上每个元素代表一条出边。

命题视角

命题人想卡住只背公式的学生：邻接表求出度只需数链表长度，邻接矩阵得一行一行扫。但‘快’不等于‘复杂度一样’——大O只看最坏情况，哪怕平均情况邻接表快十倍，只要存在某个图让邻接矩阵也O(n)，结论就不成立。更阴险的是‘度’的歧义，若学生误当成入度，两种结构都得扫n个元素，反而可能误选A。

思考心法

拿到题先问： 1. 操作具体指什么？ 求节点u的出度。 2. 两种结构怎么存？ 矩阵存一整行，链表存一条链。 3. 最坏情况是什么？ 矩阵一行n个元素，链表最长n个节点（稠密图）。 4. 遍历代价？ 矩阵必须扫完一行，O(n)；链表直接数长度，O(degree)。 5. 大O定义？ 只看最坏情况，degree最坏≈n，所以邻接表也是O(n)。 结论：两者在最坏情况下都是O(n)，时间复杂度一样，题干说法正确。

避坑详解

• 坑1：把‘度’默认当成入度。入度在矩阵里要扫整列（仍O(n)），在邻接表里得遍历所有节点（也是O(n)），看似相同，但题目没提入度，命题人利用此偷换概念误导学生。
• 坑2：混淆‘平均快’和‘复杂度一样’。邻接表在稀疏图上确实快，但大O不看平均，只看最坏。学生若只记‘邻接表快’，会误以为复杂度不同，从而选B。
• 坑3：忽略‘最坏case’的存在。有人觉得‘degree通常远小于n’，于是认为邻接表是O(1)或O(degree)就比O(n)低一档，但大O定义里degree最坏≈n，所以仍是O(n)。

考频与趋势

从题库数据看，图形结构是高频考点：共213题，2024年61题、2025年56题、2026年40题，近年持续高位。其中图的存储单独考过32题，2024年10题、2025年10题，2023年4题，呈现逐年上升趋势。这说明命题组越来越喜欢考存储结构对比，尤其是邻接矩阵和邻接表的时间/空间复杂度辨析。

预测

基于2024-2026年图形结构考频的持续走高，以及‘图的存储’在2024-2025年连续两年各10题的爆发，未来GESP七级乃至八级大概率会再次出现类似题目：要么考邻接表求入度/出度，要么考邻接矩阵求最短路径的复杂度对比，甚至可能把‘有向图’和‘无向图’混在一起问‘度’的定义陷阱。若数据不足以支撑更细的预测，则暂无足够依据预测具体题型，但可以确定：存储结构对比+复杂度分析仍是必考方向。