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