[考研类试卷]计算机专业基础综合数据结构（图）历年真题试卷汇编
10
一、综合题
1 已知一图如下图所示：(1)写出全部拓扑排序；(2)以V1为源点，以V8为终点，给出所有事件允许发生的最早时间和最晚时间，并给出关键路径；(3)求V1结点到各点的最短距离。【北京邮电大学2000五(15分)】
2 (1)对于有向无环图，叙述求拓扑有序序列的步骤；(2)对于以下的图，写出它的
四个不同的拓扑有序序列。【南开大学1998二(12分)】
3 有向图的拓扑排序能否用图的深度搜索模式来查找?若能，请简述方法；若不能，请简述原因。【西北大学2000二、8(5分)】
4 下图是带权的有向图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 请写出应填入下列叙述中( )内的正确答案。某一工程作业的网络图如图所示，其中箭头表示作业，箭头边的数字表示完成作业所需的天数。箭头前后的圆圈表示事件，圆圈中的数字表示事件的编号。用事件编号的序列(例如0一2—7—9一11)表示进行作业的路径。完成此工程的关键路径是(A)，完成此工程所需的最少天数为(B)天，此工程中具有最大充裕天数的事件是(C)，充裕天数是(D)。关键路径上的
事件的充裕天数是(E)。
【上海大学2002三(10分)】
答案见麦多课文库
7 求出下面AOE网中的关键路径(要求给出各个顶点的最早发生时间和最迟发生时间，并画出关键路径)。【北京交通大学2005五、2(5分)】
二、设计题
8 (单独命题考生做)设无向图G有n个顶点，m条边。试编写用邻接表存储该图的算法。(设顶点值用1～n或0～n一1编号)【南京航空航天大学1996十二(10分)】
9 请用流程图或类高级语言表示算法。已知有向图有n个顶点，请写算法，根据用户输入的偶对建立该有向图的邻接表。即接受用户输入的
10 设无向图G有n个顶点e条边，写一算法建立G的邻接多重表，要求该算法时间复杂性为O(n+e)，且除邻接多重表本身所占空间之外只用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语言)写成过程形式。【南开大学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个顶点的无向无权图所有顶点的度。【天津大学2005六(10分)】
17 已知某有向图用邻接表表示。该邻接表的结点表及边表说明如下(编者略)。设该有向图中必须删除数据场之值为key的结点，请设计一个程序加以实现。【上海交通大学2003四(20分)】
17 假定无向图以邻接矩阵的形式存储。邻接矩阵定义如下(编者略)。试用C语言编写算法函数并分析时间复杂度。
18 int DeleteNode(struct MGraph＆G， ElemType e)；从图G中删除顶点值为e的顶点，成功返回1，否则返回0。
19 int DeleteEdge(struct MGraph＆G， ElemType a， ElemType b )；从图G中删除(a，b)，成功返回1，否则返回0。【华中科技大学2007六、31(28／2分)】
20 已知无向图G=(V,E)，给出求图G的连通分量个数的算法。【哈尔滨工业大学2002九(9分)】【南京航空航天大学1995十一(10分)】
21 设有向图G的十字链表已建立，用C语言函数形式写出求图中各顶点度的算法：COUNT_D(G[n]，D[n])，G[n]为顶点表，D[n]为存放各顶点度的数组，n为图中顶点的个数。【北京科技大学2005四、2(10分)】
22 已知无向图采用邻接表存储方式，试写出删除边(i，j)的算法。【东南大学1999三(10分)】【北京邮电大学2006三(7分)】
答案见麦多课文库
23 试写一算法；判断以邻接表方式存储的有向图中是否存在由顶点Vi到顶点Vj的路径(i＜＞j)。注意：算法中涉及的图的基本操作必须在存储结构上实现。【哈尔滨工业大学2001九(12分)】
24 按图的广度优先搜索法写一算法判别以邻接矩阵存储的有向图中是否存在由顶点Vi到顶点Vj的路径(i≠j)。【中山大学1997五(10分)】
25 假设以邻接矩阵作为图的存储结构，编写算法判别在给定的有向图中是否存在一个简单有向回路，若存在，则以顶点序列的方式输出该回路(找到一条即可)。(注：图中不存在顶点到自己的弧)【清华大学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已用邻接表结构存储，顶点表为GL[n](n为图中顶点数)，试用“广度优先搜索”方法，写出求图G中各连通分量的C语言描述算法：BFSCOM(GL)。(注：算法中可调用队列操作的基本算法。)【北京科技大学2001七、2(10分)】
29 设计一非递归算法采用深度优先搜索对无向图进行遍历，并对算法中的无向图的存储结构予以简单说明。【大连理工大学2003二、1(45／3分)】【北京邮电大学1994十(15分)】
答案见麦多课文库
[考研类试卷]计算机专业基础综合数据结构(图)历年真题试卷汇编10.doc
