数据结构：图的练习

一、选择题

1、在一个无向图中，所有顶点的度数之和等于所有边数的（ ）倍。 A．1/2 B 1 C 2 D 4

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

A．1/2 B 1 C 2 D 4

3、已知一个图，如图所示，若从顶点a出发按深度搜索法进行遍历，则可能得到的一种顶点序列为（ ）；按广度搜索法进行遍历，则可能得到的一种顶点序列为（ ）；

① A）a，b，e，c，d，f B）a，c，f，e，b，d

C）a，e，b，c，f，d， D）a，e，d，f，c，b

② A）a，b，c，e，d，f B）a，b，c，e，f，d

C）a，e，b，c，f，d， D）a，c，f，d，e，b

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

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

5、采用邻接表存储的图的广度优先遍历算法类似于二叉树的（ ）。

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

6、具有n 个结点的连通图至少有（ ）条边。

A． n－1 B． n C． n（n－1）/2 D． 2n 7、已知图G的邻接表如图所示，

其从顶点v1出发的深度优先搜索序列为( )， 其从顶点v1出发的广度优先搜索序列为( )。

二、综合题

1、已知有向图的邻接表如图所示，请回答下面问题：

(1)给出该图的邻接矩阵；

(2)从结点A出发，写出该图的深度优先遍历序列。

2、已知带权图的邻接表如下所示，其中边表结点的结构为：

要求：

（1）写出由此得到的深度优先遍历序列； （2）写出由此得到的广度优先遍历序列；

3、已知一个图的顶点集V和边集E分别为： V={1,2,3,4,5,6,7};

E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,(3,5)12,(3,6)9,(4,6)4,

(4,7)20,(5,6)18,(6,7)25};

要求：按照普里姆算法从顶点1出发得到最小生成树，试写出在最小生成树中依次得到的各条边。

4、已知一个图的顶点集V ={1,2,3,4,5,6,7}，其共有10条边。 该图用如下边集数组存储： 起1 2 2 5 5 2 2 6 1 3 点 终6 4 5 4 7 6 7 7 7 5 点

权 1 1 2 2 2 3 3 4 5 7 要求：试用克鲁斯卡尔算法依次求出该图的最小生成树中所得到的各条边及权值。

5、如下图所示的AOE网络

(1) 这个工程最早可能在什么时间结束。

(2) 求每个事件的最早开始时间Ve[i]和最迟开始时间Vl[i]。 (3) 确定哪些活动是关键活动。画出由所有关键活动构成的图，指出哪些活动加速可使整个工程提前完成。

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