数据结构第七章图的作作业

古城微笑少年丶 2021-11-11 11:56 513阅读 0赞

*  **图的作业（共****50****分）**
 *  **答案链接[链接][Link 1]**

**一、选择题（每空****2****分，共****18****分）。**

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个顶点的无向图，若采用邻接矩阵存储，则该矩阵的大小是（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分）无向网如下：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTM2MDUxNw_size_16_color_FFFFFF_t_70][]

(1) 给出如图所示网的邻接矩阵表示（3分）：

(2) 画出最小生成树（4分）：

2 .（共8分）已知一个连通图如图所示，试给出图的邻接矩阵和邻接链表存储示意图。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTM2MDUxNw_size_16_color_FFFFFF_t_70 1][]

(1) 邻接矩阵存储示意图为（4分）:

1.  邻接链表存储示意图为（4分）:

3. （共8分）如图所示的带权无向图，请用克鲁斯卡尔算法给出最小生成树的求解过程。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTM2MDUxNw_size_16_color_FFFFFF_t_70 2][]

用克鲁斯卡尔算法求最小生成树的过程为：

**答案链接[链接][Link 1]**

[Link 1]: https://download.csdn.net/download/weixin_41360517/11798259
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTM2MDUxNw_size_16_color_FFFFFF_t_70]: /images/20211109/2e8e56c84e6d4a1196665a7a4cd86eaa.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTM2MDUxNw_size_16_color_FFFFFF_t_70 1]: /images/20211109/a8226ae2df2743b59295f757b6e40753.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTM2MDUxNw_size_16_color_FFFFFF_t_70 2]: /images/20211109/879c3d256fa646c4a157f33bbd04d90f.png