NOIP 提高组初赛 · NOIP 2014 提高组初赛试题第 19 题

选择题 · 答案 AC · 考点：图的存储

题目

以下哪些结构可以用来存储图( ).

答案：AC

图的存储

这题考图的存储结构，拿到题别急着背定义，先想图的本质是点和边的集合，再看选项哪个能完整记录点和边。邻接矩阵用二维数组存点间关系，邻接表用链表存每个点的邻居，这两个都能把图完整存下来。

学生最容易把栈和二叉树误选进去。栈是线性结构，只能在一端进出，存不了图这种复杂的关联关系；二叉树是树形结构，节点最多两个子节点，存图时会出现一个点连接多个邻居却无处安放的情况。还有同学会纠结邻接矩阵是不是只适合稠密图，其实它存的是顶点的邻接关系，稀疏图也能存，只是空间浪费点而已。

这题考查图的存储结构。图是由顶点和边组成的，存储图就是要用某种数据结构把顶点和边之间的关系完整记录下来。

图存储结构就是用来记录图中顶点和边之间关系的数据结构。对于无向图，如果顶点i和顶点j之间有边，那么i和j应该互相知道对方的存在；对于有向图，如果i到j有边，那么i应该知道j，但j不一定知道i。

第 16 题· NOIP 2009 提高组初赛试题 · 答案 ABD看解析 →
第 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看解析 →
第 12 题· CSP 2019 提高级第一轮 · 答案 D看解析 →

在 OI伴学里做这道题

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