《《数据结构》期末考试复习题第7章图.pdf》由会员分享，可在线阅读，更多相关《《数据结构》期末考试复习题第7章图.pdf（54页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第 七 章 图一、选择题1 .图中有关路径的定义是（）。【北方交通大学2 0 0 1 一、2 4 （2分）】A.由顶点和相邻顶点序偶构成的边所形成的序列C.由不同边所形成的序列2 .设无向图的顶点个数为n,则该图最多有（）条边。A.n-1 B.n（n-l）/2 C.n（n+l）/2B.由不同顶点所形成的序列D.上述定义都不是D.0 E.n2【清 华 大 学 1 9 9 8 一、5 （2分）】【西安电子科技大1 9 9 8 一、6 （2分）】【北京航空航天大学1 9 9 9 一、7 （2分）】3.一 个 n 个顶点的连通无向图，其边的个数至少为（）。【浙 江 大 学 1 9 9 9 四、4 （4
2、分）】A.n-l B.n C.n+14 .要连通具有n个顶点的有向图，至少需要（6（2分）】D.n l o g n；）条边。【北京航空航天大学2 0 0 0 一、A.n-1 B.n C.n+15.n个结点的完全有向图含有边的数目A.n*n B .n (n+1 )D.2 n()。【中山 大 学 1 9 9 8 二、9 (2 分)】C.n /2 D.n*(n 1)6.一个有n个结点的图，最 少 有（）个连通分量，最 多 有（）个连通分量。A.0B.1C.n-lD.n【北京邮电大学2 0 0 0 二、5 （2 0/8 分）】7 .在一个无向图中，所有顶点的度数之和等于所有边数（）倍，在一个有向图中，
3、所有顶点的入度之和等于所有顶点出度之和的（）倍。【哈尔滨工业大学2 0 0 1 二、3（2分）】A.1/2 B.2 C.1 D.48 .用有向无环图描述表达式（A+B）*（A+B）/A）,至少需要顶点的数目为（）。【中山大学1 9 9 9 ,1 4 A.5 B.6 C.8 D.99 .用 DFS 遍历一个无环有向图，并在DFS 算法退栈返回时打印相应的顶点，则输出的顶点序列是（）。A.逆拓扑有序 B.拓扑有序 C.无序的【中科院软件所1 9 9 8 1 0.下面结构中最适于表示稀疏无向图的是（），适于表示稀疏有向图的是（）。A.邻接矩阵 B.逆邻接表 C.邻接多重表 D.十字链表 E.邻接表【
4、北京工业大学2 0 0 1 一、3（2分）】1 1 .下 列 哪一种图的邻接矩阵是对称矩阵？（）【北方交通大学2 0 0 1 、1 1 （2分）】A.有向图 B.无向图 C.A 0 V 网 D.A 0 E网0 I o-A=1 0 11 2 .从邻接阵矩 。1。可以看出，该图共有（）个顶点；如果是有向图该图共有（）条弧；如果是无向图，则 共 有（）条边。【中科院软件所1 9 9 9 六、2 （3 分）】.A.9 B.3 C.6 D.1 E.以上答案均不正确.A.5 B.4 C.3 D.2 E.以上答案均不正确.A.5 B.4 C.3 D.2 E.以上答案均不正确1 3.当一个有N个顶点的图用邻接
5、矩阵A表示时，顶点V i 的度是（）。【南京理工大学1 9 9 8一、4（2分）】A.i=lEAi,j f 4川 AU，J力 Aj,iB.J=I C./=l D.i=i +J=11 4 .用相邻矩阵A表示图，判定任意两个顶点V i 和 V j之间是否有长度为m的路径相连,则只要检查（）的第i 行第j 列的元素是否为零即可。【武汉大学2 0 0 0 二、7 A.m A B.A C.A I）.A m-11 5 .下列说法不正确的是（）。【青岛大学2 0 0 2 二、9 （2分）】A.图的遍历是从给定的源点出发每个顶点仅被访问一次 C.图的深度遍历不适用于有向图B.遍历的基本算法有两种：深度遍历和广
6、度遍历 D.图的深度遍历是一个递归过程1 6 无 向 图 G=（V,E）,其 中：V=a,b,c,d,e,f ,E=（a,b）,（a,e）,（a,c）,（b,e）,（c,f）,（f,d）,（e,d）,对该图进行深度优先遍历，得到的顶点序列正确的是（）。【南京理工大学2 0 0 1 、1 4 （1.5 分）】A.a,b,e,c,d,f B.a,c,f,e,b,d C.a,e,b,c,f,d D.a,e,d,f,c,b1 7.设图如右所示，在下面的5 个序列中，符合深度优先遍历的序列有多少？（）【南京理工大学2 0 0 0 一、2 0 （1.5 分）】ae bdfc acfde b a e d f
7、 c b a e f d c b a e f d b1 8 .卜一图中给出由7 个顶点组成的无向图。从顶点1 出发，对它进行深度优先遍历得到的序列是（）,而进行广度优先遍历得到的顶点序列是（）。【中科院软件所1 999六、2-（1）（2分）】.A.1 3 5 4 2 67 B.1 3 4 765 2 C.1 5 3 4 2 76 D.1 2 4 765 3 E.以上答案均不正确.A.1 5 3 4 2 67 B.1 72 64 5 3 C.1 3 5 4 2 76 D.1 2 4 765 3 E.以上答案均不正确1 9.下面哪一方法可以判断出一个有向图是否有环（回路）：【东北大学2 0 0 0
8、 4、2 （4分）】A.深度优先遍历 B.拓扑排序 C.求 最 短 路 径 D.求关键路径2 0 .在图采用邻接表存储时，求最小生成树的P r i m 算法的时间复杂度为（）。A.0（n）B.0（n+e）C.0（n2）D.0（n3）【合肥工业大学2 0 0 1 -、2 （2分）】2 1 .下面是求连通网的最小生成树的p r i m 算法:集合V T,E T 分别放顶点和边,初始为（1 ）,下面步骤重复n-1 次：a：(2 )；b：(3 )；最后：(4 )。【南京理工大学1 997 一、1 1 1 4(8 分)】(1).A.V T,E T 为空 B.V T 为所有顶点，E T 为空C.V T 为
9、网中任意一点，E T 为空 I).V T 为空，E T 为网中所有边(2).A.选 i 属于V T,j 不属于V T,且(i,j)上的权最小B.选 i 属于V T,j 不属于V T,且(i,j)上的权最大C.选 i 不属于V T,j不属于V T,且(i,j)上的权最小D.选 i 不属于V T,j 不属于V T,且(i,j)上的权最大(3).A.顶 点 i 加入V T,(i,j)加入E TC.顶 点 j 加入V T,(i,j)从 E T 中删去E T(4).A.ET中为最小生成树C.E T 中有n-1 条边时为生成树，否则无解B.顶 点 j 加入V T,(i,j)加入E TD.顶 点 i,j 加
10、入V T,(i,j)加入B.不在E T 中的边构成最小生成树D.E T 中无回路时，为生成树，否则无解2 2.(1).求从指定源点到其余各顶点的迪杰斯特拉(D i j k s t r a)最短路径算法中弧上权不能为负的原因是在实际应用中无意义；(2).利用D i j k s t r a 求每一对不同顶点之间的最短路径的算法时间是0(r)；(图用邻接矩阵表示)(3).F l o y d 求每对不同顶点对的算法中允许弧上的权为负，但不能有权和为负的回路。上面不正确的是()。【南京理工大学2 0 0 0 一、2 1 (1.5 分)】A.(1),(2),(3)B.(1)C.(1),(3)D.(2),(
11、3)2 3 .当各边上的权值()时，BF S算法可用来解决单源最短路径问题。【中科院计算所2 0 0 0一、3 (2 分)】A.均相等 B.均互不相等 C.不一定相等2 4 .求解最短路径的F l o y d 算法的时间复杂度为()。【合肥工业大学1 999 一、2 (2分)】A.0 (n)B.0 (n+c)C.0 (n*n)D.0 (n*n*n)2 5 .已知有向图 G=(V,E),其中 V=%,V z,V 3,V 4,V 5,V 6,V 7,E=,G 的拓扑序列是()。A.Vb V3,V4,V6,V2,V5,V7 B.V,.V3,V2 V6,V,h V5 1 V-C.Vb V3,V4)V5
12、(V2)Vo,V r D.V1(V2)V5,V3)V,b V6,V7【北京航空航天大学2 0 0 0 一、7(2 分)】2 6.若一个有向图的邻接距阵中，主对角线以下的元素均为零，则该图的拓扑有序序列()。A.存在 B.不 存 在【中科院计算所1 9 9 8 二、6 (2 分)】【中国科技大学1 9 9 8 二、6(2 分)】2 7 .个有向无环图的拓扑排序序列()是唯一的。【北京邮电大学2 001 一、3 (2分)】A.一定 B.不一定2 8 .在有向图G的拓扑序列中，若 顶 点 Vi在 顶 点 V J 之前，则下列情形不可能出现的是(A.G中有弧 B.G中有一条从V i 到 V j 的路径
13、C.G中没有弧 D.G中有一条从V j 到 V i 的路径【南京理工大学2 000、9 （1.5 分）】2 9.在用邻接表表示图时，拓扑排序算法时间复杂度为（）oA.O（n）B.O（n+e）C.0（n*n）D.O（n*n*n）【合肥工业大学2 000 一、2 （2分）】【南京理工大学2 001 一、9 （1.5 分）】【青岛 大 学 2 002 二、3 （2分）】3 0.关键路径是事件结点网络中（）。【西安电子科技大学2 001 应 用-、4 （2分）】A.从源点到汇点的最长路径 B.从源点到汇点的最短路径C.最长回路 D.最短回路3 1 .下面关于求关键路径的说法不正确的是（）。【南京理工大
14、学1 9 9 8、1 2 （2分）】A.求关键路径是以拓扑排序为基础的B.一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同C.个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差D.关键活动一定位于关键路径上3 2.下列关于A 0E网的叙述中，不正确的是（）。A.关键活动不按期完成就会影响整个工程的完成时间B.任何一个关键活动提前完成，那么整个工程将会提前完成C.所有的关键活动提前完成，那么整个工程将会提前完成D.某些关键活动提前完成，那么整个工程将会提前完成【北方交通大学1 9 9 9 一、7 （3分）】【北京工业大学1 9 9 9 一、1 （2分）】
15、二、判断题L树中的结点和图中的顶点就是指数据结构中的数据元素。（）【青岛大学2 001 四、1 （1分）】2 .在 n 个结点的无向图中，若边数大于n-1,则该图必是连通图。（）【中科院软件所1 9 9 7一、4（1 分）】力D（Vi）3 .对有n 个顶点的无向图，其边数e 与各顶点度数间满足下列等式e=,。（）【南京航空航天大学1 9 9 6 六、4 （1 分）】4 .有 e条边的无向图，在邻接表中有e个结点。（）【南京理工大学1 9 9 8 二、5 （2分）】5 .有向图中顶点V的度等于其邻接矩阵中第V 行中的1 的个数”合肥工业大学2 001二、7（1 分）】6 .强连通图的各顶点间均可
16、达。（）【北京邮电大学2 000、3 （1 分）】7 .强连通分量是无向图的极大强连通子图。（）【北京邮电大学2 002 一、7 （1 分）】8 .连通分量指的是有向图中的极大连通子图。）【燕 山 大 学 1 9 9 8 二、4 （2 分）】9 .邻接多重表是无向图和有向图的链式存储结构。（）【南京航空航天大学1 9 9 5 五、5（1 分）】1 0.十字链表是无向图的一种存储结构。（）【青岛大学2 001 四、7 （1 分）】1 1 .无向图的邻接矩阵可用一维数组存储。（）【青岛大学2 000四、5 （1 分）】1 2 .用邻接矩阵法存储一个图所需的存储单元数目与图的边数有关。（）【东南 大
17、 学 2 001 一、4 （1 分）】【中山 大 学 1 9 9 4 一、3 （2分）】1 3 .有 n 个顶点的无向图，采用邻接矩阵表示，图中的边数等于邻接矩阵中非零元素之和的一半。（）【北京邮电大学1 9 9 8 一、5 （2 分）】1 4 .有向图的邻接矩阵是对称的。（）【青岛大学2 001 四、6 （1 分）】1 5 .无向图的邻接矩阵一定是对称矩阵，有向图的邻接矩阵一定是非对称矩阵。（）【东南 大 学 2 001 一、3 （1 分）】【哈尔滨工业大学1 9 9 9 三、4 1 6 .邻接矩阵适用于有向图和无向图的存储，但不能存储带权的有向图和无向图，而只能使用邻接表存储形式来存储它。
18、（）【上海海运学院1 9 9 5 一、9 （1 分）1 9 9 7 一、8 （1 分）1 9 9 8 、9（1 分）】1 7 .用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小与图中结点个数有关，而与图的边数无关。（）【上海海运学院1 9 9 6 一、8 （1 分）1 9 9 9 一、9 （1 分）】1 8 .一个有向图的邻接表和逆邻接表中结点的个数可能不等。（）【上海交通大学1 9 9 8一、1 2 1 9 .需要借助于一个队列来实现DF S 算法。（）【南京航空航天大学1 9 9 6 六、8 （1 分）】2 0 .广度遍历生成树描述了从起点到各顶点的最短路径。（）【合
19、肥工业大学2 0 0 1 二、8 （1 分）】2 1 .任何无向图都存在生成树。（）【北京邮电大学2 0 0 0 一、1 （1 分）】2 2 .不同的求最小生成树的方法最后得到的生成树是相同的.（）【南京理工大学1 9 9 8二、3 （2分）】2 3 .带权无向图的最小生成树必是唯一的。（）【南京航空航天大学1 9 9 6 六、7 （1 分）】2 4 .最小代价生成树是唯一的。（）【山东 大 学 2 0 0 1 一、5 （1 分）】2 5 .一 个 网（带权图）都有唯一的最小生成树。（）【大连海事大学2 0 0 1 一、1 4 （1分）】2 6 .连通图上各边权值均不相同，则该图的最小生成树是
20、唯的。（）【哈尔滨工业大学1 9 9 9 三、3 2 7 .带权的连通无向图的最小（代价）生 成 树（支撑树）是唯一的。（）【中山 大 学 1 9 9 4一、1 0 （2 分）】2 8 .最小生成树的K RU S K A L 算法是一种贪心法（G REEDY）。（）【华南理工大学2 0 0 2 一、6 （1 分）】2 9 .求最小生成树的普里姆（Pr i m）算法中边上的权可正可负。（）【南京理工大学1 9 9 8二、2 （2分）】3 0 .带权的连通无向图的最小代价生成树是唯一的。（）【东南大学2 0 0 1 、5 （1 分）】3 1 .最小生成树问题是构造连通网的最小代价生成树。（）【青岛
21、大学2 0 0 1 四、1 0 （1分）】3 2 .在图G的最小生成树G 1 中，可能会有某条边的权值超过未选边的权值。（）【合肥工业大学2 0 0 0 二、7 （1 分）】3 3 .在用F l o y d 算法求解各顶点的最短路径时，每个表示两点间路径的p a t h i l,J 一定是p a t hk I,J 的子集（k=l,2,3,n）。（）【合肥工业大学2 0 0 0 二、6 （1 分）】3 4 .拓扑排序算法把一个无向图中的顶点排成一个有序序列。（）【南京航空航天大学1 9 9 5五、8 （1 分）】3 5 .拓扑排序算法仅能适用于有向无环图。（）【南京航空航天大学1 9 9 7 一
22、、7 （1 分）】3 6 .无环有向图才能进行拓扑排序。（）【青岛大学2 0 0 2 、7 （1 分）2 0 0 1 、8 （1分）】3 7 .有环图也能进行拓扑排序。（）【青岛大学2 0 0 0 四、6 （1 分）】38.拓扑排序的有向图中，最多存在一条环路。（）【大连海事大学2001 一、6（1 分）】39.任何有向图的结点都可以排成拓扑排序，而且拓扑序列不唯一。（）【上海交通大学1998 一、1340.既使有向无环图的拓扑序列唯一，也不能唯一确定该图。（）【合肥工业大学2001二、6（1 分）】41.若一个有向图的邻接矩阵对角线以下元素均为零，则该图的拓扑有序序列必定存在。（）【中科院软
23、件所1997 一、5（1 分）】42.A0V网的含义是以边表示活动的网。（）【南京航空航天 大 学 1995五、7（1 分）】43.对一个A0V网，从源点到终点的路径最长的路径称作关键路径。【南京航空航天大学1995五、9（1 分）】44.关键路径是A0E网中从源点到终点的最长路径。（）【青岛大学2000四、10（1 分）】45.A0E网一定是有向无环图。（）【青岛大学2001 一、9（1 分）】46.在表示某工程的A0E网中，加速其关键路径上的任意关键活动均可缩短整个工程的完成时间。（）【长沙铁道 学 院 1997、2（1 分）】47.在 A0E图中，关键路径上某个活动的时间缩短，整个工程的
24、时间也就必定缩短。（）【大连海事大学2001、15（1 分）】48.在 A0E图中，关键路径上活动的时间延长多少，整个工程的时间也就随之延长多少。（）【大连海事大学2001-、16（1 分）】49.当改变网上某一关键路径上任一关键活动后，必将产生不同的关键路径。【上海交通大学 1998 一、14三、填空题1.判 断 一 个 无 向 图 是 一 棵 树 的 条 件 是。2.有向图G的 强 连 通 分 量 是 指。【北京科技大学1997 一、73.一个连通图的 是一个极小连通子图。【重庆大学2000 一、1】4.具 有 10个顶点的无向图，边 的 总 数 最 多 为。【华中理工 大 学 2000、
25、7（1 分）】5.若用n 表示图中顶点数目，则有 条边的无向图成为完全图。【燕山大学1998、6（1 分）】6.设无向图G 有 n 个顶点和e 条边，每个顶点V i的度为di（l=i=n，则 e=【福州 大 学 1998二、2（2 分）】7.G是一个非连通无向图，共有28条边，则该图至少有 个顶点。【西安电子科技大2001软件一、8（2 分）】8.在有n 个顶点的有向图中，若要使任意两点间可以互相到达，则至少需要 条弧。【合肥工业 大 学 2000三、8（2 分）】9.在有n 个顶点的有向图中，每 个 顶 点 的 度 最 大 可 达。【武汉 大 学 2000 一、310.设 G为具有N个顶点的
26、无向连通图，则 G中至少有 条边。【长沙铁道 学 院 1997二、2（2 分）】11.n 个顶点的连通无向图，其 边 的 条 数 至 少 为。【哈尔滨工业大学2000二、2（1分）】12.如果含n 个顶点的图形形成一个环，则它有 棵生成树。【西安电子科技大学2001软 件 一、2（2 分）】1 3 .N个顶点的连通图的生成树含有 条边。【中山 大 学 1 9 9 8 一、9 (1 分)】1 4 .构造n 个结点的强连通图，至少有 条弧。【北京轻工业学院2 0 0 0 一、4 (2 分)】【北京邮电大学2 0 0 1 二、5 (2 分)1 7.N 个顶点的连通图用邻接矩阵表示时,该矩阵至少有 个
27、非零元素。【中科院计算所1 9 9 8 一、6 (1 分)】【中国科技大学1 9 9 8 一、6(1 5/6 分)】1 8 .在图G的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该顶点的；对于有向图来说等于该顶点的 o【燕山大学2 0 0 1 二、5 (3 分)】1 9 .在有向图的邻接矩阵表示中，计 算 第 I个 顶 点 入 度 的 方 法 是。【青岛大学2 0 0 2三、7(2 分)】2 0 .对于一个具有n 个顶点e条边的无向图的邻接表的表示，则 表 头 向 量 大 小 为，邻接 表 的 边 结 点 个 数 为。【青岛大学2 0 0 2 三、8 (2 分)】2 1 .遍
28、 历 图 的 过 程 实 质 上 是,b r e a t h-f i r s t s e a r c h 遍 历 图 的 时 间 复 杂 度；d e p t h-f i r s t s e a r c h 遍 历 图 的 时 间 复 杂 度 两 者 不 同 之 处 在 于，反映在数据结 构 上 的 差 别 是【厦门大学1 9 9 9 一、3 2 2 .已知一无向图 G=(V,E),其中 V=a,b,c,d,e E=(a,b),(a,d),(a,c),(d,c),(b,e)现用某一种图遍历方法从顶点a开始遍历图，得到的序列为a b e c d,则采用的是 遍历方法。【南京理工大学1 9 9 6
29、二、2 (2 分)】2 3 .一无向图 G (V,E),其中 V (G)=1,2,3,4,5,6,7,E (G)=(1,2),(1,3),(2,4),(2,5),(3,6),(3,7),(6,7)(5,1),对该图从顶点3开始进行遍历，去掉遍历中未走过的边，得一生成树G (V,E ),V (G O =V (G),E (G )=(1,3),(3,6),(7,3),(1,2),(1,5),(2,4),则采用的遍历方法是 o【南京理工大学1 9 9 7 三、6 (1 分)】2 4 .为了实现图的广度优先搜索，除了一个标志数组标志访问的图的结点外，还需存放被访问的结点以实现遍历。【南京理工大学1 9
30、9 9 二、9 (2 分)】2 5.按下图所示，画出它的广度优先生成树_ _ _ _ 和深度优先生成树_ _ _ _ _ _。【西安电子科技大学1 9 9 8 三、6 (5分)】晓=-优)2 6 .构 造 连 通 网 最 小 生 成 树 的 两 个 典 型 算 法 是。【北京科技大学1 9 9 8 一、52 7 .求图的最小生成树有两种算法，算法适合于求稀疏图的最小生成树。【南京理工大学2 001 二、6 (2 分)】2 8 .P r i m （普里姆）算法适用于求 的网的最小生成树；k r u s k a l （克鲁斯卡尔）算法适用于求 的网的最小生成树。【厦门大学1 9 9 9 一、4 2
31、 9 .克 鲁 斯 卡 尔 算 法 的 时 间 复 杂 度 为，它对 图较为适合。【中科院计算所1 9 9 9二、3 （2 分）】3 0.对于含N个顶点E条边的无向连通图，利用P r i m 算法生成最小代价生成树其时间复杂度为,利 用 K r u s k a l 算 法 生 成 最 小 代 价 生 成 树 其 时 间 复 杂 度 为。【长沙铁道学院 1 9 9 8 二、2 （4 分）】3 1 .下面描述的是 种构造最小生成树算法的基本思想。设要处理的无向图包括n个节点V I,V 2,.,V n,用相邻矩阵A表示，边的权全是正数。请在下列划线处填上正确叙述。（1）.若（V i,V j）是边，则
32、 A （i,j）的值等于,若（V i,V j）不是边，则 A （i,j）的 值 是 一 个 比 任 何 边 的 权,矩阵的对角线元素全为0。（2）.构造最小生成树过程中，若节点V i 已包括进生成树，就把相邻矩阵的对角线元素A（i,i）置成,若（V i,V j）已包括进生成树，就把矩阵元素A （i,j）置成。（3）.算法结束时，相邻矩阵中 的 元 素 指 出 最 小 生 成 树 的。【山东工业大学1 9 9 8二、4（6分）】3 2 .有一个用于n个顶点连通带权无向图的算法描述如下：（1）.设集合T 1 与 T 2,初始均为空；（2）.在连通图上任选一点加入T 1；（3）.以下步骤重复n-1
33、次：a.在 i 属于T l,j 不属于T 1 的边中选最小权的边：b.该边加入T 2。上述算法完成后，T 2 中共有 条边，该算法称 算法，T 2 中 的 边 构 成 图 的。【南京理工大学1 9 9 9 二、7 （4分）】3 3 .有向图G可 拓 扑 排 序 的 判 别 条 件 是。【长沙铁道学院1 9 9 8二、9（2 分）】3 4 .D i j kstra 最短路径算法从源点到其余各顶点的最短路径的路径长度按 次序依次产生,该算法弧上的权出现 情况时，不能正确产生最短路径。【南京理工大学1 9 9 9 二、8（4分）】3 5.求从某源点到其余各顶点的D i j kstra 算法在图的顶点
34、数为1 0,用邻接矩阵表示图时计算时间约为1 0 ms,则在图的顶点数为4 0,计算时间约为 ms。【南京理工大学2 0 0 0 二、3 （1.5 分）】3 6 .求最短路径的D i j kstra 算 法 的 时 间 复 杂 度 为。【哈尔滨工业大学2 0 0 1 一、5 （2分）】3 7 .有向图G=（V,E）,其 中 V（G）=0,1,2,3,4,5 ,用 三元组表示弧 a,b 及弧上的权d.E（G）为,则从源点0 到顶点3 的 最 短 路 径 长 度 是,经 过 的 中 间 顶 点 是。【南京理工大学1 9 9 8三、6 （4分）】3 8.上面的图去掉有向弧看成无向图则对应的最小生成树
35、的边权之和为 o【南京理工大学1 9 9 8三、7 （4分）】3 9 .设有向图有n 个顶点和e条边，进行拓扑排序时，总 的 计 算 时 间 为。【西安电子科技大学1 9 9 9 软件 一、7 （2分）】【武汉 大 学 2 0 0 0 、7】4 0 .A O V 网中，结点表示,边表示 o A O E 网中，结点表示,边表示。【北京理工大学2 0 0 1 七、3 （2分）】4 1 .在 A 0 E 网中，从源点到汇点路径上各活动时间总和最长的路径称为。【重庆大学2 0 0 0 ,2 42.在 A O V 网 中，存 在 环 意 味 着,这是 的；对程序的数据流图来说，它表明存在 o【厦门大学1
36、 9 9 9 一、2 4 3 .当一个A O V 网用邻接表表示时，可按下列方法进行拓扑排序。(1).查邻接表中入度为 的顶点，并进栈：(2).若栈不空，则输出栈顶元素V j,并退栈；查 V j 的直接后继V k,对 V k入度处理，处 理 方 法 是;(3).若栈空时，输出顶点数小于图的顶点数，说明有,否则拓扑排序完成。【南京理工大学1 9 9 6 二、3 (6 分)】4 4 .已知图的邻接表结构为：C O N ST v tx num=图的顶点数T Y P E v tx ptr=l.v tx num;a rc ptr=a rc no d e;a rc no d e=R E C O R D a
37、 d j v e x:v tx ptr;ne x ta rc:a rc ptr E N D;v e x no d e=R E C O R D v e x d a ta:和顶点相关的信息;f i rsta rc:a rc ptr E N D;a d j 1 i st二 A R R A Y v tx ptr O F v e x no d e;本算法是实现图的深度优先遍历的非递归算法。其中，使用一个顺序栈sta c k。栈顶指针为t o p o v is it ed 为标志数组。P R O C d fs(g:ad jl is t;v O:v t x p t r);t o p=O;w r it e(v
38、 O);v is it ed v O:=t u r e;p:=gv O.fir s t ar c;WH I L E (t o p O O)O R(p O N I L)D OWH 1L E XD D Ov:=p 二 ad jv ex;I F (2)T H E N p:=p n ex t ar cE L S E w r it e(v);v is it 6d v:=t r u e;t o p:=t o p+l;s t ac k t o p:=p;(3)I F t o p O O T H E N p:=s t ac k t o p;t o p:=t o p-l;X4)E N D P.同济大学 2000
39、 二、2(10 分)45.下面的算法完成图的深度优先遍历，请填空。P R O G R A M gr ap h t r av er;CO N S T n l=m ax _n o d e_n u m b er;T YP E v t x p t r=l.n l;v t x p t r 0=0.n l;ar c p t r=ar c n o d e;ar c n o d e=R E C0R D v ex i,v ex j:v t x p t r;n ex t i,n ex t j:ar c p t r;E N D;v ex n o d e=R E CO R D v ex d at a:c har;fi
40、r s t in,fir s t o u t:ar c p t r;E N D;gr ap h=A R R A Yv t x p t r O O F v ex n o d e;VA R ga:gr ap h;n:in t eger;v is it ed:A R R A Yv t x p t r O O F b o o l ean ;F U N C o r d er (g:gr ap h;v:c har):v t x p t r;(1);i:=n;WH I L E gi.v ex d at aO v D Oo r d er:=i;E N D F；P R O C c r eat(v ar g:gr
41、 ap h);r ead l n(n,e);F O R i:=1 T O n D O r ead l n(gi.v ex d at a);gi.fir s t in :=N I L ;gi.fir s t o u t:=N I L;F O R k:=1 T O e D O r ead l n (v t,v h);i :=o r d er (g,v t);j:=o r d er (g,v h);n ew (p);p v ex i:=i;p v ex j:=jp n ex t.i:=(2);(3):=p;p n ex t i:=:(4);:=p;E N D P;F U N C fir s t ad
42、 j(g:gr ap h;v:c har):v t x p t r O;i:=o r d er(g,v);p:=gi.fir s t o u t;I F p O N I L T H E N fir s t ad j:=(6)ELSE fir s t ad j:=0;E N D F;F U N C n ex t ad j(g:gr ap h;v:c har;w:c har):v t x p t r O;i：=o r d er (g,v);j:=o r d er (g,w);p:=(7);WH I L E(p O N I L )A N D (p v ex jO j)D O(8);I F (9)A
43、N D(1 0)T H E N n ex t ad j:二 p 二 n ex t i v ex j E L S E n ex t ad j:=0;E N D F;P R O C d fs(g:gr ap h;v O:c har);w r it e(v 0:2);v is it ed o r d er(g,v O):=t r u e;w:=(11);WH I L E w 0 D OI F (12)T H E N d fs(g,gw.v ex d at a);w-(13);E N D P;P R O C t r av er(g:gr ap h);F O R i:=1 T O n D O v is
44、it ed i:=fal s e;F O R i:=l T O n D O I F N O T v is it ed i T H E N d fs(g,gi.v ex d at a);E N D P;B E G I Nc r eat(ga);t r av er(ga);END.【北方交通大学1999三(20分)】46.n 个顶点的有向图用邻接矩阵ar r ay 表示，下面是其拓扑排序算法，试补充完整。注：(1).图的顶点号从0 开始计；(2).in d egr ee是 有 n个分量的一维数组，放顶点的入度；(3).函 数 c r ein 用于算顶点入度；(4).有三个函数p u s h(d a
45、t a),p o p (),c hec k ()其含义为数据d at a进栈，退栈和测试栈是否空(不空返回1,否则0)。c r ein (ar r ay ,in d egr ee,n)fo r (i=0;i n;i+)in d egr eei=(1)fo r (i=0,i n;i+)fo r (j-0;j n;j+)in d egr eei +=ar r ay(2)(3);)t o p s o r t (ar r ay,in d egr ee,n)c o u n t=(4)fo r (1=0;i n;i+)if(5)p u s h(i)w hil e(c hec k()v ex=p o p()
46、;p r in t f(v ex);c o u n t+;fo r (i=0;i n;i+)k=ar r ay(6)if(7)in d egr eei ;if(8)p u s h(i);)if(c o u n t n)p r in t f(图有回路)；【南京理工大学2000三、4(6分)】47.假设给定的有向图是用邻接表表示，作为输入的是图中顶点个数n 和边的个数m,以及图的m条边。在下面的程序中，我们用r ead d at a程序过程输入图的信息，并建立该图的邻接表；利 用 t o p o l 程序过程获得图中顶点的一个拓扑序列。P R O G R A M t o p o l o r d e
47、r (in p u t ,o u t p u t);CO N S T m ax n=20;T YP E n o d ep t r=n l t y p e;n l t y p e=R E CO R D n u m :in t eger ;l in k :n o d ep t r E N D ;c ht y p e=R E CO R D c o u n t :in t eger ;head :n o d ep t r E N D ;VA R c h:A R R A Y 1.m ax n O F c ht y p e;m ,n ,t o p :in t eger ;P R O CE D U R E
48、r ead d at a;VA R i,j,u ,v :in t eger ;p :n o d ep t r ;B E G I Nw r it e(in p u t v er t ex n u m b er n=)；r ead I n (n);w r it e(in p u t ed ge n u m b er m=);r ead l n(m);F O R i:=1 T O n D O B E G I N c hi.c o u n t:=0;c hi.head:二 N I L E N D;w r it el n(,in p u t ed ges :F O R j:=1 T O m D OB E
49、 G I N w r it e(j:3,:);r ead l n(u ,v );n ew(p );c hv.c o u n t:=c hv.c o u n t+1;p n u m:=v;(2);E N DE N D ;P R O CE D U R E t o p o l ;VA R i,j,k:in t eger;t:n o d ep t r ;B E G I Nt o p:=0;F O R i:=1 T O n D OI F c hi.c o u n t=0 T H E N B E G I N c hi.c o u n t :=t o p ;t o p :=i E N D;i:=0;WH I
50、 L E 1 3)D OB E G I N (4);(5);w r it e(j:5);i:=i+1;t:=c hj.head ;WH I L E t O N I L D OB E G I N k :=t.n u m ;c hk J.c o u n t:=c hk.c o u n t -1;I F c hk.c o u n t=O T H E N B E G I N c hk.c o u n t:二 t o p;t o p:二 kE N D;(6)_;E N DE N D ;w r it ein;I F i n T H E N w r it ein (t he n et w o r k has