第六章 图

《数据结构》第六章练习题

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

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

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

A. 1/2 B. 1 C. 2 D. 4 3.一个有n个顶点的无向图最多有 条边。

A. n B. n(n-1) C. n(n-1)/2 D. 2n 4.具有4个顶点的无向完全图有 条边。

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

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

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

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

A. n B. n+1 C. n-1 D. n/2

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

A. n B. (n-1)2 C. n-1 D. n2

8.对于一个具有n个顶点和e条边的无向图，若采用邻接矩阵表示，则表头向量的大小是 1 ；所有邻接矩阵中的结点总数是 2 。 1 A. n B. n+1 C. n-1 D. n+e 2 A. e/2 B. e C. 2e D. n+e 9.对某个无向图的邻接距阵来说， 。

A．第i行上的非零元素个数和第i列的非零元素个数一定相等 B．矩阵中的非零元素等于图中的边数

C．第i行上，第i列上的非零元素总数等于顶点vi的度数 D．矩阵中非零行的行数等于图中的顶点数

10.已知一个图如图所示，若从顶点a出发按深度搜索法进行遍历，则可得到顶点序列为 1 ；按宽度搜索法进行遍历，则可得到顶点序列为 2 。

1 A. abecdf B. acfebd C. aebcfd D. aedfcb 2 A. abcedf B. abcefd C. aebcfd D. acfdeb 11.已知一有向图的邻接表存储结构如图所示 （1）根据有向图的深度优先遍历算法，从v1顶点出发，所得到的顶点序列是 1 。 （2）根据有向图的宽度优先遍历算法，从v1顶点出发，所得到的顶点序列是 2 。

1 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 A. v1,v2,v3,v4,v5 B. v1,v3,v2,v4,v5 C. v1,v2,v3,v5,v4 D. v1,v4,v3,v5,v2

12.采用邻接表存储的图的深度优先遍历算法类似于二叉树的 。

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

13.采用邻接表存储的图的宽度优先遍历算法类似于二叉树的 。

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

14.一个图中包含k个连通分量，若按深度优先搜索方法访问所有结点，则必须调用

A．K B 1 C k-1 D k+1

15.任何一个无向连通图的最小生成树

A 有一棵或多棵 B 只有一棵 C 一定有多棵 D 可能不存在 16.一下说法中不正确的是 A 无向图中的极大连通子图称为连通分量

B 连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点 C 图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点 D 有向图的遍历不可采用广度优先搜索方法

17.判定一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以利用 。

A. 求关键路径方法 B. 求最短路径的Dijkstra方法 C. 宽度优先遍历算法 D. 深度优先遍历算法 18.下面不正确的的说法是 （1）求从指点源点到其余各顶点的Dijkstra最短路径算法中弧上权不能为负的原因是实际应用中无意义；

（2）利用Dijkstra算法每一对不同顶点的最短路径的算法时间为O（n3）（图用邻接矩阵表示）；

（3）利用Floyd算法求没对不同顶点对的算法中允许弧上的权为负，但不能有权和为负的回径。 A （1）、（2）、（3） B （1） C （1）、（3） D （2）、（3） 19.关键路径是事件结点网络中

A 从源头到汇点的最长路径 B 从源头到汇点的最短路径 C 最长的回路 D 最短的回路 20.下面不正确的的说法是

（1）在AOE网中，减小任意关键活动上的权后，整个工期也就相应减少。 （2）AOE网工程工期为关键活动上的权之后。

（3）在关键路径上活动都是关键活动，而关键活动也必须在关键路径上。 A (1) B (2) C (3) D (1)、（2） 21. 下面不正确的的说法是

A 关键活动不按期完成就会影响整个工程的完成时间 B 任何一个关键活动提前完成，将使整个工程提前完成 C 所有关键活动都提前完成，则整个工程提前完成

D 某些关键活动若提前完成，将使整个工程提前完成 二、填空题

1.在n个顶点的无向图中，若边数>n-1，则该图必是连通图。此断言是 的。

2.有向图G有n个顶点{v1,v2,…,vn},它的邻接矩阵为A，A[i][j]=1表示从vi到vj存在邻接关系，而A[i][j]=0则不存在。故G中顶点vi的度为 ,而 为所有通过vk的存在形式的路径个数之和。 3.n个顶点的连通图至少 条边。 4.在无权图G的邻接矩阵中，若 (vi, vj) 或 属于图G的边集，则对

应元素A[i][j] 等于 ，否则等于 。

5.在无权图G的邻接矩阵中，若A[i][j]等于1，则等于A[j][i] = 。 6.一个图的 表示方法是唯一的，而 表示方法是不唯一的。 7.G是一个非连通无向图，共有28条边，则该图至少有 个顶点。 8.具有10个低昂点的无向图，边的总数是最多是6.已知一图的邻接矩阵表示，删除所有从第i个结点出发的边的方法是 。 。

9. 已知图G的邻接表如图所示，其从v1顶点出发的深度优先搜索序列为 ，其从v1顶点出发的宽度优先搜索序列为 。

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

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

10图的深度优先搜索序列和广度优先搜索序列不是唯一的。此断言是 的。

12.如果含n个顶点的图形成一个环，则它有 棵生成数。 13.对n个低昂点的连通图来说，它的生成树一定有 条边。

14.对于如图所示的图，用普里姆算法从顶点1开始求最小生成树，按次序产生的边为 ，共 条边；用克鲁斯卡尔算法产生的边次序是 。

15.设图G有n个顶点和e条边，采用邻接矩阵存储，则拓扑排序算法的事件复杂度为 。

16.求最小生成树的克鲁斯卡尔算法的时间复杂度 ，它的 图较为合适。

17.若一个有向图的邻接矩阵中对角线以下元素均为零，则该图的拓扑有序列必定存在。此断言是 的。 18.设有向图G如图所示。（1）写出所有的拓扑序列 ；（2）添加边

后，则仅可能有唯一的拓扑序列。

三．简答题

1.给出的图所示的无向图G的邻接矩阵和邻接表两种 存储结构。并在给定的邻接表基础上，之处指出从顶点1出发的深度优先遍历和广度优先遍历序列。

2.使用普里姆算法构造如图所示的图G的一棵最小生成树。

3.使用克鲁斯卡尔算法构造出如图所示的图G的一棵最小生成树。

4.给出一个以下带权图的邻接矩阵表示： 试完成下列要求;

(1) 写出在该图上从顶点1出发进行深度优先遍历的顶点序列，并据此判断该图是否为连通图。

(2) 画出该图的带权邻接表。

(3) 画出按普里姆算法构造最小生成树（森林）的示意图。

本文来源：https://www.bwwdw.com/article/x5hd.html