GESP 七级 · GESP202609 C++ 七级第 23 题

判断题 · 答案 B · 考点：图的存储、复杂度分析

题目

使用邻接表存储图时，遍历某个顶点的所有邻边所需时间与图中顶点数成正比。

答案：B

图的存储复杂度分析

邻接表中每个顶点维护一个链表存储其邻接点，遍历某个顶点的邻边只需扫描该顶点对应的链表，耗时取决于该顶点的度数（邻接点个数），而非图中总顶点数。命题人考察的是对邻接表结构的理解：链表长度与顶点总数无直接关系，平均度数远小于顶点数，因此时间复杂度与顶点数不成正比。

选项A的陷阱在于混淆了"遍历某个顶点"与"遍历整个图"的概念。命题人利用考生对邻接表遍历机制的模糊认识——误以为邻接表遍历需要访问所有顶点，或者将邻接表与邻接矩阵的遍历复杂度（邻接矩阵中遍历某顶点邻边需扫描整行，与顶点数成正比）相混淆。

本题考查GESP七级《数据结构》模块中"图的存储结构"知识点。命题人专门设置这道题，就是要卡住绝大多数考生对邻接表遍历机制的理解盲区——他们往往把邻接表想成"遍历整个图"的结构，却忽略了"遍历某个顶点"只需访问该顶点对应的链表这一核心特性。

看到题先想：邻接表的结构是什么？每个顶点v对应一个链表L_v，链表长度等于v的度数deg(v)。遍历L_v需要访问链表中的每个节点，时间复杂度为O(deg(v))。

关键观察：deg(v)的上界是n-1（n为顶点总数），但实际度数可远小于n。例如星形图中中心点度数为n-1，但叶子点度数均为1；随机图中平均度数约为2m/n（m为边数）。因此O(deg(v))与O(n)不是同一量级。

数值推演：设n=1000，若某顶点度数为10，遍历耗时O(10)；若度数为999，耗时O(999)。两者相差两个数量级，显然"与顶点数成正比"的说法不成立。

通法提炼：判断遍历复杂度时，先定位数据结构中对应元素的位置——邻接表是"顶点→链表"映射，邻接矩阵是"顶点→数组"映射，邻接多重表是"顶点→链表→链表"映射。复杂度取决于该位置结构的长度，而非整体规模。

第 16 题· NOIP 2009 提高组初赛试题 · 答案 ABD看解析 →
第 19 题· NOIP 2014 提高组初赛试题 · 答案 AC看解析 →
第 28 题· NOIP 2015 提高组初赛试题 · 答案 v=-1dist[i]<dist[v]dist[v]>dist[i]dist[i]<=dist[v]dist[v]>=dist[i]v=iused[v]=1dist[v]+w[v][i]<dist[i]dist[i]>dist[v]+w[v][i]dist[v]+w[v][i]<=dist[i]dist[i]>=dist[v]+w[v][i]看解析 →
第 28 题· NOIP 2016 提高组初赛试题 · 答案 dist[1]=0dist[x]+weight[j]<dist[point[j]]weight[j]+dist[x]<dist[point[j]]dist[point[j]]>weight[j]+dist[x]dist[point[j]]>dist[x]+weight[j]visit[x]=0weight[j]+dist[x]==dist[point[j]]dist[x]+weight[j]==dist[point[j]]visit[point[j]]=1看解析 →
第 28 题· NOIP 2017 提高组初赛试题 · 答案 degree[b]=degree[b]+1degree[b]++++degree[b]degree[i]==0!degree[i]degree[i]=degree[i]-1degree[i]----degree[i]head=head+1head++++headans<len[a]len[a]>ans看解析 →

在 OI伴学里做这道题

登录后可计时作答、查看完整六段式解析，并按你的错题自动生成同类练习。