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