数据结构作业.docx

AOE 网中的关键路径为 a2a5a9a13a14a15(输出序列中不要有空格、标点符号等,输出样例: a1a2a15a10 )。 A到 G的最短路径为 ABEG(输出序列中不要有空格、标点符号等,保持大写,输出样例: ABCDEFG ) 28 条边,则该无向图至少有 9个顶点。 G的邻接表表示中,每个顶点邻接表中所含的结点数,对于无向图来说等于该顶点的度;对于有向图来说等于该顶点的出度。 G=(V,E) ,其中 V={v1,v2,v3,v4,v5,v6} , E={<v1,v2>, <v1,v4>, <v2,v6>, <v3,v1>, <v3,v4>, <v4,v5>, <v5,v2>, <v5,v6>} ,G的拓扑序列是 v3v1v4v5v2v6。(输出序列中不要有空格、标点符号等,保持小写,输出样例: v1v2v3v4v5v6 ) 选择题#题目 n个结点的图,最少有( A)个连通分量,最多有( E)个连通分量。 -1 :n+1 AOV 网进行拓扑排序时,所有入度为 0的顶点被链接成一个 D结构。 AOE 网的叙述中, 不正确的是 D。 ,则整个工程一定能够提前完成 ,整个工程仍有可能按时完成 ,都会导致整个工程的延期完成 ,都会导致整个工程的提前完成 n个顶点的无向连通图采用邻接矩阵表示,则邻接矩阵中至少有 A个非零元素。 (n-1) +1 -1 n个顶点的无向图采用邻接矩阵存储方法,该邻接矩阵一定为一个 B。 7个顶点的有向图至少应有 BJU条边才能确保一个强连通图。 G的拓扑序列中,若顶点 v i在顶点 v j之前,则下列情形不可能出现的是 D。 <v i,v j> 中有一条从 v i到v j的路径 <v i,v j> 中有一条从 v j到v i的路径 n个顶点 e条边的无向连通图,利用 Kruskal 算法生成最小生成树,其时间复杂度为 A A. O(elog 2 e) B. O(e × n) C. O(elog 2 n) (nlog 2 n) n条边的无向图而言,其邻接表中边数为 B。 B. 2n C. n/2 ×n n,则该图最多有( C)条边。 -1 (n+1)/2 (n-1)/2 1. 对下图所示的 AOE 网络, 1)计算各事件的最早开始时间和最晚开始时间(如书上用一横行表示即可) 2)求出所有的关键路径 3)该工程完成的最短时间是多少? (1) 最早开始时间: v[1]-v[7]:0 3 2 6 7 5 10 最晚开始时间: v[1]-v[7]:0