全国自考数据结构导论（图）模拟试卷1

45． 假定Anxn是一个无向简单图G的邻接矩阵，其中n是图G的顶点数。对Anxn采用顺序的方法存储其下三角，然后写出对G进行宽度优先搜索的算法。

43． 已知n个顶点的有向图，用邻接矩阵表示，编写函数计算每对顶点的最短路径。

42． 已知图采用邻接表存储方式，试写出删除边(v_i，v_i)(对于无向图)或删除弧i，V_i>(对于有向图)的算法。

44． 对于一个使用邻接表存储的有向图G，可以利用深度优先遍历方法，对该图中结点进行拓扑排序，写出在遍历图的同时进行拓扑排序的算法。

41． 一个函数，根据用户输入的偶对(以输入0表示结束)建立其有向图的邻接表。

37． 对于如图所示的AOE网，写出其关键路径。

34． 已知一个无向图的邻接表如下图所示，请给出从顶点v。开始的深度优先搜索遍历序列和广度优先搜索遍历序列。

35． 已知如图所示的网，请给出从顶点A开始按Prim算法构造的最小生成树，并给出构造顺序。

36． 已知如图所示的网，请给出按Kruskal算法构造的最小生成树，并给出构造顺序。

31． 对下图所示的有向图，请回答以下问题。

(1)请给出其强连通分量。

(2)请给出每个顶点的入度和出度。

33． 对如图所示的有向图，请给出从A开始的深度优先搜索遍历序列和广度优先搜索遍历序列。

30． Prim算法适用于求_______的最小生成树，Kruskal算法适用于求________的最小生成树。

29． 有29条边的无向连通图，至少有________个顶点，至多有________个顶点；有29条边的无向非连通图，至少有_________个顶点。有29条边(弧)的有向连通图，至少有_________个顶点，至多有_________个顶点；有29条边的有向非连通图，至少有_________个顶点。

26． 用图中的顶点表示活动，用弧表示活动问的先后关系，这样的有向图称为________。

27． 事件vk的最早发生时间是从源点到顶点vk的________。

28． 在AOE网中，从源点到汇点之间具有最大路径长度的路径称为__________。

24． 图的遍历方法主要有__________和__________两种。

25． 构造图的最小生成树的方法主要有____和______两种。

22． _________算法是按路径长度递增的次序产生最短路径的算法。

21． 无向图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)}，对该图进行深度优先遍历，得到的顶点序列是_________。

23． 图的基本存储结构主要有_______和______。

19． 一个有n个顶点的无向图，采用邻接矩阵作为存储结构，则求图中边数的方法是__________。求任一顶点的度的方法是________。

20． 一个有10个顶点的有向图，它最多能有________条边。

16． 有向图的极大连通子图称为______。

17． 一个具有n个顶点的完全无向图的边数为_________；一个具有n个顶点的完全有向图的弧数为________。

18． 在有向图中，顶点的度等于_________。

14． 判断一个有向图是否存在回路，除了可以利用拓扑排序方法外，还可以利用_________。

15． 以下有关关键路径的叙述中，不正确的是_________。

12． 对于如图所示的有向图，其拓扑排序序列为__________。

13． 使用_______算法可以确定从源点到图中其余顶点的最短路径。

11． 对于如图所示的有向图，其广度优先搜索遍历序列为_______。

9． 任何一个带权的无向连通图，其最小生成树一定有__________。

10． 如下图所示的有向图，其深度优先搜索遍历序列为______。

7． 十字链表适用于______。

8． 具有n个顶点的连通图，其最小生成树具有________条边。

5． 以下哪个路径不是简单路径________。

6． 在一个含n个顶点的连通图中，任意一条简单路径的长度都不可能超过

4． 以下有关连通分量的说法中，正确的是_________。

3． 以下有关完全图的叙述中，不正确的是_________。

2． 在有向图中，所有顶点的人度之和是所有顶点出度之和的________倍。

1． 在无向图中，所有顶点的度数之和等于边数之和的_______倍。