当前位置:首页 >> 英语 >>

第7章图(习题)

第 7章 图 习 题 一、选择题 1、无向图 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)},对该图进行深度优 先遍历,得到的顶点序列正确的是( ) 。 A.a,b,e,c,d,f B.a,c,f,e,b,d C.a,e,b,c,f,d D.a,e,d,f,c,b A.a,b,e,c,d,f B.a,c,f,e,b,d C.a,e,b,c,f,d D.a,e,d,f,c,b 2、一个 n 个顶点的连通无向图,其边的个数至少为( )。 A.n-1 B.n C.n+1 D.nlogn; 3、在图采用邻接表存储时,求最小生成树的 Prim 算法的时间复杂度为( )。 2 3 A. O(n) B. O(n+e) C. O(n ) D. O(n ) 4、要连通具有 n 个顶点的有向图,至少需要( )条边。 A.n-l B.n C.n+l D.2n 5、求解最短路径的 Floyd 算法的时间复杂度为( )。 A.O(n) B. O(n+c) C. O(n*n) D. O(n*n*n) 6、一个有 n 个结点的图,最少有( )个连通分量,最多有( )个连通分量。 A.0 B.1 C.n-1 D.n 7、在一个无向图中,所有顶点的度数之和等于所有边数( )倍,在一个有向图中,所 有顶点的入度之和等于所有顶点出度之和的( )倍。 A.1/2 B.2 C.1 D.4 8、一个有向无环图的拓扑排序序列( )是唯一的。 A.一定 B.不一定 9、关键路径是事件结点网络中( ) 。 A.从源点到汇点的最长路径 B.从源点到汇点的最短路径 C.最长回路 D.最短回路 10、下列关于 AOE 网的叙述中,不正确的是( ) 。 A.关键活动不按期完成就会影响整个工程的完成时间 B.任何一个关键活动提前完成,那么整个工程将会提前完成 C.所有的关键活动提前完成,那么整个工程将会提前完成 D.某些关键活动提前完成,那么整个工程将会提前完成 二、填空题 1、克鲁斯卡尔算法的时间复杂度为______,它对______图较为适合。 2、为了实现图的广度优先搜索,除了一个标志数组标志已访问的图的结点外,还需 ______存放被访问的结点以实现遍历。 3、具有 n 个顶点 e 条边的有向图和无向图用邻接表表示,则邻接表的边结点个数分别 为 和 条。 4、在有向图的邻接矩阵表示中,计算第 I 个顶点入度的方法是______。 5、若 n 个顶点的连通图是一个环,则它有 棵生成树。 6、N 个顶点的连通图用邻接矩阵表示时,该矩阵至少有_______个非零元素。 7、有 N 个顶点的有向图,至少需要量______条弧才能保证是连通的。 8、有向图 G 可拓扑排序的判别条件是______。 9、若要求一个稠密图的最小生成树,最好用 算法求解。 10 、 AOV 网中 , 结点表示 ______, 边表示 ______ 。 AOE 网中 , 结点表示 ______, 边表示 ______。 三、判断题 1、当改变网上某一关键路径上任一关键活动后,必将产生不同的关键路径。 2、在 n 个结点的无向图中,若边数大于 n-1,则该图必是连通图。 3、在 AOE 图中,关键路径上某个活动的时间缩短,整个工程的时间也就必定缩短。 4、 若一个有向图的邻接矩阵对角线以下元素均为零, 则该图的拓扑有序序列必定存在。 5、在图 G 的最小生成树 G1 中,可能会有某条边的权值超过未选边的权值。 6、强连通图的各顶点间均可达。 7、带权的连通无向图的最小代价生成树是唯一的。 8、广度遍历生成树描述了从起点到各顶点的最短路径。 9、邻接多重表是无向图和有向图的链式存储结构。 10、 无向图的邻接矩阵一定是对称矩阵,有向图的邻接矩阵一定是非对称矩阵。 四、应用题 1.设一有向图为 G=(V,E),其中 V={a,b,c,d,e},E={<a,b>,<b,a>,<c,d>,<d,e>, <e,a>,<e,c>},请画出该有向图,并求各个顶点的入度和出度。 2.对 n 个顶点的无向图 G,采用邻接矩阵表示,判别下列有关问题: (1)图中有多少条边? (2)任意两个顶点 i 和 j 是否有边相连? (3)任意一个顶点的度是多少? V5 V1 3.如图所示为一个有向图,试给出: V6 (1)每个顶点的入度和出度 (2)邻接距阵 V2 V4 (3)邻接表 (4)逆邻接表 V3 (5)强连同分量 4.已知一有向图的邻接表如图所示。 (1) 画出该有向图。 (2) 写出从顶点 a 开始的深度优先和广度优先遍历序列。 (3) 画出从顶点 a 出发的深度优先和广度优先生成树(或森林)。 0 1 2 3 4 5 a b c d e f 2 5 3 1 3 ? ? 4 ? 2 10 1 3 3 15 2 20 6 3 5 5 4 10 11 ? 5 3 ? ? 5.(1)画出下图所示图的邻接矩阵表示。 (2)画出此图的邻接表表示。 (3)如果每个指针需要 4 个字节,每个顶点的信息 占两个字节,每条边的权占 2 个字节,顶点的下标占 1 个字节。此图采用哪种表示法所需要 的空间较多? 6.对于下面的带权有向图,写出其相邻矩阵表示,并画出其邻接表表示。 v0 3 5 6 v1 1 1 8 4 v2 v3 2 v5 4 v7 v4 9 v6 2 v8 7. 给出下图所示图(a)和图(b), 按照下列条件分别写出从顶点 v0 出发按深度优先搜索遍历 得到的顶点序列和按广度优先搜索遍历得到的顶点序列。 (1)假定它们采用邻接矩阵表示; (2)假定它们采用邻接表表示,并且假定每个顶点邻接表中的节点是按顶点序号从大到小的 次序链接的。 0 1 7 8 2 3 6 7 8 6 5 9 4 3 4 5 0 1 2 8.设有一无向图 G=(V,E),其中 V={1,2,3,4,5,6},E={(1,2)