第7章图.doc

第7章 图 7.1　选择题 1．对于一个具有n个顶点和e条边的有向图，在用邻接表表示图时，拓扑排序算法时间复杂度为（　　） A） O(n) B） O(n+e) C） O(n*n) D） O(n*n*n) 【答案】B 2．设无向图的顶点个数为n，则该图最多有（　　）条边。 A）n-1 B）n(n-1)/2 C） n(n+1)/2 D）n2 【答案】B 3．连通分量指的是（　　） A） 无向图中的极小连通子图 B） 无向图中的极大连通子图 C） 有向图中的极小连通子图 D） 有向图中的极大连通子图 【答案】B 4．n个结点的完全有向图含有边的数目（　　） A）n*n B）n（n+1） C）n/2 D）n*（n-1） 【答案】D 5．关键路径是（　　） A） AOE网中从源点到汇点的最长路径 B） AOE网中从源点到汇点的最短路径 C） AOV网中从源点到汇点的最长路径 D） AOV网中从源点到汇点的最短路径 【答案】A 6．有向图中一个顶点的度是该顶点的（　　） A）入度 B） 出度 C） 入度与出度之和 D） （入度+出度）/2 【答案】C 7．有e条边的无向图，若用邻接表存储，表中有（　　）边结点。 A） e B） 2e C） e-1 D） 2(e-1) 【答案】B 8．实现图的广度优先有哪些信誉好的足球投注网站算法需使用的辅助数据结构为（　　） A） 栈 B） 队列 C） 二叉树 D） 树 【答案】B 9．实现图的非递归深度优先有哪些信誉好的足球投注网站算法需使用的辅助数据结构为（　　） A） 栈 B） 队列 C） 二叉树 D） 树 【答案】A 10．存储无向图的邻接矩阵一定是一个（　　） A） 上三角矩阵 B）稀疏矩阵 C） 对称矩阵 D） 对角矩阵 【答案】C 11．在一个有向图中所有顶点的入度之和等于出度之和的（　　）倍 A） 1/2 B）1 C） 2 D） 4 【答案】B 12．在图采用邻接表存储时，求最小生成树的 Prim 算法的时间复杂度为（　　） A） O(n) B） O(n+e) C） O(n2) D） O(n3) 【答案】B 13．下列关于AOE网的叙述中，不正确的是（　　） A）关键活动不按期完成就会影响整个工程的完成时间 B）任何一个关键活动提前完成，那么整个工程将会提前完成 C）所有的关键活动提前完成，那么整个工程将会提前完成 D）某些关键活动提前完成，那么整个工程将会提前完成 【答案】B 14．具有10个顶点的无向图至少有多少条边才能保证连通（　　） A） 9 B）10 C） 11 D） 12 【答案】A 15．在含n个顶点和e条边的无向图的邻接矩阵中，零元素的个数为（　　） ?A） e B）2e C） n2-e D）n2-2e 【答案】D 7.2　填空题 1．无向图中所有顶点的度数之和等于所有边数的_____________倍。 【答案】2 2．具有n个顶点的无向完全图中包含有_____________条边，具有n个顶点的有向完全图中包含有_____________条边。 【答案】（1）n(n-1)/2 （2） n(n-1) 3．一个具有n个顶点的无向图中，要连通所有顶点则至少需要_____________条边。 【答案】n-1 4．假定一个图具有n个顶点和e条边，则采用邻接矩阵、邻接表表示时，其相应的空间复杂度分别为_____________和_____________。 【答案】（1）O(n2) （2） O(n+e) 5．对用邻接矩阵表示的图进行任一种遍历时，其时间复杂度为_____________，对用邻接表表示的图进行任一种遍历时，其时间复杂度为_____________。 【答案】（1）O(n2) （2） O(e) 6．对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点分别为_____________和_____________条。 【答案】（1）e （2）2e 7． 在有向图的邻接表和逆邻接表表示中，每个顶点的边链表中分别链接着该顶点的所有_____________和_____________结点。 【答案】（1）出边 （2） 入边 8． 对于一个具有n个顶点和e条边的无向图，当分别采用邻接矩阵、邻接表表示时，求任一顶点度数的时间复杂度依次为_____________和_____________。 【答案】（1）O(n) （2）O(e+n)