第7章 图习题及答案

《第7章 图习题及答案》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第7章图一、选择题1．对于一个具有n个顶点和e条边的有向图，在用邻接表表示图时，拓扑排序算法时间复杂度为（　　）A）O(n)B）O(n+e)C）O(n*n)D）O(n*n*n)【答案】B2．设无向图的顶点个数为n，则该图最多有（　　）条边。A）n-1B）n(n-1)/2C）n(n+1)/2D）n2【答案】B3．连通分量指的是（　　）A）无向图中的极小连通子图B）无向图中的极大连通子图C）有向图中的极小连通子图D）有向图中的极大连通子图【答案】B4．n个结点的完全有向图含有边的数目（　　）A）n*nB）n（n

2、+1）C）n/2D）n*（n-1）【答案】D5．关键路径是（　　）A）AOE网中从源点到汇点的最长路径B）AOE网中从源点到汇点的最短路径C）AOV网中从源点到汇点的最长路径D）AOV网中从源点到汇点的最短路径【答案】A6．有向图中一个顶点的度是该顶点的（　　）A）入度B）出度C）入度与出度之和D）（入度+出度）/2【答案】C7．有e条边的无向图，若用邻接表存储，表中有（　　）边结点。A）eB）2eC）e-1D）2(e-1)【答案】B8．实现图的广度优先搜索算法需使用的辅助数据结构为（　　）A）栈B）队列C

3、）二叉树D）树【答案】B9．实现图的非递归深度优先搜索算法需使用的辅助数据结构为（　　）A）栈B）队列C）二叉树D）树【答案】A10．存储无向图的邻接矩阵一定是一个（　　）A）上三角矩阵B）稀疏矩阵C）对称矩阵D）对角矩阵【答案】C11．在一个有向图中所有顶点的入度之和等于出度之和的（　　）倍A）1/2B）1C）2D）4【答案】B12．在图采用邻接表存储时，求最小生成树的Prim算法的时间复杂度为（　　）A）O(n)B）O(n+e)C）O(n2)D）O(n3)【答案】B13．下列关于AOE网的叙述中，不正确

4、的是（　　）A）关键活动不按期完成就会影响整个工程的完成时间B）任何一个关键活动提前完成，那么整个工程将会提前完成C）所有的关键活动提前完成，那么整个工程将会提前完成D）某些关键活动提前完成，那么整个工程将会提前完成【答案】B14．具有10个顶点的无向图至少有多少条边才能保证连通（　　）A）9B）10C）11D）12【答案】A15．在含n个顶点和e条边的无向图的邻接矩阵中，零元素的个数为（　　）A）eB）2eC）n2-eD）n2-2e【答案】D16.对于一个具有n个顶点和e条边的无向图，如果采用邻接表来表示

5、，则其表头向量的大小为。A、nB、n+1C、n-1D、n+e【答案】A二、填空题1．无向图中所有顶点的度数之和等于所有边数的_____________倍。【答案】22．具有n个顶点的无向完全图中包含有_____________条边，具有n个顶点的有向完全图中包含有_____________条边。【答案】（1）n(n-1)/2（2）n(n-1)3．一个具有n个顶点的无向图中，要连通所有顶点则至少需要_____________条边。【答案】n-15．对用邻接矩阵表示的图进行任一种遍历时，其时间复杂度为_____

6、________，对用邻接表表示的图进行任一种遍历时，其时间复杂度为_____________。【答案】（1）O(n2)（2）O(n+e)6．对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点分别为_____________和_____________条。【答案】（1）e（2）2e7．在有向图的邻接表和逆邻接表表示中，每个顶点的边链表中分别链接着该顶点的所有_____________和_____________结点。【答案】（1）出边（2）入边8．对于一个具有n个顶点和e条边的无向

7、图，当分别采用邻接矩阵、邻接表表示时，求任一顶点度数的时间复杂度依次为_____________和_____________。【答案】（1）O(n)（2）O(e)9．对于一个具有n个顶点和e条边的连通图，其生成树中的顶点数和边数分别为_____________和_____________。【答案】（1）n（2）n-110．Prim算法和Kruscal算法的时间复杂度分别为_____________和_____________。【答案】（1）O(n2)（2）O(eloge)11.假设图G中含有n个顶点，e条边

8、，且知每个顶点的度数为di，则它们三者之间满足的关系为：。【答案】e=1/2∑di12.我们把图中所有顶点加上遍历时经过的所有边构成的子图称为。【答案】生成树13、有n个顶点的无向图，其边数最大可达，像这样的有最大边数的无向图通常被称为。【答案】n(n-1)/2完全无向图14、树被定义为连通而不具有的（无向）图。【答案】回路15、对于一个图G的遍历，通常有两种方法，它们分别是和。【答案】深度优先法广度优先法16.