GESP 七级 · GESP 202503 C++ 七级第 22 题

判断题 · 答案 A · 考点：图的存储、时间复杂度分析、算法

题目

邻接表和邻接矩阵都是图的存储形式。为了操作时间复杂度考虑，同一个图可以同时维护两种存储形式。

答案：A

图的存储时间复杂度分析算法

邻接矩阵是n×n的方阵，matrix[i][j]表示顶点i到j是否有边（有权图存权值）。n个顶点需n²空间。

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

【考点】图的存储结构｜时间复杂度分析｜算法优化策略

七级算法模块中"图的存储与遍历"核心考点。命题人专卡考生对数据结构适用场景的模糊认知——多数学生能背诵邻接表适合稀疏图、邻接矩阵适合稠密图，但常忽略"双存储"在特定场景下的互补价值。

第 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伴学里做这道题

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