数据结构第五章图习题

第第页数据结构第五章图习题

05图

【单选题】

1.设无向图G中有五个顶点，各顶点的度分别为2、4、3、1、2，则G中边数为（C）。Ａ、4条Ｂ、5条Ｃ、6条Ｄ、无法确定

2.含n个顶点的无向完全图有（D）条边；含n个顶点的有向图最多有（C）条弧；含n个顶点的有向强连通图最多有（C）条弧；含n个顶点的有向强连通图最少有（Ｆ）条弧；设无向图中有n个顶点，则要接通全部顶点至少需（G）条边。

A、n2B、n(n+1)C、n(n-1)D、n(n-1)/2E、n+1F、nG、n-1

3.对下图从顶点a出发进行深度优先遍历，则（A）是可能得到的遍历序列。A、acfgdebB、abcdefgC、acdgbefD、abefgcd

对下图从顶点a出发进行广度优先遍历，则（D）是不可能得到的遍历序列。A、abcdefgB、acdbfgeC、abdcegfD、adcbgef

?010???4.设图G的邻接矩阵A=101，则G中共有（C）个顶点；若G为有向图，则G中共有（D）????010??条弧；若G为无向图，则G中共有（B）条边。

A、1B、2C、3D、4E、5F、9G、以上答案都不对

5.含n个顶点的图，最少有（B）个连通分量，最多有（D）个连通分量。A、0B、1C、n-1D、n

6.用邻接表存储图所用的空间大小（A）。

A、与图的顶点数和边数都有关B、只与图的边数有关C、只与图的顶点数有关D、与边数的平方有关

7.n个顶点的无向图的邻接表最多有（B）个表结点。A、n2B、n(n-1)C、n(n+1)D、n(n-1)/2

8.无向图G=(V,E)，其中：V={a,b,c,d,e,f}，E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}，对该图进行深度优先遍历，得到的顶点序列正确的是（D）。

A、a,b,e,c,d,fB、a,c,f,e,b,dC、a,e,b,c,f,dD、a,e,d,f,c,b

9.图的BFS生成树的树高比DFS生成树的树高（A）。A、小或相等B、小C、大或相等D、大

10.下列不正确的是（C）。

(1)求从指定源点到其余各顶点的迪杰斯特拉（Dijkstra）最短路径算法中弧上权不能为负的原因是在实际应用中无意义；

(2)利用Dijkstra求每一对不同顶点之间的最短路径的算法时间是O(n3)；（图用邻接矩阵表示）(3)Floyd求每对不同顶点对的算法中允许弧上的权为负，但不能有权和为负的回路。A、(1),(2),(3)B、(1)C、(1),(3)D、(2),(3)

11.当各边上的权值（A）时，BFS算法可用来解决单源最短路径问题。A、均相等B、均互不相等C、不一定相等

12.若一个有向图具有拓扑排序序列，那么它的邻接矩阵必定为（C）。A、对称矩阵B、稀疏矩阵C、三角矩阵D、一般矩阵

13.在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是（D）。A、G中有弧B、G中有一条从Vi到Vj的路径C、G中没有弧D、G中有一条从Vj到Vi的路径

14.关键路径是AOE网中（B）。

A、从始点到终点的最短路径B、从始点到终点的最长路径

C、人始点到终点的边数最多的路径D、从始点到终点的边数最少的路径

15.下面关于求关键路径的说法不正确的是（C）。A、求关键路径是以拓扑排序为基础的

B、一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同

C、一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差D、关键活动一定位于关键路径上

【填空题】

1.设无向连通图G含n个顶点e条边，则G的生成树含个顶点条边。2.连通分量是无向图的子图，生成树是无向连通图的子图。3.对稀疏图而言，在邻接矩阵和邻接表这两种存储结构中选择更为适宜。4.设无向图G含n个顶点e条边，则G的邻接表表示中含个边表结点。5.设有向图G含n个顶点e条弧，则G的邻接表表示中含个边表结点。

【计算题】

1.设无向图如下，写出对该图从顶点a出发进行广度优先遍历可能得到的所有遍历序列。

解：abcdefg、abdcegf、acbdfeg、acdbfge、adbcgef、adcbgfe。

2.设有向图如下，写出对该图从顶点a出发进行深度优先遍历可能得到的所有遍历序列。

解：abedc、acbed、acdbe。

3.设无向网如下，(1)写出其邻接矩阵；(2)基于该邻接矩阵求深度优先生成树和广度优先生成树；(3)基于该邻接矩阵按普里姆算法求最小生成树；(4)写出其邻接表；(5)基于该邻接表按克鲁斯卡尔算法求最小生成树。

解：???4??3(1)??????????????4?559???35?5???5?55?7654?9?7?3?????63?2????5?2?6?????5??4??????6?????(2)深度优先生成树：；广度优先生成树：

(3)最小生成树：；求解过程：

(4)邻接表：

(5)最小生成树：

4.设AOV图如下，写出对该图进行拓扑排序可能得到的所有拓扑序列。

解：abcdefg、abcdfeg、abcfdeg

5.设AOE网如下，试求关键路径。

解：关键路径１：v1→v2→v5→v7关键路径２：v1→v3→v6→v7。

6.设有向网如下，试