1、计算机专业基础综合数据结构（图）历年真题试卷汇编 4及答案解析(总分：58.00，做题时间：90 分钟)一、综合题(总题数：7，分数：14.00)1.已知一图如下图所示：(1)写出全部拓扑排序；(2)以 V1为源点，以 V8为终点，给出所有事件允许发生的最早时间和最晚时间，并给出关键路径；(3)求 V1结点到各点的最短距离。【北京邮电大学 2000五(15分)】 （分数：2.00）_2.(1)对于有向无环图，叙述求拓扑有序序列的步骤；(2)对于以下的图，写出它的四个不同的拓扑有序序列。【南开大学 1998二(12 分)】 （分数：2.00）_3.有向图的拓扑排序能否用图的深度搜索模式来查找?若
2、能，请简述方法；若不能，请简述原因。【西北大学 2000二、8(5 分)】（分数：2.00）_4.下图是带权的有向图 G的邻接表表示法，求：(1)以结点 V1出发深度遍历图 G所得的结点序列；(2)以结点 V1出发广度遍历图 G所得的结点序列；(3)从结点 V1到结点 V8的最短路径；(4)从结点 V1到结点V8的关键路径。 （分数：2.00）_5.下表给出了某工程各工序之间的优先关系和各工序所需时间。(1)画出相应的 AOE网； (2)列出各事件的最早发生时间，最迟发生时间；(3)找出关键路径并指明完成该工程所需最短时间。 （分数：2.00）_6.请写出应填入下列叙述中( )内的正确答案。某
3、一工程作业的网络图如图所示，其中箭头表示作业，箭头边的数字表示完成作业所需的天数。箭头前后的圆圈表示事件，圆圈中的数字表示事件的编号。用事件编号的序列(例如 0一 279一 11)表示进行作业的路径。完成此工程的关键路径是(A)，完成此工程所需的最少天数为(B)天，此工程中具有最大充裕天数的事件是(C)，充裕天数是(D)。关键路径上的事件的充裕天数是(E)。 （分数：2.00）_7.求出下面 AOE网中的关键路径(要求给出各个顶点的最早发生时间和最迟发生时间，并画出关键路径)。【北京交通大学 2005五、2(5 分)】 （分数：2.00）_二、设计题(总题数：21，分数：44.00)8.(单独
4、命题考生做)设无向图 G有 n个顶点，m 条边。试编写用邻接表存储该图的算法。(设顶点值用1n 或 0n 一 1编号)【南京航空航天大学 1996十二(10 分)】（分数：2.00）_9.请用流程图或类高级语言表示算法。已知有向图有 n个顶点，请写算法，根据用户输入的偶对建立该有向图的邻接表。即接受用户输入的(以其中之一为 0标志结束)，对于每条这样的边，申请一个结点，并插入单链表中，如此反复，直到将图中所有边处理完毕。提示：先产生邻接表的 n个头结点(其结点数值域从 1到 n)。【上海大学 2000四(16 分)】（分数：2.00）_10.设无向图 G有 n个顶点 e条边，写一算法建立 G的
5、邻接多重表，要求该算法时间复杂性为 O(n+e)，且除邻接多重表本身所占空间之外只用 O(1)辅助空间。【东南大学 1995六(16 分)1997 二(15 分)】（分数：2.00）_11.给出以十字链表作存储结构，建立图的算法，输入(i，j，v)，其中 i、j 为顶点号，v 为权值。【河海大学 1998六(10 分)】（分数：2.00）_12.设有向图 G有 n个点(用 1，2，n 表示)，e 条边，写一算法根据 G的邻接表生成 G的反向邻接表，要求算法时间复杂性为 O(n+e)。【东南大学 1996三(13 分)1992 六(18 分)】【北京邮电大学 2006五、3(10分)】（分数：2
6、.00）_13.写出从图的邻接表表示转换成邻接矩阵表示的算法，用类 Pascal语言(或 C语言)写成过程形式。【南开大学 1998四(16 分)】【天津大学 1999五】【华南理工大学 2006三、2(6 分)】（分数：2.00）_14.试写出把图的邻接矩阵表示转换为邻接表表示的算法。【哈尔滨工业大学 2002七(8 分)】【中山大学1998五、2(10 分)】【南开大学 2000三、3】【北京邮电大学 2006五、3(10 分)】（分数：2.00）_15.已知某有向图(n 个结点)的邻接表，求该图各结点的入度数。【天津大学 2001五(10 分)2006 二、1(7分)】【南京理工大学 1
7、997四、2(10 分)】（分数：2.00）_16.设计一个算法，统计一个采用邻接矩阵存储，具有 n个顶点的无向无权图所有顶点的度。【天津大学2005六(10 分)】（分数：2.00）_17.已知某有向图用邻接表表示。该邻接表的结点表及边表说明如下(编者略)。设该有向图中必须删除数据场之值为 key的结点，请设计一个程序加以实现。【上海交通大学 2003四(20 分)】（分数：2.00）_假定无向图以邻接矩阵的形式存储。邻接矩阵定义如下(编者略)。试用 C语言编写算法函数并分析时间复杂度。（分数：4.00）(1).int DeleteNode(struct MGraphG， ElemType
8、e)；从图 G中删除顶点值为 e的顶点，成功返回1，否则返回 0。（分数：2.00）_(2).int DeleteEdge(struct MGraphG， ElemType a， ElemType b )；从图 G中删除(a，b)，成功返回 1，否则返回 0。【华中科技大学 2007六、31(282 分)】（分数：2.00）_18.已知无向图 G=(V,E)，给出求图 G的连通分量个数的算法。【哈尔滨工业大学 2002九(9 分)】【南京航空航天大学 1995十一(10 分)】（分数：2.00）_19.设有向图 G的十字链表已建立，用 C语言函数形式写出求图中各顶点度的算法：COUNT_D(G
9、n，Dn)，Gn为顶点表，Dn为存放各顶点度的数组，n 为图中顶点的个数。【北京科技大学 2005四、2(10 分)】（分数：2.00）_20.已知无向图采用邻接表存储方式，试写出删除边(i，j)的算法。【东南大学 1999三(10 分)】【北京邮电大学 2006三(7 分)】（分数：2.00）_21.试写一算法；判断以邻接表方式存储的有向图中是否存在由顶点 V i 到顶点 V j 的路径(ij)。注意：算法中涉及的图的基本操作必须在存储结构上实现。【哈尔滨工业大学 2001九(12 分)】（分数：2.00）_22.按图的广度优先搜索法写一算法判别以邻接矩阵存储的有向图中是否存在由顶点 V i
10、 到顶点 V j 的路径(ij)。【中山大学 1997五(10 分)】（分数：2.00）_23.假设以邻接矩阵作为图的存储结构，编写算法判别在给定的有向图中是否存在一个简单有向回路，若存在，则以顶点序列的方式输出该回路(找到一条即可)。(注：图中不存在顶点到自己的弧)【清华大学1994六(15 分)】【吉林大学 1997五(16 分)】（分数：2.00）_24.假设一个有向图 G已经以十字链表形式存储在内存中，试写一个判断该有向图中是否有环路(回路)的算法。【中科院研究生院 2005五(15 分)】【东南大学 2005数据结构部分五(15 分)】（分数：2.00）_25.在有向图 G中，如果
11、r到 G中的每个结点都有路径可达，则称结点 r为 G的根结点。编写一个算法完成下列功能：(1)建立有向图 G的邻接表存储结构；(2)判断有向图 G是否有根，若有，则打印出所有根结点的值。【东北大学 2001五(15 分)】【中国海洋大学 2006九(15 分)】（分数：2.00）_26.设无向图 G已用邻接表结构存储，顶点表为 GLn(n为图中顶点数)，试用“广度优先搜索”方法，写出求图 G中各连通分量的 C语言描述算法：BFSCOM(GL)。(注：算法中可调用队列操作的基本算法。)【北京科技大学 2001七、2(10 分)】（分数：2.00）_27.设计一非递归算法采用深度优先搜索对无向图进
12、行遍历，并对算法中的无向图的存储结构予以简单说明。【大连理工大学 2003二、1(453 分)】【北京邮电大学 1994十(15 分)】（分数：2.00）_计算机专业基础综合数据结构（图）历年真题试卷汇编 4答案解析(总分：58.00，做题时间：90 分钟)一、综合题(总题数：7，分数：14.00)1.已知一图如下图所示：(1)写出全部拓扑排序；(2)以 V1为源点，以 V8为终点，给出所有事件允许发生的最早时间和最晚时间，并给出关键路径；(3)求 V1结点到各点的最短距离。【北京邮电大学 2000五(15分)】 （分数：2.00）_正确答案：(正确答案：(1) )解析：2.(1)对于有向无环
13、图，叙述求拓扑有序序列的步骤；(2)对于以下的图，写出它的四个不同的拓扑有序序列。【南开大学 1998二(12 分)】 （分数：2.00）_正确答案：(正确答案：(1)对有向图，求拓扑序列步骤为： 1)在有向图中选一个没有前驱(即入度为零)的顶点并输出。 2)在图中删除该顶点及所有以它为尾的弧。 3)重复 1)和 2)，直至全部顶点输出，这时拓扑排序完成；否则，图中存在环，拓扑排序失败。 (2)这里使用形式化描述方法，当有多个顶点可以输出时，将其按序从上往下排列，这样不会丢掉拓扑序列。这里只画出从顶点 1开始的所有可能的拓扑序列，从顶点 3开始的拓扑序列可类似画出。 )解析：3.有向图的拓扑排
14、序能否用图的深度搜索模式来查找?若能，请简述方法；若不能，请简述原因。【西北大学 2000二、8(5 分)】（分数：2.00）_正确答案：(正确答案：图的深度优先遍历可用于拓扑排序。带环的有向图不能拓扑排序。深度优先遍历如何发现环呢?若从有向图某顶点 V出发进行遍历，在 dfs(v)结束之前出现从顶点 W到顶点 V的回边，由于 W在生成树上是 V的子孙，则有向图中必定存在包含顶点 V和 W的环。其算法实现见下面五、45 题。)解析：4.下图是带权的有向图 G的邻接表表示法，求：(1)以结点 V1出发深度遍历图 G所得的结点序列；(2)以结点 V1出发广度遍历图 G所得的结点序列；(3)从结点
15、V1到结点 V8的最短路径；(4)从结点 V1到结点V8的关键路径。 （分数：2.00）_正确答案：(正确答案：(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 )解析：5.下表给出了某工程各工序之间的优先关系和各工序所需时间。(1)画出相应的 AOE网； (2)列出各事件的最早发生时间，最迟发生时间；(3)找出关键路径并指明完成该工程所需最短时间。 （分数：2.00）_正确答案：(正确答案：(1)AOE 网如下图所示：图中虚线表示在时间上前后工序之间仅是接
16、续顺序关系不存在依赖关系。顶点代表事件，弧代表活动，弧上的权代表活动持续时间。题中顶点 1代表工程开始事件，顶点 11代表工程结束事件。 (2)各事件发生的最早和最晚时间如下表。 )解析：6.请写出应填入下列叙述中( )内的正确答案。某一工程作业的网络图如图所示，其中箭头表示作业，箭头边的数字表示完成作业所需的天数。箭头前后的圆圈表示事件，圆圈中的数字表示事件的编号。用事件编号的序列(例如 0一 279一 11)表示进行作业的路径。完成此工程的关键路径是(A)，完成此工程所需的最少天数为(B)天，此工程中具有最大充裕天数的事件是(C)，充裕天数是(D)。关键路径上的事件的充裕天数是(E)。 （
17、分数：2.00）_正确答案：(正确答案：A.02 一 69一 11B.20C.事件顶点 1、5 和 7各充裕两天 D.顶点 7和顶点 10间的活动充裕 4天 E0)解析：7.求出下面 AOE网中的关键路径(要求给出各个顶点的最早发生时间和最迟发生时间，并画出关键路径)。【北京交通大学 2005五、2(5 分)】 （分数：2.00）_正确答案：(正确答案：上面已有这类问题的解答。回答这类问题，只要认真细致，就能得到正确答案，否则，一步疏忽，将导致结论错误。)解析：二、设计题(总题数：21，分数：44.00)8.(单独命题考生做)设无向图 G有 n个顶点，m 条边。试编写用邻接表存储该图的算法。(
18、设顶点值用1n 或 0n 一 1编号)【南京航空航天大学 1996十二(10 分)】（分数：2.00）_正确答案：(正确答案：邻接表存储结构是顶点向量和顶点的邻接点链表相结合的存储结构。核心语句段如下： 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=gifirsta
19、rc；gifirstarc=p； 将边结点链入 p=new(ArcNode)(ArcNode)； 申请边结点，链入 j到 i的一条边 P 一adjvex=i；P 一next=gjfirstarc ； gjfrstarc=p； for)解析：9.请用流程图或类高级语言表示算法。已知有向图有 n个顶点，请写算法，根据用户输入的偶对建立该有向图的邻接表。即接受用户输入的(以其中之一为 0标志结束)，对于每条这样的边，申请一个结点，并插入单链表中，如此反复，直到将图中所有边处理完毕。提示：先产生邻接表的 n个头结点(其结点数值域从 1到 n)。【上海大学 2000四(16 分)】（分数：2.00）_正
20、确答案：(正确答案：与第 1题类似i，j户表示 i到 j的一条弧。)解析：10.设无向图 G有 n个顶点 e条边，写一算法建立 G的邻接多重表，要求该算法时间复杂性为 O(n+e)，且除邻接多重表本身所占空间之外只用 O(1)辅助空间。【东南大学 1995六(16 分)1997 二(15 分)】（分数：2.00）_正确答案：(正确答案：邻接多重表的边结点结构是(ivex，jvex，ilink，jlink，mark)。输入一条边的核心语句段如下： cinvlv2 ； i=GraphLocateVertex(g，V1)；j=GraphLocateVertex(g，v2)； p=new(ENode)
21、；申请边结点 P 一ivex=i；p-jvex=j； P 一ilink=gifirstedge；p 一j link=gjfirstedge； gifirstedge=p；gjfirstedge=p；)解析：11.给出以十字链表作存储结构，建立图的算法，输入(i，j，v)，其中 i、j 为顶点号，v 为权值。【河海大学 1998六(10 分)】（分数：2.00）_正确答案：(正确答案：十字链表的边结点结构为(headvex，tailvex，weight，headlink，tailink)，输入一条弧的核心语句段如下： cinijv； p=new(OrArcNode)； 申请结点 P 一headv
22、ex=j；p-tailvex=i；P 一weight=v； 弧结点中权值域 P 一headlink=gjfirstin； gjfirstin=p； P 一tailink=gifirstout； gifirstout=p；)解析：12.设有向图 G有 n个点(用 1，2，n 表示)，e 条边，写一算法根据 G的邻接表生成 G的反向邻接表，要求算法时间复杂性为 O(n+e)。【东南大学 1996三(13 分)1992 六(18 分)】【北京邮电大学 2006五、3(10分)】（分数：2.00）_正确答案：(正确答案：从顶点 i到邻接点的弧，改造成从邻接点到 i的弧，核心语句段如下： for(i=0
23、 ； iadjvex； s=new(ArcNode)； 申请结点空间 s 一adjvex=i；s 一next=ginjfirstarc ； ginjfirstarc=s ； p=P 一next； 下一个邻接点 while for)解析：13.写出从图的邻接表表示转换成邻接矩阵表示的算法，用类 Pascal语言(或 C语言)写成过程形式。【南开大学 1998四(16 分)】【天津大学 1999五】【华南理工大学 2006三、2(6 分)】（分数：2.00）_正确答案：(正确答案：for(i=0 ； iadjvex：1 jp=p 一next； )解析：14.试写出把图的邻接矩阵表示转换为邻接表表示
24、的算法。【哈尔滨工业大学 2002七(8 分)】【中山大学1998五、2(10 分)】【南开大学 2000三、3】【北京邮电大学 2006五、3(10 分)】（分数：2.00）_正确答案：(正确答案：核心语句段如下： for(i=0；iadjvex=j ； 顶点 i的邻接点是 j P一next=glifirstarc; 链入顶点 i的邻接点链表中 glifirstarc=p； if)解析：15.已知某有向图(n 个结点)的邻接表，求该图各结点的入度数。【天津大学 2001五(10 分)2006 二、1(7分)】【南京理工大学 1997四、2(10 分)】（分数：2.00）_正确答案：(正确答案
25、：在邻接表中求顶点入度，需要遍历整个邻接表。求顶点 f的入度的语句段如下： for(j=0；jn； j+) 遍历整个邻接表，求顶点 i的入度 if(i!=j) p=gjfirstarc； while(p) (if(p一adjvex=i)num+；P=p 一next；num 初值为 0 )解析：16.设计一个算法，统计一个采用邻接矩阵存储，具有 n个顶点的无向无权图所有顶点的度。【天津大学2005六(10 分)】（分数：2.00）_正确答案：(正确答案：设邻接矩阵元素不 1是边的用 0表示，所有顶点的度就是邻接矩阵中非零元素的个数。)解析：17.已知某有向图用邻接表表示。该邻接表的结点表及边表说
26、明如下(编者略)。设该有向图中必须删除数据场之值为 key的结点，请设计一个程序加以实现。【上海交通大学 2003四(20 分)】（分数：2.00）_正确答案：(正确答案：在有向图的邻接表中删除一个顶点，除在顶点向量中删除该顶点并顶点数减 1外，要删除该顶点的所有出度边和入度边，并调整相关边结点中邻接点的值。核心语句段如下： for(i=0；inext；delete(u)； 删除被删顶点的所有出度边 for(j=0； jn；j+) 查被删顶点的所有入度边 if(j!=i) p=q=gjfirstarc ； 设置前驱 q if(p一adjvex=i) 第一个邻接点是被删顶点 (u=p； gjfi
27、rstarc=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=p；p=p 一next； 邻接点链表指针后移继续查找 while(p) if(j!=i) for(j=i+1 ； j解析：假定无向图以邻接矩阵的形式存储。邻接矩阵定义如下(编者略)。试用 C语言编写算法函数并分析时
28、间复杂度。（分数：4.00）(1).int DeleteNode(struct MGraphG， ElemType e)；从图 G中删除顶点值为 e的顶点，成功返回1，否则返回 0。（分数：2.00）_正确答案：(正确答案：删除以邻接矩阵存储结构的无向图的顶点 i，要做三件事：一是将第 i行和第 i列的元素都变成 0删除顶点 i；二是将第 i+1列到第 n一 1列的元素向左平移一列；三是将第 i+1行到第 n一 1行的元素向上平移一行；最后顶点个数减 1，形成 n一 1阶的邻接矩阵。)解析：(2).int DeleteEdge(struct MGraphG， ElemType a， ElemT
29、ype b )；从图 G中删除(a，b)，成功返回 1，否则返回 0。【华中科技大学 2007六、31(282 分)】（分数：2.00）_正确答案：(正确答案：删除一条边容易，只要将邻接矩阵中对称的两个元素位置置 0即可。)解析：18.已知无向图 G=(V,E)，给出求图 G的连通分量个数的算法。【哈尔滨工业大学 2002九(9 分)】【南京航空航天大学 1995十一(10 分)】（分数：2.00）_正确答案：(正确答案：使用图的遍历可以求出图的连通分量。进入 dis或 bfs一次，就可以访问到图的一个连通分量的所有顶点。核心语句是： for(i=0；i解析：19.设有向图 G的十字链表已建立
30、，用 C语言函数形式写出求图中各顶点度的算法：COUNT_D(Gn，Dn)，Gn为顶点表，Dn为存放各顶点度的数组，n 为图中顶点的个数。【北京科技大学 2005四、2(10 分)】（分数：2.00）_正确答案：(正确答案：在有向图中，顶点的度是顶点的出度和入度之和。核心语句段如下： for(i=0；itaillink； 计算出度，di初值是 0 p=gifirstin； while(p)di+；p=p 一headlink； 计算入度 )解析：20.已知无向图采用邻接表存储方式，试写出删除边(i，j)的算法。【东南大学 1999三(10 分)】【北京邮电大学 2006三(7 分)】（分数：2.
31、00）_正确答案：(正确答案：在用邻接表方式存储的无向图 g中，删除边(i,j)，要在顶点 i的邻接点链表中删除邻接点为 j的边结点，在顶点 j的邻接点链表中删除邻接点为 i的边结点。)解析：21.试写一算法；判断以邻接表方式存储的有向图中是否存在由顶点 V i 到顶点 V j 的路径(ij)。注意：算法中涉及的图的基本操作必须在存储结构上实现。【哈尔滨工业大学 2001九(12 分)】（分数：2.00）_正确答案：(正确答案：从 V i 深度优先遍历，若在未退出深度优先遍历时遍历到 V i ，说明 V i 到 V j 存在路径。if(V i =V j )return 1； v i 到顶点 v
32、 j 存在路径 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 到顶点 v 1 不存在路径 )解析：22.按图的广度优先搜索法写一算法判别以邻接矩阵存储的有向图中是否存在由顶点 V i 到顶点 V j 的路径(ij)。【中山大学 1997五(10 分)】（分数：2.00）_正确答案：(正确答案：用广度优先遍历法判别以邻接矩阵存储的有向图中是否存在由顶点 V i 到顶点 V j 的路径，应该使用队列。从
33、顶点 V i 开始遍历，若遇到顶点 V j ，说明有路径。 int visitedn； 设有向图有 n个顶点 int PathiToj(Adj Matrix g，vertype V i ，vertype V j ) 判断以邻接矩阵方式存储的有向图中是否存在由顶点 v i 到顶点 v j 的路径 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 ； 1i 到顶点 Vj存在路径”； return(1)；) if(gvw=1& !visitedw) visitedw=1；QueueIn(Q，w)； for couttailvex=i)k=
