第六章 图

课程名称：算法与数据结构 总分：76分 答题时长：60分钟 出卷人：刘辉

一、单项选择题：(共13题，26分)
1、 在一个图中，所有顶点的度数之和等于图的边数的（ ）倍。
0.5
1
2
4
2、 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（ ）倍。
0.5
1
2
4
3、 具有n个顶点的有向图最多有（ ）条边。
n
n(n-1)
n(n+1)
n2
4、 G是一个非连通无向图，共有28条边，则该图至少有（ ）个顶点。
7
8
9
10
5、 若从无向图的任意一个顶点出发进行一次深度优先搜索可以访问图中所有的顶点，则该图一定是（ ）图。
非连通
连通
强连通
有向
6、 下面（　）算法适合构造一个稠密图G的最小生成树。
Prim算法
Kruskal算法
Floyd算法
Dijkstra算法
7、 n个顶点的连通图用邻接距阵表示时，该距阵至少有（ ）个非零元素。
n
2(n-1)
n/2
n2
8、 用邻接表表示图进行深度优先遍历时，通常借助（ ）来实现算法。
栈
队列
树
图
9、 深度优先遍历类似于二叉树的（ ）。
先序遍历
中序遍历
后序遍历
层次遍历
10、 广度优先遍历类似于二叉树的（ ）。
先序遍历
中序遍历
后序遍历
层次遍历
11、 图的BFS生成树的树高比DFS生成树的树高（ ）。
小
相等
小或相等
大或相等
12、 用邻接表表示图进行广度优先遍历时，通常借助（ ）来实现算法。
栈
队列
树
图
13、 下面（ ）方法可以判断出一个有向图是否有环。
深度优先遍历
拓扑排序
求最短路径
求关键路径
二、简答题：(共3题，15分)
1、 试对图6.36所示的AOE-网：

2、 已知图6.32所示的有向图，请给出：

① 每个顶点的入度和出度；    

② 邻接矩阵；

③ 邻接表；

④ 逆邻接表。            

3、 已知如图6.33所示的无向网，请给出：

① 邻接矩阵；    

② 邻接表；

③ 最小生成树

三、问答题：(共5题，25分)
1、 分别以邻接矩阵和邻接表作为存储结构，实现以下图的基本操作： ① 增加一个新顶点v，InsertVex(G, v)； ② 删除顶点v及其相关的边，DeleteVex(G, v); ③ 增加一条边，InsertArc(G, v, w); ④ 删除一条边，DeleteArc(G, v, w)。
2、 一个连通图采用邻接表作为存储结构，设计一个算法，实现从顶点v出发的深度优先遍历的非递归过程。
3、 试基于图的深度优先搜索策略写一算法，判别以邻接表方式存储的有向图中是否存在由顶点vi到顶点vj的路径（i≠j）。
4、 采用邻接表存储结构，编写一个算法，判别无向图中任意给定的两个顶点之间是否存在一条长度为k的简单路径。
5、 设计一个算法，求图G中距离顶点v的最短路径长度最大的一个顶点，设v可达其余各个顶点。