第七章 图作业及答案（满分50分）.docx
5星
- 浏览量: 0
- 大小:None
- 文件类型：None
简介：
这份文档包含了第七章图的相关练习题及其详细解答，满分为50分，适用于检验学生对图论基本概念和算法的理解与掌握情况。
1. 下列哪一种图的邻接矩阵是对称矩阵？（ ） A．有向图 B．无向图 C．AOV网 D．AOE网
2. 在边表示活动的AOE网络中，关键活动的最迟开始时间（ ）最早开始时间。
A. >
B. <
C. >=
D. =
3. 带权有向图G用邻接矩阵A存储，则顶点i的入度等于A中的：
A．第i行非∞的元素之和
B．第i列非∞的元素之和
C．第i行非∞且非0的元素个数
D. 第i列非∞且非0的元素个数
4. 在一个无向图中，所有顶点度数之和等于边数的（ ）倍。
A．1/2
B. 1
C. 2
D. 4
5. 对于具有n个顶点的无向图，若采用邻接矩阵存储，则该矩阵大小为：
A．n
B．(n-1)²
C．n-1
D．n²
6. 下列有关拓扑序列叙述中错误的是（ ）。
A. 拓扑序列包含有向图全部顶点
B. 带环的有向图一定不存在拓扑序列
C. 无环的有向图不一定存在唯一拓扑序
D. 每个无环有向图至少有一个拓扑排序
7．对于描述工程任务的AOE网络，下列说法正确的是（）。
A. 网络中唯一的出度为零顶点称为源点
B. 网络中唯一入度为零顶点称为汇点
C. 关键路径是源到汇最短路径
D．关键路径可能多条
8．最小生成树指的是（ ）。
A. 连通网边数最少的生成树
B. 连通图顶点较少的生成树
C. 权值之和最小的连通子图
D．极小连通子图
9．一个有向图n条弧，则所有顶点度总和为（ ）。
A．2n
B． n
C. n-1
D. n/2
二、填空题
1. 连通的无向图至少包含__ _ 条边。具有n个节点的无向图最多有_______条边。
2. 广度优先遍历算法中，辅助队列每个顶点至多进入_ 次。
3．含有n个节点的完全有向图共有________条弧
三、综合题
1. 请给出下述网络：
(1) 邻接矩阵表示（3分）
(2) 最小生成树绘制（4分）
2. 给出下列连通图形，提供邻接矩阵和链表存储示意。
(1) 存储结构为______形式的图
(2) 存储结构为_______形式的图
3．请用克鲁斯卡尔算法求解下述带权无向网络最小生成树：
过程：（8分）
全部评论 (0)
