第六章 图 测验题

A. 概述

1. 两个通过一条边连起来的顶点之间的关系称为：邻接

2. 一笔画问题即要找出：欧拉路径

B. 邻接矩阵

1. 任何两个顶点间都有一条（无向）边的图称为完全图，包含n个顶点的完全图用Kn表示。下列哪个图一定不是平面图？K5

（显然其余三个都是平面图。K_5不是平面图可以用欧拉公式以及平面图中的一个面最多平均对应3/2条边这一事实来证明。）

2. 第二题：

3. 在包含n个顶点的用邻接矩阵实现的图中，顶点v有m个邻居，遍历所有m个邻居的时间复杂度为：O(n)

（需要访问邻接表中的一行）

4. 图G包含n个顶点(n>0)，用邻接矩阵实现。在其中加入一个新的顶点后邻接矩阵增加了多少项？2n+1

（邻接矩阵增加了一行一列）

C. 广度优先搜索

1. 对图进行遍历某种意义上是将图转化为：树

2. 图的广度优先搜索访问各顶点的模式类似于二叉树的：层次遍历

3. 第三题：

4. 对于用邻接表实现的包含n个顶点e条边的图，BFS的时间复杂度为：O(n+e)

D. 广度优先搜索

1. 第一题：

2. u 和 v 为图中两个顶点，对图进行 DFS 后，dTime(u) < dTime(v) < fTime(v) < fTime(u)，则 u 和 v 在 DFS 森林中的关系是：u 为 v 的祖先

3. 对同一个无向图分别运行广度优先算法和深度优先算法，得到的树边数量：两种算法得到的树边一样多

（树边的数量总是等于顶点数减去连通分量的数量）

4. 对图进行DFS，一下哪种情况意味着该图包含环路：有BACKWARD边

章节测试

1. 在含20个顶点的简单无向图中，边的数量最多为：190；此时度最小的顶点的度为：19

2. 某宴会一共有7个人参加，与会者之间进行了亲切的握手。已知他们中的每个人进行握手的次数分别为：3, 1, 2, 2, 3, 1, 2

请问宴会上总共发生了多少次握手？ 7

（做出无向图即可看出结果）

3. 在人类的历史长河中，每个人都可能要与其他人握手。如果某人在他的一生中进行握手的次数为奇数，则称他为A类人，否则称为B类人。试问从古至今A类人的个数是：(假设人类只能和人类握手)  偶数

（无向图的边数等于各顶点度数之和的一半，变数为奇数则顶点数必定为偶数）

4. 以上有向图的邻接矩阵为（图中顶点以A、B、C、D为顺序）

 5. 对于包含n个顶点e条边的简单无向图，以下关于它的邻接矩阵A的说法中错误的是：

 A有n行e列，其中元素取值于{0, 1}

（n行n列）

6. G是简单无向图，A为G的邻接矩阵，M为G的关联矩阵，D是对角线上第i个元素为顶点i的度的对角矩阵,它们的关系是：（习题6-1）

 7. 用邻接矩阵实现含n个顶点e条边的图，空间复杂度：O(n^2)

8. 删除边(i, j)的时间复杂度：O(1)

9. 遍历顶点v的所有邻居的时间复杂度：O(n)

10. 访问顶点v中存储的数据的时间复杂度：O(1)

11.  G是有向无环图，(u, v)是G中的一条由u指向v的边。对G进行DFS的结果是：fTime(u) > fTime(v)

（G不含环路，(u, v)不可能是BACKWARD，对u的访问结束时对v的访问必然已经结束）

12. 下面是对一个简单无向图进行DFS后得到各顶点的dTime和fTime:

得到的DFS树为：

 13. 从s开始，对以上无向图进行BFS，同一顶点的邻居之间以a~z为序，求顶点的dTime：

 s的dTime = 1；a的dTime = 2；b的dTime = 6；e的dTime = 5；f的dTime = 7

（注意题干为BFS，根据进入队列顺序，可以知道s和a-g的dTime依次为：1，2，6，3，4，5，7，8即s, a, c, d, e, b, f, g）

14. 从s开始，对以上无向图进行DFS，同一顶点的邻居之间以a~z为序，求各顶点的dTime和fTime:

s的dTime = 1, s的fTime = 16；c的dTime = 3, c的fTime = 14；g的dTime = 7, g的fTime = 12

（注意题干为DFS，根据算法原理可以整理出下表：

）