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

计算机专业基础综合数据结构（图）历年真题试卷汇编(分：60.00做题时间：分钟)一、单项择(总题数：6，数12.00)1.有n个点、e条边的图G采用邻接存储，则拓扑排序算法的时间复杂度为)。【南京理工大2005一、2(1)A.O(n)B.O(n+e)

√C.O(nD.O(n

e))2.在下列网中()边不带权值的图。【华南理工大学2007】A.电图B.AOVC.路网D.AOE

√3.关键路径是AOE网()【中南大学一10(1分)A.始点到终点的最短路径B.始点到终点的最长路径√C.始点到终点的边数最多的路径D.始点到终点的边数最少的路径4.下面关于求关键径的说法不正确的是)。【南京理工学1998一12(2分)】A.关键路径是以拓扑排序为基础的B.个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同C.个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差√D.键活动一定位于关键路径上C的叙述有误。一个事件的最迟开始时间，是该事件所有后继事件点)迟开始时间和相应活动持续时间差的最小值。例如，某事(为E)有3后继事件顶点)它3后继事件有3条弧(活动)，求3个后继事件和弧头指向它的那个活动的持续时间的差，取最小值就得到最迟开始时间。5.下列关AOE网的叙述中，不正确的是)。北方交通大学1999一7(3)【北京工业大学1999一、1(2)【哈尔滨工业大学2004二3(1分)A.键活动不按期完成就会影响整个工程的完成时间B.何一个关键活动提前完成，那么整个工程将会提前完成√C.有的关键活动提前完成，那么整个工程将会提前完成D.些关键活动若提前完成，那么整个工程将会提前完成B之所以错误，是因为只有减少所有关键路径上共有的关键活动，才能缩短工期。若某活动不为关键路径共享，减少它，并没影响其他关键路径。6.下列有关图的说错误的是()【中南大学2003二、19(1分A.有向图中，出度为的点称为叶子B.邻接矩阵表示图，容易判断任意两个结点之间是否有边相连，并求得各结点的度C.深度方向遍历图和先根次序遍历树类似，得到的结果是唯一的√D.有向图G中从结点Vi到结点Vj有一条路径，则在图G结点的线性序列中结点V必在结点V之前的话，则称为一个拓扑序列图的深度优先遍历的确和树的先根遍历类似。但若只给逻辑图形，没有存储结构，则图的深度优先遍历结果会不唯一。即使给了存储结构，例如只说用邻接表存储，但没说邻接点如何排列，是升序还是降序，还是随意，无法确定谁是第一邻接点，都会造成结果不唯一。二、填空(总题数：10，分数：20.00)

7.若一个具有n个顶点、条边的无向图是一个森林，则该森林中必有_________棵。【哈尔滨工业大学2005一、分)】__________________________________________________________________________________________正确答案：(确答案：n一e)8.设无向G有n顶点和e条每个顶点的度为di(1in>则e=__________福州大学1998二、2(2)__________________________________________________________________________________________正确答案：(确答案：)9.在有n个顶点的有图中，每个顶点的度最大可达__________。中南大学2002一、1(1分)__________________________________________________________________________________________正确答案：(确答案：2(n一1))10.具10个顶点的无向图，边的总数最多为_________。华中理工大学一7(1分)】__________________________________________________________________________________________正确答案：(确答案：45)11.在据结构中线性结构树形结构和图形结构数据元素之间分别存在___________________和联系。【南京理工大学2004】__________________________________________________________________________________________正确答案：(确答案：一对一、一对多、多对多12.G是个非连通无向图，共28条边，则该图至少__________个顶点。西安电子科技大学2001软件一、8(2)__________________________________________________________________________________________正确答案：(确答案：9计算方法：至少需要构成无向完全图8顶点和一个孤立顶点。13.n个点的连通图至少有__________条。【中南大学二、4(2分__________________________________________________________________________________________正确答案：(确答案：n一1)14.有图G的强连通分量是指_________。【北京科技大1997一、7】__________________________________________________________________________________________正确答案：(确答案：有向图的极大强连通子图15.在n顶点的有向图中，若要使任意两点间可以互相到达，则至少需__________弧【合肥工业大学2000三、分)】__________________________________________________________________________________________正确答案：(确答案：n。n条形成一个环。)16.n个点的无向连通图的连通分量个数为__________个。【电子科技大2005二1(1分)__________________________________________________________________________________________正确答案：(确答案：1)三、判断(总题数：14，分数：28.00)17.图G一棵最小代价生成树的代价未必小于G其他任何一棵生成树的代价南大2005三、4(2)A.确B.误

√18.对任意一个图，从它的某个顶点进行一次先深或先广搜索可以访问到该图的每个顶点。()【哈尔滨工业大学2002三、分)A.确B.误

√19.需借助于一个队列来实现法。()南京航空航天大学六8(1分A.确B.误

√20.采邻接表存储的图广度优先遍历类似于二叉树的先序遍历北京交通大学2005三)

A.确B.误

√21.若v0开始对有向图g进深度遍历序列唯一，则可唯一确定该图。)【北京邮电大学2006二6(1分)A.确B.误

√对一个逻辑图进行深度／广度优先遍历，其遍历序列一般是不唯一的，因为没确定存储结构。即使给出存储结构，若没说明邻接点的排列规则，遍历序列也不唯一。因为第一邻接点的确定以及下一邻接点的确定并没说明。本题的错误在于没说明进入dfs次数。例如，若vx没路径vx可能是孤立顶点，也可能有弧指向遍历序列上某顶点，从开的深度遍历序列都是相同的，但不能唯一确定该图。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=12，，，n)。()合肥工业大学二6(1分)】A.确B.误√

[I,J]一定path

[I,J]27.如有向图的拓扑排序序列是唯一的，则图中必定只有一个顶点的入度0一个顶点的出度为0()【北方交通大学2003三4(2分)】A.确B.误

√28.具n个顶点条的无向图邻接矩阵作为存储结构任意顶点的度数的时间复杂