数据结构第7节图习题.docx

第七章图习题1单项选择题1、图中有关路径的定义是（）。 A、由顶点和相邻顶点序偶构成的边所形成的序列B、由不同顶点所形成的序列C、由不同边所形成的序列D、上述定义都不对2、设无向图的顶点个数为n，则该图最多有（）条边。A、n–1B、n (n–1)/2C、n (n+1)/2D、n23、一个n个顶点的连通无向图，其边的个数至少为（）。A、n–1B、nC、n+1D、nlogn4、下面结构中最适于表示稀疏无向图的是（）。A、邻接矩阵B、逆邻接表C、邻接多重表D、十字链表5、下列哪一种图的邻接矩阵是对称矩阵？（）A、有向图B、无向图C、AOV网D、AOE网6、当一个有N个顶点的图用邻接矩阵A表示时，顶点Vi的度是（）。A、第j列所有元素之和B、第i行所有元素之和C、不确定D、第j列所有元素之和+第i行所有元素之和7、下面哪一方法可以判断出一个有向图是否有环（回路）（）。A、深度优先遍历B、拓扑排序C、求最短路径D、求关键路径8、在图采用邻接表存储时，求最小生成树的 Prim 算法的时间复杂度为( )。A、O(n)B、O(n+e)C、O(n2)D、O(n3)9、求解最短路径的Floyd算法的时间复杂度为( )。A、O(n)B、O(n+e)C、O(n2)D、O(n3)10、已知有向图G=(V,E)，其中V={v1, v2, v3, v4, v5, v6, v7}，E={v1,v2,v1,v3,v1,v4,v2,v5,v3,v5,v3,v6,v4,v6,v5,v7,v6,v7},G的拓扑序列是（）。A、v1,v3,v4,v6,v2,v5,v7B、v1,v3,v2,v6,v4,v5,v7C、v1,v,v4,v5,v2,v6,v7D、v1,v2,v5,v3,v4,v6,v711、在用邻接表表示图时，拓扑排序算法时间复杂度为( )。A、O(n)B、O(n+e)C、O(n2)D、O(n3)12、关键路径是事件结点网络中（）。A、从源点到汇点的最长路径B、从源点到汇点的最短路径C、最长路径D、最短路径13、下面关于求关键路径的说法不正确的是（）。A、求关键路径是以拓扑排序为基础的B、一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同C、一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差D、关键活动一定位于关键路径上14、下列关于AOE网的叙述中，不正确的是（）。A、关键活动不按期完成就会影响整个工程的完成时间B、任何一个关键活动提前完成，那么整个工程将会提前完成C、所有的关键活动提前完成，那么整个工程将会提前完成D、某些关键活动提前完成，那么整个工程将会提前完成15、采用邻接表存储图的深度优先遍历算法类似于二叉树的（）。A、层序遍历B、先序遍历C、中序遍历D、后序遍历16、图G中，所有顶点的度数之和等于所有边数的（）倍。A、1B、2C、3D、1/217、一个具有n个顶点的无向图若采用邻接矩阵存储，则该矩阵的大小是（）。A、n–1B、n+1C、(n–1)2D、n218、要连通n个顶点的有向图，至少需要（）条边。A、n– 1B、nC、n+1D、nlogn19、从图的邻接矩阵中可以看出，该图有（① ）个顶点，如果是有向图，该图有（②）条弧，如果是无向图，则有（③）条边。① A、9B、3C、6D、1② A、5B、4C、3D、2③ A、5B、4C、3D、220、设图V={a, b, c, d, e, f}，E={(a,b), (a, e),(a, c),(b, e),(c, f), (f, d),(e, d)}，对该图进行深度优先遍历，得到的顶点序列是（）。A、abecdfB、acfebdC、aebcfdD、aedfcb21、在有向图G的拓扑序列中，若顶点vi在顶点vj之前，则下面情况不可能出现的是（）。A、G中有弧vi,vjB、G中有一条从vi到vj的路径C、G中没有弧vi,vjD、G中有一条从vj到vi的路径2填空题1、如果含n个顶点的图形成一个环，则它有（）棵生成树。2、下图所示的强连通分量有（）个。3、N个顶点的连通图用邻接矩阵表示时，该矩阵至少有（）个非零元素。4、求图的最小生成树有两种算法，其中（）算法适合求解稀疏图的最小生成树。5、有向图G可以拓扑排序的判别条件是（）。6、在AOV网中，存在环意味着（）；对程序的数据流图来说，它表明存在（）。7、已知一个图的广度优先生成树如下图所示，则与此相应的广度优先遍历序列为（）。8、在有n个顶点的有向图中，每个顶点的度最大可达（）。9、已知一无向图G = (V, E)，其中V = {a, b, c, d, e}，E = {(a, b), (a, d), (a, c), (d, c), (b, e)}，现用某种遍历方法从顶点a开始遍历图，得到的遍历