NOIP 提高组初赛 · NOIP 2009 提高组初赛试题第 16 题

选择题 · 答案 ABD · 考点：图的存储、图的基本概念

题目

若 $3$ 个顶点的无权图 $G$ 的邻接矩阵用数组存储为 $\{\{0,1,1\},\{1,0,1\},\{0,1,0\}\}$，假定在具体存储中顶点依次为: $v_1, v_2, v_3$。关于该图，下面的说法哪些是正确的：

答案：ABD

这题考有向图邻接矩阵判断、强连通定义、入出度性质及遍历差异。先看矩阵不对称性定有向，再验证任意两点互达定强连通，最后结合遍历规则看序列是否重合。

容易把矩阵不对称当成无向图，忽略有向图邻接矩阵不一定对称；入出度之和差值误算成非零，其实有向图入度总和恒等于出度总和；DFS与BFS序列默认不同，但在本图特定结构中可能巧合相同，需仔细推演。

本题核心是有向图邻接矩阵、强连通图、入出度关系以及DFS/BFS遍历序列。邻接矩阵中，matrix[i][j]=1表示存在有向边 v_i→v_j；强连通要求任意两点互相可达；有向图必有入度总和=出度总和；DFS/BFS序列取决于访问顺序和队列/栈的调度。

命题人喜欢用“不对称矩阵”考有向图，用“看似连通但需验证互达”考强连通，用“入出度差值”考基本概念，用“特定图DFS/BFS序列相同”考遍历细节。本题把四个点串在一起，难度适中。

第 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看解析 →
第 12 题· CSP 2019 提高级第一轮 · 答案 D看解析 →

在 OI伴学里做这道题

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