1、计算机专业基础综合数据结构（图）历年真题试卷汇编 6 及答案与解析一、填空题1 在 n 个顶点的非空无向图中，最多有_个连通分量。【中南大学 2003三、10(1 分)】2 n 个顶点的连通无向图，其边的条数至少为_。【哈尔滨工业大学 2000二、2(1 分) 】3 如果具有 n 个顶点的图是一个环，则它有_棵生成树。【中南大学2005 二、9(2 分) 】4 N 个顶点的连通图的生成树含有_条边。 【中山大学 1998 一、9(1 分)】5 若无向图满足_，则该图是树。【中国科学技术大学 2004】6 有 n 个顶点的有向图，至少需要_条弧才能保证是连通的。【西安电子科技大学 2003 一、
2、8(2 分)】7 n 个顶点的无向图的邻接矩阵至少有_个非零元素；n 个顶点的有向图是强连通图至少有_条边。【中国科学技术大学 1998 一、1(2 分)】8 N 个顶点的连通图用邻接矩阵表示时，该矩阵至少有 _个非零元素。【中科院计算所 1998 一、6(1 分)】【中国科技大学 1998 一、6(156 分)】【北京航空航天大学 2006 一、7(1 分)】【中南大学 2003 三、9(1 分)】9 无向图 G 有 16 条边，有 3 个 4 度顶点，4 个 3 度顶点，其余顶点的度均小于3，则图 G 至少有_个顶点。【湖南大学 2006】10 已知一个图的邻接矩阵表示，删除所有从第 i
3、个结点出发的边的方法是_。【北京交通大学，2005 二、4(2 分)】11 一个有 n 个顶点、e 条边的连通图的生成树有 _条边。【南开大学2004】12 在一个无向图的的邻接表中，若表结点的个数是 m，则图中边的条数是_条。【西安电子科技大学 2003 一、3(2 分)】13 n 个顶点 e 条边的图采用邻接表存储，则空间复杂度是_。【东南大学 2005 数据结构部分二、8(1 分)】14 遍历图的过程实质上是(1)，breathfirst search 遍历图的时间复杂度(2)；depth-firstsearch 遍历图的时间复杂度(3) ，两者不同之处在于 (4)，反映在数据结构上的差
4、别是(5)。 【 厦门大学 1999 一、3(204) 】15 已知一无向图 G=(V,E)，其中 V=a，b，c，d,eE=(a，b)，(a，d)，(a ，c)，(d,c)，(b ，e) 现用某一种图遍历方法从顶点 a 开始遍历图，得到的序列为 abecd，则采用的是_遍历方法。【南京理工大学 1996 二、2(2 分)】16 已知带权连通图 G(V,E)如下：图的最小生成树(1)；去掉图中的权值，图 G 用邻接矩阵存储。给出从顶点 1 出发的深度优先搜索序列(2)和广度优先搜索序列(3)。【南京理工大学 2005 二、6(3 分)】17 一无向图 G(V，E) ，其中 V(G)=1，2，3
5、，4， 5，6，7)，E(G)=(1，2)，(1，3)，(2，4)，(2，5) ，(3，6)，(3，7)，(6 ，7)，(5，1)，对该图从顶点 3 开始进行遍历，去掉遍历中未走过的边，得一生成树 G， (V，E)，V(G)=坎 G)，E(G)=(1， 3)，(3，6)，(7，3)，(1 ，2)，(1，5)，(2，4)，则采用的遍历方法是_。【南京理工大学 1997 三、6(1 分)】18 为了实现图的广度优先搜索，除了一个标志数组标志已访问的图的结点外，还需_以存放被访问的结点以实现遍历。【南京理工大学 1999 二、9(2 分)】二、判断题19 若一个有向图无环，则它一定有唯一的拓扑序列。
6、( )【兰州大学 2000 一、8(1分)】（A）正确（B）错误20 不是所有的 AOV 网都有一个拓扑序列。( )【武汉理工大学 2002 二、8(1 分)】（A）正确（B）错误21 拓扑排序的有向图中，最多存在一条环路。( )【大连海事大学 2001 一、6(1分)】（A）正确（B）错误22 任何有向图的结点都可以排成拓扑排序，而且拓扑序列不唯一。( )【上海交通大学 1998 一、13(1 分)】【烟台大学 2007 二、13(1 分)】（A）正确（B）错误23 在拓扑序列中，任意两个相继结点 Vi 和 Vj 都存在从 Vi 到 Vj 的路径。( )【吉林大学 2007 一、3(1 分)
7、 】（A）正确（B）错误24 即使有向无环图的拓扑序列唯一，也不能唯一确定该图。( )【合肥工业大学2001 二、6(1 分) 】（A）正确（B）错误25 若一个有向图的邻接矩阵对角线以下元素均为零，则该图的拓扑有序序列必定存在。( ) 【 中科院软件所 1997 一、5(1 分) 】（A）正确（B）错误26 AOV 网的含义是以边表示活动的网。( )【南京航空航天大学 1995 五、7(1 分)】（A）正确（B）错误27 对一个 AOV 网，从源点到终点的路径最长的路径称作关键路径。( )【南京航空航天大学 1995 五、9(1 分)】（A）正确（B）错误28 关键路径是 AOE 网中从源点
8、到汇点的最短路径。( )【北京交通大学 2005 三、8(2 分)】（A）正确（B）错误三、综合题29 带权图(权值非负，表示边连接的两顶点间的距离)的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径，假设从初始顶点到目标顶点之间存在路径，现有一种解决该问题的方法：设最短路径初始时仅包含初始顶点，令当前顶点“为初始顶点； 选择离 u 最近且尚未在最短路径中的一个顶点 v，加入到最短路径中，修改当前顶点 u=v； 重复步骤，直到 u 是目标顶点时为止。请问上述方法能否求得最短路径? 若该方法可行，请证明之，否则，请举例说明。【2009 年全国试题 41(10 分) 】30 已知有 6 个
9、顶点(顶点编号为 05)的有向带权图 G，其邻接矩阵 A 为上三角矩阵，按行为主序(行优先) 保存在如下的一维数组中。要求： (1)写出图 G 的邻接矩阵 A。(2)画出有向带权图 G。(3) 求图 G 的关键路径，并计算该关键路径的长度。【2011 年全国试题 41(8 分)】计算机专业基础综合数据结构（图）历年真题试卷汇编 6 答案与解析一、填空题1 【正确答案】 n2 【正确答案】 n 一 13 【正确答案】 n(自由树，无根树)4 【正确答案】 N15 【正确答案】 n 个顶点 n 一 1 条边的无向连通图6 【正确答案】 n7 【正确答案】 0n8 【正确答案】 2(N1)9 【正确
10、答案】 11。无向图 16 条边，其度数为 16*2=32。设无向图顶点数是 n，根据已知条件，度为 4 和 3 的顶点度数是 3*4+4*3=24，其余顶点度最大为 2，个数是 n 一 34，度数为(n 一 34)*2，故顶点度数之和等于 24+(n 一 34)*2=2n+10，因为 2，z+10=32，所以，图至少有 11 个顶点。10 【正确答案】 将第 i 个非零元素都变为零元素。11 【正确答案】 n 一 1。n 个顶点的无向连通图的生成树有 n1 条边。至于无向连通图原有的边数 e 具体多大，只要 en 一 1 就可以。12 【正确答案】 m213 【正确答案】 O(n+e)14
11、【正确答案】 (1)查找顶点的邻接点的过程 (2)O(n+e) (3)O(n+e) (4)访问顶点的顺序不同 (5)队列和栈15 【正确答案】 深度优先16 【正确答案】 (1)(2)v1v2v3v4v5v6 (3)v1v2v5v6v3v417 【正确答案】 广度优先遍历18 【正确答案】 队列二、判断题19 【正确答案】 B20 【正确答案】 A21 【正确答案】 B22 【正确答案】 B23 【正确答案】 B24 【正确答案】 B25 【正确答案】 A26 【正确答案】 B【试题解析】 AOV 网是用顶点代表活动，弧表示活动间的优先关系的有向图，叫顶点表示活动的网。27 【正确答案】 B2
12、8 【正确答案】 B【试题解析】 本题及以下各判断题都涉及关键路径的概念。AOE 网中关键路径是从“源点”到“汇点”路径长度最长的路径。关键路径上的活动叫关键活动。只有减少关键活动的时间才可能缩短工期。但是还要注意：只有减少所有关键路径上共有的关键活动的时间才可能缩短工期；只有在不改变关键路径的前提下减少关键活动的时间才可能缩短工期；为求关键路径，有时要增加“虚活动”，“虚活动”仅表示前后活动间的逻辑关系和指明活动前进方向，其权值为 0。三、综合题29 【正确答案】 上述方法不能求得最短路径。离 u 最近未必离初始顶点最近。例如，下图求 v0 到 v1 的最短路径，按题目所给方法得 45(v0 一 v2 一 v3 一 v1)，并非最短路径。详细证明请参照 Dijkstra 或 Floyd 算法。30 【正确答案】 (1) (2)(3)关键路径：顶点序列是 01235，路径长度=4+5+4+3=16。
