第七章图 选择题 1.图中有关路径的定义是()。【北方交通大学2001一、24(2分)】 A.由顶点和相邻顶点序偶构成的边所形成的序列 由不同顶点所形成的序列 C.由不同边所形成的序列 D.上述定义都不是 设无向图的顶点个数为n,则该图最多有()条边 B.n(n-1)/2 C.n(n+1)/2 【清华大学1998、5(2分)】【西安电子科技大1998一、6(2分)】 【北京航空航天大学1999、7(2分)】 3.一个n个顶点的连通无向图,其边的个数至少为()。【浙江大学1999四、4(4 分)】 4.要连通具有n个顶点的有向图,至少需要()条边。【北京航空航天大学2000一 6(2分)】 A.n-1 C.n+1 5.n个结点的完全有向图含有边的数目 )。【中山大学1998二、9(2分)】 A. n*kn B.n(n+1) C.n/2 D.n*(n-1) 6.一个有n个结点的图,最少有()个连通分量,最多有()个连通分量。 A.0 B.1 C.n-1 【北京邮电大学2000二、5(20/8分)】 7.在一个无向图中,所有顶点的度数之和等于所有边数()倍,在一个有向图中,所 有顶点的入度之和等于所有顶点出度之和的()倍。【哈尔滨工业大学2001二、3(2 分)】 A.1/2 8.用有向无环图描述表达式(A+B)*((A+B)/A),至少需要顶点的数目为()。【中山大学 1999 14】 A.5 9.用DFS遍历一个无环有向图,并在DFS算法退栈返回时打印相应的顶点,则输出的顶点 序列是() 逆拓扑有序 B.拓扑有序 无序的 【中科院软件所 1998】 10.下面结构中最适于表示稀疏无向图的是(),适于表示稀疏有向图的是()。 A.邻接矩阵 B.逆邻接表C.邻接多重表 D.十字链表E.邻接 【北京工业大学2001一、3(2分)】 11.下列哪一种图的邻接矩阵是对称矩阵?()【北方交通大学2001一、11(2分)】 A.有向图 B.无向图 C.AOV网 D.AOE网 12.从邻接阵矩Lo 以看出,该图共有(①)个顶点:如果是有向图该图共有 (②)条弧:如果是无向图,则共有(③)条边。【中科院软件所1999六、2(3分)】 ①.A.9B.3 C.6D.1E.以上答案均不正确 ②.A.5B.4C.3D.2E.以上答案均不正确 ③.A.5B.4C.3D.2E.以上答案均不正确
第七章 图 一、选择题 1．图中有关路径的定义是（ ）。【北方交通大学 2001 一、24 （2 分）】 A．由顶点和相邻顶点序偶构成的边所形成的序列 B．由不同顶点所形成的序列 C．由不同边所形成的序列 D．上述定义都不是 2．设无向图的顶点个数为 n，则该图最多有（ ）条边。 A．n-1 B．n(n-1)/2 C． n(n+1)/2 D．0 E．n 2 【清华大学 1998 一、5 （2 分）】【西安电子科技大 1998 一、6 （2 分）】 【北京航空航天大学 1999 一、7 （2 分）】 3．一个 n 个顶点的连通无向图，其边的个数至少为（ ）。【浙江大学 1999 四、4 (4 分)】 A．n-1 B．n C．n+1 D．nlogn； 4．要连通具有 n 个顶点的有向图，至少需要（ ）条边。【北京航空航天大学 2000 一、 6(2 分）】 A．n-l B．n C．n+l D．2n 5．n 个结点的完全有向图含有边的数目（ ）。【中山大学 1998 二、9 （2 分）】 A．n*n Ｂ．n（n＋１） C．n／2 D．n*（n－l） 6．一个有 n 个结点的图，最少有（ ）个连通分量，最多有（ ）个连通分量。 A．0 B．1 C．n-1 D．n 【北京邮电大学 2000 二、5 （20/8 分）】 7．在一个无向图中，所有顶点的度数之和等于所有边数（ ）倍，在一个有向图中，所 有顶点的入度之和等于所有顶点出度之和的（ ）倍。【哈尔滨工业大学 2001 二、3 （2 分）】 A．1/2 B．2 C．1 D．4 8．用有向无环图描述表达式(A+B)*（（A+B）/A），至少需要顶点的数目为( )。【中山大学 1999 一、14】 A．5 B．6 C．8 D．9 9．用 DFS 遍历一个无环有向图，并在 DFS 算法退栈返回时打印相应的顶点，则输出的顶点 序列是( )。 A．逆拓扑有序 B．拓扑有序 C．无序的 【中科院软件所 1998】 10．下面结构中最适于表示稀疏无向图的是（ ），适于表示稀疏有向图的是（ ）。 A．邻接矩阵 B．逆邻接表 C．邻接多重表 D．十字链表 E．邻接 表 【北京工业大学 2001 一、3 (2 分)】 11．下列哪一种图的邻接矩阵是对称矩阵？（ ）【北方交通大学 2001 一、11 （2 分）】 A．有向图 B．无向图 C．AOV 网 D．AOE 网 12． 从邻接阵矩 = 0 1 0 1 0 1 0 1 0 A 可以看出，该图共有（①）个顶点；如果是有向图该图共有 （②） 条弧；如果是无向图，则共有（③）条边。【中科院软件所 1999 六、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．以上答案均不正确
13.当一个有N个顶点的图用邻接矩阵A表示时,顶点Vi的度是()。【南京理工大学1998 、4(2分)】 [, ∑A∑4 ∑北n∑A 14.用相邻矩阵A表示图,判定任意两个顶点ⅵi和Vj之间是否有长度为m的路径相连 则只要检查 )的第i行第j列的元素是否为零即可。【武汉大学2000二、7】 D. Am-1 15.下列说法不正确的是()。【青岛大学2002二、9(2分)】 A.图的遍历是从给定的源点出发每一个顶点仅被访问一次C.图的深度遍历不适用 于有向图 遍历的基本算法有两种:深度遍历和广度遍历 D.图的深度遍历是一个 递归过程 无 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)},对该图进行深度优 先遍历,得到的顶点序列正确的是()。【南京理工大学2001一、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, b 17.设图如右所示,在下面的5个序列中,符合深度优先遍历的序列有多少?( 【南京理工大学2000一、20(1.5分)】 ae b d fc a cfdeb a e d fcb ae f d cb a e f d b 4个 个 D.2个 第17题图 第18题图 18.下图中给出由7个顶点组成的无向图。从顶点1出发,对它进行深度优先遍历得到的序 列是(①),而进行广度优先遍历得到的顶点序列是(②)。【中科院软件所1999六、2 (1)(2分)】 ①.A.1354267B.1347652C.1534276D.1247653E.以上答案均 不正确 ②.A.1534267B.1726453C.1354276D.1247653E.以上答案 均不正确 19.下面哪一方法可以判断出一个有向图是否有环(回路):【东北大学20004、2(4分)】 A.深度优先遍历B.拓扑排序C.求最短路径D.求关键路径 20.在图采用邻接表存储时,求最小生成树的Prim算法的时间复杂度为() A.0(n) B.0(n+e) C.0(n2) 【合肥工业大学2001一、2(2分)】 21.下面是求连通网的最小生成树的prim算法:集合ⅥT,ET分别放顶点和边,初始为(1)
a b e d c f 13．当一个有 N 个顶点的图用邻接矩阵 A 表示时，顶点 Vi 的度是（ ）。【南京理工大学 1998 一、4(2 分）】 A． = n i A i j 1 [ , ] B． = n j 1 A i, j C． = n i A j i 1 [ , ] D． = n i A i j 1 [ , ] + = n j 1 A j,i 14．用相邻矩阵 A 表示图，判定任意两个顶点 Vi 和 Vj 之间是否有长度为 m 的路径相连， 则只要检查（ ）的第 i 行第 j 列的元素是否为零即可。【武汉大学 2000 二、7】 A．mA B．A C．A m D．Am-1 15. 下列说法不正确的是（ ）。【青岛大学 2002 二、9 （2 分）】 A．图的遍历是从给定的源点出发每一个顶点仅被访问一次 C．图的深度遍历不适用 于有向图 B．遍历的基本算法有两种：深度遍历和广度遍历 D．图的深度遍历是一个 递归过程 16 ． 无 向 图 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)}，对该图进行深度优 先遍历，得到的顶点序列正确的是（ ）。【南京理工大学 2001 一、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,b 17. 设图如右所示，在下面的 5 个序列中，符合深度优先遍历的序列有多少？（ ） 【南京理工大学 2000 一、20 （1.5 分）】 a e b d f c a c f d e b a e d f c b a e f d c b a e f d b c A．5 个 B．4 个 C．3 个 D．2 个 第 17 题图 第 18 题图 18.下图中给出由 7 个顶点组成的无向图。从顶点 1 出发，对它进行深度优先遍历得到的序 列是( ① )，而进行广度优先遍历得到的顶点序列是（ ② ）。【中科院软件所 1999 六、2- （1）（2 分）】 ①．A．1354267 B．1347652 C．1534276 D．1247653 E．以上答案均 不正确 ②．A．1534267 B．1726453 C．l354276 D．1247653 E．以上答案 均不正确 19．下面哪一方法可以判断出一个有向图是否有环（回路）：【东北大学 2000 4、2（4 分）】 A．深度优先遍历 B. 拓扑排序 C. 求最短路径 D. 求关键路径 20. 在图采用邻接表存储时，求最小生成树的 Prim 算法的时间复杂度为( )。 A. O(n) B. O(n+e) C. O(n2 ) D. O(n3 ) 【合肥工业大学 2001 一、2 （2 分）】 21. 下面是求连通网的最小生成树的 prim 算法：集合 VT，ET 分别放顶点和边，初始为（ 1 ）
下面步骤重复n-1次:a:(2):b:(3):最后:(4)。【南京理工大学1997一、1114 (8分)】 (1).A.VT,ET为空 B.ⅥT为所有顶点,ET为空 C.ⅥT为网中任意一点,ET为空 VT为空,ET为网中所有边 (2).A.选i属于ⅥT,j不属于ⅥT,且(i,j)上的权最小 B.选i属于ⅥT,j不属于ⅥT,且(i,j)上的权最大 C.选i不属于ⅥT,j不属于Ⅵ,且(i,j)上的权最小 D.选i不属于ⅥT,j不属于ⅥT,且(i,j)上的权最大 (3).A.顶点i加入ⅥT,(i,j)加入ET B.顶点j加入ⅥT,(i,j)加入ET C.顶点j加入ⅥT,(i,j)从ET中删去D.顶点i,j加入ⅥT,(i,j)加入 (4).A.ET中为最小生成树 B.不在ET中的边构成最小生成树 C.ET中有n-1条边时为生成树,否则无解D.ET中无回路时,为生成树,否 则无解 22.(1).求从指定源点到其余各顶点的迪杰斯特拉( Di jkstra)最短路径算法中弧上权不 能为负的原因是在实际应用中无意义 (2).利用 Di jkstra求每一对不同顶点之间的最短路径的算法时间是0(m);(图用邻 接矩阵表示) (3). Floyd求每对不同顶点对的算法中允许弧上的权为负,但不能有权和为负的回路。 上面不正确的是()。【南京理工大学2000一、21(1.5分)】 B.(1 C.(1),(3) D.(2),(3) 23.当各边上的权值()时,BFS算法可用来解决单源最短路径问题。【中科院计算所2000 3(2分)】 A.均相等B.均互不相等C.不一定相等 24.求解最短路径的 Floyd算法的时间复杂度为()。【合肥工业大学1999一、2(2 分)】 A.0(n) B.0(n+c) C.0(n*n) 25.已知有向图G=(V,E),其中V={V1,V2,V3,V4,V3,V,V}, E={V1,V2>,,,,,,,},G的拓扑序列 是()。 A. V1, V3, V4, V6, V2, V5, V7 B.V1,V3,V2,V6,V4,V5,V7 C.V1,V,V4,V,V2,V6,V7 D. V, V2, V5, V3, V4, V6, V7 【北京航空航天大学2000一、7(2分)】 26.若一个有向图的邻接距阵中,主对角线以下的元素均为零,则该图的拓扑有序序列 A.存在B.不存在【中科院计算所1998二、6(2分)】【中国科技大学1998二、6 (2分)】 27.一个有向无环图的拓扑排序序列()是唯一的。【北京邮电大学2001一、3(2 分)】 定 28.在有向图G的拓扑序列中,若顶点i在顶点Vj之前,则下列情形不可能出现的是 ()。 A.G中有弧<Vi,Vj B.G中有一条从Vi到Vj的路径 C.G中没有弧<Vi,Vj D.G中有一条从Vj到Vi的路径
下面步骤重复 n-1 次: a：（ 2 ）；b：（ 3 ）；最后：（ 4 ）。【南京理工大学 1997 一、11_14 （8 分）】 （1）．A．VT，ET 为空 B．VT 为所有顶点，ET 为空 C．VT 为网中任意一点，ET 为空 D．VT 为空，ET 为网中所有边 （2）．A. 选 i 属于 VT，j 不属于 VT，且（i，j）上的权最小 B．选 i 属于 VT，j 不属于 VT，且（i，j）上的权最大 C．选 i 不属于 VT，j 不属于 VT，且（i，j）上的权最小 D．选 i 不属于 VT，j 不属于 VT，且（i，j）上的权最大 （3）．A．顶点 i 加入 VT，（i,j）加入 ET B. 顶点 j 加入 VT，（i,j）加入 ET C. 顶点 j 加入 VT，（i,j）从 ET 中删去 D．顶点 i,j 加入 VT，（i,j）加入 ET （4）．A．ET 中为最小生成树 B．不在 ET 中的边构成最小生成树 C．ET 中有 n-1 条边时为生成树，否则无解 D．ET 中无回路时，为生成树，否 则无解 22. (1). 求从指定源点到其余各顶点的迪杰斯特拉（Dijkstra）最短路径算法中弧上权不 能为负的原因是在实际应用中无意义； (2). 利用 Dijkstra 求每一对不同顶点之间的最短路径的算法时间是 O(n3 ) ；（图用邻 接矩阵表示） (3). Floyd 求每对不同顶点对的算法中允许弧上的权为负，但不能有权和为负的回路。 上面不正确的是（ ）。【南京理工大学 2000 一、21 （1.5 分）】 A．(1),(2),(3) B．(1) C．(1),(3) D．(2),(3) 23．当各边上的权值( )时，BFS 算法可用来解决单源最短路径问题。【中科院计算所 2000 一、3 (2 分）】 A．均相等 B．均互不相等 C．不一定相等 24. 求解最短路径的 Floyd 算法的时间复杂度为( )。【合肥工业大学 1999 一、2 （2 分）】 A．O（n） B. O（n+c） C. O（n*n） D. O（n*n*n） 25．已知有向图 G=(V,E)，其中 V={V1,V2,V3,V4,V5,V6,V7}， E={,,,,,,,,},G 的拓扑序列 是（ ）。 A．V1,V3,V4,V6,V2,V5,V7 B．V1,V3,V2,V6,V4,V5,V7 C．V1,V3,V4,V5,V2,V6,V7 D．V1,V2,V5,V3,V4,V6,V7 【北京航空航天大学 2000 一、7 （2 分）】 26．若一个有向图的邻接距阵中,主对角线以下的元素均为零,则该图的拓扑有序序列 （ ）。 A．存在 B．不存在【中科院计算所 1998 二、6 (2 分）】【中国科技大学 1998 二、6 （2 分）】 27．一个有向无环图的拓扑排序序列（ ）是唯一的。【北京邮电大学 2001 一、3 （2 分）】 A．一定 B．不一定 28. 在有向图 G 的拓扑序列中，若顶点 Vi 在顶点 Vj 之前，则下列情形不可能出现的是 （ ）。 A．G 中有弧 B．G 中有一条从 Vi 到 Vj 的路径 C．G 中没有弧 D．G 中有一条从 Vj 到 Vi 的路径
【南京理工大学2000一、9(1.5分)】 29.在用邻接表表示图时,拓扑排序算法时间复杂度为() A.0(n) B.0(n+e) C.0(n*n) D.0(n*n*n) 【合肥工业大学2000一、2(2分)】【南京理工大学2001一、9(1.5分)】 【青岛大学2002二、3(2分)】 30.关键路径是事件结点网络中()。【西安电子科技大学2001应用一、4(2分)】 A.从源点到汇点的最长路径 B.从源点到汇点的最短路径 C.最长回路 D.最短回路 31.下面关于求关键路径的说法不正确的是()。【南京理工大学1998一、12(2分)】 A.求关键路径是以拓扑排序为基础的 B.一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同 C.一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续 的差 时间的 D.关键活动一定位于关键路径上 32.下列关于AOE网的叙述中,不正确的是() A.关键活动不按期完成就会影响整个工程的完成时间 B.任何一个关键活动提前完成,那么整个工程将会提前完成 C.所有的关键活动提前完成,那么整个工程将会提前完成 D.某些关键活动提前完成,那么整个工程将会提前完成 【北方交通大学1999一、7(3分)】【北京工业大学1999一、1(2分)】 判断题 1.树中的结点和图中的顶点就是指数据结构中的数据元素。(青岛大学2001四、1(1 分)】 2.在n个结点的无向图中,若边数大于n-1,则该图必是连通图。()【中科院软件所1997 4(1分)】 ∑TDVZ 3.对有n个顶点的无向图,其边数e与各顶点度数间满足下列等式e=l 【南京航空航天大学1996六、4(1分)】 4.有e条边的无向图,在邻接表中有e个结点。()【南京理工大学1998二、5(2 分)】 5.有向图中顶点Ⅴ的度等于其邻接矩阵中第V行中的1的个数。()【合肥工业大学2001 二、7(1分)】 6.强连通图的各顶点间均可达。()【北京邮电大学2000一、3(1分)】 7.强连通分量是无向图的极大强连通子图。()【北京邮电大学2002一、7(1分)】 8.连通分量指的是有向图中的极大连通子图。()【燕山大学1998二、4(2分)】 9.邻接多重表是无向图和有向图的链式存储结构。()【南京航空航天大学1995五 (1分)】 10.十字链表是无向图的一种存储结构。()【青岛大学2001四、7(1分)】 11.无向图的邻接矩阵可用一维数组存储。()【青岛大学2000四、5(1分)】 12.用邻接矩阵法存储一个图所需的存储单元数目与图的边数有关。() 【东南大学2001一、4(1分)】【中山大学1994一、3(2分)】 13.有n个顶点的无向图,采用邻接矩阵表示,图中的边数等于邻接矩阵中非零元素之和的
【南京理工大学 2000 一、9 （1.5 分）】 29. 在用邻接表表示图时，拓扑排序算法时间复杂度为( )。 A. O(n) B. O(n＋e) C. O(n*n) D. O(n*n*n) 【合肥工业大学 2000 一、2 （2 分）】【南京理工大学 2001 一、9 （1.5 分）】 【青岛大学 2002 二、3 （2 分）】 30. 关键路径是事件结点网络中（ ）。【西安电子科技大学 2001 应用 一、4 （2 分）】 A．从源点到汇点的最长路径 B．从源点到汇点的最短路径 C．最长回路 D．最短回路 31. 下面关于求关键路径的说法不正确的是（ ）。【南京理工大学 1998 一、12 （2 分）】 A．求关键路径是以拓扑排序为基础的 B．一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同 C．一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续 时间的差 D．关键活动一定位于关键路径上 32．下列关于 AOE 网的叙述中，不正确的是（ ）。 A．关键活动不按期完成就会影响整个工程的完成时间 B．任何一个关键活动提前完成，那么整个工程将会提前完成 C．所有的关键活动提前完成，那么整个工程将会提前完成 D．某些关键活动提前完成，那么整个工程将会提前完成 【北方交通大学 1999 一、7 （3 分）】【北京工业大学 1999 一、1 (2 分)】 二、判断题 1.树中的结点和图中的顶点就是指数据结构中的数据元素。（ ）【青岛大学 2001 四、1 （1 分）】 2．在 n 个结点的无向图中，若边数大于 n-1,则该图必是连通图。（ ）【中科院软件所 1997 一、4(1 分）】 3．对有 n 个顶点的无向图，其边数 e 与各顶点度数间满足下列等式 e= = n i TD Vi 1 ( ) 。（ ） 【南京航空航天大学 1996 六、4 （1 分）】 4. 有 e 条边的无向图，在邻接表中有 e 个结点。（ ）【南京理工大学 1998 二、5 （2 分）】 5. 有向图中顶点 V 的度等于其邻接矩阵中第 V 行中的 1 的个数。（ ）【合肥工业大学 2001 二、7(1 分）】 6．强连通图的各顶点间均可达。（ ）【北京邮电大学 2000 一、3 （1 分）】 7．强连通分量是无向图的极大强连通子图。（ ）【北京邮电大学 2002 一、7 （1 分）】 8．连通分量指的是有向图中的极大连通子图。（ ）【燕山大学 1998 二、4 （2 分）】 9．邻接多重表是无向图和有向图的链式存储结构。（ ）【南京航空航天大学 1995 五、5 （1 分）】 10. 十字链表是无向图的一种存储结构。（ ）【青岛大学 2001 四、7 （1 分）】 11. 无向图的邻接矩阵可用一维数组存储。（ ）【青岛大学 2000 四、5 （1 分）】 12．用邻接矩阵法存储一个图所需的存储单元数目与图的边数有关。（ ） 【东南大学 2001 一、4 （1 分）】 【中山大学 1994 一、3 （2 分）】 13．有 n 个顶点的无向图, 采用邻接矩阵表示, 图中的边数等于邻接矩阵中非零元素之和的
半。() 【北京邮电大学1998 (2分)】 14.有向图的邻接矩阵是对称的 )【青岛大学2001四、6(1分)】 15.无向图的邻接矩阵一定是对称矩阵,有向图的邻接矩阵一定是非对称矩阵。( 【东南大学2001一、3(1分)】【哈尔滨工业大学1999三、4】 16.邻接矩阵适用于有向图和无向图的存储,但不能存储带权的有向图和无向图,而只能使 用邻接表存储形式来存储它。()【上海海运学院1995、9(1分)1997一、8(1分) 1998、9(1分)】 17.用邻接矩阵存储一个图时,在不考虑压缩存储的情况下,所占用的存储空间大小与图中 结点个数有关,而与图的边数无关。()【上海海运学院1996一、8(1分)1999一、 9(1分)】 18.一个有向图的邻接表和逆邻接表中结点的个数可能不等。()【上海交通大学1998 19.需要借助于一个队列来实现DFS算法。()【南京航空航天大学1996六、8(1分)】 20.广度遍历生成树描述了从起点到各顶点的最短路径。()【合肥工业大学2001二、 8(1分)】 21.任何无向图都存在生成树。()【北京邮电大学2000一、1(1分)】 22.不同的求最小生成树的方法最后得到的生成树是相同的.()【南京理工大学1998 二、3(2分)】 带权无向图的最小生成树必是唯一的。()【南京航空航天大学1996六、7(1分)】 最小代价生成树是唯一的。()【山东大学2001一、5(1分)】 25.一个网(带权图)都有唯一的最小生成树。()【大连海事大学2001一、14(1 分)】 26.连通图上各边权值均不相同,则该图的最小生成树是唯一的。()【哈尔滨工业大学 1999 27.带权的连通无向图的最小(代价)生成树(支撑树)是唯一的。()【中山大学1994 、10(2分)】 28.最小生成树的 KRUSKAL算法是一种贪心法( GREEDY)。()【华南理工大学2002 6(1分)】 29.求最小生成树的普里姆(Prim)算法中边上的权可正可负。()【南京理工大学1998 二、2(2分)】 30.带权的连通无向图的最小代价生成树是唯一的。()【东南大学2001一、5(1分)】 31.最小生成树问题是构造连通网的最小代价生成树。()【青岛大学2001四、10(1 分)】 32.在图G的最小生成树G1中,可能会有某条边的权值超过未选边的权值。() 【合肥工业大学2000二、7(1分)】 33.在用 Floyd算法求解各顶点的最短路径时,每个表示两点间路径的path[I,J一定是 path[I,J的子集(k=1,2,3,…,n)。()【合肥工业大学2000二、6(1分)】 4.拓扑排序算法把一个无向图中的顶点排成一个有序序列。()【南京航空航天大学1995 五、8(1分)】 35.拓扑排序算法仅能适用于有向无环图。()【南京航空航天大学1997一、7(1分)】 36.无环有向图才能进行拓扑排序。()【青岛大学2002一、7(1分)2001一、8(1 分)】 37.有环图也能进行拓扑排序。()【青岛大学2000四、6(1分)】
一半。（ ） 【北京邮电大学 1998 一、5 （2 分）】 14. 有向图的邻接矩阵是对称的。（ ）【青岛大学 2001 四、6 （1 分）】 15．无向图的邻接矩阵一定是对称矩阵，有向图的邻接矩阵一定是非对称矩阵。（ ） 【东南大学 2001 一、3 （1 分）】【哈尔滨工业大学 1999 三、4】 16. 邻接矩阵适用于有向图和无向图的存储，但不能存储带权的有向图和无向图，而只能使 用邻接表存储形式来存储它。（ ）【上海海运学院 1995 一、9（1 分） 1997 一、8（1 分） 1998 一、9（1 分）】 17. 用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小与图中 结点个数有关，而与图的边数无关。（ ）【上海海运学院 1996 一、8 （1 分） 1999 一、 9 （1 分）】 18．一个有向图的邻接表和逆邻接表中结点的个数可能不等。（ ）【上海交通大学 1998 一、12】 19．需要借助于一个队列来实现 DFS 算法。（ ）【南京航空航天大学 1996 六、8 （1 分）】 20. 广度遍历生成树描述了从起点到各顶点的最短路径。（ ）【合肥工业大学 2001 二、 8 （1 分）】 21．任何无向图都存在生成树。（ ）【北京邮电大学 2000 一、1 （1 分）】 22. 不同的求最小生成树的方法最后得到的生成树是相同的.（ ）【南京理工大学 1998 二、3 （2 分）】 23．带权无向图的最小生成树必是唯一的。（ ）【南京航空航天大学 1996 六、7 （1 分）】 24. 最小代价生成树是唯一的。（ ）【山东大学 2001 一、5 （1 分）】 25．一个网（带权图）都有唯一的最小生成树。（ ）【大连海事大学 2001 一、14 （1 分）】 26．连通图上各边权值均不相同，则该图的最小生成树是唯一的。（ ）【哈尔滨工业大学 1999 三、3】 27．带权的连通无向图的最小（代价）生成树（支撑树）是唯一的。（ ）【中山大学 1994 一、10（2 分）】 28. 最小生成树的 KRUSKAL 算法是一种贪心法（GREEDY）。（ ）【华南理工大学 2002 一、 6（1 分）】 29. 求最小生成树的普里姆(Prim)算法中边上的权可正可负。（ ）【南京理工大学 1998 二、2 （2 分）】 30．带权的连通无向图的最小代价生成树是唯一的。（ ）【东南大学 2001 一、5（1 分）】 31. 最小生成树问题是构造连通网的最小代价生成树。（ ）【青岛大学 2001 四、10（1 分）】 32. 在图 G 的最小生成树 G1 中，可能会有某条边的权值超过未选边的权值。（ ） 【合肥工业大学 2000 二、7（1 分）】 33. 在用 Floyd 算法求解各顶点的最短路径时，每个表示两点间路径的 pathk-1 [I,J]一定是 pathk [I,J]的子集(k=1,2,3,…,n)。（ ）【合肥工业大学 2000 二、6 （1 分）】 34．拓扑排序算法把一个无向图中的顶点排成一个有序序列。（ ）【南京航空航天大学 1995 五、8（1 分）】 35．拓扑排序算法仅能适用于有向无环图。（ ）【南京航空航天大学 1997 一、7 （1 分）】 36. 无环有向图才能进行拓扑排序。（ ）【青岛大学 2002 一、7 （1 分）2001 一、8 （1 分）】 37. 有环图也能进行拓扑排序。（ ）【青岛大学 2000 四、6 （1 分）】
38.拓扑排序的有向图中,最多存在一条环路。()【大连海事大学2001一、6(1分)】 39.任何有向图的结点都可以排成拓扑排序,而且拓扑序列不唯一。()【上海交通大学 1998 40.既使有向无环图的拓扑序列唯一,也不能唯一确定该图。()【合肥工业大学2001 二、6(1分)】 41.若一个有向图的邻接矩阵对角线以下元素均为零,则该图的拓扑有序序列必定存在 () 【中科院软件所1997一、5(1分)】 42.AOV网的含义是以边表示活动的网。()【南京航空航天大学1995五、7(1分)】 43.对一个A0V网,从源点到终点的路径最长的路径称作关键路径。【南京航空航天大学1995 五、9(1分)】 44.关键路径是AOE网中从源点到终点的最长路径。()【青岛大学2000四、10(1分)】 45.AOE网一定是有向无环图。()【青岛大学2001一、9(1分)】 46.在表示某工程的AE网中,加速其关键路径上的任意关键活动均可缩短整个工程的完成 时间。() 【长沙铁道学院1997一、2(1分)】 47.在AOE图中,关键路径上某个活动的时间缩短,整个工程的时间也就必定缩短。() 【大连海事大学2001一、15(1分)】 48.在AOE图中,关键路径上活动的时间延长多少,整个工程的时间也就随之延长多少 () 【大连海事大学2001一、16(1分)】 49.当改变网上某一关键路径上任一关键活动后,必将产生不同的关键路径。【上海交通大 学1998 14】 、填空题 1.判断一个无向图是一棵树的条件是 2.有向图G的强连通分量是指 【北京科技大学1997、7】 3.一个连通图的 是一个极小连通子图。【重庆大学2000一、1】 4.具有10个顶点的无向图,边的总数最多为 【华中理工大学2000一、7(1分)】 5.若用n表示图中顶点数目,则有 条边的无向图成为完全图。【燕山大学1998 6(1分)】 6.设无向图G有n个顶点和e条边,每个顶点Vi的度为di(1<=i<=n),则e 【福州大学1998二、2(2分)】 7.G是一个非连通无向图,共有28条边,则该图至少有 个顶点。 【西安电子科技大2001软件一、8(2分)】 8.在有n个顶点的有向图中,若要使任意两点间可以互相到达,则至少需要_条弧 【合肥工业大学2000三、8(2分)】 在有n个顶点的有向图中,每个顶点的度最大可达。【武汉大学2000-、3】 10.设G为具有N个顶点的无向连通图,则G中至少有 条边。 【长沙铁道学院1997二、2(2分)】 11.n个顶点的连通无向图,其边的条数至少为。【哈尔滨工业大学2000 分)】 12.如果含n个顶点的图形形成一个环,则它有 棵生成树 【西安电子科技大学2001软件一、2(2分)】
38．拓扑排序的有向图中，最多存在一条环路。（ ）【大连海事大学 2001 一、6（1 分）】 39．任何有向图的结点都可以排成拓扑排序，而且拓扑序列不唯一。（ ）【上海交通大学 1998 一、13】 40. 既使有向无环图的拓扑序列唯一，也不能唯一确定该图。（ ）【合肥工业大学 2001 二、6（1 分）】 41．若一个有向图的邻接矩阵对角线以下元素均为零，则该图的拓扑有序序列必定存在。 （ ） 【中科院软件所 1997 一、5 （1 分）】 42．AOV 网的含义是以边表示活动的网。（ ）【南京航空航天大学 1995 五、7 （1 分）】 43．对一个 AOV 网，从源点到终点的路径最长的路径称作关键路径。【南京航空航天大学 1995 五、9(1 分）】 44. 关键路径是 AOE 网中从源点到终点的最长路径。（ ）【青岛大学 2000 四、10（1 分）】 45. AOE 网一定是有向无环图。（ ）【青岛大学 2001 一、9 （1 分）】 46. 在表示某工程的 AOE 网中，加速其关键路径上的任意关键活动均可缩短整个工程的完成 时间。（ ） 【长沙铁道学院 1997 一、2 (1 分)】 47．在 AOE 图中，关键路径上某个活动的时间缩短，整个工程的时间也就必定缩短。（ ） 【大连海事大学 2001 一、15 （1 分）】 48．在 AOE 图中，关键路径上活动的时间延长多少，整个工程的时间也就随之延长多少。 （ ） 【大连海事大学 2001 一、16 （1 分）】 49．当改变网上某一关键路径上任一关键活动后，必将产生不同的关键路径。【上海交通大 学 1998 一、14】 三、填空题 1.判断一个无向图是一棵树的条件是______。 2．有向图 G 的强连通分量是指______。【北京科技大学 1997 一、7】 3．一个连通图的______是一个极小连通子图。【重庆大学 2000 一、1】 4．具有 10 个顶点的无向图，边的总数最多为______。【华中理工大学 2000 一、7 （1 分）】 5．若用 n 表示图中顶点数目，则有_______条边的无向图成为完全图。【燕山大学 1998 一、 6（1 分）】 6. 设无向图 G 有 n 个顶点和 e 条边，每个顶点 Vi 的度为 di（1<=i<=n〉，则 e=______ 【福州大学 1998 二、2 (2 分)】 7．G 是一个非连通无向图，共有 28 条边，则该图至少有______个顶点。 【西安电子科技大 2001 软件一、8 （2 分）】 8. 在有 n 个顶点的有向图中，若要使任意两点间可以互相到达，则至少需要______条弧。 【合肥工业大学 2000 三、8 （2 分）】 9．在有 n 个顶点的有向图中，每个顶点的度最大可达______。【武汉大学 2000 一、3】 10．设 G 为具有 N 个顶点的无向连通图，则 G 中至少有______条边。 【长沙铁道学院 1997 二、2 (2 分)】 11．n 个顶点的连通无向图，其边的条数至少为______。【哈尔滨工业大学 2000 二、2（1 分）】 12．如果含 n 个顶点的图形形成一个环，则它有______棵生成树。 【西安电子科技大学 2001 软件 一、2 （2 分）】
13.N个顶点的连通图的生成树含有 条边。【中山大学1998、9(1分)】 14.构造n个结点的强连通图,至少有条弧。【北京轻工业学院2000一、4(2分)】 15.有N个顶点的有向图,至少需要量条弧 才能保证是连通的。【西南交通大学2000一、3】 16.右图中的强连通分量的个数为()个 【北京邮电大学2001二、5(2分)】 17.N个顶点的连通图用邻接矩阵表示时,该矩阵 至少有 个非零元素。【中科院计算所1998一、6(1分)】【中国科技大学1998 6(15/6分)】 18.在图G的邻接表表示中,每个顶点邻接表中所含的结点数,对于无向图来说等于该顶点 的 对于有向图来说等于该顶点的 【燕山大学2001二、5(3分)】 19.在有向图的邻接矩阵表示中,计算第I个顶点入度的方法是。【青岛大学2002 三、7(2分)】 20.对于一个具有n个顶点e条边的无向图的邻接表的表示,则表头向量大小为,邻 接表的边结点个数为 【青岛大学2002三、8(2分)】 21.遍历图的过程实质上是 , breath- first search遍历图的时间复杂度 depth- first search遍历图的时间复杂度 两者不同之处在于 ,反映在数据 结构上的差别是 【厦门大学1999、3】 22.已知一无向图G=(V,E),其中V={a,b,c,d,e}E={(a,b),(a,d),(a,c),(d,c),(b,e)} 现用某一种图遍历方法从顶点a开始遍历图,得到的序列为 abcd,则采用的是遍历 方法 【南京理工大学1996二、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开始进行遍历,去掉遍历中未走过 的边,得一生成树G(V,E'),V(G’)=V(G),E(G’)={(1,3),(3,6),(7,3),(1,2), (1,5),(2,4)},则采用的遍历方法是 【南京理工大学1997三、6(1分)】 24.为了实现图的广度优先搜索,除了一个标志数组标志已访问的图的结点外,还需 存放被访问的结点以实现遍历。【南京理工大学1999二、9(2分)】 25.按下图所示,画出它的广度优先生成树 和深度优先生成树 【西安电子科技大学1998三、6(5分)】③ 26.构造连通网最小生成树的两个典型算法是。【北京科技大学1998一、5】 27.求图的最小生成树有两种算法,算法适合于求稀疏图的最小生成树 【南京理工大学2001二、6(2分)】
13．N 个顶点的连通图的生成树含有______条边。【中山大学 1998 一、9 （1 分）】 14．构造 n 个结点的强连通图，至少有______条弧。【北京轻工业学院 2000 一、4（2 分）】 15．有 N 个顶点的有向图，至少需要量______条弧 才能保证是连通的。【西南交通大学 2000 一、3】 16．右图中的强连通分量的个数为（ ）个。 【北京邮电大学 2001 二、5 （2 分）】 17．N 个顶点的连通图用邻接矩阵表示时,该矩阵 至少有_______个非零元素。【中科院计算所 1998 一、6（1 分）】【中国科技大学 1998 一、 6（15/6 分）】 18．在图 G 的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该顶点 的______；对于有向图来说等于该顶点的______。 【燕山大学 2001 二、5 （3 分）】 19. 在有向图的邻接矩阵表示中，计算第 I 个顶点入度的方法是______。【青岛大学 2002 三、7 （2 分）】 20. 对于一个具有 n 个顶点 e 条边的无向图的邻接表的表示，则表头向量大小为______，邻 接表的边结点个数为______。【青岛大学 2002 三、8 （2 分）】 21. 遍历图的过程实质上是______，breath-first search 遍历图的时间复杂度______； depth-first search 遍历图的时间复杂度______，两者不同之处在于______，反映在数据 结构上的差别是______。 【厦门大学 1999 一、3】 22. 已知一无向图 G=（V，E），其中 V={a,b,c,d,e } E={(a,b),(a,d),(a,c),(d,c),(b,e)} 现用某一种图遍历方法从顶点 a 开始遍历图，得到的序列为 abecd，则采用的是______遍历 方法。 【南京理工大学 1996 二、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 开始进行遍历，去掉遍历中未走过 的边，得一生成树 G’(V，E’）,V（G’）=V（G），E（G’）={（1,3），（3,6），（7,3），（1,2）， （1,5），（2,4）}，则采用的遍历方法是______。 【南京理工大学 1997 三、6 （1 分）】 24. 为了实现图的广度优先搜索，除了一个标志数组标志已访问的图的结点外，还需______ 存放被访问的结点以实现遍历。【南京理工大学 1999 二、9 （2 分）】 25. 按下图所示，画出它的广度优先生成树______和深度优先生成树______。 【西安电子科技大学 1998 三、6 （5 分）】 26．构造连通网最小生成树的两个典型算法是______。【北京科技大学 1998 一、5】 27．求图的最小生成树有两种算法，______算法适合于求稀疏图的最小生成树。 【南京理工大学 2001 二、6（2 分）】
28.Prim(普里姆)算法适用于求 的网的最小生成树; kruskal(克鲁斯卡尔)算法 适用于求的网的最小生成树。【厦门大学1999一、4】 29.克鲁斯卡尔算法的时间复杂度为 它对图较为适合。【中科院计算所1999 、3(2分)】 对于含N个顶点E条边的无向连通图,利用Prim算法生成最小代价生成树其时间复杂 度为 利用 Kruskal算法生成最小代价生成树其时间复杂度为 【长沙铁道学 院1998二、2(4分)】 31.下面描述的是一种构造最小生成树算法的基本思想。设要处理的无向图包括n个节点 Ⅵ1,V2,,Ⅶn,用相邻矩阵A表示,边的权全是正数。请在下列划线处填上正确叙述 (1).若(Vi,Vj)是边,则A(i,j)的值等于,若(Vi,Vj)不是边,则A(i, j)的值是一个比任何边的权 矩阵的对角线元素全为 (2).构造最小生成树过程中,若节点Vi已包括进生成树,就把相邻矩阵的对角线元素 A(i,i)置成 若(vi,Vj)已包括进生成树,就把矩阵元素A(i,j)置成 (3).算法结束时,相邻矩阵中的元素指出最小生成树的【山东工业大学1998 二、4(6分)】 32.有一个用于n个顶点连通带权无向图的算法描述如下: (1).设集合T1与T2,初始均为空; (2).在连通图上任选一点加入T1: (3).以下步骤重复n-1次: a.在i属于T1,j不属于T1的边中选最小权的边 b.该边加入T2 上述算法完成后,T2中共有条边,该算法称算法,T2中的边构成图的。 【南京理工大学1999二、7(4分)】 有向图G可拓扑排序的判别条件是 【长沙铁道学院1998二、9(2分)】 34. Di jkstra最短路径算法从源点到其余各顶点的最短路径的路径长度按 次序依次 产生,该算法弧上的权出现情况时,不能正确产生最短路径。【南京理工大学1999二、 8(4分)】 35.求从某源点到其余各顶点的 Di jkstra算法在图的顶点数为10,用邻接矩阵表示图时计 算时间约为10ms,则在图的顶点数为40,计算时间约为ms。【南京理工大学2000二、 分)】 6.求最短路径的 Dijkstra算法的时间复杂度为【哈尔滨工业大学2001-、5(2 分)】 37.有向图G=(V,E),其中VG)={0,1,2,3,4,5},用三元组表示弧及弧上的权 d.E(G)为{<0,4,30)<4,5,60〉<3,5,10)<2,3,50)<4,3,20)》},则 从源点0到顶点3的最短路径长度是_,经过的中间顶点是【南京理工大学1998 三、6(4分)】 38.上面的图去掉有向弧看成无向图则对应的最小生成树的边权之和为 【南京理工大学1998三、7(4分)】 9.设有向图有n个顶点和e条边,进行拓扑排序时,总的计算时间为 【西安电子科技大学1999软件一、7(2分)】【武汉大学2000一、7】 40.AOV网中,结点表示 边表示 。AOE网中,结点表示 边表示 【北京理工大学2001七、3(2分)】 41.在AOE网中,从源点到汇点路径上各活动时间总和最长的路径称为。【重庆大学 2000
28. Prim（普里姆）算法适用于求______的网的最小生成树；kruskal（克鲁斯卡尔）算法 适用于求______的网的最小生成树。【厦门大学 1999 一、4】 29．克鲁斯卡尔算法的时间复杂度为______,它对______图较为适合。【中科院计算所 1999 二、3 （2 分）】 30．对于含 N 个顶点 E 条边的无向连通图，利用 Prim 算法生成最小代价生成树其时间复杂 度为______，利用 Kruskal 算法生成最小代价生成树其时间复杂度为______。【长沙铁道学 院 1998 二、2 (4 分)】 31．下面描述的是一种构造最小生成树算法的基本思想。设要处理的无向图包括 n 个节点 V1，V2，．．．，Vn，用相邻矩阵 A 表示，边的权全是正数。请在下列划线处填上正确叙述。 （1）．若（Vi，Vj）是边，则 A（i，j）的值等于______，若（Vi，Vj）不是边，则 A（i， j）的值是一个比任何边的权______， 矩阵的对角线元素全为 0。 （2）．构造最小生成树过程中，若节点 Vi 已包括进生成树，就把相邻矩阵的对角线元素 A（i，i）置成______，若（Vi，Vj）已包括进生成树，就把矩阵元素 A（i，j）置成______。 （3）．算法结束时，相邻矩阵中_____的元素指出最小生成树的_____。【山东工业大学 1998 二、4(6 分）】 32. 有一个用于 n 个顶点连通带权无向图的算法描述如下： （1）．设集合 T1 与 T2，初始均为空； （2）．在连通图上任选一点加入 T1； （3）．以下步骤重复 n-1 次： a.在 i 属于 T1，j 不属于 T1 的边中选最小权的边； b.该边加入 T2。 上述算法完成后，T2 中共有______条边，该算法称______算法，T2 中的边构成图的______。 【南京理工大学 1999 二、7 （4 分）】 33. 有向图 G 可拓扑排序的判别条件是______。【长沙铁道学院 1998 二、9(2 分)】 34. Dijkstra 最短路径算法从源点到其余各顶点的最短路径的路径长度按______次序依次 产生，该算法弧上的权出现______情况时，不能正确产生最短路径。【南京理工大学 1999 二、 8（4 分）】 35. 求从某源点到其余各顶点的 Dijkstra 算法在图的顶点数为 10，用邻接矩阵表示图时计 算时间约为 10ms,则在图的顶点数为 40，计算时间约为______ms。【南京理工大学 2000 二、 3 （1.5 分）】 36．求最短路径的 Dijkstra 算法的时间复杂度为______。【哈尔滨工业大学 2001 一、5 （2 分）】 37.有向图 G=(V,E),其中 V(G)={0,1,2,3,4,5}，用三元组表示弧及弧上的权 d.E(G)为{,}，则 从源点0到顶点3的最短路径长度是______，经过的中间顶点是______。【南京理工大学 1998 三、6 （4 分）】 38. 上面的图去掉有向弧看成无向图则对应的最小生成树的边权之和为______。 【南京理工大学 1998 三、7（4 分）】 39．设有向图有 n 个顶点和 e 条边，进行拓扑排序时，总的计算时间为______。 【西安电子科技大学 1999 软件 一、7 （2 分）】【武汉大学 2000 一、7】 40．AOV 网中,结点表示______,边表示______。AOE 网中,结点表示______,边表示______。 【北京理工大学 2001 七、3 （2 分）】 41．在 AOE 网中，从源点到汇点路径上各活动时间总和最长的路径称为______。【重庆大学 2000 一、2】
42.在AOV网中,存在环意味着_,这是的;对程序的数据流图来说,它表明 存在 【厦门大学1999一、2】 43.当一个AOV网用邻接表表示时,可按下列方法进行拓扑排序 (1).查邻接表中入度为的顶点,并进栈 (2).若栈不空,则①输出栈顶元素Vj,并退栈:②查Vj的直接后继Vk,对Vk入度处 理,处理方法是 (3).若栈空时,输出顶点数小于图的顶点数,说明有 否则拓扑排序完成。 【南京理工大学1996二、3(6分)】 44.已知图的邻接表结构为: CoNST vtxnum={图的顶点数} TYPE vtxptr=l. vtxnum arcptr= arcnode arcnode=RECORD ad jvex: vtxptr: nextarc: arcptr end vexnode= RECORD vexdata:{和顶点相关的信息}; firestar: arcptr END jlist=ARRAY [vtxptrJOF vexnode 本算法是实现图的深度优先遍历的非递归算法。其中,使用一个顺序栈 stack。栈顶指针为 topo visited为标志数组。 PRoc dfs(g: adjlist; v0: vtxptr): top=0; writevO): visited[v0]: =ture: p: =g[vo]. firstarc WhiLe (top<>0)OR(p<>NIL) DO [WHILE (1 Iv: =p. adjvex; IF(2 Then p: =p. nextarc ELSE [write(v): visited[v]: true; top: =top+1: stack [top]: =p (3)]] F top<>0 THEN[p: =stack[top]: top: =top-1:(4) ENDP.同济大学2000二、2(10分)】 45.下面的算法完成图的深度优先遍历,请填空 PROGRAM graph traver CONST nl=max node number, TYPE vtxptr=l. nl: vtxptr0=0. nI arcptr= arcnod arcnode=RECORD vexi vex: vtxptr: nexti, next j: arcptr: END vexnode=RECORD vexdata: char; firstin, firstout: arcptr: END AY [vtxptrO] OF vexnode VaR ga: graph visited: ARRAY [vtxptrO] OF boolean FUNC order (g: graph; v: char): vtxptr WhiLe gli. vexdata>v Do i: =i-1 order: =1 ENDE
42．在 AOV 网 中，存在环意味着______，这是______的；对程序的数据流图来说，它表明 存在______。 【厦门大学 1999 一、2】 43. 当一个 AOV 网用邻接表表示时，可按下列方法进行拓扑排序。 （1）．查邻接表中入度为______的顶点，并进栈； （2）．若栈不空，则①输出栈顶元素 Vj，并退栈；②查 Vj 的直接后继 Vk，对 Vk 入度处 理，处理方法是______； （3）．若栈空时，输出顶点数小于图的顶点数，说明有______，否则拓扑排序完成。 【南京理工大学 1996 二、3 （6 分）】 44．已知图的邻接表结构为： CONST vtxnum={图的顶点数} TYPE vtxptr=1..vtxnum; arcptr=^arcnode; arcnode=RECORD adjvex:vtxptr; nextarc:arcptr END; vexnode=RECORD vexdata:{和顶点相关的信息}；firstarc:arcptr END; adjlist=ARRAY[vtxptr]OF vexnode; 本算法是实现图的深度优先遍历的非递归算法。其中，使用一个顺序栈 stack。栈顶指针为 top。visited 为标志数组。 PROC dfs(g:adjlist;v0:vtxptr); top=0; write(v0); visited[v0]:=ture; p:=g[v0].firstarc; WHILE (top<>0)OR(p<>NIL)DO [WHILE(1)_______DO [v:=p^.adjvex; IF(2)_______ THEN p:=p^.nextarc ELSE [write(v); visited[v]:=true; top:=top+1; stack[top]:=p; (3)_______] ] IF top<>0 THEN[p:=stack[top]; top:=top-1; (4)_______] ] ENDP.同济大学 2000 二、2 (10 分)】 45．下面的算法完成图的深度优先遍历，请填空。 PROGRAM graph_traver; CONST nl=max_node_number; TYPE vtxptr=1..nl; vtxptr0=0..nl; arcptr=^arcnode; arcnode=RECORD vexi ,vexj: vtxptr; nexti, nextj: arcptr; END;; vexnode=RECORD vexdata: char; firstin，firstout: arcptr; END; graph=ARRAY[vtxptr0] OF vexnode ; VAR ga:graph; n: integer; visited: ARRAY[vtxptr0] OF boolean ; FUNC order (g: graph; v: char): vtxptr; (1)_______; i:=n; WHILE g[i].vexdata<>v DO i:=i-1; order:=i; ENDF；
PROc creat(var g: graph) readIn(n, e) FoR i To n Do [readIn(g[i]. vexdata): g[i]. first ENIL g[i]. firstout: =NIL FOR k: =1 TO e Do [readln (vt, vh i: = order (g, vt); j: =order (g, vh); new (p): p. vexi: =i: p. vexj: =j p p. nextI:=:(4);_(5): ENDP FUNC firstadj(g: graph; v: char): vtxptrO i:=order(g, v); p: =g[i].firstout IF p<>NIL THEN firstadj: =(6) ELSE firstadj: =0 FUNC nextadj (g: graph; v: char: w: char): vtxptrO i: =order(g, v): j: =order(g, w): p: =(7) WHILE (poNIL )AND (p. vexj>j)DO( 8) IF(9 AND (10) THen nextadj: = p. nexti. vexj ELSe nextadj: =0 ENDE PRoc dfs (g: graph: vO: char) write(v0: 2): visited [order(g, v0)]: =true; w: =(11) WHILE W<>0 [IF(12) then dfs(g, g[w]. vexdata) PROC traver(g: graph FOR i: =1 TO n DO visited[il: = false FOR i: =1 TO n DO IF NOT visited [i] then dfs(g, gli]. vexdata) ENDP BEGIN creat(ga): traver(ga) END.【北方交通大学1999三(20分)】 46.n个顶点的有向图用邻接矩阵 array表示,下面是其拓扑排序算法,试补充完整 注:(1).图的顶点号从0开始计:(2). indegree是有n个分量的一维数组,放顶 点的入度 (3).函数 crean用于算顶点入度:(4).有三个函数push(data),pop(), check() 其含义为数据data进栈,退栈和测试栈是否空(不空返回1,否则0)。 crein( array, indegree, n) I for (i=0; i<n; i++) indegree[i]=( for(i=0, i<n: i++) for (j=0; j<n: j++) indegree [i]+=array[(2) topsort (array, indegree, n) for (i=0; i<n; i++) if ((5) push(i)
PROC creat(var g: graph); readln(n,e); FOR i:= 1 TO n DO [readln(g[i].vexdata); g[i].firstin :=NIL ; g[i].firstout:=NIL;] FOR k:= 1 TO e DO [readln (vt,vh); i:=order (g,vt); j:=order (g,vh); new (p); p^.vexi:=i ; p^.vexj:=j p^.nextj:= ____(2)____; ___(3)____ :=p; p^.nexti:=: ____(4)____; ___(5)____ :=p;] ENDP; FUNC firstadj(g:graph; v:char): vtxptr0; i:=order(g,v); p:=g[i].firstout; IF p<>NIL THEN firstadj:=(6)_______ELSE firstadj:=0; ENDF; FUNC nextadj(g:graph; v:char; w:char): vtxptr0; i:=order(g,v); j:=order(g,w); p:=(7)_______; WHILE(p<>NIL ) AND (p^.vexj<>j) DO(8)______; IF (9)______AND(10)______THEN nextadj:=p^.nexti^.vexj ELSE nextadj:=0; ENDF; PROC dfs(g:graph; v0:char); write(v0:2); visited[order(g,v0)]:=true; w:=(11)_______; WHILE w<>0 DO [IF (12)______ THEN dfs(g,g[w].vexdata); w:=(13)_______;] ENDP; PROC traver(g:graph); FOR i:=1 TO n DO visited[i]:=false; FOR i:=1 TO n DO IF NOT visited[i] THEN dfs(g,g[i].vexdata); ENDP; BEGIN creat(ga); traver(ga); END. 【北方交通大学 1999 三（20 分）】 46．n 个顶点的有向图用邻接矩阵 array 表示，下面是其拓扑排序算法，试补充完整。 注：（1）．图的顶点号从 0 开始计； （2）．indegree 是有 n 个分量的一维数组，放顶 点的入度； （3）．函数 crein 用于算顶点入度；（4）．有三个函数 push(data),pop( ),check( ) 其含义为数据 data 进栈，退栈和测试栈是否空（不空返回 1，否则 0）。 crein( array ,indegree,n) { for (i=0;i<n;i++) indegree[i]= ((1)_______) for(i=0,i<n;i++) for (j=0;j<n; j++) indegree[i]+=array[(2)_______][(3)_______]; } topsort (array,indegree,n) { count= ((4)_______) for (i=0;i<n;i++) if ((5)_______) push(i)
