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