计算机专业基础综合数据结构(图)历年真题试卷汇编6

计算机专业基础综合数据结构（图）历年真题试卷汇编6(总分：60.00，做题时间：90分钟)一、单项选择题(总题数：6，分数：12.00)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.从始点到终点的边数最少的路径4.下面关于求关键路径的说法不正确的是( )。

【南京理工大学1998一、12(2分)】A.求关键路径是以拓扑排序为基础的B.一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同C.一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差√D.关键活动一定位于关键路径上C的叙述有误。

一个事件的最迟开始时间，是该事件所有后继事件(顶点)最迟开始时间和相应活动持续时间差的最小值。

例如，某事件(设为E)有3个后继事件(顶点)，它到3个后继事件有3条弧(活动)，求出3个后继事件和弧头指向它的那个活动的持续时间的差，取最小值就得到E的最迟开始时间。

5.下列关于AOE网的叙述中，不正确的是( )。

【北方交通大学1999一、7(3分)】【北京工业大学1999一、1(2分)】【哈尔滨工业大学2004二、3(1分)】A.关键活动不按期完成就会影响整个工程的完成时间B.任何一个关键活动提前完成，那么整个工程将会提前完成√C.所有的关键活动提前完成，那么整个工程将会提前完成D.某些关键活动若提前完成，那么整个工程将会提前完成B之所以错误，是因为只有减少所有关键路径上共有的关键活动，才能缩短工期。

若某活动不为关键路径共享，减少它，并没影响其他关键路径。

6.下列有关图的说法错误的是( )。

【中南大学2003二、19(1分)】A.在有向图中，出度为0的结点称为叶子B.用邻接矩阵表示图，容易判断任意两个结点之间是否有边相连，并求得各结点的度C.按深度方向遍历图和先根次序遍历树类似，得到的结果是唯一的√D.若有向图G中从结点Vi到结点Vj有一条路径，则在图G的结点的线性序列中结点V i必在结点V j之前的话，则称为一个拓扑序列图的深度优先遍历的确和树的先根遍历类似。

但若只给逻辑图形，没有存储结构，则图的深度优先遍历结果会不唯一。

即使给了存储结构，例如只说用邻接表存储，但没说邻接点如何排列，是升序还是降序，还是随意，无法确定谁是第一邻接点，都会造成结果不唯一。

二、填空题(总题数：10，分数：20.00)7.若一个具有n个顶点、e条边的无向图是一个森林，则该森林中必有__________棵树。

【哈尔滨工业大学2005一、7(1分)】__________________________________________________________________________________________ 正确答案：(正确答案：n一e)8.设无向图G有n个顶点和e条边，每个顶点Vi的度为di(1≤i≤n>，则e=__________。

【福州大学1998二、2(2分)】__________________________________________________________________________________________正确答案：(9.在有n个顶点的有向图中，每个顶点的度最大可达__________。

【中南大学2002一、1(1分)】__________________________________________________________________________________________ 正确答案：(正确答案：2(n一1))10.具有10个顶点的无向图，边的总数最多为__________。

【华中理工大学2000一、7(1分)】__________________________________________________________________________________________ 正确答案：(正确答案：45)11.在数据结构中，线性结构、树形结构和图形结构数据元素之间分别存在__________、__________和的联系。

【南京理工大学2004】__________________________________________________________________________________________ 正确答案：(正确答案：一对一、一对多、多对多)12.G是一个非连通无向图，共有28条边，则该图至少有__________个顶点。

【西安电子科技大学2001软件一、8(2分)】__________________________________________________________________________________________ 正确答案：(正确答案：9。

计算方法：至少需要构成无向完全图的8个顶点和一个孤立顶点。

)13.n个顶点的连通图至少有__________条边。

【中南大学2005二、4(2分)】__________________________________________________________________________________________ 正确答案：(正确答案：n一1)14.有向图G的强连通分量是指__________。

【北京科技大学1997一、7】__________________________________________________________________________________________ 正确答案：(正确答案：有向图的极大强连通子图)15.在有n个顶点的有向图中，若要使任意两点间可以互相到达，则至少需要__________条弧。

【合肥工业大学2000三、8(2分)】__________________________________________________________________________________________ 正确答案：(正确答案：n。

n条弧形成一个环。

)16.n个顶点的无向连通图的连通分量个数为__________个。

【电子科技大学2005二、1(1分)】__________________________________________________________________________________________ 正确答案：(正确答案：1)三、判断题(总题数：14，分数：28.00)17.图G的一棵最小代价生成树的代价未必小于图G的其他任何一棵生成树的代价。

( )【中南大学2005三、4(2分)】A.正确B.错误√18.对于任意一个图，从它的某个顶点进行一次先深或先广搜索可以访问到该图的每个顶点。

( )【哈尔滨工业大学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.错误√对一个逻辑图进行深度／广度优先遍历，其遍历序列一般是不唯一的，因为没确定存储结构。

即使给出存储结构，若没说明邻接点的排列规则，遍历序列也不唯一。

因为第一邻接点的确定以及下一邻接点的确定并没说明。

本题的错误在于没说明进入dfs的次数。

例如，若vx和v0没路径，vx可能是孤立顶点，也可能有弧指向遍历序列上某顶点，从v0开始的深度遍历序列都是相同的，但不能唯一确定该图。

22.对一个无向图进行先深搜索时，得到的先深序列是唯一的。

( )【哈尔滨工业大学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，3，…，n)。

( )【合肥工业大学2000二、6(1分)】A.正确B.错误√27.如果有向图的拓扑排序序列是唯一的，则图中必定只有一个顶点的入度为0，一个顶点的出度为0。

( )【北方交通大学2003三、4(2分)】A.正确√B.错误28.具有n个顶点、e条边的无向图，若用邻接矩阵作为存储结构，则求任意顶点的度数的时间复杂度为O(e)。

( )【哈尔滨工程大学2004】A.正确B.错误√O(n)29.广度优先搜索遍历图的时间复杂度和深度优先搜索遍历相同。

( )【同济大学2004】A.正确√B.错误两种遍历方法只是访问顶点的时机不同。

以邻接矩阵存储遍历的时间复杂度都是O(n 2)，以邻接表存储遍历的时间复杂度都是O(n+e)。

30.有环路的有向图不能进行拓扑分类。

( )【哈尔滨工业大学2005三、1(1分)】A.正确√B.错误。