全国自考数据结构导论（图）模拟试卷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)请给出每个顶点的入度和出度。