资源描述：
《第七章∶图练习题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第七章：图练习题一、选择题1、一个有n个顶点的无向图最多有（）条边。A、nB、n(n-1)C、n(n-1)/2D、2n2、具有6个顶点的无向图至少有（）条边才能保证是一个连通图。A、5B、6C、7D、83、具有n个顶点且每一对不同的顶点之间都有一条边的图被称为（）。A、线性图B、无向完全图C、无向图D、简单图4、具有4个顶点的无向完全图有（）条边。A、6B、12C、16D、205、G是一个非连通无向图，共有28条边，则该图至少有（）个顶点A、6B、7C、8D、96、存储稀疏图的数据结构常用的是（）。A、邻接矩阵B、三元组C、邻
2、接表D、十字链表7、对一个具有n个顶点的图，采用邻接矩阵表示则该矩阵的大小为（）。A、nB、(n-1)2C、(n+1)2D、n28、设连通图G的顶点数为n，则G的生成树的边数为（）。A、n-1B、nC、2nD、2n-19、n个顶点的无向图的邻接表中结点总数最多有（）个。A、2nB、nC、n/2D、n(n-1)10、对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表向量的大小为（），所有顶点邻接表的结点总数为（）。A、nB、n+1C、n-1D、2nE、e/2F、eG、2eH、n+e11、在有向图的邻接表存储结构中，顶点
3、v在表结点中出现的次数是（）。A、顶点v的度B、顶点v的出度C、顶点v的入度D、依附于顶点v的边数12、已知一个图，若从顶点a出发进行深度和广度优先搜索遍历，则可能得到的顶点序列分别为（）和（）（1）A、abecdfB、acfebdC、acebfdD、acfdeb（2）A、abcedfB、abcefdC、abedfcD、acfdeb13、采用邻接表存储的图的深度和广度优先搜索遍历算法类似于二叉树的（）和（）。A、中序遍历B、先序遍历C、后序遍历D、层次遍历14、已知一有向图的邻接表存储结构如下图所示，分别根据图的深度和广度优先
4、搜索遍历算法，从顶点v1出发，得到的顶点序列分别为（）和（）。A、v1,v2,v3,v4,v5B、v1,v3,v2,v4,v5C、v1,v2,v3,v5,v4D、v1,v4,v3,v5,v215、已知有8个顶点为A，B，C，D，E，F，G，H的无向图，其邻接矩阵存储结构如下，由此结构，从A点开始深度遍历，得到的顶点序列为（）。ABCDEFGHA01010000B10101110C01010000D10100010E01000001F01000011G01010101H00001110A、ABCDGHFEB、ABCDGFHEC、
5、ABGHFECDD、ABFHEGDCE、ABEHFGDCF、ABEHGFCD16、已知一个图如下，在该图的最小生成树中各边上权值之和为（），在该图的最小生成树中，从v1到v6的路径为（）。A、31B、38C、36D、43E、v1,v3,v6F、v1,v4,v6G、v1,v5,v4,v6H、v1,v4,v3,v617、关键路径是事件结点网络中的（）。A、从源点到汇点的最长路径B、从源点到汇点的最短路径C、最长的回路D、最短的回路18、正确的AOE网必须是（），AOE网中某边权值应当是（），权值为0的边表示（）。（1）A、完全图B
6、、哈密尔顿图C、无环图D、强连通图（2）A、实数B、正整数C、正数D、非负数（3）A、为决策而增加的活动B、为计算方便而增加的活动C、表示活动间的时间顺序关系D、该活动为关键活动19、已知一个图如下，则由该图得到的一种拓扑序列为（）。A、v1,v4,v6,v2,v5,v3B、v1,v2,v3,v4,v5,v6C、v1,v4,v2,v3,v6,v5D、v1,v2,v4,v6,v3,v520、下面结论中正确的是（）A、在无向图中，边的条数是顶点度数之和。B、在图结构中，顶点可以没有任何前驱和后继。C、在n个顶点的无向图中，若边数大
7、于n-1，则该图必定是连通图D、图的邻接矩阵必定是对称矩阵。21、下面结论中正确的是（）A、若有向图的邻接矩阵中对角线以下元素均为0，则该图的拓扑排序序列必定存在。B、网络的最小代价生成树是唯一的。C、在拓扑排序序列中，任意两个相继顶点vi和vj都存在从vi到vj的路径。D、在有向图中，从一个顶点到另一个顶点的最短路径是唯一的。22、下面结论不正确的是（）。A、无向图的连通分量是该图的极大连通子图。B、有向图用邻接矩阵表示容易实现求顶点度数的操作。C、无向图用邻接矩阵表示，图中的边数等于邻接矩阵元素之和的一半。D、有向图的邻接
8、矩阵必定不是对称矩阵。23、下面结论中正确的是（）。A、按深度优先搜索遍历图时，与始点相邻的顶点先于不与始点相邻的顶点访问。B、一个图按深度优先搜索遍历的结果是唯一的。C、若有向图G中包含一个环，则G的顶点间不存在拓扑排序。D、图的拓扑排序序列是唯一的。24、下面结论中不正确
