发布时间 : 星期六 文章第七章 图更新完毕开始阅读ff5e30e19b89680203d825c8
A1B?6534C72E821 11106F9 1716H12WG133 5 2 2 1 2 2 7 6 0 5 4 4 3 4 9 3 7 3 7 5 4 3 8 1 10 11 6 D
第52题图 第53题 工程作业的网络图
53．请写出应填入下列叙述中（ ）内的正确答案。
某一工程作业的网络图如图所示，其中箭头表示作业，箭头边的数字表示完成作业所需的天数。箭头前后的圆圈表示事件，圆圈中的数字表示事件的编号。用事件编号的序列（例如0-2-7-9-11）表示进行作业的路径。
完成此工程的关键路径是（A）完成此工程所需的最少天数为（B）天，此工程中具有最大充裕天数的事件是（C），充裕天数是（D）。关键路径上的事件的充裕天数是（E）。【上海大学 2002 三 （10分）】
五、算法设计题 1．（单独命题考生做）设无向图G有n个顶点，m条边。试编写用邻接表存储该图的算法。（设顶点值用1～n或0～n-1编号） 【南京航空航天大学 1996 十二 （10分）】
2．请用流程图或类高级语言(pascal或c)表示算法。已知有向图有n个顶点,请写算法,根据用户输入的偶对建立该有向图的邻接表。即接受用户输入的
3．设无向图G有n个点e条边，写一算法建立G的邻接多表，要求该算法时间复杂性为O（n+e），且除邻接多表本身所占空间之外只用O（1）辅助空间。【东南大学 1995 六（16分） 1997 二 （15分）】
4．给出以十字链表作存储结构，建立图的算法，输入(i,j,v)其中i,j为顶点号，v为权值。
【河海大学 1998 六 （10分）】
5．设有向G图有n个点(用1,2,?,n表示),e条边,写一算法根据其邻接表生成其反向邻接表,要求算法复杂性为O(n+e)。【东南大学 1996 三 （13分）】
类似本题的另外叙述有：
（1）下图（编者略）是有向图按出度建立的邻接表，试写一算法，将此出度邻接表改成入度建立的邻接表。【北京邮电大学 1993 五 （15分）】
（2）编写算法实现以下功能：根据含有n个顶点的有向图邻接表，构造相应的逆邻接表。
【东南大学 1992 六（18分）】
6．写出从图的邻接表表示转换成邻接矩阵表示的算法，用类PASCAL语言（或C语言）写成过程形式。
【南开大学 1998 四 (16分)】 类似本题的另外叙述有：
（1）已知某个图的邻接表，试建立该图的相邻矩阵。【天津大学 1999 五】
7．设已给出图的邻接矩阵，要求将邻接矩阵转换为邻接表，用类pascal语言写为过程形式。
【南开大学 1998 四 ( 14分)】 类似本题的另外叙述有：
（1）设已给出图的邻接矩阵，要求将图的邻接矩阵转化为邻接表，试实现其算法。【南开大学2000三3】
（2）编写算法，将图的邻接矩阵存储改为邻接表的存储。【中山大学 1998 五、2 （10分）】 8．试写一算法，判断以邻接表方式存储的有向图中是否存在由顶点Vi到顶点Vj的路径（i<>j）。注意：算法中涉及的图的基本操作必须在存储结构上实现。【哈尔滨工业大学 2001 九 （12分）】
类似本题的另外叙述有：
（1）设计一个深度优先搜索算法，以判断用邻接表方式存储的有向图中是否存在由顶点Vi到顶点Vj（i≠j）的路径。【中山大学 1999数 四 （15分）】
（2）按图的宽度优先搜索法写一算法判别以邻接矩阵存储的有向图中是否存在由顶点Vi到顶点Vj的路径（i≠j）。【中山大学 1997 五 （10分）】
（3）请用流程图或类高级语言(pascal或c)表示算法。写算法判别以邻接方式存储的无向图中是否存在由顶点Vi到顶点Vj的路径(i≠j)。【上海大学 1999 三、2 （14分）】
9．已知无向图采用邻接表存储方式，试写出删除边（i，j）的算法。 【东南大学 1999 三 （10分）】
类似本题的另外叙述有：
（1）一个无向连通图的存储结构以邻接表的形式给定，设计算法删除该图中的一条边(i,j)。 【北京工业大学 1996 二 (15分)】
（2）无向图G已按下图（编者略）邻接表存储。试编写算法在该邻接表上操作，删除从顶点I到顶点J之间的一条边。【上海大学 1996 六（18分）】
（3）设无向图G用邻接表表示，（编者略）请写出在该无向图中删除边 (i,j)的算法。 【青岛海洋大学 1999 五（13分）】 10．假设有向图以邻接表存储，试编写算法删除弧 【南京理工大学 1997 四、2（10分）】 13．假设以邻接矩阵作为图的存储结构，编写算法判别在给定的有向图中是否存在一个简单有向回路，若存在，则以顶点序列的方式输出该回路（找到一条即可）。（注：图中不存在顶点到自己的弧） 【清华大学 1994 六 （15分）】 类似本题的另外叙述有： （1）假定G=（V，E）是有向图，V={1，2，?，n }，n>=1，G以邻接矩阵方式存储，G的邻接矩阵为A，即A是一个二维数组，如果i到 j有边，则A[ i,j]=1，否则A[ i,j]=0。请给出一个算法，该算法能判断G是否是非循环图（即G中是否存在回路），要求算法的时间复杂性为O（ n*n ）。 【吉林大学 1997 五 (16分)】 14．假设一个有向图G已经以十字链表形式存储在内存中，试写一个判断该有向图中是否有环路（回路）的算法。【东北大学 2000 四、3 (12分)】 15．用邻接多重表存储结构，编写FIRST-ADJ(G,V)函数，函数返回值为第一个邻接点，若V没有邻接点，返回零。【北京工商大学 1999 四 （12分）】 16．在有向图G中，如果r到G中的每个结点都有路径可达，则称结点r为G的根结点。编写一个算法完成下列功能： （1）．建立有向图G的邻接表存储结构； （2）．判断有向图G是否有根，若有，则打印出所有根结点的值。【东北大学 2001 五 (15分)】 17．试编写求无向图G的连通分量的算法。要求输出每一连通分量的顶点值。(设图G已用邻接表存储) 【南京航空航天大学 1995 十一（10分）】 类似本题的另外叙述有： （1）写出求无向图G中各连通分量的顶点集的算法COMF（G）。可调用的运算是：FIRST_ADJ（G，V）--求顶点V的第一邻接点，NEXTADJ（G，V，W）--求顶点V关于W的下一个邻接点。 【北京科技大学 1998 八、2（10分）】 （2）编程求解无向图G的所有连通分量。 【南京航空航天大学 2000 七】 18．设无向图G已用邻接表结构存储，顶点表为GL[n] (n为图中顶点数)，试用“广度优先搜索”方法，写出求图G中各连通分量的C语言描述算法：BFSCOM(GL)。（注：算法中可调用队列操作的基本算法。） 【北京科技大学 2001 七、2 （10分）】 19．设一个连通无向图G=(V,E)采用邻接表方式存储，V=(1,2,?,n}，一维数组HAED[1?n]用来存放每个单链表的头指针，单链表中节点结构为(VER,LINK)，其中LINK是链接字段，VER字段表示顶点内容，一维数组MARK[1?n]用于对相应顶点加标号，MARK[i]=0表示顶点i未被访问到, MARK[i]=1表示顶点i已经被访问过,试写出对上述图G进行广度(或宽度)优先遍历(或访问)的非递归算法BFS(HEAD,n,s,MARK,MARK)，其中S为任一遍历起始顶点。 【吉林大学 2000 二、1 （7分）】 20．写出图的深度优先搜索DFS算法的非递归算法。 【北京邮电大学 1994 十 （15分）】 21．已知连通图如下： D F C A B E （1）．给出本图的邻接表； （2）．若从顶点B出发对该图进行遍历，在（1）的基础上分别给出本图的按深度优先搜索和按广度优先搜索的顶点序列； （3）．写出按深度优先搜索的递归程序。【厦门大学 2001 三 （12%分）】 22．试编写从某一顶点出发按深度优先搜索策略在图的邻接表上遍历一个强连通图的非递归算法。（用类PASCAL语言）【燕山大学 1999 十、2 （8分）】 23. 设计算法以实现对无向图G的深度遍历，要求：将每一个连通分量中的顶点以一个表的形式输出。例如，下图的输出结果为：（1，3）（2，6，7，4，5，8）（9，10） 1 2 4 5 9 3 8 10 6 7 （注：本算法中可以调用以下几个函数： firstadj（g,v）——返回图g中顶点v的第一个邻接点的号码，若不存在，则返回0； nextadj（g,v,w）——返回图g中顶点v的邻接点中处于w之后的邻接点的号码，若不存在，则返回0。nodes（g）——返回图g中的顶点数） 【合肥工业大学 2000 五、4（8分）】 24．请设计一个图的抽象数据类型（只需要用类PASCAL或类C/C++语言给出其主要功能函数或过程的接口说明，不需要指定存储结构，也不需要写出函数或过程的实现方法），利用抽象数据类型所提 供的函数或过程编写图的宽度优先周游算法。算法不应该涉及具体的存储结构，也不允许不通过函数或过程而直接引用图结构的数据成员，抽象数据类型和算法都应该加足够的注释。【北京大学 1999 二、1（10分）】 25. 设计算法以判断给定的无向图G中是否存在一条以V0为起点的包含所有顶点的简单路径，若存在，返回TRUE，否则，返回FALSE（注：本算法中可以调用以下几个函数：FIRSTADJ（G，V）——返回图G中顶点V的第一个邻接点的号码，若不存在，则返回0；NEXTADJ（G，V，W）——返回图G中顶点V的邻接点中处于W之后的邻接点的号码，若不存在，则返回0；NODES（G）——返回图G中的顶点数） 【合肥工业大学 1999 五、5 (8分)】 26．已有邻接表表示的有向图，请编程判断从第u顶点至第v顶点是否有简单路径，若有则印出该路径上的顶点。要求：先描述图的存储结构，并简述算法思路；查找邻接点等图的运算要自己实现。（尽量采用非递归算法，否则满分１５分）【北京工业大学 2000 六 （20分）】 类似本题的另外叙述有： (1) (1) 已知有向图和图中的两个结点u和v，试编写算法求有向图中从u到v的所有简单路径。 【东南大学 2001 四 （15分）】 (2) 已知有向图和图中两个顶点U和V，编写算法求有向图中从U到V的所有简单路径，并以下图为例执行所编写的算法，画出相应的搜索过程图。【山东科技大学 2002 六 （18分）】 a u b f C e 第27题图 v d 第26题图 27． 图的D_搜索类似与BFS,不同之处在于使用栈代替BFS中的队列 ,入出队列的操作改为入出栈的操作，即当一个顶点的所有邻接点被搜索之后,下一个搜索出发点应该是最近入栈(栈顶)的顶点。 （1）．用邻接表做存储结构,写一个D_搜索算法；（15分） （2）．用 D_搜索方法的访问次序和相应的生成树，当从某顶点出发搜索它的邻接点，请按邻接点序号递增序搜索，以使答案唯一。（5分）【中科院 1998 六 （20分）】 28．令G=（V，E）为一个有向无环图，编写一个给图G中每一个顶点赋以一个整数序号的算法，并满足以下条件：若从顶点i至顶点j有一条弧则应使i 30．我们可用“破圈法”求解带权连通无向图的一棵最小代价生成树。所谓“破圈法”就是“任取一圈，去掉圈上权最大的边”，反复执行这一步骤，直到没有圈为止。请给出用“破圈法”求解给定的带权连通无向图的一棵最小代价生成树的详细算法，并用程序实现你所给出的算法。注：圈就是回路。 【复旦大学 1997 六 （13分）】 31. 设图用邻接表表示，写出求从指定顶点到其余各顶点的最短路径的Dijkstra 算法。