1、计算机专业基础综合数据结构（图）历年真题试卷汇编 5 及答案与解析一、单项选择题1 有 n 个顶点、e 条边的图 G 采用邻接表存储，则拓扑排序算法的时间复杂度为( )。【南京理工大学 2005 一、2(1 分)】（A）O(n)（B） O(n+e)（C） O(n*e)（D）O(n 2)2 在下列网中，( ) 是边不带权值的图。【华南理工大学 2007】（A）邮电图（B） AOV 网（C）公路网（D）AOE 网3 关键路径是 AOE 网中( )。【中南大学 2003 一、10(1 分)】（A）从始点到终点的最短路径（B）从始点到终点的最长路径（C）从始点到终点的边数最多的路径（D）从始点到终点的
2、边数最少的路径4 下面关于求关键路径的说法不正确的是( )。【南京理工大学 1998 一、12(2 分)】（A）求关键路径是以拓扑排序为基础的（B）一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同（C）一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差（D）关键活动一定位于关键路径上5 下列关于 AOE 网的叙述中，不正确的是( )。【北方交通大学 1999 一、7(3 分)】【北京工业大学 1999 一、1(2 分)】【哈尔滨工业大学 2004 二、3(1 分)】（A）关键活动不按期完成就会影响整个工程的完成时间（B）任何一个关键活动提前完成，那么
3、整个工程将会提前完成（C）所有的关键活动提前完成，那么整个工程将会提前完成（D）某些关键活动若提前完成，那么整个工程将会提前完成6 下列有关图的说法错误的是( )。【中南大学 2003 二、19(1 分)】（A）在有向图中，出度为 0 的结点称为叶子（B）用邻接矩阵表示图，容易判断任意两个结点之间是否有边相连，并求得各结点的度（C）按深度方向遍历图和先根次序遍历树类似，得到的结果是唯一的（D）若有向图 G 中从结点 Vi 到结点 Vj 有一条路径，则在图 G 的结点的线性序列中结点 Vi 必在结点 Vj 之前的话，则称为一个拓扑序列二、填空题7 若一个具有 n 个顶点、e 条边的无向图是一个森
4、林，则该森林中必有_棵树。【哈尔滨工业大学 2005 一、7(1 分)】8 设无向图 G 有 n 个顶点和 e 条边，每个顶点 Vi 的度为 di(1in，则e=_。【福州大学 1998 二、2(2 分)】9 在有 n 个顶点的有向图中，每个顶点的度最大可达_。【中南大学2002 一、1(1 分) 】10 具有 10 个顶点的无向图，边的总数最多为_。【华中理工大学 2000一、7(1 分) 】11 在数据结构中，线性结构、树形结构和图形结构数据元素之间分别存在_、_和的联系。【南京理工大学 2004】12 G 是一个非连通无向图，共有 28 条边，则该图至少有 _个顶点。【西安电子科技大学
5、2001 软件一、8(2 分)】13 n 个顶点的连通图至少有_条边。【中南大学 2005 二、4(2 分)】14 有向图 G 的强连通分量是指_。【北京科技大学 1997 一、7】15 在有 n 个顶点的有向图中，若要使任意两点间可以互相到达，则至少需要_条弧。【合肥工业大学 2000 三、8(2 分)】16 n 个顶点的无向连通图的连通分量个数为_个。【电子科技大学 2005二、1(1 分) 】三、判断题17 图 G 的一棵最小代价生成树的代价未必小于图 G 的其他任何一棵生成树的代价。( )【中南大学 2005 三、4(2 分) 】（A）正确（B）错误18 对于任意一个图，从它的某个顶点
6、进行一次先深或先广搜索可以访问到该图的每个顶点。 ( ) 【哈尔滨工业大学 2002 三、1(1 分)】（A）正确（B）错误19 需要借助于一个队列来实现 DFS 算法。( )【 南京航空航天大学 1996 六、8(1分)】（A）正确（B）错误20 采用邻接表存储的图，其广度优先遍历类似于二叉树的先序遍历。( )【北京交通大学 2005 三、5(2 分)】（A）正确（B）错误21 若从 v0 开始对有向图 g 进行深度遍历序列唯一，则可唯一确定该图。( )【北京邮电大学 2006 二、6(1 分)】（A）正确（B）错误22 对一个无向图进行先深搜索时，得到的先深序列是唯一的。( )【哈尔滨工业
7、大学 2005 三、8(1 分) 】（A）正确（B）错误23 若有向图不存在回路，即使不用访问标志位同一结点也不会被访问两次。( )【北京邮电大学 2005 二、7(1 分)】（A）正确（B）错误24 采用深度优先搜索或拓扑排序算法可以判断出一个有向图中是否有环(回路)。( )【中南大学 2003 一、9(1 分)】（A）正确（B）错误25 一个图的广度优先遍历生成树是唯一的。( )【中国海洋大学 2006 二、11(1 分)】（A）正确（B）错误26 在用 Floyd 算法求解各顶点间的最短路径时，每个表示两点间路径的 path(k-1)I,J一定是 path(k)I,J的子集(K=1 ，2
8、，3，n)。 ( )【合肥工业大学 2000 二、6(1分)】（A）正确（B）错误27 如果有向图的拓扑排序序列是唯一的，则图中必定只有一个顶点的入度为 0，一个顶点的出度为 0。( )【北方交通大学 2003 三、4(2 分)】（A）正确（B）错误28 具有 n 个顶点、e 条边的无向图，若用邻接矩阵作为存储结构，则求任意顶点的度数的时间复杂度为 O(e)。( )【哈尔滨工程大学 2004】（A）正确（B）错误29 广度优先搜索遍历图的时间复杂度和深度优先搜索遍历相同。( )【同济大学2004】（A）正确（B）错误30 有环路的有向图不能进行拓扑分类。( )【哈尔滨工业大学 2005 三、1
9、(1 分)】（A）正确（B）错误计算机专业基础综合数据结构（图）历年真题试卷汇编 5 答案与解析一、单项选择题1 【正确答案】 B2 【正确答案】 B3 【正确答案】 B4 【正确答案】 C【试题解析】 C 的叙述有误。一个事件的最迟开始时间，是该事件所有后继事件(顶点)最迟开始时间和相应活动持续时间差的最小值。例如，某事件(设为 E)有 3个后继事件(顶点) ，它到 3 个后继事件有 3 条弧(活动)，求出 3 个后继事件和弧头指向它的那个活动的持续时间的差，取最小值就得到 E 的最迟开始时间。5 【正确答案】 B【试题解析】 B 之所以错误，是因为只有减少所有关键路径上共有的关键活动，才能
10、缩短工期。若某活动不为关键路径共享，减少它，并没影响其他关键路径。6 【正确答案】 C【试题解析】 图的深度优先遍历的确和树的先根遍历类似。但若只给逻辑图形，没有存储结构，则图的深度优先遍历结果会不唯一。即使给了存储结构，例如只说用邻接表存储，但没说邻接点如何排列，是升序还是降序，还是随意，无法确定谁是第一邻接点，都会造成结果不唯一。二、填空题7 【正确答案】 n 一 e8 【正确答案】 9 【正确答案】 2(n 一 1)10 【正确答案】 4511 【正确答案】 一对一、一对多、多对多12 【正确答案】 9。计算方法：至少需要构成无向完全图的 8 个顶点和一个孤立顶点。13 【正确答案】 n
11、 一 114 【正确答案】 有向图的极大强连通子图15 【正确答案】 n。n 条弧形成一个环。16 【正确答案】 1三、判断题17 【正确答案】 B18 【正确答案】 B19 【正确答案】 B20 【正确答案】 B21 【正确答案】 B【试题解析】 对一个逻辑图进行深度广度优先遍历，其遍历序列一般是不唯一的，因为没确定存储结构。即使给出存储结构，若没说明邻接点的排列规则，遍历序列也不唯一。因为第一邻接点的确定以及下一邻接点的确定并没说明。本题的错误在于没说明进入 dfs 的次数。例如，若 vx 和 v0 没路径，vx 可能是孤立顶点，也可能有弧指向遍历序列上某顶点，从 v0 开始的深度遍历序列都是相同的，但不能唯一确定该图。22 【正确答案】 B23 【正确答案】 B24 【正确答案】 A25 【正确答案】 B26 【正确答案】 B27 【正确答案】 A28 【正确答案】 B【试题解析】 O(n)29 【正确答案】 A【试题解析】 两种遍历方法只是访问顶点的时机不同。以邻接矩阵存储遍历的时间复杂度都是 O(n2)，以邻接表存储遍历的时间复杂度都是 O(n+e)。30 【正确答案】 A
