1、计算机专业基础综合数据结构（图）历年真题试卷汇编 2 及答案与解析一、单项选择题1 下列关于无向连通图特性的叙述中，正确的是( )。【2009 年全国试题 7(2 分)】I所有顶点的度之和为偶数边数大于顶点个数减 1至少有一个顶点的度为 1（A）只有 I（B）只有 （C） I 和（D）I 和2 若无向图 G=(V,E)中含有 7 个顶点，要保证图 G 在任何情况下都是连通的，则需要的边数最少是( ) 。【2010 年全国试题 7(2 分)】（A）6（B） 15（C） 16（D）213 对下图进行拓扑排序，可以得到不同拓扑序列的个数是( )。【2010 年全国试题8(2 分)】（A）4（B） 3
2、（C） 2（D）14 下列关于图的叙述中，正确的是( )。【2011 年全国试题 8(2 分)】I回路是简单路径存储稀疏图，用邻接矩阵比邻接表更省空间若有向图中存在拓扑序列，则该图不存在回路（A）仅（B）仅 I、（C）仅 （D）仅 I、5 对有 n 个结点、e 条边且使用邻接表存储的有向图进行广度优先遍历，其算法时间复杂度是( ) 。【2012 年全国试题 5(2 分) 】（A）O(n)（B） O(e)（C） O(n+e)（D）O(ne)6 若用邻接矩阵存储有向图，矩阵中主对角线以下的元素均为零，则关于该图拓扑序列的结论是( ) 。【2012 年全国试题 6(2 分) 】（A）存在，且唯一（B
3、）存在，且不唯一（C）存在，可能不唯一（D）无法确定是否存在7 对如下有向带权图，若采用迪杰斯特拉(Dijkstra)算法求从源点口到其他各顶点的最短路径，则得到的第一条最短路径的目标顶点是 6，第二条最短路径的目标顶点是 c，后续得到的其余各最短路径的目标顶点依次是( )。K2012 年全国试题 7(2 分)】（A）d，e， f（B） e，d,f（C） f,d,e（D）f,e，d8 下列关于最小生成树的叙述中，正确的是( )。【2012 年全国试题 8(2 分)】I最小生成树的代价唯一所有权值最小的边一定会出现在所有的最小生成树中使用普里姆(Prim)算法从不同顶点开始得到的最小生成树一定相
4、同使用普里姆算法和克鲁斯卡尔(Kruskal) 算法得到的最小生成树总不相同（A）仅 I（B）仅 （C）仅 I、（D）仅、9 设图的邻接矩阵 A 如下所示。各顶点的度依次是 ( )。【2013 年全国试题 7(2 分)】（A）1，2，1，2（B） 2，2，1，1（C） 3，4，2，3 （D）4，4，2，210 若对如下无向图进行遍历，则下列选项中，不是广度优先遍历序列的是( )。【2013 年全国试题 8(2 分)】（A）h，c， a，b，d,e，g,f（B） e，a,f,g，b，h，c，d（C） d,b，c，a ，h，e ，f,g（D）a，b， c，d，h，e,f,g11 下面AOE 网表示
5、一项包含 8 个活动的工程。通过同时加快若干活动的进度可以缩短整个工程的工期。下列选项中，加快其进度就可以缩短工程工期的是( )。2013 年全国试题 9(2 分) 】（A）c 和 e（B） d 和 c（C） f 和 d （D）f 和 h12 对如下所示的有向图进行拓扑排序，得到的拓扑序列可能是( )。【2014 年全国试题 7(2 分) 】（A）3，1，2，4，5，6（B） 3，1，2，4，6，5（C） 3，1，4，2，5，6（D）3，1，4，2，6，513 设有向图 G=(V,E)，顶点集 V=V0，V 1，V 2，V 3，边集庐0，v 1， 0，v 2， 0，v 3， 1，v 3，若从顶
6、点 V0 开始对图进行深度优先遍历，则可能得到的不同遍历序列个数是( )。【2015 年全国试题 5(2 分)】（A）2（B） 3（C） 4（D）514 求下面带权图的最小(代价)生成树时，可能是克鲁斯卡尔(Kruskal)算法第二次选中但不是普里姆(Prim)算法(从 V4 开始)第 2 次选中的边是( )。【2015 年全国试题6(2 分)】（A）(V 1，V 3)（B） (V1，V 4)（C） (V2，V 3)（D）(V 3，V 4)15 以下图的叙述中，正确的是( )。【华南理工大学 2006 一、1(2 分)】（A）图与树的区别在于图的边数大于或等于顶点数（B）假设有图 G=(V,E
7、)，顶点集 VV，EE ，则 V 和E构成 G 的子图（C）无向图的连通分量指无向图中的极大连通子图（D）图的遍历就是从图中某一顶点出发访遍图中其余顶点16 图中有关路径的定义是( )。【北方交通大学 2001 一、24(2 分)】（A）由顶点和相邻顶点序偶构成的边所形成的序列（B）由不同顶点所形成的序列（C）由不同边所形成的序列（D）上述定义都不是17 设无向图的顶点个数为 n，则该图最多有( )条边。【清华大学 1998 一、5(分)】（A）n 一 1（B） n(n-1) 2（C） n(n+1)2（D）0（E）n 218 具有 n 个顶点的有向完全图有( )条边。【湖南大学 2008】（A
8、）n(n 一 1)2（B） n(n 一 1)（C） n(n+1)2（D）n(n+1)19 一个 n 个顶点的连通无向图，其边的个数至少为( )。【浙江大学 1999 四、4(4分)】（A）g 一 1（B） n（C） n+1（D）nlogn20 要连通具有 n 个顶点的有向图，至少需要( )条边。【北京航空航天大学 2000一、6(2 分) 】（A）n-1（B） n （C） n+1（D）2n二、判断题21 n 个结点的无向图，若不允许结点到自身的边，也不允许结点到结点的多重边，且边的总数为 n(n1)2，则该无向图一定是连通图。( )【中南大学 2003 一、18(1 分 )】（A）正确（B）错
9、误22 在 n 个结点的无向图中，若边数n1，则该图必是连通图。( )【中国海洋大学 2006 二、10(1 分) 】（A）正确（B）错误23 n 个结点的有向图，若它有 n(n 一 1)条边，则它一定是强连通的。( )【吉林大学 2006 一、7(1 分) 】（A）正确（B）错误24 强连通图的各顶点间均可达。( )【北京邮电大学 2000 一、3(1 分)】（A）正确（B）错误25 强连通分量是无向图的极大强连通子图。( )【北京邮电大学 2002 一、7(1 分)】（A）正确（B）错误26 若有向图有 n 个顶点，则其强连通分量最多有，z 个。( )【北京邮电大学 2006二、7(1 分
10、) 】（A）正确（B）错误27 无向图中任何一个边数最少且连通所有顶点的子图都是该图无向图的生成树。( )【武汉大学 2004】（A）正确（B）错误28 有向图中顶点 V 的度等于其邻接矩阵中第 V 行中的 1 的个数。( )【合肥工业大学 2001 二、7(1 分) 】（A）正确（B）错误29 图 g 的顶点 v 的入度等于其邻接矩阵中第 1，列中的 1 的个数。( )【北京邮电大学 2006 二、7(1 分) 】（A）正确（B）错误30 用邻接矩阵法存储一个图所需的存储单元数目与图的边数有关。( )【东南大学 2001 一、4(1 分) 】【中山大学 1994 一、3(2 分)】（A）正确
11、（B）错误计算机专业基础综合数据结构（图）历年真题试卷汇编 2 答案与解析一、单项选择题1 【正确答案】 A【试题解析】 无向图中一条边要连接两个顶点，因此顶点的度数之和必为偶数。n 个顶点的无向连通图至少需要 n-1 条边。无向连通图并不要求“至少有一个顶点的度为 1”。2 【正确答案】 C【试题解析】 要保证 n 个顶点的无向图 G 在任何情况下都是连通的，则需要先由 n-1 个顶点组成完全图，从第 n 个顶点引一条到 n-1 任一顶点的边，则图肯定是连通的。本题先由 6 个顶点组成完全图，需要 6(6-1)2=15 条边，故按题目要求“需要的边数最少”是 15+1=16。3 【正确答案】
12、 B4 【正确答案】 C【试题解析】 图中第 1 个顶点和最后一个顶点相同的路径称为回路或环。序列中所有顶点不重复出现的路径称为简单路径，邻接矩阵的大小只和顶点个数相关，存储稀疏图，用邻接表比邻接矩阵更省空间。拓扑序列成功的前提是有向图中不存在回路。5 【正确答案】 C6 【正确答案】 C7 【正确答案】 C8 【正确答案】 A【试题解析】 若有较小的相等权值，最小生成树可能不唯一，但是其代价是唯一的。的错误在于“所有权值最小的边一定会出现在”，这可能形成环。的错误在于“最小生成树一定相同”，的错误在于两种算法“最小生成树总不相同”。若无相同权值，生成树一定相同；若有较小相等权值，生成树可能会
13、不同。9 【正确答案】 C【试题解析】 有向图的邻接矩阵中，第 i 行非零元素个数是第 i 个顶点的出度，第 i 列非零元素个数是第 i 个顶点的入度，第 i 个顶点的度是其出度和入度之和。10 【正确答案】 D11 【正确答案】 C12 【正确答案】 D13 【正确答案】 D【试题解析】 不同的遍历序列(只列出下标)是：0321，0312，0132，0231，0213。14 【正确答案】 C【试题解析】 Kruskal 算法是按权值升序选择边的，首先选权值为 5 的边(V1，V4)，接着选择权值为 8 的边，这时有 3 种选择：(V1，V3) 、(V3，V4)和(V2，V3)。Prim 从
14、V4 开始，首先选择权值为 5 的边(V1，V4)，接着可以选择(V1，V3)或(V3，V3)，不可能选择 (V2，V3)。15 【正确答案】 C【试题解析】 树是一对多的关系，图是多对多的关系，所以 A 错。若 E 中两个顶点不在 V 中，则 V 和F无法构成图，所以 B 错。D 没强调对图的各顶点遍历一次且仅一次。16 【正确答案】 A17 【正确答案】 B18 【正确答案】 B19 【正确答案】 A20 【正确答案】 B【试题解析】 强连通图是指在有向图中，对于每一对不同的顶点 Vi，V j，V iVj，都存在从 Vi 到 Vj 及 vj到 vi 的路径。n 个顶点用弧向同一方向连接形成
15、一个环时，就是强连通图，需要弧最少。二、判断题21 【正确答案】 A22 【正确答案】 B23 【正确答案】 A24 【正确答案】 A25 【正确答案】 B【试题解析】 连通分量和连通图是无向图所具有的，凡带“强”字的都是有向图，例如，强连通分量、强连通图。26 【正确答案】 A【试题解析】 当有向图没有弧(边)时，n 个顶点的有向图有最多的 n 个强连通分量。27 【正确答案】 A28 【正确答案】 B【试题解析】 有向图中顶点 V 的度等于 V 的出度和入度之和，出度是其邻接矩阵中第 V 行中的 1 的个数，而入度是其邻接矩阵中第 V 列中的 1 的个数。29 【正确答案】 A30 【正确答案】 B
