《第7章 作业7-2【基础资料】》由会员分享，可在线阅读，更多相关《第7章 作业7-2【基础资料】（28页珍藏版）》请在金锄头文库上搜索。
1、数据结构（C语言版）第7章 图 作业7-2,计算机与信息工程学院 于江德,1,苍松优选,1. 有n个结点的无向图的边数最多为（ ） An+1 Bn(n-1)/2 Cn(n+1) D2n(n+1),2,苍松优选,2. 无向图中一个顶点的度是指图中（ ） A通过该顶点的简单路径数 B通过该顶点的回路数 C与该顶点相关联的边的数目 D与该顶点连通的顶点数,3,苍松优选,2. 无向图中一个顶点的度是指图中（ ） A通过该顶点的简单路径数 B通过该顶点的回路数 C与该顶点相邻接的顶点数 D与该顶点连通的顶点数,4,苍松优选,3. 在一个图中，所有顶点的度数之和与图的边数的比是（ ） A1:2 B1:1
2、C2:1 D4:1,5,苍松优选,4. 在无向图中定义顶点Vi与Vj之间的路径为从Vi到达Vj的一个（ ）。 A顶点序列 B边序列 C权值总和 D边的条数,6,苍松优选,5. 在一个具有n个顶点的无向图中，要连通全部顶点至少需要（ ）条边。 An B. n+1 C. n-1 D. n/2,7,苍松优选,6. 若G是一个具有36条边的非连通无向图（不含自回路和多重边），则图G至少有（ ）个顶点。 A11 B. 10 C. 9 D. 8,8,苍松优选,7. 下列哪一种图的邻接矩阵是对称矩阵？ （） A. 有向图 B. 无向图 C. AOV网 D. AOE网,9,苍松优选,8.简单无向图的邻接矩阵是
3、对称的，可以对其进行压缩存储。若无向图G有n个结点，其邻接矩阵为A1n,1n，且压缩存储在B1k，则k的值至少为（ ）。 An(n+1)/2 B. n2/2 C. (n-1)(n+1)/2 D. n(n-1)/2,10,苍松优选,9.一个含有n个顶点和e条边的简单无向图，在其邻接矩阵存储结构中共有（ ）个零元素。 Ae B. 2e C. n2-e D. n2-2e,11,苍松优选,10.若采用邻接矩阵来存储简单有向图，则其某一个顶点i的入度等于该矩阵（ ）。 A第i行中值为1的元素个数 B. 所有值为1的元素个数 C第i行及第i列中值为1的元素总个数 D第i列中值为1的元素个数,12,苍松优选
4、,11. 下面关于图的存储的叙述中，哪一个是正确的。 （ ） A用邻接矩阵法存储图,占用的存储空间数只与图中结点个数有关,而与边数无关 B用邻接矩阵法存储图,占用的存储空间数只与图中边数有关,而与结点个数无关 C用邻接表法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关 D用邻接表法存储图，占用的存储空间数只与图中边数有关，而与结点个数无关,13,苍松优选,12要连通具有n个顶点的有向图，至少需要（ ）条边。 An-l Bn Cn+l D2n,14,苍松优选,13在一个无向图中，所有顶点的度数之和等于所有边数（ ）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（ ）倍。
5、 A1/2 B2 C1 D4,15,苍松优选,14. 下列说法不正确的是（ ）。 A图的遍历是从给定的源点出发每一个顶点仅被访问一次 B遍历的基本算法有两种：深度遍历和广度遍历 C图的深度遍历不适用于有向图 D图的深度遍历是一个递归过程,16,苍松优选,15.无向图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)，对该图进行深度优先遍历，得到的顶点序列正确的是（ ）。 Aa,b,e,c,d,f Ba,c,f,e,b,d Ca,e,b,c,f,d Da,e,d,f,c,b,17,苍松优选,注：南京理工大学以前
6、的题 16.设图如右所示，在下面的5个序列中，符合深度优先遍历的序列有多少？（ ） a e b d f c a c f d e b a e d f c b a e f d c b a e f d b c A5个 B4个 C3个 D2个,18,苍松优选,17.在图采用邻接表存储时，求最小生成树的 Prim 算法的时间复杂度为( )。 A. O(n) B. O(n+e) C. O(n2) D. O(n3),19,苍松优选,18.下面是求连通网的最小生成树的prim算法：集合VT，ET分别放顶点和边，初始为（ 1 ），下面步骤重复n-1次: a：（ 2 ）；b：（ 3 ）；最后：（ 4 ）。CABA
7、 （1）AVT，ET为空 BVT为所有顶点，ET为空 CVT为网中任意一点，ET为空 DVT为空，ET为网中所有边 （2）A. 选i属于VT，j不属于VT，且（i，j）上的权最小 B选i属于VT，j不属于VT，且（i，j）上的权最大 C选i不属于VT，j不属于VT，且（i，j）上的权最小 D选i不属于VT，j不属于VT，且（i，j）上的权最大 （3）A顶点i加入VT，（i,j）加入ET B. 顶点j加入VT，（i,j）加入ET C. 顶点j加入VT，（i,j）从ET中删去 D顶点i,j加入VT，（i,j）加入ET （4）AET 中为最小生成树 B不在ET中的边构成最小生成树 CET中有n-1条
8、边时为生成树，否则无解 DET中无回路时，为生成树，否则无解,20,苍松优选,19.已知有向图G=(V,E)，其中V=v1,v2,v3,v4,v5,v6,v7，E=，G的拓扑序列是（ ）。 Av1,v3,v4,v6,v2,v5,v7 Bv1,v3,v2,v6,v4,v5,v7 Cv1,v3,v4,v5,v2,v6,v7 Dv1,v2,v5,v3,v4,v6,v7,21,苍松优选,20.一个有向无环图的拓扑排序序列（ ）是唯一的。 A一定 B不一定,22,苍松优选,21.在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是（ ）。 AG中有弧 BG中有一条从Vi到Vj的路径
9、 CG中没有弧 DG中有一条从Vj到Vi的路径,23,苍松优选,22.在用邻接表表示图时，拓扑排序算法时间复杂度为( )。 A. O(n) B. O(ne) C. O(n*n) D. O(n*n*n),24,苍松优选,23. 关键路径是事件结点网络中（ ）。 A从源点到汇点的最长路径 B从源点到汇点的最短路径 C最长回路 D最短回路,25,苍松优选,24.下面关于求关键路径的说法不正确的是（ ）。 A求关键路径是以拓扑排序为基础的 B一个事件的最早发生时间同以该事件为尾的弧的活动最早开始时间相同 C一个事件的最迟发生时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差 D关键活动一定位于关键路径上,26,苍松优选,25.下列关于AOE网的叙述中，不正确的是（ ）。 A关键活动不按期完成就会影响整个工程的完成时间 B任何一个关键活动提前完成，那么整个工程将会提前完成 C所有的关键活动提前完成，那么整个工程将会提前完成 D某些关键活动提前完成，那么整个工程将会提前完成,27,苍松优选,你的问题？,Thanks！,28,苍松优选,
