发布时间 : 星期四 文章数据结构习题更新完毕开始阅读144210a7195f312b3169a5d5
4．一棵有n个顶点的生成树有且仅有 条边。 5．图的遍历中，设置辅助数组是为了 。
6．G是一个非连通图，共有28条边，则该图至少有 个顶点。
7. 设图G=(V,E)，V={1,2,3,4}, E={<1,2>,<1,3>,<2,4>,<3,4>}，从顶点1出发，对图G进行广度优先搜索的序列有________种。
8．在用于表示有向图的邻接矩阵中，对第i行的元素进行累加，可得到第i个顶点的 度，而对第j列的元素进行累加，可得到第j个顶点的 度。
9．一个连通图的生成树是该图的 连通子图。若这个连通图有n个顶点，则它的生成树有 条边。
三、判断题
1.存储图的邻接矩阵中，邻接矩阵的大小仅与顶点个数有关，而与图的边数无关。
2.存储图的邻接矩阵中，邻接矩阵的大小不但与图的顶点个数有关，而且与图的边数也有关。 3.在n个结点的无向图中，如边数大于n-1，则该图必存在回路。 4.用邻接矩阵法存储一个图所需的存储单元数目与图的边数有关。 5. 对于AOE网络，加速任一关键活动都能使整个工程提前完成。 6.带权的无向连通图的最小生成树是唯一的。 7．一个具有 n 个顶点的完全图的边数为（ ）。 8．无向图中的连通分量定义为无向图的（ ）。
9．设无向图 G 的顶点数为 n ，则 G 最少有（ ）条边。 10．一个具有 n 个顶点的有向完全图的弧数为（ ）。 11．有向图中的强连通分量定义为有向图的（ ）。
四、应用题
1.从供选择的答案中选择与下面有关图的叙述中各括号相匹配的词句，将其编号填入相应的括号内。 (1)对于一个具有n个结点和e条边的无向图，若采用邻接表表示，则顶点表的大小为（ A ），所有边链表中边结点的总数为（ B ）。
(2)采用邻接表存储的图的深度优先遍历算法类似于树的（ C ）。 (3)采用邻接表存储的图的广度优先遍历算法类似于树的（ D ）。
(4)判断有向图是否存在回路，除了可以利用拓扑排序方法外，还可以利用（ E ）。 供选择的答案
41
A：① n ② n+1 ③ n-1 ④ n+e B：① e/2 ② e ③ 2e ④ n+e
C~D：① 中根遍历 ② 先根遍历 ③ 后根遍历 ④ 按层次遍历 E：① 求关键路径的方法
② 求最短路径的Dijkstra方法 ③ 深度优先遍历算法 ④广度优先遍历算法
2． 假设一棵完全图包含 A 、 B ，…， G 七个结点，写出其邻接矩阵。 3． 假设一棵完全图包含 A ， B ， C ， D 四个结点，画出其邻接表。 4．证明下列命题：
（1）在任意一个有向图中，所有顶点的入度之和与出度之和相等。 （2）任一无向图中各顶点的度的和一定为偶数。 5．证明：有向树中仅有n-1条弧。
6．在图G分别采用邻接矩阵和邻接表存储时，分析深度遍历算法的时间复杂度。 7．对下列图，分别执行dfs(1)和dfs(5)，写出遍历序列，并构造出相应的dfs生成树。
8.下图为一无向带权图，（1）写出其邻接矩阵和邻接表；（2）按克鲁斯卡尔算法求其最小生成树。
9.如图所示的AOE网络中，计算各顶点的ve(i)和vl(i)函数值及各活动的e(i)和l(i)函数值，并求出关
42
键活动和关键路径。其中：a1=6,a2=4,a3=4,a4=6,a5=8,a6=6,a7=4,a8=2
10．对下图G所示的邻接表，不用还原出原图，请执行dfs(1)，写出遍历序列，并构造出相应的dfs生成树。
11. 已知一个带权图的顶点集V和边集G分别为： V={0,1,2,3,4,5,6};E={(0,1)19,(0,2)10,(0,3)14, (1,2)6,(2,3)26,(2,4)15,(3,4)18,(4,5)6,(4,6)6};试画出该图的示意图，并给出邻接表和邻接矩阵。 12.至少给出下面的有向图的四个拓扑排序，并判断是否存在回路。
V1
V3 V4 V2
V5 V6 V7 V8
13．分别用prim算法和Kruskal算法求解下图的最小生成树，并标注出中间求解过程的各状态。
14．对下列AOV网，完成如下操作：
（1）按拓扑排序方法进行拓扑排序，写出中间各步的入度数组和栈的状态值，并写出拓扑序列。
43
（2）写出左图所示AOV网的所有的拓扑序列。
27．对下面的图，求出从顶点1到其余各顶点的最短路径。
26．分析在图分别采用邻接矩阵和邻接表存储时的拓扑排序算法的时间复杂度。
28．分析在图分别采用邻接矩阵和邻接表存储时，求最短路径的Dijkstra算法的时间复杂度。 29．采用Floyd算法求解下图中各顶点之间的最短路径。
五、算法设计题
1.请补充图的广度优先非递归遍历图G的算法。
void BFSTraverse(Graph G,Status (*visit)(int v)) {
for (v=0;v InitQueue(Q); for (v=0;v { visited[v]=TRUE; Visit(v); ; while (!Q.ueueEmpty(Q)) 44