数据结构第七章考试题库(含答案).pdf

《数据结构第七章考试题库(含答案).pdf》由会员分享，可在线阅读，更多相关《数据结构第七章考试题库(含答案).pdf（59页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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分）】A.n-l B.

2、n C.n+14.要连通具有n 个顶点的有向图，至少需要（D.n lo g n；）条边。【北京航空航天大学2 0 0 0 一、6（2分】5.6.A.n-l B.nn个结点的完全有向图含有边的数目A.n*n B .n （n+1 ）一个有n 个结点的图，最 少 有（A.0 B.1C.n+1 D.2 n（）o【中山 大 学 1 9 9 8 二、9 （2分】C.n /2 D.n*（n 1）个连通分量，最 多 有（）个连通分量。C.n-l D.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 4A.5 B.6 C.8 D.99.用 DFS 遍历一个无环有向图，并在DFS 算法退栈返回时打印相应的顶点，则输出的顶点序列是（）oA.逆拓扑有序 B.拓扑有序 C.无序的【中科院软件所1 9 9 8 1 0.下面结构中最适于表示稀疏无向图的是（）,适于表示稀疏有向图的是（）。A.邻接矩阵 B.逆邻接表 C.邻接多重表 D.十字链表 E.邻接表【北京工业大学2 0 0 1 一、3

4、（2分）】1 1.下列哪一种图的邻接矩阵是对称矩阵？（）【北方交通大学2 0 0 1 一、1 1 （2分】A.有向图 B,无向图 C.A 0 V 网 D.A O E网1 2.从邻接阵矩 可以看出，该图共有（）个顶点；如果是有向图该图共有（）条弧；如果是无向图，则 共 有（）条边。【中科院软件所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个顶点的图用邻接矩阵A表示时，顶点V i 的度是()。【南京理工大学1 9 9 8一、4(2

5、分】A.B.C.1).+1 4.用相邻矩阵A表示图，判定任意两个顶点V i 和 V j 之间是否有长度为m的路径相连,则只要检查()的第i 行第j 列的元素是否为零即可。【武汉大学2 0 0 0 二、7 A.m A B.A C.A D.A m-11 5 .下列说法不正确的是()。【青岛大学2 0 0 2 二、9 (2 分】A.图的遍历是从给定的源点出发每一个顶点仅被访问一次 C.图的深度遍历不适用于有向图B.遍历的基本算法有两种：深度遍历和广度遍历 D.图的深度遍历是一个递归过程1 6 无 向 图 G=(V,E),其 中：V=a,b,c,d,e,f ,E=(a,b),(a,e),(a,c),(

6、b,e),(c,f),(f,d),(e,d),对该图进行深度优先遍历，得到的顶点序列正确的是()。【南京理工大学20 0 1 一、14 (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,b17.设图如右所示，在下面的5 个序列中，符合深度优先遍历的序列有多少？()c【南京理工大学20 0 0 、20 (1.5 分】ae b d fc a c f d e b a e d f c bA.5个 B.4个 C.3 个a e f d c bD.2 个a e f d b第 17题图 第 18题图18.下图中给出由7 个顶点组成的无向图

7、。从顶点1 出发，对它进行深度优先遍历得到的序列是()，而进行广度优先遍历得到的顶点序列是()。【中科院软件所1999六、2-(1)(2 分 .A.135 4 267 B.134 765 2 C.15 34 276 1).124 765 3 E.以上答案均不正确.A.15 34 267 B.17264 5 3 C.135 4 276 I).124 765 3 E.以上答案均不正确19.下面哪一方法可以判断出一个有向图是否有环(回路)：【东北 大 学 20 0 0 4、2(4 分】A.深度优先遍历 B.拓扑排序 C.求 最 短 路 径 D.求关键路径20 .在图采用邻接表存储时，求最小生成树的P

8、 r i m 算法的时间复杂度为()。A.0(n)B.O(n+e)C.0(n2)D.0(n3)【合肥工业大学20 0 1 一、2(2分】21.下面是求连通网的最小生成树的p r i m 算法:集合V T,E T 分别放顶点和边,初始为(1),下面步骤重复n-1次：a：(2)；b：(3)；最后：(4 )。【南京理工大学1997 一、11_ 14(8分(1).A.V T,E T 为空C.V T 为网中任意一点，E T 为空(2).A.选 i 属于V T,j 不属于V T,且B.选 i 属于V T,j 不属于V T,且B.V T 为所有顶点，E T 为空D.V T 为空，E T 为网中所有边(i,j

9、)上的权最小(i,j)上的权最大C.选 i 不属于V T,j 不属于V T,且(i,D.选 i 不属于V T,j 不属于V T,且(i,j)上的权最小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 加入V T,(i,j)加入B.不在E T 中的边构成最小生成树D.E T 中无回路时，为生成树，否则无解22.(1).求从指定源点到其余各顶点的迪杰斯特拉(D i j k s t r

10、 a)最短路径算法中弧上权不能为负的原因是在实际应用中无意义；(2).利用D i j k s t r a 求每一对不同顶点之间的最短路径的算法时间是0(/)；(图用邻接矩阵表示)(3).F lo y d求每对不同顶点对的算法中允许弧上的权为负，但不能有权和为负的回路。上面不正确的是()。【南京理工大学20 0 0 一、21(1.5 分】A.(1),(2),(3)B.(1)C.(1),(3)D.(2),(3)23.当各边上的权值()时，B F S 算法可用来解决单源最短路径问题。【中科院计算所20 0 0一、3(2分】A.均相等 B.均互不相等 C.不一定相等24 .求解最短路径的F lo y

11、d算法的时间复杂度为()。【合肥工业大学1999 一、2(2分】A.0 (n)B.0 (n+c)C.0 (n*n)D.0 (n*n*n)25 .已知有向图 G=(V,E),其中 V=%,V e,V j,E=,V;(,V D,G 的拓扑序列是()。A.V VT B.Vb V3,V2,V6,V4,V5,V7C.VI,V3)V4)V5(V2)V6)V 7 D.V 1,V2)V5)V3)V4)V6 V7【北京航空航天大学20 0 0 一、7(2分】26.若一个有向图的邻接距阵中，主对角线以下的元素均为零，则该图的拓扑有序序列()。A.存在 B.不存在【中科院计算所1 9 9 8 二、6 (2分)】【中

12、国科技大学1 9 9 8 二、6(2分】27 .一个有向无环图的拓扑排序序列()是唯一的。【北京邮电大学20 0 1 一、3 (2分】A.一定 B.不一定28 .在有向图G 的拓扑序列中，若 顶 点 Vi在 顶 点 Vj之前，则下列情形不可能出现的是()。A.G 中有弧 B.G 中有一条从V i 到 V j 的路径C.G 中没有弧 V i,V j D.G 中有一条从V j 到 V i 的路径【南京理工大学20 0 0 一、9 （1.5 分】2 9.在用邻接表表示图时，拓扑排序算法时间复杂度为（）。A.0（n）B.O（n+e）C.0（n*n）D.0（n*n*n）【合肥工业大学20 0 0 一、2

13、（2 分）】【南京理工大学20 0 1 一、9 （1.5 分】【青岛 大 学 20 0 2二、3 （2 分】3 0 .关键路径是事件结点网络中（）。【西安电子科技大学20 0 1 应 用 一、4 （2 分】A.从源点到汇点的最长路径 B.从源点到汇点的最短路径C.最长回路 D.最短回路3 1 .下面关于求关键路径的说法不正确的是（）。【南京理工大学1 9 9 8、1 2（2 分】A.求关键路径是以拓扑排序为基础的B.一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同C.一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差D.关键活动一定位于关键路径上3

14、2.下列关于A 0 E 网的叙述中，不正确的是（）。A.关键活动不按期完成就会影响整个工程的完成时间B.任何一个关键活动提前完成，那么整个工程将会提前完成C.所有的关键活动提前完成，那么整个工程将会提前完成D.某些关键活动提前完成，那么整个工程将会提前完成【北方交通大学1 9 9 9 一、7 （3分）】【北京工业大学1 9 9 9 一、1 （2 分）】二、判断题1 .树中的结点和图中的顶点就是指数据结构中的数据元素。（）【青岛大学20 0 1 四、1 （1分】2.在 n个结点的无向图中，若边数大于n-1,则该图必是连通图。（）【中科院软件所1 9 9 7一、4（1 分】3 .对有n个顶点的无向

15、图，其边数e与各顶点度数间满足下列等式6=o （）【南京航空航天大学1 9 9 6 六、4 （1 分】4 .有 e条边的无向图，在邻接表中有e个结点。（）【南京理工大学1 9 9 8 二、5 （2分】5 .有向图中顶点V的度等于其邻接矩阵中第V行中的1 的个数/”合肥工业大学20 0 1二、7（1 分】6 .强连通图的各顶点间均可达。（）【北京邮电大学20 0 0 一、3 （1 分】7 .强连通分量是无向图的极大强连通子图。（）【北京邮电大学20 0 2 一、7 （1 分】8 .连通分量指的是有向图中的极大连通子图。（）【燕山大学1 9 9 8 二、4 （2 分】9 .邻接多重表是无向图和有向

16、图的链式存储结构。（）【南京航空航天大学1 9 9 5 五、5（1 分】1 0 .十字链表是无向图的一种存储结构。（）【青岛大学20 0 1 四、7 （1 分）】1 1 .无向图的邻接矩阵可用一维数组存储。（）【青岛 大 学 20 0 0 四、5 （1 分】1 2.用邻接矩阵法存储个图所需的存储单元数目与图的边数有关。（）【东南 大 学 20 0 1 、4 （1 分】【中山 大 学 1 9 9 4 一、3 （2 分】1 3 .有n个顶点的无向图，采用邻接矩阵表示，图中的边数等于邻接矩阵中非零元素之和的一半。（）【北京邮电大学1 9 9 8 一、5 （2 分】1 4 .有向图的邻接矩阵是对称的。

17、（）【青岛大学20 0 1 四、6 （1 分】1 5 .无向图的邻接矩阵定是对称矩阵，有向图的邻接矩阵一定是非对称矩阵。（）【东南 大 学 20 0 1 一、3 （1 分）】【哈尔滨工业大学1 9 9 9 三、4 1 6 .邻接矩阵适用于有向图和无向图的存储，但不能存储带权的有向图和无向图，而只能使用邻接表存储形式来存储它。（）【上海海运学院1 9 9 5 一、9 （1 分）1 9 9 7 一、8 （1 分）1 9 9 8 一、9 （1 分】1 7 .用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小与图中结点个数有关，而与图的边数无关。（）【上海海运学院1 9 9 6 一

18、、8 （1 分）1 9 9 9 一、9 （1 分】1 8 .一个有向图的邻接表和逆邻接表中结点的个数可能不等。（）【上海交通大学1 9 9 8 、1 2 1 9 .需要借助于一个队列来实现D F S 算法。（）【南京航空航天大学1 9 9 6 六、8 （1 分】2 0 .广度遍历生成树描述了从起点到各顶点的最短路径。（）【合肥工业大学2 0 0 1 二、8 （1 分】2 1 .任何无向图都存在生成树。（）【北京邮电大学2 0 0 0 一、1 （1 分】2 2 .不同的求最小生成树的方法最后得到的生成树是相同的.（）【南京理工大学1 9 9 8二、3 （2分】2 3 .带权无向图的最小生成树必是

19、唯一的。（）【南京航空航天大学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 .连通图上各边权值均不相同，则该图的最小生成树是唯一-的。（）【哈尔滨工业大学1 9 9 9 三、3 2 7 .带权的连通无向图的最小（代价）生 成 树（支撑树）是唯一的。（）【中山大学1 9 9 4一、1 0 （2分】2 8 .最小生成树的KR U S KAL算法是一种贪心法（G R E E D Y）。（）【华南理工大学2 0 0 2 、6

20、（1 分 2 9 .求最小生成树的普里姆（P r i m）算法中边上的权可正可负。（）【南京理工大学1 9 9 8二、2 （2分】3 0 .带权的连通无向图的最小代价生成树是唯一的。（）【东南 大 学 2 0 0 1 一、5 （1 分】3 1 .最小生成树问题是构造连通网的最小代价生成树。（）【青岛大学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-Il,J 一定是p a t h

21、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 、7 （1 分】3 6 .无环有向图才能进行拓扑排序。（）【青岛大学2 0 0 2 、7 （1 分）2 0 0 1 、8 （1分】3 7 .有环图也能进行拓扑排序。（）【青岛大学2 0 0 0 四、6 （1 分】3 8 .拓扑排序的有向图中，最多存在一条环路。（）【大连海事大学2 0 0 1 一、6 （1 分】

22、3 9 .任何有向图的结点都可以排成拓扑排序，而且拓扑序列不唯一。（）【上海交通大学1 9 9 8 一、1 3 4 0 .既使有向无环图的拓扑序列唯一，也不能唯确定该图。（）【合肥工业大学2 0 0 1二、6 （1 分】4 1 .若一个有向图的邻接矩阵对角线以下元素均为零，则该图的拓扑有序序列必定存在。（）【中科院软件所1 9 9 7 一、5 （1 分】4 2 .A0 V网的含义是以边表示活动的网。（）【南京航空航天 大 学 1 9 9 5 五、7 （1 分】4 3 .对一个AO V网，从源点到终点的路径最长的路径称作关键路径。【南京航空航天大学1 9 9 5五、9（1 分】4 4 .关键路径

23、是A O E 网中从源点到终点的最长路径。（）【青岛大学2 0 0 0 四、1 0（1 分】4 5.A 0 E 网一定是有向无环图。（）【青岛大学2 0 0 1 一、9 （1 分】4 6 .在表示某工程的A 0 E 网中，加速其关键路径上的任意关键活动均可缩短整个工程的完成时间。（）【长沙铁道学院1 9 9 7 、2 （1 分）】4 7 .在 A 0 E 图中，关键路径上某个活动的时间缩短，整个工程的时间也就必定缩短。（）【大连海事大学2 0 0 1 、1 5（1 分】4 8 .在 A 0 E 图中，关键路径上活动的时间延长多少，整个工程的时间也就随之延长多少。（）【大连海事大学2 0 0 1

24、 一、1 6 （1 分】4 9 .当改变网上某一关键路径上任一关键活动后，必将产生不同的关键路径。【上海交通大学 1 9 9 8 一、1 4 三、填空题L判 断 一 个 无 向 图 是 一 棵 树 的 条 件 是。2.有向图G的 强 连 通 分 量 是 指。【北京科技大学1 9 9 7 一、7 3.一个连通图的 是一个极小连通子图。【重庆大学2 0 0 0 、1】4.具 有 1 0 个顶点的无向图，边 的 总 数 最 多 为。【华中理工大学2 0 0 0 一、7 （1 分】5.若用n表示图中顶点数目，则有 条边的无向图成为完全图。【燕山大学1 9 9 8 、6 （1 分】6 .设 无 向 图

25、G有 n个顶点和e条边，每个顶点Vi的度为d i （l=i =n ，则e=【福州 大 学 1 9 9 8 二、2 （2分）】7 .G是一个非连通无向图，共有2 8 条边，则该图至少有 个顶点。【西安电子科技大2 0 0 1 软件 一、8 （2分】8 .在有n个顶点的有向图中，若要使任意两点间可以互相到达，则至少需要 条弧。【合肥工业 大 学 2 0 0 0 三、8 （2 分】9 .在有n 个顶点的有向图中，每 个 顶 点 的 度 最 大 可 达。【武汉 大 学 2 0 0 0 一、3 1 0 .设 G为具有N个顶点的无向连通图，则 G中至少有 条边。【长沙铁道学院1 9 9 7 二、2 （2分

26、）】1 1 .n个顶点的连通无向图，其 边 的 条 数 至 少 为。【哈尔滨工业大学2 0 0 0 二、2 （1分】1 2 .如果含n 个顶点的图形形成一个环，则它有 棵生成树。【西安电子科技大学2 0 0 1 软 件 一、2 （2分】1 3 .N个顶点的连通图的生成树含有 条边。【中山大学1 9 9 8 一、9 (1 分】1 4 .构造n个结点的强连通图，至少有 条弧。【北京轻工业学院2 0 0 0 一、4 (2 分)1 5.有 N个顶点的有向图，至少需要量 条弧 q 爪才能保证是连通的。【西南交通大学2 0 0 0 一、3 1 6 .右图中的强连通分量的个数为()个。C T X/【北京邮电

27、大学2 0 0 1 二、5(2 分】1 7 .N个顶点的连通图用邻接矩阵表示时，该矩阵 至少有 个非零元素。【中科院计算所1 9 9 8 、6 (1 分)】【中国科技大学1 9 9 8 、6 (1 5/6 分 1 8 .在图G的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该顶点的：对 于 有 向 图 来 说 等 于 该 顶 点 的。【燕山大学2 0 0 1 二、5(3 分】1 9 .在有向图的邻接矩阵表示中，计 算 第 I个 顶 点 入 度 的 方 法 是。【青岛大学2 0 0 2三、7 (2 分】2 0 .对于一个具有n个顶点e条边的无向图的邻接表的表示，则 表 头 向 量

28、 大 小 为,邻接 表 的 边 结 点 个 数 为。1青岛大学2 0 0 2 三、8 (2 分】2 1 .遍 历 图 的 过 程 实 质 上 是.b r e a t h-f i r s t s e a r c h 遍 历 图 的 时 间 复 杂 度；d e pt h-f i r s t s e a r c h 遍 历 图 的 时 间 复 杂 度,两 者 不 同 之 处 在 于,反映在数据结构 上 的 差 别 是。【厦门大学19 9 9 一、322.已知一无向图 G=(V,E),其中 V=a,b,c,d,e E=(a,b),(a,d),(a,c),(d,c),(b,e)现用某一种图遍历方法从顶点

29、a开始遍历图，得到的序列为a b e cd,则采用的是 遍历方法。【南京理工大学19 9 6 二、2(2分】23.一无向图 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 开始进行遍历，去掉遍历中未走过的边，得 一生成树生(V,E),V (G)=V (G),E (G D =(1,3),(3,6),(7,3),(1,2),(1,5),(2,4),则 采 用 的 遍 历 方 法 是。【南京理工大学19 9 7 三、6 (1分】24.为了实现图的广度优先搜索，除了一

30、个标志数组标志己访问的图的结点外，还需存放被访问的结点以实现遍历。【南京理工大学19 9 9 二、9 (2分】25 .按下图所示，画出它的广度优先生成树 和深度优先生成树【西安电子科技大学19 9 8 三、6 (5 分】26 .构 造 连 通 网 最 小 生 成 树 的 两 个 典 型 算 法 是。【北京科技大学19 9 8 一、5 27 .求图的最小生成树有两种算法，算法适合于求稀疏图的最小生成树。【南京理工大学2001二、6 (2分】28 .P r i m (普里姆)算法适用于求 的网的最小生成树；k r u s k a l (克鲁斯卡尔)算法适用于求 的网的最小生成树。【厦门大学19 9

31、 9 一、429 .克 鲁 斯 卡 尔 算 法 的 时 间 复 杂 度 为，它对 图较为适合。【中科院计算所19 9 9二、3(2分】30.对于含N 个顶点E条边的无向连通图，利用P r i m 算法生成最小代价生成树其时间复杂度为，利用K r u s k a l 算 法 生 成 最 小 代 价 生 成 树 其 时 间 复 杂 度 为。【长沙铁道学院 19 9 8 二、2(4 分)】31.下面描述的是一种构造最小生成树算法的基本思想。设要处理的无向图包括n个节点V I,V 2,.,V n,用相邻矩阵A表示，边的权全是正数。请在下列划线处填上正确叙述。(1).若(V i,V j)是边，则 A (

32、i,j)的值等于,若(V i,V j)不是边，则 A (i,j)的 值 是 一 个 比 任 何 边 的 权，矩阵的对角线元素全为0。(2).构造最小生成树过程中，若节点V i 已包括进生成树，就把相邻矩阵的对角线元素A (i,i)置成,若(V i,V j)已包括进生成树，就把矩阵元素A (i,j)置成。(3).算法结束时，相邻矩阵中 的 元 素 指 出 最 小 生 成 树 的。【山东工业大学19 9 8二、4(6 分 32.有一个用于n个顶点连通带权无向图的算法描述如下：(1).设集合U与 T 2,初始均为空；(2).在连通图上任选一点加入T1；(3).以下步骤重复n-1 次：a.在 i 属于

33、Tl,j 不属于T 1 的边中选最小权的边；b.该边加入T2。上述算法完成后，T 2 中共有 条边，该算法称 算法，T 2 中 的 边 构 成 图 的。【南京理工大学1 9 9 9 二、7(4 分】3 3 .有向图G可 拓 扑 排 序 的 判 别 条 件 是。【长沙铁道学院1 9 9 8 二、9(2 分)】3 4 .D i j k s t r a 最短路径算法从源点到其余各顶点的最短路径的路径长度按 次序依次产生,该算法弧上的权出现 情况时，不能正确产生最短路径。【南京理工大学1 9 9 9 二、8 (4 分】3 5.求从某源点到其余各顶点的D i j k s t r a 算法在图的顶点数为1

34、 0,用邻接矩阵表示图时计算时间约为1 0 m s,则在图的顶点数为4 0,计算时间约为 m s。【南京理工大学2 0 0 0 二、3 (1.5 分】3 6 .求最短路径的D i j k s t r a 算 法 的 时 间 复 杂 度 为。【哈尔滨工业大学2 0 0 1 一、5 (2分】3 7.有向图G=(V,E),其 中 V(G)=0,1,2,3,4,5 ,用 三元组表示弧 及弧上的权d.E(G)为 ,则从源点0 到顶点3 的 最 短 路 径 长 度 是,经 过 的 中 间 顶 点 是。【南京理工大学1 9 9 8三、6 (4 分】3 8 .上面的图去掉有向弧看成无向图则对应的最小生成树的边

35、权之和为。【南京理工大学1 9 9 8 三、7(4 分】3 9 .设有向图有n 个顶点和e 条边，进行拓扑排序时，总 的 计 算 时 间 为。【西安电子科技大学1 9 9 9 软件 一、7(2 分)】【武汉 大 学 2 0 0 0 、7】4 0 .A0 V网中，结点表示，边表示 o AO E 网中，结点表示，边表示【北京理工大学2 0 0 1 七、3 (2 分】4 1 .在 AO E 网中，从源点到汇点路径上各活动时间总和最长的路径称为。【重庆大学2 0 0 0 s 2 4 2 .在 AO V网 中，存 在 环 意 味 着,这是 的；对程序的数据流图来说，它表明存在 0【厦门 大 学 1 9

36、9 9 一、2 4 3 .当一个AO V网用邻接表表示时，可按下列方法进行拓扑排序。(1).查邻接表中入度为 的顶点，并进栈：(2).若栈不空，则输出栈顶元素V j,并退栈；查V j 的直接后继V k,对 Vk 入度处理，处 理 方 法 是；(3).若栈空时，输出顶点数小于图的顶点数，说明有,否则拓扑排序完成。【南京理工大学1 9 9 6 二、3 (6 分】4 4 .已知图的邻接表结构为：C O N ST v t x n um=图的顶点数TY PE v t x pt r=l.v t x n um;a r c pt r=a r c n o d e;a r c n o d e=RE C O RD

37、a d j v e x:v t x pt r;n e x t a r c:a r c pt r E N D;v e x n o d e=RE C O RD v e x d a t a:和顶点相关的信息;f i r s t a r c:a r c pt r E N D;a d j l i s t=ARRAY v t x pt r O F v e x n o d e;本算法是实现图的深度优先遍历的非递归算法。其中，使 用 个顺序栈s ta ck。栈顶指针为to p o v is ited为标志数组。P R O C dfs(g:a djlis t;v O:v tx p tr);to p=0;w ri

38、te(v O);v is ited v O :=tu re;p:=g v O .firs ta rc;W HIL E(to p O O)O R (p O N IL)DOWH I LE C 1)D O v:=p a djv ex;IF(2)THEN p:=p nex ta rcEL SE w rite(v);v is ited v :=tru e;to p:=to p+l;s ta ckfto p :=p;(3)IF to p O O THEN p:=s ta ck to p ;to p:=to p-l;EN DP.同济大学 2000 二、2(10 分)45.下面的算法完成图的深度优先遍历，请填

39、空。P R O GR AM gra p h_ tra v er;CO N ST nl=ma x _ no de nu mb er;TY P E v tx p tr=l.nl;v tx p tr0=0.nl;a rcp tr=a rcno de;a rcno de=R ECO R D v ex i,v ex j:v tx p tr;nex ti,nex tj:a rcp tr;EN D;v ex no de=R ECO R D v ex da ta:cha r;firs tin,firs to u t:a rcp tr;EN D;gra p h=AR R AY v tx p trO O F v

40、ex no de;V AR ga:gra p h;n:integer;v is ited:AR R AY v tx p trO O F b o o lea n;FU N C o rder(g:gra p h;v:cha r):v tx p tr;(1);i:=n;W HIL E g i.v ex da ta O v DO i:=i-l;o rder:=i;EN DF；P R O C crea t(v a r g:gra p h);rea dln(n,e);FO R i:=1 TO n DO rea dln(g i.v ex da ta);g i.firs tin:=N IL ;g i.firs

41、 to u t:=N IL;FO R k:=1 TO e DO rea dln(v t,v h);i:=o rder(g,v t);j:=o rder(g,v h);new (p);p v ex i:=i;p v ex j:=jp nex ti:=(2);(3):=p;p nex ti:=:(4);(5):=p;EN DP;FU N C firs ta dj(g:gra p h;v:cha r):v tx p trO;i:=o rder(g,v);p:=g i.firs to u t;IF p O N IL THEN firs ta dj:二幽_ _ _ _ _ _ _EL SE firs t

42、a dj:=0;EN DF;FU N C nex ta dj(g:gra p h;v:cha r;w:cha r):v tx p trO;i:=o rder(g,v);j:=o rder(g,w);p:=(7);W HIL E(p O N IL )AN D(p v ex jO j)D0(8);IF 侬 _ _ _ _ _ _AN D(10)THEN nex ta dj:=p nex ti v ex j EL SE nex ta dj:=0;EN DF;P R O C dfs(g:gra p h;v O:cha r);w rite(v O:2);v is ited o rder(g,v 0):=

43、tru e;w:=(ll);W HIL E w O O DO IF(12)THEN dfs(g,g w .v ex da ta);w:=(13);EN DP;P R O C tra v er(g:gra p h);FO R i:=1 TO n DO v is ited i:=fa ls e;FO R i:=1 TO n DO IF N O T v is ited i THEN dfs(g,g i.v ex da ta);EN DP;BEGINcrea t(ga);tra v er(ga);E ND.【北方交通大学1999三(20分】46.n个顶点的有向图用邻接矩阵a rra y表示，下面是其拓

44、扑排序算法，试补充完整。注(1).图的顶点号从0开始计；(2).indegree是 有n个分量的一维数组，放顶点的入度；(3).瞰 crein用于算顶点入度；(4).有三个函数p u s h(da ta),p o p(),check()其含义为数据da ta进栈，退栈和测试栈是否空(不空返回1,否则0)。crein(a rra y ,indegree,n)fo r(i=0;in;i+)indegree i=(1)fo r(i=0,in;i+)fo r(j=0;jn;j+)indegree i +=a rra y _(2)(3);)to p s o rt(a rra y,indegree,n)c

45、o u nt=(4)fo r(i=0;in;i+)if(5)p u s h(i)w hile(check()v ex=p o p();p rintf(v ex);co u nt+;fo r(i=0;in;i+)k=a rra y(6)if(Q)indegree i ;if(8)p u s h(i);)if(co u ntn)p rintf(“图有回路”)；【南京理工大学2000三、4(6分】47.假设给定的有向图是用邻接表表示，作为输入的是图中顶点个数n 和边的个数叫 以及图的m 条边。在下面的程序中，我们用rea dda ta 程序过程输入图的信息，并建立该图的邻接表；利用to p o l程

46、序过程获得图中顶点的一个拓扑序列。P R O GR AM to p o l_ o rder(inp u t,o u tp u t);CO N ST ma x n=20;TY P E no dep tr=nlty p e;nlty p e二 R ECO R D nu m:integer;1 ink:no dep tr EN D;chty p e=R ECO R D co u nt:integer;hea d:no dep tr EN D;V AR ch:AR R AY 1.ma x n O F chty p e;m,n,to p :integer;P R O CEDU R E rea dda t

47、a ;V AR i,j,u ,v :integer;p :no dep tr;BEGINw rite(inp u t v ertex nu mb er n=，);rea dln(n);w rite(inp u t edge nu mb er m=)；rea dln(m);FO R i:=l TO n DO BEGIN ch i.co u nt:=0;ch i.hea d:=N IL EN D;w ritein(7 inp u t edges :FO R j:=1 TO m DOBEGIN w rite(j:3,:);rea dln(u ,v );new(p );ch v .co u nt:=c

48、h v ,co u nt+1;p nu m:=v;(1);(2);EN DEN D;P R O CEDU R E to p o l;V AR i,j,k:integer;t:no dep tr;BEGINto p:=0;FO R i :=1 TO n DOIF ch i.co u nt=0 THEN BEGIN ch i.co u nt:=to p ;to p :=i EN D;i:=0;W HIL E(3)DOBEGIN (4);w rite(j:5);i:=i+1;t:=ch j.hea d;W HIL E tO N IL DOBEGIN k:=t.nu m;ch k.co u nt:=c

49、h k.co u nt-1 ;IF ch k.co u nt=0 THEN BEGIN ch k.co u nt:=to p;to p:=kEN D;(6);EN DEN D;w ritein;IF in THEN w riteIn(the netw o rk ha s a cy cle!)EN D;BEGINrea dda ta ;w ritein(o u tp u t to p o l o rder:;to p o lEN D.【复旦 大 学 1995三(18分】4 8.如下为拓扑排序的C程序，(1).列出对右图执行该程序后的输出结果。(2).在程序空白处填上适当语句。v o id to

50、p s o rt(hdno des gra p h ,int n)int i,j,k,to p;no de_ p o inter p tr;to p=-l;fo r(i=0;in;i+)if(Igra p hL i.co u nt)gra p h i.co u nt=to p;to p=i;fo r(i=0;ilink)k=p tr-v ertex;gra p h k.co u nt;if(3)_ _ _ _ _)gra p h k.co u nt=to p;to p=k;)【浙江 大 学 2000六(15分)】四、应用题1.(1).如果G 1 是一个具有n 个顶点的连通无向图，那么G 1 最