1、计算机专业基础综合数据结构（图）历年真题试卷汇编 10 及答案与解析一、综合题1 已知一图如下图所示：(1)写出全部拓扑排序；(2)以 V1 为源点，以 V8 为终点，给出所有事件允许发生的最早时间和最晚时间，并给出关键路径；(3)求 V1 结点到各点的最短距离。【北京邮电大学 2000 五(15 分)】2 (1)对于有向无环图，叙述求拓扑有序序列的步骤；(2)对于以下的图，写出它的四个不同的拓扑有序序列。【南开大学 1998 二(12 分)】3 有向图的拓扑排序能否用图的深度搜索模式来查找?若能，请简述方法；若不能，请简述原因。【西北大学 2000 二、8(5 分)】4 下图是带权的有向图
2、G 的邻接表表示法，求：(1)以结点 V1 出发深度遍历图 G所得的结点序列；(2)以结点 V1 出发广度遍历图 G 所得的结点序列；(3)从结点 V1到结点 V8 的最短路径；(4)从结点 V1 到结点 V8 的关键路径。【中国海洋大学 1999 四(10 分) 】5 下表给出了某工程各工序之间的优先关系和各工序所需时间。(1)画出相应的AOE 网； (2)列出各事件的最早发生时间，最迟发生时间；(3)找出关键路径并指明完成该工程所需最短时间。【山东大学 2002 七(15 分)】【北京交通大学 1995 六(15 分)】6 请写出应填入下列叙述中( )内的正确答案。某一工程作业的网络图如图
3、所示，其中箭头表示作业，箭头边的数字表示完成作业所需的天数。箭头前后的圆圈表示事件，圆圈中的数字表示事件的编号。用事件编号的序列(例如 0 一 279 一 11)表示进行作业的路径。完成此工程的关键路径是(A)，完成此工程所需的最少天数为(B)天，此工程中具有最大充裕天数的事件是(C)，充裕天数是(D)。关键路径上的事件的充裕天数是(E)。 【上海大学 2002 三(10 分)】7 求出下面 AOE 网中的关键路径(要求给出各个顶点的最早发生时间和最迟发生时间，并画出关键路径)。【北京交通大学 2005 五、2(5 分)】二、设计题8 (单独命题考生做) 设无向图 G 有 n 个顶点，m 条边
4、。试编写用邻接表存储该图的算法。(设顶点值用 1n 或 0n 一 1 编号)【南京航空航天大学 1996 十二(10 分)】9 请用流程图或类高级语言表示算法。已知有向图有 n 个顶点，请写算法，根据用户输入的偶对建立该有向图的邻接表。即接受用户输入的( 以其中之一为0 标志结束)，对于每条这样的边，申请一个结点，并插入单链表中，如此反复，直到将图中所有边处理完毕。提示：先产生邻接表的 n 个头结点(其结点数值域从1 到 n)。【上海大学 2000 四(16 分)】10 设无向图 G 有 n 个顶点 e 条边，写一算法建立 G 的邻接多重表，要求该算法时间复杂性为 O(n+e)，且除邻接多重表
5、本身所占空间之外只用 O(1)辅助空间。【东南大学 1995 六(16 分)1997 二(15 分) 】11 给出以十字链表作存储结构，建立图的算法，输入(i，j，v)，其中 i、j 为顶点号，v 为权值。【河海大学 1998 六(10 分)】12 设有向图 G 有 n 个点(用 1，2，n 表示)， e 条边，写一算法根据 G 的邻接表生成 G 的反向邻接表，要求算法时间复杂性为 O(n+e)。【东南大学 1996 三(13分)1992 六(18 分)】【北京邮电大学 2006 五、3(10 分)】13 写出从图的邻接表表示转换成邻接矩阵表示的算法，用类 Pascal 语言(或 C 语言)写
6、成过程形式。【南开大学 1998 四(16 分)】【天津大学 1999 五】【华南理工大学 2006 三、2(6 分) 】14 试写出把图的邻接矩阵表示转换为邻接表表示的算法。【哈尔滨工业大学 2002七(8 分 )】【 中山大学 1998 五、2(10 分) 】【南开大学 2000 三、3】【北京邮电大学 2006 五、3(10 分) 】15 已知某有向图(n 个结点)的邻接表，求该图各结点的入度数。【天津大学 2001五(10 分 )2006 二、1(7 分) 】【南京理工大学 1997 四、2(10 分)】16 设计一个算法，统计一个采用邻接矩阵存储，具有 n 个顶点的无向无权图所有顶点
7、的度。【天津大学 2005 六(10 分)】17 已知某有向图用邻接表表示。该邻接表的结点表及边表说明如下(编者略)。设该有向图中必须删除数据场之值为 key 的结点，请设计一个程序加以实现。【上海交通大学 2003 四(20 分) 】17 假定无向图以邻接矩阵的形式存储。邻接矩阵定义如下(编者略)。试用 C 语言编写算法函数并分析时间复杂度。18 int DeleteNode(struct MGraphG， ElemType e)；从图 G 中删除顶点值为 e 的顶点，成功返回 1，否则返回 0。19 int DeleteEdge(struct MGraphG， ElemType a， El
8、emType b ) ；从图 G 中删除(a ，b)，成功返回 1，否则返回 0。【华中科技大学 2007 六、31(282 分)】20 已知无向图 G=(V,E)，给出求图 G 的连通分量个数的算法。【哈尔滨工业大学2002 九(9 分)】【南京航空航天大学 1995 十一(10 分)】21 设有向图 G 的十字链表已建立，用 C 语言函数形式写出求图中各顶点度的算法：COUNT_D(Gn，Dn)，Gn为顶点表，Dn 为存放各顶点度的数组，n 为图中顶点的个数。【北京科技大学 2005 四、2(10 分)】22 已知无向图采用邻接表存储方式，试写出删除边(i，j) 的算法。【东南大学 199
9、9三(10 分 )】【 北京邮电大学 2006 三(7 分) 】23 试写一算法；判断以邻接表方式存储的有向图中是否存在由顶点 Vi 到顶点 Vj 的路径(ij) 。注意：算法中涉及的图的基本操作必须在存储结构上实现。【哈尔滨工业大学 2001 九(12 分)】24 按图的广度优先搜索法写一算法判别以邻接矩阵存储的有向图中是否存在由顶点 Vi 到顶点 Vj 的路径(ij)。【中山大学 1997 五(10 分)】25 假设以邻接矩阵作为图的存储结构，编写算法判别在给定的有向图中是否存在一个简单有向回路，若存在，则以顶点序列的方式输出该回路(找到一条即可)。(注：图中不存在顶点到自己的弧)【清华大
10、学 1994 六(15 分)】【吉林大学 1997 五(16 分)】26 假设一个有向图 G 已经以十字链表形式存储在内存中，试写一个判断该有向图中是否有环路(回路) 的算法。【中科院研究生院 2005 五(15 分)】【东南大学 2005数据结构部分五(15 分) 】27 在有向图 G 中，如果 r 到 G 中的每个结点都有路径可达，则称结点 r 为 G 的根结点。编写一个算法完成下列功能：(1)建立有向图 G 的邻接表存储结构；(2)判断有向图 G 是否有根，若有，则打印出所有根结点的值。【东北大学 2001 五(15 分)】【中国海洋大学 2006 九(15 分) 】28 设无向图 G
11、已用邻接表结构存储，顶点表为 GLn(n 为图中顶点数)，试用“广度优先搜索” 方法，写出求图 G 中各连通分量的 C 语言描述算法：BFSCOM(GL)。(注：算法中可调用队列操作的基本算法。)【北京科技大学 2001 七、2(10 分)】29 设计一非递归算法采用深度优先搜索对无向图进行遍历，并对算法中的无向图的存储结构予以简单说明。【大连理工大学 2003 二、1(453 分)】【北京邮电大学 1994 十(15 分) 】计算机专业基础综合数据结构（图）历年真题试卷汇编 10 答案与解析一、综合题1 【正确答案】 (1) (2)关键路径有 3条，长 17。各事件允许发生的最早时间和最晚时
12、间略。V1V2V6V8，V1V3V5V7V8，V1V7V8V1V4V5V8(3)V1 结点到其他各结点的最短距离为：2，3，6，12 ，10，15，16。2 【正确答案】 (1)对有向图，求拓扑序列步骤为：1)在有向图中选一个没有前驱(即入度为零)的顶点并输出。2)在图中删除该顶点及所有以它为尾的弧。3)重复 1)和 2)，直至全部顶点输出，这时拓扑排序完成；否则，图中存在环，拓扑排序失败。(2)这里使用形式化描述方法，当有多个顶点可以输出时，将其按序从上往下排列，这样不会丢掉拓扑序列。这里只画出从顶点 1 开始的所有可能的拓扑序列，从顶点 3 开始的拓扑序列可类似画出。3 【正确答案】 图的
13、深度优先遍历可用于拓扑排序。带环的有向图不能拓扑排序。深度优先遍历如何发现环呢?若从有向图某顶点 V 出发进行遍历，在 dfs(v)结束之前出现从顶点 W 到顶点 V 的回边，由于 W 在生成树上是 V 的子孙，则有向图中必定存在包含顶点 V 和 W 的环。其算法实现见下面五、45 题。4 【正确答案】 (1)V1 ，V2，V3，V8，V5，V7，V4，V6(2)V1，V2，V4，V6，V3，V5，V7，V8(3)V1 到 V8 最短路径 56，路径为 V1 一 V2一 V5 一 V7 一 V8 (4)V1 到 V8 的关键路径是V1 一 V6 一 V5 一 V3 一 V8，长 97。5 【正
14、确答案】 (1)AOE 网如下图所示：图中虚线表示在时间上前后工序之间仅是接续顺序关系不存在依赖关系。顶点代表事件，弧代表活动，弧上的权代表活动持续时间。题中顶点 1 代表工程开始事件，顶点 11 代表工程结束事件。(2)各事件发生的最早和最晚时间如下表。(3)关键路径为顶点序列：1246891011；事件序列：ACEGHLM，完成工程所需的最短时间为 445。6 【正确答案】 A.02 一 69 一 11B.20C.事件顶点 1、5 和 7 各充裕两天 D.顶点7 和顶点 10 间的活动充裕 4 天 E07 【正确答案】 上面已有这类问题的解答。回答这类问题，只要认真细致，就能得到正确答案，
15、否则，一步疏忽，将导致结论错误。二、设计题8 【正确答案】 邻接表存储结构是顶点向量和顶点的邻接点链表相结合的存储结构。核心语句段如下：cinnm； n 个顶点和 m 条边for(i=0，igivertex) ；gifirstarc=null；for(k=0；k(m;k+ 输入边信息cinv1v2； 输入两个顶点i=GraphLocateVertex (g，V1)； j=GraphLocateVertex (g，v2)；顶点定位p=new(ArcNode； 申请边结点p-adjvex=j；P 一next=gifirstarc；gifirstarc=p； 将边结点链入p=new(ArcNode)
16、(ArcNode)； 申请边结点，链入 j 到 i 的一条边P 一adjvex=i；P 一next=gjfirstarc ； gjfrstarc=p ； for9 【正确答案】 与第 1 题类似i，j户表示 i 到 j 的一条弧。10 【正确答案】 邻接多重表的边结点结构是(ivex，jvex，ilink ，jlink，mark) 。输入一条边的核心语句段如下：cinvlv2 ；i=GraphLocateVertex(g，V1)；j=GraphLocateVertex(g ，v2)；p=new(ENode)；申请边结点P 一ivex=i；p-jvex=j；P 一ilink=gifirstedg
17、e；p 一j link=gjfirstedge；gifirstedge=p ；gj firstedge=p；11 【正确答案】 十字链表的边结点结构为(headvex，tailvex，weight，headlink ，tailink)，输入一条弧的核心语句段如下：cinijv； p=new(OrArcNode)； 申请结点P 一headvex=j；p-tailvex=i；P 一weight=v ； 弧结点中权值域P 一headlink=gjfirstin； gj firstin=p ；P 一tailink=gifirstout； gifirstout=p ；12 【正确答案】 从顶点 i 到邻
18、接点的弧，改造成从邻接点到 i 的弧，核心语句段如下：for(i=0 ； iadjvex；s=new(ArcNode)； 申请结点空间s 一adjvex=i；s 一next=ginjfirstarc ； ginjfirstarc=s ；p=P 一next； 下一个邻接点 while for13 【正确答案】 for(i=0 ； iadjvex：1 jp=p 一next；14 【正确答案】 核心语句段如下：for(i=0；iadjvex=j ； 顶点 i 的邻接点是 jP 一next=glifirstarc; 链入顶点 i 的邻接点链表中glifirstarc=p； if15 【正确答案】 在邻
19、接表中求顶点入度，需要遍历整个邻接表。求顶点 f 的入度的语句段如下：for(j=0；j n； j+) 遍历整个邻接表，求顶点 i 的入度if(i!=j)p=gjfirstarc；while(p)(if(p 一adjvex=i)num+；P=p 一next；num 初值为 016 【正确答案】 设邻接矩阵元素不 1 是边的用 0 表示，所有顶点的度就是邻接矩阵中非零元素的个数。17 【正确答案】 在有向图的邻接表中删除一个顶点，除在顶点向量中删除该顶点并顶点数减 1 外，要删除该顶点的所有出度边和入度边，并调整相关边结点中邻接点的值。核心语句段如下：for(i=0；inext；delete(u
20、)； 删除被删顶点的所有出度边for(j=0； jn；j+) 查被删顶点的所有入度边if(j!=i)p=q=gjfirstarc ； 设置前驱 qif(p 一adjvex=i) 第一个邻接点是被删顶点(u=p； gjfirstarc=p 一next ； p=p-next ； free(u)；else 第一个邻接点不是被删顶点，查找被删结点的入度边while(p)(if(p 一adjvex=i)u=p；q-next=p 一next；delete(u)；break； 删除被删顶点的入度边if(p 一adjvexi)P 一adjvex 一一； i 之后的顶点在向量中的下标前移q 一next=p；q=
21、p；p=p 一next； 邻接点链表指针后移继续查找while(p) if(j!=i)for(j=i+1 ； jtaillink； 计算出度，di初值是 0p=gifirstin；while(p)di+；p=p 一headlink； 计算入度22 【正确答案】 在用邻接表方式存储的无向图 g 中，删除边(i,j)，要在顶点 i 的邻接点链表中删除邻接点为 j 的边结点，在顶点 j 的邻接点链表中删除邻接点为 i 的边结点。23 【正确答案】 从 Vi 深度优先遍历，若在未退出深度优先遍历时遍历到 Vi，说明Vi 到 Vj 存在路径。if(V i=Vj)return 1； v i 到顶点 vj
22、存在路径 else visitedV i=1； for(p=gvdfirstarc ；P ；p=p-next) k=p 一adjvex； if(!visitedk&Pathitoj(g，k，V j)return 1； for return 0； v i 到顶点 v1 不存在路径 24 【正确答案】 用广度优先遍历法判别以邻接矩阵存储的有向图中是否存在由顶点 Vi 到顶点 Vj 的路径，应该使用队列。从顶点 Vi 开始遍历，若遇到顶点 Vj，说明有路径。 int visitedn ； 设有向图有 n 个顶点 int PathiToj(Adj Matrix g，vertype V i，vertyp
23、e V j) 判断以邻接矩阵方式存储的有向图中是否存在由顶点 vi 到顶点 vj 的路径 for(i=0；i i)； 顶点定位 j=GraphLocateVertex(g，V j)； QueueInit(Q)； Q 是队列，容量足够大，队列元素是顶点编号(0n 一 1) visitedi=1； QueueIn(Q，i)； V i 入队 while(!QueueEmpty(Q) v=QueueOut(Q)；for(w=0 ； 1 i 到顶点 Vj 存在路径”； return(1)；) if(gvw=1& !visitedw) visitedw=1；QueueIn(Q，w)； for cout i
24、 到顶点 Vj 不存在路径”)； return(0)；25 【正确答案】 拓扑排序可以判断有向图是否有环。设向量 indegree，存放各顶点的入度值，并用值为 0 的入度域当栈，用 top(初值一 1)指向栈顶元素。若拓扑排序失败，则有向图有环。for(i=0；itailvex=i)k=p 一headvex ； 找顶点 i 的邻接点else k=p-taiivex；gkindegree 一一； 邻接点入度减 1if(gkindegree=0)gkindegree=top；top=k；入度为 0 的顶点再入栈if(p 一headvex=i)p=p 一headlink； 找顶点 i 的下一邻接点
25、else p=p-taillink； while(p)27 【正确答案】 使用深度优先遍历，设在主调函数中从顶点 1，开始进入 dfs(v)，对遍历顶点记数，若退出 dfs()前，已访问完有向图的全部顶点 (设为 n 个)，则有向图有根，v 为根结点。将 n 个顶点从 1 到 n 编号，各调用一次 dfs()过程，就可以求出全部的根结点。判断有向图是否有根的算法的核心语句段如下：Void dfS(v)fvisitedv=1； num+； 访问的顶点数 num+1，num 是全局变量，初值是0if(num=n)(coutadjvex=0)dfs(p 一adjvex)；p=p 一next； whi
26、levisitedv=0；num- ； 恢复顶点 v，使该顶点可重新使用 dfs28 【正确答案】 广度优先遍历，从主调函数进入 bfs 一次就可求出一个连通分量。29 【正确答案】 下面是深度优先遍历 dfso 的算法片段。若是非连通图，则主调函数循环调用 dfs0 若干次(次数等于连通分量的个数)。while(top0 P!=null) 初值：top=0；p=gv firstarc；stack+top=p；(while(p)if(pvisitedp 一adjvex)p=p 一next；elsecoutadjVex；visitedp-adjvex=1；stack+top=p；p=gp 一adjvexfirstarc； elseif(top0p=stacktop 一一 ；p=p 一next ； while
