1.下列哪一种图的邻接矩阵是对称矩阵?( )
A.有向图 B.无向图 C.AOV网 D.AOE网
2.在边表示活动的AOE网中,关键活动的最迟开始时间( ) 最早开始时间。
A.> B.= 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个顶点的无向图,若采用邻接矩阵存储,则该矩阵的大小是(D)
A.n B.(n-1)2 C.n-1 D.n2
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
二、填空题(每空3分,共9分)。
1.有n个顶点的连通图至少有___条边。有n个顶点的无向图至多有 条边。
2. 图的广度优先遍历算法中用到辅助队列,每个顶点最多进队 次。
3.在一个具有n个顶点的有向完全图中包含有 条边。
三、综合题(共23分)(答案可以在纸上笔画然后拍照贴图到文档的方式)。
1. (共7分)无向网如下:
(1) 给出如图所示网的邻接矩阵表示(3分):
(2) 画出最小生成树(4分):
2 .(共8分)已知一个连通图如图所示,试给出图的邻接矩阵和邻接链表存储示意图。
(1) 邻接矩阵存储示意图为(4分):
(2) 邻接链表存储示意图为(4分):
3. (共8分)如图所示的带权无向图,请用克鲁斯卡尔算法给出最小生成树的求解过程。
用克鲁斯卡尔算法求最小生成树的过程为:
1