1、计算机专业基础综合数据结构（图）历年真题试卷汇编 3 及答案与解析一、单项选择题1 设有向图 G 是有 10 个顶点的强连通图，则 G 至少有( )条边。【哈尔滨工业大学 2005 二、7(1 分) 】（A）45（B） 90（C） 10（D）92 具有 6 个顶点的无向图，当有( )条边时能确保是一个连通图。【华中科技大学2007 一、11(2 分) 】（A）8（B） 9（C） 10（D）113 n 个结点的完全有向图含有边的数目( )。【中山大学 1998 二、9(2 分)】（A）n *n（B） n(n+1)（C） n2 （D）n *(n1)4 一个有 n 个结点的图，最少有( )个连通分量
2、，最多有( )个连通分量。【北京邮电大学 2000 二、5(208 分)】（A）0（B） 1（C） n-1（D）n5 在一个无向图中，所有顶点的度数之和等于所有边数( )倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的( )倍。【哈尔滨工业大学 2001 二、3(2 分)】（A）12（B） 2（C） 1（D）46 一个有向图，共有 n 条弧，则所有顶点的度的总和为( )。【华南理工大学 2006一、9(2 分) 】（A）2n（B） n（C） n-1（D）n27 对于一个具有 n 个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小为( )。【中南大学 2005 一、5(2 分)】（A
3、）(n-1) 2（B） n2（C） n-1（D）n8 用有向无环图描述表达式(A+B) *(A+B)/A)，至少需要顶点的数目为( )。【中山大学 1999 一、14】（A）5（B） 6（C） 8 （D）99 无向网(加权图) 的邻接矩阵是( ) 矩阵。【华中科技大学 2006 一、8(2 分)】（A）下三角（B）上三角（C）稀疏（D）对称10 设有两个无向图 G=V,E)，G=( 矿，E) ，如果 G 是 G 的生成树，则下列说法不正确的是( )。【北京交通大学 2006 一、5(2 分) 】（A）G 是 G 的子图（B） G 是 G 的连通分量（C） G 是 G 的无环子图（D）G 是 G
4、 的极小连通子图，且 V=V11 用邻接表存储图所用的空间大小( )。【北京交通大学 2004 一、7(2 分)】（A）与图的顶点数和边数都有关（B）只与图的边数有关（C）只与图的顶点数有关（D）与边数的平方有关12 对邻接表的叙述中，( )是正确的。【华南理工大学 2006 一、10(2 分)】（A）无向图的邻接表中，第 i 个顶点的度为第 i 个链表中结点数的二倍（B）邻接表比邻接矩阵的操作更简单（C）邻接矩阵比邻接表的操作更简便（D）求有向图结点的度，必须遍历整个邻接表13 在有向图的邻接表存储结构中，顶点 v 在链表中出现的次数是( )。【北京理工大学 2006 五、10(1 分)20
5、04 一、7(1 分) 】（A）顶点 v 的度（B）顶点 v 的出度（C）顶点 v 的入度（D）依附于顶点 v 的边数14 m 个顶点的无向图的邻接表最多有( )个表结点。【华中科技大学 2006 一、9(2 分)】（A）n 2（B） n(n1)（C） n(n+1)（D）n(n-1)215 图 G 是 n 个顶点的无向完全图，则下列说法正确的有： ( )。【电子科技大学2003 一、6(208 分) 】（A）G 的邻接多重表需要 n(n 一 1)个边结点和 n 个顶点结点（B） G 的连通分量个数最少（C） G 为连通图（D）G 所有顶点的度的总和为 n(n 一 1)16 下列表述中，错误的说
6、法是( )。【北京工业大学 2005 一、2(2 分)】（A）n 个结点的树的各结点度数之和为 n-1（B） n 个顶点的无向图最多有 n*(n-1)条边（C）用邻接矩阵存储图时所需存储空间的大小与图的顶点数有关，而与边数无关（D）哈希表中冲突的可能性大小与装填因子有关17 以下图的叙述中，正确的是( )。【华南理工大学 2005 一、1(2 分)】（A）强联通有向图的任何顶点到其他所有顶点都有弧（B）任意图顶点的入度等于出度（C）有向完全图一定是强联通有向图（D）有向图的边集的子集和顶点集的子集可构成原有向图的子图18 下列哪一种图的邻接矩阵是对称矩阵? ( ) 【北方交通大学 2001 一
7、、11(2 分)】（A）有向图（B）无向图（C） AOV 网（D）AOE 网19 当一个有 N 个顶点的图用邻接矩阵 A 表示时，顶点 Vi 的度是( )。【南京理工大学 1998 一、4(2 分) 】（A）（B）（C）（D）20 若邻接表中有奇数个边结点，则一定是( )。【中国科学院 2007】（A）图中有奇数个结点（B）图中有偶数个结点（C）图为无向图（D）图为有向图二、判断题21 无向图的邻接矩阵一定是对称矩阵，有向图的邻接矩阵一定是非对称矩阵。( )【东南大学 2001 一、3(1 分)】【哈尔滨工业大学 2000 三、4(2 分)】（A）正确（B）错误22 用邻接矩阵存储一个图时，在
8、不考虑压缩存储的情况下，所占用的存储空间大小与图中结点个数有关，而与图的边数无关。( )【吉林大学 2006 一、8(1 分)】（A）正确（B）错误23 邻接表法只能用于有向图的存储，邻接矩阵法对于有向图和无向图的存储都适用。( )【中国海洋大学 2007 二、11(1 分) 】【江苏大学 2005 二、4(1 分)】（A）正确（B）错误24 有 e 条边的无向图，在邻接表中有 P 个结点。( )【南京理工大学 1998 二、5(2分)】（A）正确（B）错误25 一个有向图的邻接表和逆邻接表中的结点个数一定相等。( )【电子科技大2001 二、2(1 分) 】【北京邮电大学 2006 二、2(
9、1 分)】（A）正确（B）错误26 有 n 一 1 条边的图肯定都是生成树。( )【同济大学 2005 二、9(15 分)】（A）正确（B）错误27 任何无向图都存在生成树。( )【北京邮电大学 2000 一、1(1 分)】（A）正确（B）错误28 对于无向图的生成树，从同一顶点出发所得的生成树相同。( )【南京理工大学 2004 二、6(1 分) 】（A）正确（B）错误29 不同的求最小生成树的方法最后得到的生成树是相同的。( )【南京理工大学1998 二、3(2 分) 】（A）正确（B）错误30 一个带权的无向连通图的最小生成树的权值之和是唯一的。( )【哈尔滨工业大学 2002 三、2(
10、1 分) 】【中国海洋大学 2005 二、2(1 分)】（A）正确（B）错误计算机专业基础综合数据结构（图）历年真题试卷汇编 3 答案与解析一、单项选择题1 【正确答案】 C2 【正确答案】 D3 【正确答案】 D4 【正确答案】 B,D【试题解析】 无向图中极大的连通子图称为它的连通分量。当无向图是连通图时，连通分量的个数最少等于 1，当没有任何边时，连通分量的个数最多，等于顶点数n。5 【正确答案】 B,C【试题解析】 因为一条边要连接两个顶点，每个顶点都要计算度，因此，无向图顶点的度数之和应是边数的二倍。对有向图从某顶点发出的弧，必然射入另一顶点，因此，有向图顶点的出度之和必然等于顶点的
11、入度之和。6 【正确答案】 A7 【正确答案】 B8 【正确答案】 A9 【正确答案】 D10 【正确答案】 B11 【正确答案】 A【试题解析】 邻接表的顶点向量所占空间和顶点个数有关，边结点所占空间和边数有关。所以邻接表所占空间和顶点个数与边数相关。12 【正确答案】 D【试题解析】 无向图的邻接表中，顶点 vi 的度为第 i 个链表中的结点个数。有向图的邻接表中，顶点 vi 的出度为第 i 个链表中的结点个数，为求 vi 的入度则需遍历整个邻接表，其值等于邻接点为 i 的边结点的个数。13 【正确答案】 C14 【正确答案】 B15 【正确答案】 B,C,D16 【正确答案】 B17 【
12、正确答案】 C【试题解析】 强联通图的任何顶点到其他所有顶点都有路径，未必都有弧，只有完全图才任意两个顶点都有双向弧。有向图顶点的出度之和等于顶点的入度之和，未必顶点的入度等于出度。有向图的边集的子集和顶点集的子集不一定构成原有向图的子图。18 【正确答案】 B19 【正确答案】 B20 【正确答案】 D二、判断题21 【正确答案】 B22 【正确答案】 A23 【正确答案】 B【试题解析】 邻接矩阵和邻接表既能存储无向图，也能存储有向图，也都能存储带权图。十字链表是有向图的另一种存储结构，邻接多重表是无向图的另一种存储结构。24 【正确答案】 B25 【正确答案】 A26 【正确答案】 B【
13、试题解析】 是生成树问题。只有无向连通图才有生成树，非连通无向图会形成生成森林。n 个顶点的无向连通图的生成树具有图的全部顶点和足以使图连通的 n一 1 条边，是该图的极小连通子图。生成树一般不唯一。但是 n 个顶点 n 一 1 条边的无向图不一定是生成树。27 【正确答案】 B28 【正确答案】 B29 【正确答案】 B【试题解析】 是最小生成树问题。上面已说明，无向连通图的生成树可能有多棵，最小生成树是代价(权值之和)最小的那棵生成树。最小生成树的权值之和是唯一的，但在具有较小相等权值的情况下，最小生成树一般不唯一。若权值互不相同，最小生成树则是唯一的。在具有较小相等权值的情况下，有可能较小权值的边没被全包括在生成树中(如若包括会形成环)。30 【正确答案】 A
