圣才电子书www.100xuexi.com十万种考研考证电子书、题库视频学习平台第5章图一、单项选择题1．设无向图G＝（V，E）和G′＝（V′，E′），如果G′是G的生成树，则下面说法中错误的是（）。A．G′是G的子图B．G′是G的连通分量C．G′是G的极小连通子图且V＝V′D．G′是G的一个无环子图【答案】B【解析】连通分量是无向图的极大连通子图（将依附于连通分量中顶点的所有边都加上），所以连通分量中可能存在回路。2．若采用邻接矩阵来存储简单有向图，则其某一个顶点i的入度等于该矩阵（A．第i行中值为1的元素个数B．所有值为1的元素个数C．第i行及第i列中值为1的元素总个数D．第i列中值为1的元素个数【答案】D）。【解析】对于无向图，其邻接矩阵的第i行的和即为第i个顶点的度。对于有向图，邻接矩阵的第i行元素的和即为第i个顶点的出度，而邻接矩阵的第j列元素的和即为第j个顶点的出度。1/125圣才电子书www.100xuexi.com十万种考研考证电子书、题库视频学习平台3．下列关于无向连通图特性的叙述中，正确的是（Ⅰ．所有顶点的度之和为偶数Ⅱ．边数大于顶点个数减1Ⅲ．至少有一个顶点的度为1A．只有B．只有ⅡC．Ⅰ和ⅡD．Ⅰ和Ⅲ【答案】A【解析】基础题，略。）。4．下面关于对图的操作的说法不正确的是（A．寻找关键路径是关于带权有向图的操作B．寻找关键路径是关于带权无向图的操作C．连通图的生成树不一定是唯一的D．带权无向图的最小生成树不一定是唯一的【答案】B【解析】基础题，略。）。5．下面关于图的存储的叙述中，正确的是（）。A．用邻接矩阵法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关2/125圣才电子书www.100xuexi.com十万种考研考证电子书、题库视频学习平台B．用邻接矩阵法存储图，占用的存储空间数只与图中边数有关，而与结点个数无关C．用邻接表法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关D．用邻接表法存储图，占用的存储空间数只与图中边数有关，而与结点个数无关【答案】A【解析】对于n个节点的图来说，用邻接矩阵法存储图，需要n×n个存储单元，只与图中结点个数有关，与边数无关；用邻接表法存储图，与图的结点个数和边数都有关。6．在一个具有n个顶点的无向图中，要连通全部顶点至少需要（A．nB．n＋1C．n－1D．n/2【答案】C）条边。【解析】假设每顶点都和其他顶点有边，则至少需要n－1条边将所有顶点连通。7．若将数据结构中的数据元素称为结点，则一般没有开始结点和终端结点的数据结构是（）。A．树B．图C．多维数组D．线性表【答案】B3/125圣才电子书www.100xuexi.com十万种考研考证电子书、题库视频学习平台【解析】图G由两个集合V和E组成，记为G＝（V，E）。其中V是顶点的有限集合，记为V（（G）；E是连接V中两个不同顶点（顶点对）的边的有限集合，记为E（G）。图是由有限集合的顶点和边构成，没有开始结点和终端结点。8．无向图中一个顶点的度是指图中（A．通过该顶点的简单路径数B．通过该顶点的回路数C．与该顶点相邻接的顶点数D．与该顶点连通的顶点数【答案】C）。【解析】无向图中一个顶点的度是指和该顶点关联的边的数目，一条边连接两个顶点，因此，无向图中一个顶点的度也是和该顶点项邻接的顶点数。9．设无向图的顶点个数为n，则该图最多有（A．n－1B．n（n－1）/2C．n（n＋1）/2D．n2【答案】B）条边。【解析】对无向图来说边数最多的情况是任意两顶点之间都有边，即C?n(n?1)/2
4/1252n圣才电子书www.100xuexi.com十万种考研考证电子书、题库视频学习平台10．（）的邻接矩阵是对称矩阵。A．有向图B．无向图C．AOV网D．AOF网【答案】B【解析】无向图的邻接矩阵一定是一个对称矩阵。11．假设一个有n个顶点和e条弧的有向图用邻接表表示，则删除与某个顶点v相关的所有弧的时间复杂度是（A．O（n）B．O（e）C．O（n＋e）D．O（n×e）【答案】C【解析】由有向图的邻接表存储结构可知，每个顶点v链接的顶点只包含从v发出的弧所指向的顶点，不包含指向v的弧所对应的尾结点。又因为邻接表的结点数是边数与顶点数的总和，所以要删除与某个顶点相关的所有弧时间复杂度为O（n＋e）。）。12．若G是一个具有36条边的非连通无向图（不含自回路和多重边），则图G至少有（）个顶点。5/125
全国硕士研究生入学统一考试计算机科学与技术学科联考计算机网络章节题库-第五章至第七章【圣才出品】
