数据结构第7章 图习题(2)

v1 v2 v3 v4 ∧ v5 v6 ∧ 2 3 6 ∧ 3 5 ∧ 4 ∧ 4 6 3 ∧ 图7-3 图G的邻接表

11．n个顶点连通图的生成树一定有__________条边。 12．一个连通图的___________是一个极小连通子图。

13．Prim算法适用于求_________的网的最小生成树，Kruskal算法适用于求

________的网的最小生成树。

14．在AOV图中，顶点表示________,有向边表示________。 15．可以进行拓扑排序的有向图一定是_________。

16．从源点到汇点长度最长的路径称为关键路径，该路径上的活动称为________。 17．Dijkstra算法从源点到其它各顶点的路径长度按________次序依次产生，该

算法在边上的权出现_________情况时，不能正确产生最短路径。 18．求从某源点到其余各项点的Dijkstra算法在图的顶点数为10，用邻接矩阵表

示图时计算时间约为10ms，则在图的顶点数为40时，计算时间约为_________ms。

三、判断题

1．具有n个顶点的无向图至多有n（n-1）条边。 2．有向图中各顶点的入度之和等于各顶点的出度之和。 3．邻接矩阵只储存了边的信息，没有存储顶点的信息。

4．对同一个有向图，只保存出边的邻接表中结点的数目总是和只保存入边的邻接表中结点的数目一样多。

5．如果表示图的邻接矩阵是对称矩阵，则该图一定是无向图。

6．如果表示有向图的邻接矩阵是对称矩阵，则该有向图一定是有向完全图。

7．如果表示某个图的邻接矩阵不是对称矩阵，则该图一定是有向图。 8．连通分量是无向图的极小连通子图。 9．强连通分量是有向图的极大连通子图。

10．对有向图G，如果以任一顶点出发进行一次深度优先或广度优先搜索能访问

到每一个顶点，则该图一定是完全图。

11．连通图的广度优先搜索中一般要采用队列来暂时刚访问过的顶点。 12．图的深度优先搜索中一般要采用栈来暂时刚访问过的顶点。 13．有向图的遍历不可采用广度优先搜索方法。 14．连通图的生成树包含了图中所有顶点。

15．设G为具有n个顶点的连通图，如果其中的某个子图有n个顶点，n-1条边，则该子图一定是G的生成树。 16．最小生成树是指边数最小的生成树。

17．从n个顶点的连通图中选取n-1条权值最小的边，即可构成最小生成树。 18．只要无向网中没有权值相同的边，其最小生成树就是惟一的。 19．只要无向网中有权值相同的边，其最小生成树就可能不是惟一的。 20．有环图也能进行拓扑排序。

21．拓扑排序算法仅适用于有向无环图。

22．任何有向无环图的结点都可以排成拓扑排序，而且拓扑序列不惟一。 23．关键路径是由权值最大的边构成的。

24．在AOE网中，减小任一关键活动上的权值后，整个工期也就相应减小。 25．在AOE网中工程工期为关键活动上权值之和。

26．在关键路径的活动都是关键活动，而关键活动未必在关键路径上。 27．关键活动不按期完成就会影响整个工程的完成时间。 28．所有关键活动都提前完成，则整个工程将提前完成。 29．某些关键活动若提前完成，将可能使整个工程提前完成。 30．求单源最短路径的狄克斯特拉算法不适用于有回路的有向网。

四、简答题

1．图G是一个非连通无向图，共有28条边，则该图至少有多少个顶点？ 2．用邻接矩阵表示图时，矩阵元素的个数与顶点个数是否相关？与边的条数是

否有关？

3．对于稠密图和稀疏图，就存储而言，采用邻接矩阵和邻接表哪个更好些？ 4．请回答下列关于图的一些问题：

（1）有n个顶点的有向强连通图最多有多少条边？最少有多少条边？ （2）表示一个有1000个顶点，1000条边的有向图的邻接矩阵有多少个矩阵

元素？是否为稀疏矩阵？

（3）对于一个有向图，不用拓扑排序，如何判断图是否存在环？

5．对n个顶点的无向图和有向图，采用邻接表表示时，如何判别下列有关问题？ （1）图中有多少条边？

（2）任意两个顶点i和j是否有边相连？ （3）任意一个顶点的度是多少？

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

4 1 3 5 2 图7-4 一个无向图

7．对于图7-5所示的有向图，试给出：

（1）邻接矩阵。 （2）邻接表 （3）强连通分量 （4）对照邻接表，给出从顶点1出发的深度优先遍历序列。 （5）对照邻接表，给出从顶点3出发的深度优先遍历序列。

1 5 4 6 2 3 图7-5 一个有向图

8．什么样的图其最小生成树是惟一的？

9．已知带权连通图G(V,E)邻接表如图7-6所示，请画出该图，并分别以深度优

先和广度优先遍历该图，写出遍历中结点的序列，并画出该图的一棵最小生成树，其中表结点的3个域各为： 1. 2. 3 4. 5

v1 v2 v3 v4 v5 顶点号 边上所带的权 3 16 3 2 2 2 3 4 4 10 ∧ 指针 4 18 ∧ 5 22 ∧ 4 4 ∧ 5 10 ∧ 2 12 1 12 1 16 1 18 2 22 图7-6 连通图的邻接表

10．已知世界6大城市为：北京（B）纽约（N）巴黎（P）伦敦（L）东京（T）

墨西哥城（M）试用由表1给出的交通网确定最小生成树，并说明所使用的方法及其时间复杂度。

B N B 1 09 N 109 P 82 58 L 81 55 T 21 108 M 124 32 P L T M 82 81 21 124 58 55 108 32 3 97 92 3 95 89 97 95 113 92 89 113 11．对于图7-7所示的带权有向图，采用狄克斯特拉算法求从顶点1到其它顶点

的最短路径，要求给出求解过程。

1 2 8 9 5 3 2 1 3 2 2 1 15 7 4 4 0 13 13 5 4 3 4 6 2 12 12 3

图7-7 一个有向图 图7-8一个有向图

12．设图7-8中的顶点表示村庄，有向边代表交通路线，若要建立一家医院，试

问建在哪个村庄能使个村庄总体交通代价最小。

13．表2所示给出了某工程各工序之间的优先关系和各工序所需的时间。

表2 某工程各工序关系表

工序代号 A B C D E F G H I J K L M N 所需时间 15 10 50 8 15 40 300 15 120 60 15 30 20 40 先驱工作 - - A,B B C,D B E G,I E I F,I H,J,K L G 完成如下各小题：

（1）画出相应的AOE网

（2）列出事件的最早发生时间，最迟发生时间。 （3）找出关键路径并指明完成该工程所需的最短时间。 14．如图7-9所示的AOE网，求：

（1）每项活动ai最早开始时间e(ai)和最迟开始时间l(ai)。 （2）完成此工程最少需要多少天（设边上权值为天数）。 （3）哪些是关键活动

（4）是否存在某项活动，当其提高速度后能使整个工程缩短工期？

a3=3 2 a1=5 1 a2=6 3 a5=3 5 a4=6 a6=3 7 a10=5 9 8 a11=2 10

4 a7=4 6 a12=4 a8=1 a9=4 a13=2 图7-9 五、算法设计题

1．假设图G采用邻接表存储，分别设计实现以下要求的算法： （1）求出图G中每个顶点的入度。 （2）求出图G中每个顶点的出度

（3）求出图G中出度最大的一个顶点，输出该顶点的编号。 （4）计算图G中出度为0的顶点数。

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数据结构第7章 图习题(2)在线全文阅读。