Day10 查缺补漏专项（图搜索·拓扑排序·网络基础）

满分 100 分，共 50 题。所有程序均为完整程序组；请先读程序功能，再回答该组问题。

---

一、基础选择题

覆盖图的存储、DFS/BFS、DAG 与拓扑排序、计算机网络、操作系统、数据库、信息安全及算法识别。

第 1 题

一个含 $n$ 个顶点、$m$ 条边的稀疏图，若需要遍历某个顶点的所有邻接点，通常更适合使用（ ）。

{{ select(1) }}

• 哈希表且不保存边
• 邻接表
• 邻接矩阵
• 只保存顶点数组

第 2 题

用邻接矩阵存储一个有 $n$ 个顶点的图，其空间复杂度通常是（ ）。

{{ select(2) }}

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

第 3 题

无向图中有 $m$ 条边。若邻接表对每条边的两个方向都各存一次，则所有邻接链表中的元素总数是（ ）。

{{ select(3) }}

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

第 4 题

在有向图中，顶点 $v$ 的入度是指（ ）。

{{ select(4) }}

• 以 $v$ 为起点的边数
• 与 $v$ 相邻的所有顶点数且不分方向
• 从 $v$ 出发能到达的顶点数
• 以 $v$ 为终点的边数

第 5 题

下列关于有向无环图（DAG）的说法，正确的是（ ）。

{{ select(5) }}

• 一定没有出度为 0 的顶点
• 一定存在至少一个入度为 0 的顶点
• 一定只有一个入度为 0 的顶点
• 一定是连通图

第 6 题

对一个有向图执行 Kahn 拓扑排序，最终得到的顶点数少于图中顶点总数，说明（ ）。

{{ select(6) }}

• 图中没有边
• 图的邻接表一定构造错误
• 图中存在有向环
• 图一定不连通

第 7 题

关于拓扑序列，下列说法正确的是（ ）。

{{ select(7) }}

• 无向图也能按同样定义进行拓扑排序
• 一个 DAG 可能存在多个不同的拓扑序列
• 任意有向图都存在拓扑序列
• 拓扑序列要求每条边的终点都排在起点之前

第 8 题

递归实现 DFS 时，系统主要依靠哪种结构保存尚未返回的调用信息？（ ）

{{ select(8) }}

• 队列
• 堆
• 并查集
• 栈

第 9 题

对无权图从源点 $s$ 执行 BFS，第一次访问顶点 $v$ 时得到的层数表示（ ）。

{{ select(9) }}

• 图中经过 $v$ 的环数
• 从 $s$ 到 $v$ 的最少边数
• 从 $s$ 到 $v$ 的最长简单路长度
• 顶点 $v$ 的度数

第 10 题

使用邻接表存储图时，一次完整 DFS 或 BFS 的时间复杂度通常是（ ）。

{{ select(10) }}

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

第 11 题

在 DFS/BFS 中使用 visited 数组的主要目的是（ ）。

{{ select(11) }}

• 避免同一顶点被反复访问
• 自动将邻接点排序
• 记录每条边的权值
• 把有向图变成无向图

第 12 题

在无权图中要求从一个源点到其余各点的最短步数，最直接的算法是（ ）。

{{ select(12) }}

• BFS
• 只做一次冒泡排序
• 普通二分查找
• 哈夫曼编码

第 13 题

域名 www.example.com 需要被转换为网络通信使用的 IP 地址，这项工作通常由（ ）完成。

{{ select(13) }}

• SQL
• DNS
• CPU
• ASCII

第 14 题

IPv4 地址由多少个二进制位组成？（ ）

{{ select(14) }}

• 128
• 32
• 16
• 64

第 15 题

下列协议中，通常用于浏览器与 Web 服务器之间传输网页内容的是（ ）。

{{ select(15) }}

• HTTP/HTTPS
• DNS
• DHCP
• ARP

第 16 题

与 UDP 相比，TCP 的典型特点是（ ）。

{{ select(16) }}

• 面向连接并提供可靠传输
• 一定比 UDP 延迟更低
• 不需要确认和重传
• 只能在局域网中使用

第 17 题

IP 地址主要用于标识（ ）。

{{ select(17) }}

• 文件在磁盘中的物理扇区
• 数据库表中的主键
• 网络中的主机或接口
• C++ 程序中的变量

第 18 题

HTTPS 相比 HTTP 主要增加了（ ）。

{{ select(18) }}

• 把域名永久替换成 MAC 地址
• 保证网页没有任何程序错误
• 取消客户端与服务器的通信
• 加密与身份认证机制

第 19 题

操作系统的核心职责不包括（ ）。

{{ select(19) }}

• 管理文件和设备
• 替程序员自动证明所有算法正确
• 管理进程
• 管理内存

第 20 题

编译器的主要作用是（ ）。

{{ select(20) }}

• 管理数据库表
• 只检查键盘是否正常
• 把源程序翻译成目标程序或机器可执行形式
• 给计算机分配 IP 地址

第 21 题

数据库表中的主键应当满足的核心要求是（ ）。

{{ select(21) }}

• 只能由中文字符串构成
• 必须等于记录的存储地址
• 能够唯一标识一条记录
• 每条记录的主键必须相同

第 22 题

收到自称老师的陌生链接，要求立即输入账号和密码，较安全的做法是（ ）。

{{ select(22) }}

• 立刻输入并把验证码一并发送
• 把链接转发给所有同学
• 关闭杀毒软件后再打开
• 通过可信渠道核实，不直接在链接中输入密码

第 23 题

数组 pre[i] 表示前 $i$ 个数之和，则闭区间 $[l,r]$ 的元素和为（ ）。

{{ select(23) }}

• pre[r] - pre[l - 1]
• pre[r] + pre[l - 1]
• pre[l] - pre[r]
• pre[r - l]

第 24 题

当数据规模很小，需要枚举所有可能方案并逐一验证时，这种方法通常称为（ ）。

{{ select(24) }}

• 枚举法
• 拓扑排序
• 哈夫曼编码
• 地址解析

第 25 题

回溯法搜索所有方案时，在尝试一个选择后继续递归；递归返回后通常还需要（ ）。

{{ select(25) }}

• 清空整个输入
• 把所有顶点入度加一
• 结束程序且不再搜索
• 撤销刚才的选择

---

二、阅读程序一：邻接表与 DFS

程序读入一个无向图，使用邻接表存储，并通过 DFS 统计图的连通分量个数。

#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> g;
vector<int> visited;

void dfs(int u) {
    visited[u] = 1;
    for (int v : g[u]) {
        if (!visited[v]) dfs(v);
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    g.assign(n + 1, {});
    visited.assign(n + 1, 0);
    for (int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    int cnt = 0;
    for (int i = 1; i <= n; ++i) {
        if (!visited[i]) {
            ++cnt;
            dfs(i);
        }
    }
    cout << cnt;
}

第 26 题

输入 6 4，四条边依次为 1 2、2 3、4 5、5 6，程序输出为（ ）。

{{ select(26) }}

• 3
• 4
• 2
• 1

第 27 题

变量 cnt 表示（ ）。

{{ select(27) }}

• 无向图的连通分量个数
• 图中边的条数
• 度数最大的顶点编号
• 从 1 号点出发的最短距离

第 28 题

若图有 $n$ 个顶点且没有任何边，程序输出为（ ）。

{{ select(28) }}

• $n-1$
• $n$
• 0
• 1

第 29 题

在当前无向图程序中，如果删除 visited 数组及相应判断，递归可能无法结束，主要原因是（ ）。

{{ select(29) }}

• 一条无向边会使两个端点互相递归访问
• 邻接表无法保存无向边
• vector 不能在递归中使用
• 顶点编号必须从 0 开始

第 30 题

该程序使用邻接表时的时间复杂度是（ ）。

{{ select(30) }}

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

---

三、阅读程序二：BFS 与无权最短路

程序读入一个无向无权图和源点，使用 BFS 输出源点到每个顶点的最少边数；不可达顶点输出 -1。

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main() {
    int n, m, s;
    cin >> n >> m >> s;
    vector<vector<int>> g(n + 1);
    for (int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    vector<int> dist(n + 1, -1);
    queue<int> q;
    dist[s] = 0;
    q.push(s);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int v : g[u]) {
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }
    for (int i = 1; i <= n; ++i) cout << dist[i] << ' ';
}

第 31 题

输入 6 5 1，五条边依次为 1 2、1 3、2 4、3 5、5 6，程序输出为（ ）。

{{ select(31) }}

• 0 1 1 2 2 3
• 1 2 2 3 3 4
• 0 1 1 2 3 4
• 0 1 2 3 4 5

第 32 题

若顶点 $v$ 从源点 $s$ 不可达，程序最终输出的 dist[v] 为（ ）。

{{ select(32) }}

• $n$
• -1
• 0
• 1

第 33 题

发现一个尚未访问的邻接点 v 时立即设置 dist[v] 的作用不包括（ ）。

{{ select(33) }}

• 记录最少边数
• 标记 v 已经发现
• 避免 v 被重复加入队列
• 计算带负权边图的最短路

第 34 题

若把队列换成栈并保持其余代码形式，通常将变成类似（ ）的访问过程。

{{ select(34) }}

• 归并排序
• 迭代式 DFS
• 二分查找
• 拓扑排序且一定正确

第 35 题

BFS 能保证本程序的距离最短，是因为（ ）。

{{ select(35) }}

• 每个顶点的编号都比前驱大
• 邻接表自动按边权排序
• 无向图一定是一棵树
• 顶点按距离从小到大的层次被扩展

---

四、阅读程序三：DAG 与拓扑排序

程序读入一个有向图，使用 Kahn 算法求拓扑序；若无法输出全部顶点，则输出 cycle。

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> g(n + 1);
    vector<int> indeg(n + 1, 0);
    for (int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        ++indeg[b];
    }
    queue<int> q;
    for (int i = 1; i <= n; ++i)
        if (indeg[i] == 0) q.push(i);

    vector<int> order;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        order.push_back(u);
        for (int v : g[u]) {
            --indeg[v];
            if (indeg[v] == 0) q.push(v);
        }
    }
    if ((int)order.size() < n) cout << "cycle";
    else for (int x : order) cout << x << ' ';
}

第 36 题

输入 5 5，五条有向边依次为 1 3、2 3、3 4、2 5、4 5，程序输出为（ ）。

{{ select(36) }}

• 2 1 3 4 5
• 1 3 2 4 5
• 1 2 5 3 4
• 1 2 3 4 5

第 37 题

执行 --indeg[v] 表示（ ）。

{{ select(37) }}

• 计算从源点到 v 的最短距离
• 删除已输出顶点 u 指向 v 的影响
• 给图增加一条指向 v 的边
• 把顶点 v 从邻接表中删除

第 38 题

输入包含有向边 1 2、2 3、3 1 时，程序会输出 cycle，原因是（ ）。

{{ select(38) }}

• 邻接表不能存储三条边
• 队列只能保存两个顶点
• 这三个顶点构成有向环，无法全部变成入度 0
• 顶点编号不是连续的

第 39 题

若希望每次选择编号最小的入度为 0 的顶点，可把 queue<int> 换成（ ）。

{{ select(39) }}

• 邻接矩阵
• 小根优先队列
• 普通栈
• 字符串

第 40 题

关于拓扑序唯一性的判断，正确的是（ ）。

{{ select(40) }}

• 只要边数为 $n-1$，拓扑序就唯一
• 任意 DAG 的拓扑序都唯一
• 若 Kahn 算法每一步都只有一个可选的入度 0 顶点，则拓扑序唯一
• 只要图连通，拓扑序就唯一

---

五、完善程序一：DFS 统计连通分量

请补全程序。程序读入无向图，使用邻接表和 DFS，输出连通分量个数。

#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> g;
vector<int> visited;

void dfs(int u) {
    visited[u] = 1;
    for (int v : g[u]) {
        if (①) dfs(②);
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    g.assign(n + 1, {});
    visited.assign(n + 1, 0);
    for (int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        ③;
    }
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        if (④) {
            ++ans;
            ⑤;
        }
    }
    cout << ans;
}

第 41 题

①处应填（ ）。

{{ select(41) }}

• !visited[v]
• visited[u]
• u == v
• g.empty()

第 42 题

②处应填（ ）。

{{ select(42) }}

• m
• v
• u
• n

第 43 题

③处应填（ ）。

{{ select(43) }}

• g[a].push_back(a)
• visited[b] = 1
• g.clear()
• g[b].push_back(a)

第 44 题

④处应填（ ）。

{{ select(44) }}

• i == 0
• g[i].empty()
• !visited[i]
• visited[i]

第 45 题

⑤处应填（ ）。

{{ select(45) }}

• visited.assign(n + 1, 0)
• return 0
• dfs(i)
• dfs(0)

---

六、完善程序二：BFS 求最短步数

请补全程序。程序读入无向无权图和源点，输出源点到每个顶点的最少边数；不可达顶点输出 -1。

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main() {
    int n, m, s;
    cin >> n >> m >> s;
    vector<vector<int>> g(n + 1);
    for (int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    vector<int> dist(n + 1, ①);
    queue<int> q;
    dist[s] = 0;
    ②;
    while (!q.empty()) {
        int u = ③;
        q.pop();
        for (int v : g[u]) {
            if (④) {
                dist[v] = ⑤;
                q.push(v);
            }
        }
    }
    for (int i = 1; i <= n; ++i) cout << dist[i] << ' ';
}

第 46 题

①处应填（ ）。

{{ select(46) }}

• 0
• 1
• n
• -1

第 47 题

②处应填（ ）。

{{ select(47) }}

• q.push(0)
• dist.clear()
• q.push(s)
• q.pop()

第 48 题

③处应填（ ）。

{{ select(48) }}

• q.back()
• s + 1
• dist[s]
• q.front()

第 49 题

④处应填（ ）。

{{ select(49) }}

• v == s
• dist[u] < 0
• dist[v] == -1
• dist[v] == 0

第 50 题

⑤处应填（ ）。

{{ select(50) }}

• dist[u] + 1
• dist[u] - 1
• dist[v] + 1
• u + v