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

计算机专业基础综合数据结构（图）历年真题试卷汇编4

(总分：58.00，做题时间：90分钟)

一、综合题(总题数：7，分数：14.00)

1.已知一图如下图所示：(1)写出全部拓扑排序；(2)以V1为源点，以V8为终点，给出所有事件允许发生

的最早时间和最晚时间，并给出关键路径；(3)求V1结点到各点的最短距离。【北京邮电大学2000五(15

分)】

__________________________________________________________________________________________

正确答案：(正确答案：(1)(2)关键路径有3条，长17。各事件允许发生的最早时间和最晚时间略。

V1→V2→V6→V8，V1→V3→V5→V7→V8，V1→V7→V8→V1→V4→V5→V8(3)V1结点到其他各结点的最短距

离为：2，3，6，12，10，15，16。)

2.(1)对于有向无环图，叙述求拓扑有序序列的步骤；(2)对于以下的图，写出它的四个不同的拓扑有序序

列。【南开大学1998二(12分)】

__________________________________________________________________________________________

正确答案：(正确答案：(1)对有向图，求拓扑序列步骤为：1)在有向图中选一个没有前驱(即入度为零)

的顶点并输出。2)在图中删除该顶点及所有以它为尾的弧。3)重复1)和2)，直至全部顶点输出，这时拓

扑排序完成；否则，图中存在环，拓扑排序失败。(2)这里使用形式化描述方法，当有多个顶点可以输出

时，将其按序从上往下排列，这样不会丢掉拓扑序列。这里只画出从顶点1开始的所有可能的拓扑序列，

从顶点3开始的拓扑序列可类似画出。)

3.有向图的拓扑排序能否用图的深度有哪些信誉好的足球投注网站模式来查找?若能，请简述方法；若不能，请简述原因。【西北大

学2000二、8(5分)】

__________________________________________________________________________________________

正确答案：(正确答案：图的深度优先遍历可用于拓扑排序。带环的有向图不能拓扑排序。深度优先遍历如

何发现环呢?若从有向图某顶点V出发进行遍历，在dfs(v)结束之前出现从顶点W到顶点V的回边，由于W

在生成树上是V的子孙，则有向图中必定存在包含顶点V和W的环。其算法实现见下面五、45题。)

4.下图是带权的有向图G的邻接表表示法，求：(1)以结点V1出发深度遍历图G所得的结点序列；(2)以结

点V1出发广度遍历图G所得的结点序列；(3)从结点V1到结点V8的最短路径；(4)从结点V1到结点V8的

关键路径。【中国海洋大学1999四(10分)】

__________________________________________________________________________________________

正确答案：(正确答案：(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.下表给出了某工程各工序之间的优先关系和各工序所需时间。(1)画出相应的AOE网；(2)列出各事件的

最早发生时间，最迟发生时间；(3)找出关键路径并指明完成该工程所需最短时间。【山东大学2002

七(15分)】【北京交通大学1995六(15分)】

__________________________________________________________________________________________

正确答案：(正确答案：(1)AOE网如下图所示：图中虚线表示在时间上前后工序之间仅是接续顺序关系不

存在依赖关系。顶点代表事件，弧代表活动，弧上的权代表活动持续时间。题中顶点1代表工程开始事件，

顶点11代表工程结束事件。