数据结构基本复习 第七章 图一、单选题共25题1. 在一个图G中所有顶点的度数之和等于所有边数之和的C倍。A1/2B1C2D42. 一个具有n个顶点的无向完全图包含C条边。Ann-1Bnn1C nn-1/2D nn1/23. 一个具有n个顶点的有向完全图包含A条边。Ann-1Bnn1C nn-1/2D nn1/24. 对于一个具有n个顶点和e条边的无向图若采用邻接表表示则所有顶点邻接表中的结点总数为D。AnBeC2nD2e5. 在有向图的邻接表中每个顶点邻接表链接着该顶点所有B邻接点。A入边B出边C入边和出边D不是入边也不是出边6. 邻接表是图的一种B。A顺序存储结构B链式存储结构C索引存储结构D散列存储结构解析邻接表由顶点数组边链表组成。每个顶点的邻接点用链表存储因此整体属于链式存储结构。7. 如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点则该图一定是B。A. 完全图B连通图C有回路D. 一棵树8.下列有关图遍历的说法不正确的是C。A连通图的深度优先搜索是一个递归过程B图的广度优先搜索中邻接点的寻找具有“先进先出”的特征C非连通图不能用深度优先搜索法D图的遍历要求每一顶点仅被访问一次解析非连通图也能用深度优先搜索只需对每个未被访问的顶点依次调用深度优先搜索即可遍历所有连通分量。9. 无向图的邻接矩阵是一个A。A对称矩阵B零矩阵C上三角矩阵D对角矩阵10. 图的深度优先遍历算法类似于二叉树的A遍历。A先序B中序C后序D层次11. G是一个非连通无向图共28条边则该图至少有D个顶点。A. 6B. 7C. 8D. 9解析为了在给定的边数下顶点数最少应让其中一个连通分量边数尽量多其余顶点孤立无边。假如有8个顶点构造无向完全图则边数为8*(8-1)/228,为了构成非连通图至少还要一个孤立的顶点所以至少要9个顶点。12. 在一个无向图中若两顶点之间的路径长度为k则该路径上的顶点数为B。AkBk1Ck2D. 2k解析路径长度通常定义为路径上边的数目。一条由k条边构成的路径经过的顶点数为k1。13. n个顶点的强连通图中至少含有(B)。An-1条有向边Bn条有向边Cn(n-1)2条有向边Dn(n-1)条有向边解析强连通图要求任意两个顶点之间互相可达有路径。最少边数情况将n个顶点排成一个有向环例如1→2→3→…→n→1每个顶点有一条出边、一条入边总边数n。此时图是强连通的沿环可以到达任意顶点。注意强连通图要求是任意两个顶点之间互相可达而不是直接可达。14. 已知如图1所示的一个图若从顶点a出发按深度优先搜索法进行遍历则可能得到的一种顶点序列为C。AabecdfBacfebdCaedfcbDaebcfd15. 关键路径是事件结点网络中A。A. 从源点到汇点的最长路径B. 从源点到汇点的最短路径C. 最长的回路D. 最短的回路解析源点工程开始时间0汇点工程结束为什么找“最长路径”工程中有多条路径工序并行。所有路径都必须在汇点完成。只有最长的那条路径上的所有活动都完成了工程才算结束。所以最长路径决定了工程的最短完成时间。16. 下面B可以判断出一个有向图中是否有环回路。A. 广度优先遍历B. 拓扑排序C. 求最短路径D. 求关键路径解析拓扑排序对DAG有向无环图进行拓扑排序时如果所有顶点都能输出则无环如果存在环则一定会有顶点无法输出入度不为0但已无入度为0的顶点。因此拓扑排序可以用来检测有向图是否存在环。17. 采用邻接表存储的图其深度优先遍历类似于二叉树的B。A. 中序遍历B. 先序遍历C. 后序遍历D. 按层次遍历18. 已知无向图G的顶点数为n边数为e其邻接表表示的空间复杂度为C。A. O(n2)B. O(n*e)C. O(ne)D. O(2n)解析邻接表存储无向图时顶点表长度为n空间O(n)边表每条无向边对应2个边结点边结点总数为2e空间O(e)因此总空间复杂度为O(ne)19. 已知一个图如下图所示若从顶点a出发按广度优先搜索法进行遍历则可能得到的一种顶点序列为D。A. acfdebB. acfebdC. acbdefD. abecdf20. 在无向图中定义顶点vi与vj之间的路径为从vi到vj的一个A。A. 顶点序列B. 边序列C. 权值总和D. 边的条数解析在无向图中路径通常定义为顶点序列21. 在有向图的逆邻接表中每个顶点邻接表链接着该顶点所有A邻接点。A. 入边B. 出边C. 入边和出边D. 不是出边也不是入边22. 设G1(V1,E1)和G2(V2,E2)为两个图如果V1ÍV2,E1ÍE2则称A。A. G1是G2的子图B. G2是G1的子图C. G1是G2的连通分量D. G2是G1的连通分量23. 已知一个有向图的邻接矩阵表示要删除所有从第i个结点发出的边应B。A. 将邻接矩阵的第i行删除B. 将邻接矩阵的第i行元素全部置为0C. 将邻接矩阵的第i列删除D. 将邻接矩阵的第i列元素全部置为0解析在有向图的邻接矩阵中行表示从该顶点出发的边出边列表示进入该顶点的边入边比如说顶点1到顶点3有通路则第1行第3列值为1如果顶点3到顶点1也有通路则第3行第1列的值为1。二、判断题1. 图的深度优先搜索序列和广度优先搜索序列不是惟一的。√2. 邻接表只能用于存储有向图而邻接矩阵则可存储有向图和无向图。×3. 存储图的邻接矩阵中邻接矩阵的大小不但与图的顶点个数有关而且与图的边数也有关。×4. AOV网是一个带权的有向图。×5. 从源点到终点的最短路径是唯一的。×6. 图的生成树是惟一的。×7. 对连通图进行深度优先遍历可以访问到该图中的所有顶点。√8. 有n个结点的无向图中若边数大于n-1则该图是连通的。×解析边数en−1只是说明图可能连通但不能保证一定连通。比如有8个结点其中7个结点构成无向完全图即边数7*(7-1)/221,另一个结点完全孤立。21(8-1)但该图并不连通。9. 若一个有向图的邻接矩阵中对角线以下元素均为零则该图的拓扑有序序列必定存在。√解析邻接矩阵对角线以下元素均为零意味着所有边⟨i,j⟩⟨i,j⟩都满足ijij即顶点编号小的指向编号大的。这种矩阵对应的是无环有向图DAG。对DAG进行拓扑排序时按顶点编号从小到大的顺序输出就是一个拓扑有序序列。因此拓扑有序序列必定存在。10. AOV网拓扑排序的结果是惟一的。×11. 图的广度优先搜索序列是惟一的。×12. 具有n个顶点的无向图采用邻接矩阵表示图中的边数等于邻接矩阵中非零元素之和的一半。√13. 若连通图上各边权值均不相同则该图的最小生成树是惟一的。√解析在连通图中若所有边的权值均不相同则使用Kruskal或Prim算法构造最小生成树时每一步选择的边都是唯一确定的。因此该图的最小生成树是唯一的。14. 无向图的邻接矩阵一定是对称的。√15. 有向图的邻接矩阵一定是非对称的。×16. 用邻接矩阵存储图的时候占用空间大小不但与图的结点个数有关还与图的边数有关。×17. 图的连通分量是无向图的极小连通子图。×解析连通分量定义为无向图的极大连通子图再增加一个顶点就会破坏连通性。极小连通子图通常指生成树边数最少的连通子图不是连通分量的定义。18. 图的强连通分量是无向图的极大连通子图。×解析强连通分量定义在有向图中不是无向图。无向图没有“强连通分量”这个概念只能说“连通分量”。强连通分量是有向图的极大强连通子图任意两点互相可达。19. 对任意一个图从它的某个顶点出发进行一次深度优先或广度优先搜索遍历可访问到该图的每个顶点。×20. 一个有向图的邻接表和逆邻接表中的节点个数一定相等。√21. 有向图用邻接矩阵表示后顶点i的出度等于第i行中非0且非无穷的元素个数。√22. 图G的某一最小生成树的代价一定小于其他生成树的代价。×解析如果图G的最小生成树是唯一的则最小生成树的代价一定小于其他生成树的代价。如果图G有多个不同的最小生成树则它和其他最小生成树的代价是相等的不是“小于”。23. 任一个有向图的拓扑序列只有一个。×24. 一个无向连通图的生成树是含有该连通图的全部顶点的极小连通子图。√25. 采用邻接表存储的图的广度优先遍历算法类似于二叉树的按层次遍历。√三、程序填空题2题附加题1.已知图G的邻接矩阵如下所示从顶点1出发的广度优先搜索序列为A。A. 123 456B. 213546C. 312456D. 423615解析无权图和带权图在邻接矩阵的不同表示方法无权图邻接矩阵中的值是0或11表示有边0表示无边带权图邻接矩阵中的值是权值或∞具体数值表示边的权值∞或一个大数表示无边。2.对于一个无向图假定采用邻接矩阵表示试分别写出从顶点0出发按深度优先搜索遍历得到的顶点序列。C注每一种序列都是唯一的因为都是在存储结构上得到的。A. 0234516B. 0235164C. 0235614D. 0234516