习　题　7

一、选择题

1.有n个顶点的无向完全图具有（　　）条边。

A.n（n＋1）/2　　　B.n－1　　　C.n　　　D.n（n－1）

2.在一个图中,所有顶点的度数之和等于图的边数的（　　）倍。

A.1/2　　　　B.1　　　　C.2　　　　D.4

3.在一个有向图中,所有顶点的入度之和等于所有顶点的出度之和的（　　）倍。

A.1/2　　　　B.1　　　　C.2　　　　D.4

4.有8个结点的有向完全图有（　　）条边。

A.14　　　　B.28　　　　C.56　　　　D.112

5.用邻接表表示图进行广度优先遍历时,通常是采用（　　）来实现算法的。

A.栈　　　　B.队列　　　　C.树　　　　D.图

6.深度优先遍历类似于二叉树的（　　）。

A.先序遍历　　　B.中序遍历　　　C.后序遍历　　　D.层次遍历

7.广度优先遍历类似于二叉树的（　　）。

A.先序遍历　　　B.中序遍历　　　C.后序遍历　　　D.层次遍历

二、填空题

1.网是带＿＿＿＿的图。

2.图的常用存储结构有＿＿＿＿和＿＿＿＿。

3.图的遍历方法一般有＿＿＿＿和＿＿＿＿两种。

4.无向图G是连通的无回路图,有且仅有＿＿＿＿条边。

5.如果n个顶点的图是一个环,则它有＿＿＿＿棵生成树。（以任意一顶点为起点,得到n－1条边）

6.n个顶点e条边的图,若采用邻接矩阵存储,则空间复杂度为＿＿＿＿。

7.n个顶点e条边的图,若采用邻接表存储,则空间复杂度为＿＿＿＿。

8.设有一稀疏图G,则G采用＿＿＿＿存储较省空间。

9.设有一稠密图G,则G采用＿＿＿＿存储较省空间。

10.已知一个图的邻接矩阵表示,删除所有从第i个顶点出发的边方法是＿＿＿＿。

11.图的深度优先遍历序列＿＿＿＿唯一的。

12.n个顶点e条边的图采用邻接矩阵存储,深度优先遍历算法的时间复杂度为＿＿＿＿；若采用邻接表存储时,该算法的时间复杂度为。

13.用普里姆（Prim）算法求具有n个顶点e条边的图的最小生成树的时间复杂度为＿＿＿＿；用克鲁斯卡尔（Kruskal）算法的时间复杂度是＿＿＿＿。

14.用Dijkstra算法求某一顶点到其余各顶点间的最短路径是按路径长度＿＿＿＿的次序来得到最短路径的。

15.若要求一个稀疏图G的最小生成树,最好用＿＿＿＿算法来求解。

16.若要求一个稠密图G的最小生成树,最好用＿＿＿＿算法来求解。

17.拓扑排序算法是通过重复选择具有＿＿＿＿个前驱顶点的过程来完成的。

三、判断题

1.有向图中一个顶点i的出度等于其邻接矩阵中第i列的非零元素的个数。（　　）

2.连通图G的生成树是G的极小连通子图。（　　）

3.连通网络的最小生成树是唯一的。（　　）

4.连通图的邻接矩阵是对称的,有向图的邻接矩阵是不对称的。（　　）

5.有n个顶点,n－1条边的图一定是生成树。（　　）

6.树是一种特殊形式的图。（　　）

7.图的BFS生成树的树高比DFS生成树的树高。（　　）

四、分析题

1.已知某图的邻接表存储结构如下图所示,则

（1）画出该图。

（2）根据该邻接表从顶点A出发,分别写出按深度优先搜索遍历法和广度优先遍历法进行遍历的结点序列。

2.下图矩阵表示一个无向网,画出该无向网,并构造出其最小生成树。

3.写出下图所示的有向图的邻接矩阵及该图的所有拓扑排序序列。

4.带权图（权值非负,表示边连接的两顶点间的距离）的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。假定从初始顶点到目标顶点之间存在路径,现有一种解决该问题的方法:

①设最短路径初始时仅包含初始顶点,令当前顶点u为初始顶点；

②选择离u最近且尚未在最短路径中的一个顶点v,加入到最短路径中,修改当前顶点u＝v；

③重复步骤②,直到u是目标顶点时为止。

请问上述方法能否求得最短路径？若该方法可行,请证明之；否则,请举例说明。

5.如下图所示为5个乡镇之间的交通图,乡镇之间道路的长度如图中边上所注。现在要在这5个乡镇中选择一个乡镇建立一个消防站,问这个消防站应建在哪个乡镇,才能使离消防站最远的乡镇到消防站的路程最短。试回答解决上述问题应采用什么算法,并写出应用该算法解答上述问题的每一步计算结果。

6.采用邻接表存储结构,编写一个判别无向图中任意给定的两个顶点之间是否存在一条长度为k的简单路径的算法（注:一条路径为简单路径指的是其顶点序列中不含有重现的顶点）。