练习题

一、填空题

1.n 个顶点的连通图至少____________条边。

2.在无权图G的邻接矩阵A中，若（vi，vj）或＜vi，vj＞属于图G的边集合，则对应元素A［i］［j］等于____________，否则等于____________。

3.在无向图G的邻接矩阵A中，若A［i］［j］等于1，则A［j］［i］等于____________。

4.已知图G的邻接表如题图7－1所示，其从顶点v1出发的深度有限搜索序列为____________，其从顶点v1出发的宽度优先搜索序列为____________。

题图7－1

5.已知一个有向图的邻接矩阵表示，计算第i 个结点的入度的方法是____________。

6.已知一个图的邻接矩阵表示，删除所有从第i 个结点出发的边的方法是________。

7.一个图的____________表示法是唯一的，而____________表示法是不唯一的。

8.图的两种最基本的存储方式是_____________________和____________。

9.n 个结点的完全有向图含有边的数目____________。

10.哪一种图的邻接矩阵是对称矩阵？_____________。

二、选择题

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

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

2.任何一个无向连通图的最小生成树（ ）。

A.只有一棵　B.有一棵或多棵　C.一定有多棵　D.可能不存在

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

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

4.一个有n个顶点的无向图最多有（ ）条边。

A.n　B.n（n－1）　C.n（n－1）／2　D.2n

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

A.6　B.12　C.16　D.20

6.具有6个顶点的无向图至少应有（ ）条边才能确保是一个连通图。

A.5　B.6　C.7　D.8

7.在一个具有n个顶点的无向图中，要连通全部顶点至少需要（ ）条边。

A.n　B.n＋1　C.n－1　D.n／2

8.对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是（ ）。

A.n　B.（n－1）2　 C.n－1　D.n2

9.已知一个图如题图7－2所示，若从顶点a出发按深度搜索法进行遍历，则可能得到的一种顶点序列为___________①；按宽度搜索法进行遍历，则可能得到的一种顶点序列为___________②。

①A.a，b，e，c，d，f B.e，c，f，e，b，d C.a，e，b，c，f，d D.a，e，d，f，c，b

②A.a，b，c，e，d，f B.a，b，c，e，f，d C.a，e，b，c，f，d D.a，c，f，d，e，b

题图7－2

10.已知一有向图的邻接表存储结构如题图7－3所示。

题图7－3

（1）根据有向图的深度优先遍历算法，从顶点v1出发，所得到的顶点序列是（ ）。

A.v1，v2，v3，v5，v4　B.v1，v2，v3，v4，v5

C.v1，v3，v4，v5，v2　D.v1，v4，v3，v5，v2

（2）根据有向图的宽度优先遍历算法，从顶点v1出发，所得到的顶点序列是（ ）。

A.v1，v2，v3，v4，v5　B.v1，v3，v2，v4，v5

C.v1，v2，v3，v5，v4　D.v1，v4，v3，v5，v2

11.关键路径是事件结点网络中（ ）。

A.从源点到汇点的最长路径　B.从源点到汇点的最短路径

C.最长的回路　D.最短的回路

12.在题图7－4所示的拓扑排列的结果序列为（ ）。

A.125634　B.516234　C.123456　D.521634

题图7－4

13.若用邻接矩阵表示一个有向图，则其中每一列包含的“1”的个数为（ ）。

A.图中每个顶点的入度　B.图中每个顶点的出度

C.图中弧的条数　D.图中连通分量的数目

14.在一个带权连通图G中，权值最小的边一定包含在G的（ ）。

A.最小生成树中　B.深度优先生成树中

C.广度优先生成树中　D.深度优先生成森林中

15.为便于判别有向图中是否存在回路，可借助于（ ）。

A.最小生成树算法　B.最短路径算法

C.拓扑排序算法　D.深度遍历算法

三、应用题

1.已知如题图7－5所示的有向图，请给出该图：

题图7－5

（1）每个顶点的入度、出度；

（2）邻接矩阵；

（3）邻接表；

（4）逆邻接表；

（5）十字链表；

（6）强连通分量。

2.已知如题图7－6所示的无向图，请给出该图：

（1）邻接多重表（要求每个边结点中第一个顶点号小于第二个顶点号，且每个顶点的各邻接边的链接顺序，为它所邻接到的顶点序号由小到大的顺序）；

题图7－6

（2）深度优先遍历该图所得顶点序列和边的序列；

（3）广度优先遍历该图所得顶点序列和边的序列。

3.已知如题图7－7所示的AOE网，试求：

（1）每个事件的最早发生时间和最晚发生时间；

（2）每个活动的最早开始时间和最晚开始时间；

（3）给出关键路径。

题图7－7

4.已知如题图7－8所示的有向网，试利用Dijkstra算法求顶点1到其余顶点的最短路径，并给出算法执行过程中各步的状态。

题图7－8

5.编写算法，由依次输入的顶点数目、弧的数目、各顶点的信息和各条弧的信息建立有向图的邻接表。

6.试在邻接矩阵存储结构上实现图的基本操作：InsertVertex（G，v），InsertArc（G，v，w），DeleteVertex（G，v）和DeleteArc（G，v，w）。