Day 20　图的基本概念与性质

建议用时：15～25 分钟。请先完成自主学习，再独立提交本页答案。

今日学习资料

• 打开今日蓝白学习页
• 下载今日 PDF

学习目标：完成当天知识点阅读与易错清单自查，然后作答下方选择题。

今日练习

1. 一个有 8 个顶点的无向完全图共有（　）条边。

{{ select(1) }}

• 8
• 16
• 28
• 56

2. 一个有 6 个顶点的有向完全图共有（　）条弧。

{{ select(2) }}

• 15
• 21
• 30
• 36

3. 【CSP-J 2024 初赛·第 11 题】在无向图中，所有顶点的度数之和等于（　）。

{{ select(3) }}

• 图的边数
• 图的边数的两倍
• 图的顶点数
• 图的顶点数的两倍

4. 一个有 n 个顶点的无向图若是连通的，则它至少有（　）条边。

{{ select(4) }}

• n − 1
• n
• n(n−1)/2
• 2n − 2

5. 一个有 10 个顶点的无向图，至少要有（　）条边才能 保证 它一定是连通图。

{{ select(5) }}

• 9
• 36
• 37
• 45

6. 判断题：任何一个无向图中，度为奇数的顶点个数一定是偶数。（　）

{{ select(6) }}

• 正确
• 错误

7. 关于拓扑排序，下列说法 错误 的是（　）。

{{ select(7) }}

• 只有有向无环图才存在拓扑序列
• 一个有向无环图的拓扑序列可能不唯一
• 若有向图中存在环，则无法得到包含全部顶点的拓扑序列
• 无向连通图也可以进行拓扑排序

8. 用邻接矩阵存储一个有 n 个顶点、m 条边的图，所需的存储空间为（　）。

{{ select(8) }}

• O(n)
• O(m)
• O(n + m)
• O(n²)

9. 在无向图的邻接矩阵中，第 i 行所有元素之和等于（　）。

{{ select(9) }}

• 顶点 i 的度
• 顶点 i 的入度
• 图的边数
• 图的顶点数

10. 一个无向连通图存在欧拉回路的充要条件是（　）。

{{ select(10) }}

• 所有顶点的度都是偶数
• 恰有两个顶点的度是奇数
• 所有顶点的度都相等
• 边数等于顶点数减 1