Day10-A1 图的概念与邻接表专项（GESP高等级风格）

独立训练图的方向、度数、邻接矩阵、邻接表及存储复杂度。后四题共用完整程序。

#include <iostream>
#include <vector>
using namespace std;
int main(){
    int n,m; cin>>n>>m;
    vector<vector<int>> g(n+1);
    for(int i=0;i<m;++i){
        int u,v; cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for(int i=1;i<=n;++i) cout<<g[i].size()<<' ';
}

第 1 题

稀疏图需要频繁枚举邻接点时，通常优先使用（ ）。

{{ select(1) }}

• 二维前缀和
• 邻接表
• 邻接矩阵
• 只保存顶点

第 2 题

含 $n$ 个顶点的邻接矩阵空间复杂度是（ ）。

{{ select(2) }}

• $O(n^2)$
• $O(m)$
• $O(\log n)$
• $O(n)$

第 3 题

无向图有 $m$ 条边，按两个方向存入邻接表，表项总数为（ ）。

{{ select(3) }}

• $m$
• $2m$
• $n+m$
• $n^2$

第 4 题

有向边 $u\to v$ 会使哪个量增加 1？（ ）

{{ select(4) }}

• 顶点 $v$ 的出度
• 图的顶点数
• 顶点 $v$ 的入度
• 顶点 $u$ 的入度

第 5 题

输入 4 3，边为 1 2、1 3、2 4，输出为（ ）。

{{ select(5) }}

• 2 2 1 1
• 3 3 3 3
• 1 1 1 1
• 2 1 1 0

第 6 题

程序中 g[u] 表示（ ）。

{{ select(6) }}

• 从 u 出发的最短路
• 第 u 条边
• 图中所有入度
• 与顶点 u 直接相邻的顶点序列

第 7 题

若输入边允许自环 u u，当前建边代码会把 u 放入 g[u]（ ）次。

{{ select(7) }}

• 0
• 1
• 2
• n

第 8 题

遍历所有 g[i] 中的元素，时间复杂度为（ ）。

{{ select(8) }}

• $O(1)$
• $O(2^n)$
• $O(n^2m)$
• $O(n+m)$