第六部分 图练习题带答案

第六部分 图一、选择题1n 个顶点的带权无向连通图的最小生成树包含(B)个顶点。A.n-1 B.n C.n/2 D.n+12无向完全图的邻接矩阵是(A)矩阵。A. 对称 B. 上三角 C. 下三角 D. 稀疏3. 若采用邻接矩阵法存储一个n个顶点的无向图，则该邻接矩阵是一个(D)。A. 上三角矩阵 B. 稀疏矩阵 C. 对角矩阵D. 对称矩阵4. 具有 n 个顶点的有向完全图有(B)条弧。A. n B. n*(n-1) C. n*(n+1) D. n*n5. n 个顶点的连通图至少有(A)条边。A. n-1 B. nC. n+1 D. 06在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的(B)倍。A1/2B1C2D47在含n个顶点和e条边的无向图的邻接矩阵中,零元素的个数为(D)Ae B2e Cn2e Dn22e8假设一个有n个顶点和e条弧的有向图用邻接表表示,则删除与某个顶点vi相关的所有弧的时间复杂度是(C)AO(n)BO(e) CO(n+e) DO(n*e)9对于一个无向图，下面(A)的说法是正确的。A. 每个顶点的入度等于出度B. 每个顶点的度等于其入度与出度之和C. 每个顶点的入度为0D. 每个顶点的出度为0二、填空题1具有10个顶点的无向图,边的总数最多为 _45_ 。2在有n个顶点的有向图中，每个顶点的度最大可达 2(n-1) 。3有向图g用邻接矩阵a1m,1m来存储，其第i行的所有元素之和等于顶点i的出度之和。4关键路径是 指途中从原点到汇点的路径长度最长的路径 。5请给出对于下面AOV网络，使用上述算法进行拓扑排序的结果，以及在count数组中建立的链式栈的变化。（top是栈顶指针）top A B C D E F初始 6有n个球队参加的足球联赛按主客场制进行比赛，共需进行 n(n-1) 场比赛。7带权连通图G=，其中V=v1,v2,v3,v4,v5,E=(v1,v2)7,(v1,v4)6，(v1,v4)9，(v2,v3)8，(v2,v4)4，(v2,v5)4，(v3,v4)6，(v4,v5)2，(注：顶点偶对右下角的数据为边上的权值)，G的最小生成树的权值之和为_ 。8若AOE图中有 环路 ，则对该图求关键路径不成功。9n(n0) 个结点、 (n-1) 条边的连通无向图中，顶点度数最大值为 _2_ 。三、判断题1有向图是一种非线性结构。( R )2带权连通图的最小生成树的权值之和一定小于它的其它生成树的权值之和。( R )3AOE 网是一种带权的无环连通图。( R )四、操作题1图的邻接矩阵:2有向图的逆邻接表: 3找出下面网络的最小生成树（WPL=23）。 4找出下面网络的最小生成树(WPL=33):5试画出下列图的邻接表。 图6对下面的带权无向图采用prim算法从顶点 开始构造最小生成树。（写出加入生成树顶点集合S和选择边Edge的顺序）S:顶点号Edge:(顶点，顶点，权值)(，9)(，5)( ，7)(，6)( ，7)7对图所示有向图，试用Dijkstra算法求出从源点1到其它各顶点的最短路径，并写出执行算法过程中扩充结点的每次循环状态。D2D3D4D5D6V12015V1，V319#25V1，V3,V2#2925V1，V3,V2,V6#2929#V1，V3,V2,V6,V4#29#V1，V3,V2,V6,V4,V5#8. 已某个不带权的无向图采用邻接矩阵存储方法依次将顶点的数据信息存放于一维数组ABCDEFGH中，边的信息存放于邻接矩阵中，邻接矩阵为请写出从顶点A出发对该图进行深度有限搜索后得到的顶点序列。ACDFBEGH0 1 1 0 0 0 0 01 0 0 0 1 0 1 11 0 0 1 0 1 0 00 0 1 0 0 1 0 00 1 0 0 0 0 0 10 0 1 1 0 0 0 00 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0