大家好，我是讯享网，很高兴认识大家。



 <p>第七章图</p> 

讯享网

一、选择题

1.图中有关路径的定义是（）。【北方交通大学2001—、24（2分】

A.由顶点和相邻顶点序偶构成的边所形成的序列B.由不同顶点所形成的序列

C.由不同边所形成的序列D.上述定义都不是

2.设无向图的顶点个数为n,则该图最多有（）条边。

A.n-1B.n（n-l）/2C.n（n+l）/2D.0E.n2

【清华大学1998一、5（2分）】【西安电子科技大1998一、6（2分】

【北京航空航天大学1999一、7（2分】

3.一个n个顶点的连通无向图，其边的个数至少为（）。【浙江大学1999四、4（4

分）】

A.n-lB.nC.n+1D.nlogn；

4.要连通具有n个顶点的有向图，至少需要（）条边。【北京航空航天大学2000一、

6（2分]

A.n-lB.nC.n+1D.2n

5.n个结点的完全有向图含有边的数目（）o【中山大学1998二、9（2分】

A.n*nB.n（n+1）C.n/2D.n*（n—1）

6.一个有n个结点的图，最少有（）个连通分量，最多有（）个连通分量。

A.0B.1C.n-lD.n

【北京邮电大学2000二、5（20/8分】

7.在一个无向图中，所有顶点的度数之和等于所有边数（）倍，在一个有向图中，所

有顶点的入度之和等于所有顶点出度之和的（）倍。【哈尔滨工业大学2001二、3（2

分】

A.1/2B.2C.1D.4

8.用有向无环图描述表达式（A+B）*（（A+B）/A）,至少需要顶点的数目为（）o【中山大学

1999—,14]

A.5B.6C.8D.9

9.用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点

序列是（）o

A.逆拓扑有序B.拓扑有序C.无序的【中科院软件所

1998]

10.下面结构中最适于表示稀疏无向图的是（）,适于表示稀疏有向图的是（）。

A.邻接矩阵B.逆邻接表C.邻接多重表D.十字链表E.邻接

表

【北京工业大学2001一、3（2分）】

11.下列哪一种图的邻接矩阵是对称矩阵？（）【北方交通大学2001一、11（2分】

A.有向图B,无向图C.A0V网D.AOE网

-O1o-

A=10I

12.从邻接阵矩1。1。」可以看出，该图共有（①）个顶点；如果是有向图该图共有

(②)条弧；如果是无向图，则共有（③）条边。【中科院软件所1999六、2（3分】

①.A.9B.3C.6D.1E.以上答案均不正确

(2).A.5B.4C.3D.2E.以上答案均不正确

(3).A.5B.4C.3D.2E.以上答案均不正确

13.当一个有N个顶点的图用邻接矩阵A表示时，顶点Vi的度是()。【南京理工大学1998

一、4(2分】

iA[i,j]EA[i,j]XA[j,i]YA[i,j]EA[j,i]

A.i=iB.>‘C.i=iD.<=1+j=i

14.用相邻矩阵A表示图，判定任意两个顶点Vi和Vj之间是否有长度为m的路径相连,

则只要检查()的第i行第j列的元素是否为零即可。【武汉大学2000二、7]

A.mAB.AC.A”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,fB.a,c,f,e,b,dC.a,e,b,c,f,dD.a,e,d,f,c,b

17.设图如右所示，在下面的5个序列中，符合深度优先遍历的序列有多少？（）

【南京理工大学2000—、20（1.5分】

aebdfcacfdebaedfcbaefdcbaefdb

18.下图中给出由7个顶点组成的无向图。从顶点1出发，对它进行深度优先遍历得到的序

列是(①)，而进行广度优先遍历得到的顶点序列是(②)。【中科院软件所1999六、2-

(1)(2分]

①.A.B.C.).E.以上答案均

不正确

②.A.B.C.I).E.以上答案

均不正确

19.下面哪一方法可以判断出一个有向图是否有环(回路)：【东北大学20004、2(4分】

A.深度优先遍历B.拓扑排序C.求最短路径D.求关键路径

20.在图采用邻接表存储时，求最小生成树的Prim算法的时间复杂度为()。

A.0(n)B.0(n+e)C.0(n2)D.0(n3)

【合肥工业大学2001一、2(2分】

21.下面是求连通网的最小生成树的prim算法:集合VT,ET分别放顶点和边,初始为(1),

下面步骤重复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)加入ETB.顶点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中有nT条边时为生成树，否则无解D.ET中无回路时，为生成树，否

则无解

22.(1).求从指定源点到其余各顶点的迪杰斯特拉(Dijkstra)最短路径算法中弧上权不

能为负的原因是在实际应用中无意义；

(2).利用Dijkstra求每一对不同顶点之间的最短路径的算法时间是0(/)；(图用邻

接矩阵表示)

(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.0(n)B.0(n+c)C.0(n*n)D.0(n*n*n)

25.已知有向图G=(V,E),其中V={%,Ve,Vj,

E={<%,V2>,<V1,V3>,<V,,V4>,<V2,V5>,<V;(,VD,<V3,V6>,<V,bV6>,<V5,V7>,<V6,%>},G的拓扑序列

是()。

A.V——VTB.VbV3,V2,V6,V4,V5,V7

C.VI,V3)V4)V5(V2)V6)V7D.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中有弧<Vi,Vj>B.G中有一条从Vi到Vj的路径

C.G中没有弧〈Vi,Vj>D.G中有一条从Vj到Vi的路径

【南京理工大学2000一、9（1.5分】

29.在用邻接表表示图时，拓扑排序算法时间复杂度为（）o

A.0（n）B.O（n+e）C.O（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.下列关于A0E网的叙述中，不正确的是（）。

A.关键活动不按期完成就会影响整个工程的完成时间

B.任何一个关键活动提前完成，那么整个工程将会提前完成

C.所有的关键活动提前完成，那么整个工程将会提前完成

D.某些关键活动提前完成，那么整个工程将会提前完成

【北方交通大学1999一、7（3分）】【北京工业大学1999一、1（2分）】

二、判断题

L树中的结点和图中的顶点就是指数据结构中的数据元素。（）【青岛大学2001四、1（1

分】

2.在n个结点的无向图中，若边数大于n-1,则该图必是连通图）【中科院软件所1997

一、4（1分】

3.对有n个顶点的无向图，其边数e与各顶点度数间满足下列等式e=，w。（）

【南京航空航天大学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一、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算法求解各顶点的最短路径时，每个表示两点间路径的path-Il,J]一定是

path”[I,J]的子集（k=l,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一、13]

40.既使有向无环图的拓扑序列唯一，也不能唯一确定该图。()【合肥工业大学2001

二、6(1分】

41.若一个有向图的邻接矩阵对角线以下元素均为零，则该图的拓扑有序序列必定存在。

()

【中科院软件所1997一、5(1分】

42.A0V网的含义是以边表示活动的网。()【南京航空航天大学1995五、7(1分】

43.对一个AOV网，从源点到终点的路径最长的路径称作关键路径。【南京航空航天大学1995

五、9(1分】

44.关键路径是A0E网中从源点到终点的最长路径。()【青岛大学2000四、10(1分】

45.A0E网一定是有向无环图。()【青岛大学2001一、9(1分】

46.在表示某工程的AOE网中，加速其关键路径上的任意关键活动均可缩短整个工程的完成

时间。()

【长沙铁道学院1997—、2(1分)】

47.在AOE图中，关键路径上某个活动的时间缩短，整个工程的时间也就必定缩短。()

【大连海事大学2001—、15(1分】

48.在A0E图中，关键路径上活动的时间延长多少，整个工程的时间也就随之延长多少。

()

【大连海事大学2001一、16(1分】

49.当改变网上某一关键路径上任一关键活动后，必将产生不同的关键路径。【上海交通大

学1998一、14]

三、填空题

1.判断一个无向图是一棵树的条件是O

2.有向图G的强连通分量是指。【北京科技大学1997一、7]

3.一个连通图的是一个极小连通子图。【重庆大学2000一、1】

4.具有10个顶点的无向图，边的总数最多为。【华中理工大学2000-、7(1分】

5.若用n表示图中顶点数目，则有条边的无向图成为完全图。【燕山大学1998-、

6(1分】

6.设无向图G有n个顶点和e条边，每个顶点Vi的度为di(l<=i<=n〉，则e=

【福州大学大学二、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个顶点的有向图，至少需要量_条弧Q

才能保证是连通的。【西南交通大学2000一、3]

16.右图中的强连通分量的个数为(

【北京邮电大学2001二、5(2分】

17.N个顶点的连通图用邻接矩阵表示时，该矩阵Q

至少有个非零元素。【中科院计算所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-firstsearch遍历图的时间复杂度；

depth-firstsearch遍历图的时间复杂度，两者不同之处在于，反映在数据

结构上的差别是o

【厦门大学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(GD=V(G),E(G’)={(1,3),(3,6),(7,3),(1,2),

(1,5),(2,4)},则采用的遍历方法是.

【南京理工大学1997三、6。分】

24.为了实现图的广度优先搜索，除了一个标志数组标志已访问的图的结点外，还需

存放被访问的结点以实现遍历。【南京理工大学1999二、9(2分】

25.按下图所示，画出它的广度优先生成树_和深度优先生成树______。

【西安电子科技大学1998三、6(5分】(fY———————–Q

26.构造连通网最小生成树的两个典型算法是。【北京科技大学1998-、5]

27.求图的最小生成树有两种算法，算法适合于求稀疏图的最小生成树。

【南京理工大学2001二、6(2分】

28.Prim(普里姆)算法适用于求的网的最小生成树；kruskal(克鲁斯卡尔)算法

适用于求的网的最小生成树。【厦门大学1999一、4]

29.克鲁斯卡尔算法的时间复杂度为它对图较为适合。【中科院计算所1999

二、3(2分)】

30.对于含N个顶点E条边的无向连通图，利用Prim算法生成最小代价生成树其时间复杂

度为，利用Kruskal算法生成最小代价生成树其时间复杂度为。【长沙铁道学

院1998二、2(4分)】

31.下面描述的是一种构造最小生成树算法的基本思想。设要处理的无向图包括n个节点

VI,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)置成o

(3).算法结束时，相邻矩阵中的元素指出最小生成树的。【山东工业大学1998

二、4(6分】

32.有一个用于n个顶点连通带权无向图的算法描述如下：

(1).设集合T1与T2,初始均为空；

(2).在连通图上任选一点加入T1；

(3).以下步骤重复n-1次：

a.在i属于Tl,j不属于T1的边中选最小权的边；

b.该边加入T2。

上述算法完成后，T2中共有条边，该算法称算法，T2中的边构成图的。

【南京理工大学1999二、7(4分】

33.有向图G可拓扑排序的判别条件是。【长沙铁道学院1998二、9(2分)】

34.Dijkstra最短路径算法从源点到其余各顶点的最短路径的路径长度按次序依次

产生,该算法弧上的权出现情况时，不能正确产生最短路径。【南京理工大学1999二、

8(4分】

35.求从某源点到其余各顶点的Dijkstra算法在图的顶点数为10,用邻接矩阵表示图时计

算时间约为10ms,则在图的顶点数为40,计算时间约为ins。【南京理工大学2000二、

3(1.5分】

36.求最短路径的Dijkstra算法的时间复杂度为。【哈尔滨工业大学2001一、5(2

分】

37.有向图G=(V,E),其中V(G)={0,1,2,3,4,5),用<a,b,d>三元组表示弧<a,b>及弧上的权

d.E(G)为{<0,5,100>,<0,2,10X1,2,5X0,4,30X4,5,60X3,5,10X2,3,50X4,3,20>},则

从源点0到顶点3的最短路径长度是，经过的中间顶点是I南京理工大学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网中，存在环意味着,这是的；对程序的数据流图来说，它表明

存在0

【厦门大学19992]

43.当一个AOV网用邻接表表示时，可按下列方法进行拓扑排序。

(1).查邻接表中入度为的顶点，并进栈；

(2).若栈不空，则①输出栈顶元素Vj,并退栈；②查Vj的直接后继Vk,对Vk入度处

理，处理方法是；

(3).若栈空时，输出顶点数小于图的顶点数，说明有,否则拓扑排序完成。

【南京理工大学1996二、3(6分】

44.已知图的邻接表结构为：

CONSTvtxnum=｛图的顶点数｝

TYPEvtxptr=l..vtxnum;

arcptr=“arcnode;

arcnode=RECORDadjvex:vtxptr;nextarc:arcptrEND;

vexnode=RECORDvexdata:｛和顶点相关的信息｝;firstarc:arcptrEND;

adjlist=ARRAY[vtxptr]OFvexnode;

本算法是实现图的深度优先遍历的非递归算法。其中，使用一个顺序栈stack。栈顶指针为

topovisited为标志数组。

PROCdfs(g:adjlist;vO:vtxptr);

top=0;write(vO);visited[vO]:=ture;p:=g[vO].firstarc;

WHILE(topOO)OR(pONIL)DO

[WHILE。)DO

[v:二p~.adjvex;

IF(2)THENp:=p.nextarc

ELSE[write(v);visited[v]:=true;top:=top+l;stack[top]:=p;

(3)]]

IFtopOOTHEN[p:=stack[top];top:=top-l;]

]

ENDP.同济大学2000二、2(10分)]

45.下面的算法完成图的深度优先遍历，请填空。

PROGRAMgraph_traver;

CONSTn1=max_node_number;

TYPEvtxptr=l..nl;vtxptr0=0..nl;

arcptr=“arcnode;

arcnode=REC0RDvexi,vexj:vtxptr;nexti,nextj:arcptr;END;;

vexnode二RECORDvexdata:char;firstin,firstout:arcptr;END;

graph=ARRAY[vtxptrO]OFvexnode;

VARga:graph;n:integer;

visited:ARRAY[vtxptrO]OFboolean;

FUNCorder(g:graph;v:char):vtxptr;

(1)；i:=n;

WHILEg[i].vexdataOvDOi:=i-l;

order:=i;

ENDF；

PROCcreat(varg:graph);

readln(n,e);

FORi:=1TOnDO[readln(g[i].vexdata);g[i].firstin:=NIL;

g[i].firstout:=NIL;]

FORk:=1TOeDO[readIn(vt,vh);

i:=order(g,vt);j:=order(g,vh);new(p);pvexi:=i;p^.vexj:=j

p二nextj:=(2);⑶:=p;

p exti:=:(4);⑸:=p;]

ENDP;

FUNCfirstadj(g:graph;v:char):vtxptrO;

i:=order(g,v);p:=g[i].firstout;

IFpONILTHENfirstadj:=⑥ELSEfirstadj:=O;

ENDF;

FUNCnextadj(g:graph;v:char;w:char):vtxptrO;

i:=order(g,v);j:=order(g,w);p:-(7);

WHILE(pONIL)AND(pvexjOj)1)0(8);

IF(9)AND(10)THENnextadj:=p extivexjELSEnextadj:=0;

ENDF;

PROCdfs(g:graph;vO:char);

write(vO:2);visited[order(g,vO)]:=true;w:=(ll);

WHILEwOODO

[IF(12)THENdfs(g,g[w].vexdata);

w-(13);]

ENDP;

PROCtraver(g:graph);

FORi:=lTOnDOvisited[i]:=false;

FORi:=lTOnDOIFNOTvisited[i]THENdfs(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)

while(check())

{vex=pop();printf(vex);count++；

for(i=0;i<n;i++)

{k=array(6)

if((7)){indegree[i]—;if(^8))push(i);}

)

)

if(count<n)printf(““图有回路”)；

}【南京理工大学2000三、4(6分】

47.假设给定的有向图是用邻接表表示，作为输入的是图中顶点个数n和边的个数叫以及

图的m条边。在下面的程序中，我们用readdata程序过程输入图的信息，并建立该图的邻

接表；利用topol程序过程获得图中顶点的一个拓扑序列。

PROGRAMtopolorder(input,output);

CONSTmaxn=20;

TYPEnodeptr二人nltype;

nltype二RECORDnum:integer;1ink:nodeptrEND;

chtype二RECORDcount:integer;head:nodeptrEND;

VARch:ARRAY[1..maxn]OFchtype;m,n,top:integer;

PROCEDUREreaddata;

VARi,j,u,v:integer;p:nodeptr;

BEGIN

write(‘inputvertexnumbern=，)；readln(n);

write(‘inputedgenumberm=’)；readln(m);

FORi:=lTOnDOBEGINch[i].count:=0;ch[i].head:=NILEND;

writein(7inputedges:

FORj:=1TOmDO

BEGINwrite(j:3,‘:’);readln(u,v);new(p);

ch[v].count:=ch[v].count+1;p um:=v;⑴;(2);END

END;

PROCEDUREtopol;

VARi,j,k:integer;t:nodeptr;

BEGIN

top:=0;

FORi:=1TOnDO

IFch[i].count=0THENBEGINch[i].count:=top;top:=iEND;

i:=0;

WHILE(3)DO

BEGIN(4);⑸;write(j:5);i:=i+1；t:=ch[j].head;

WHILEtONILDO

BEGINk:=t”.num;ch[k].count:=ch[k].count-1;

IFch[k].count=0THENBEGINch[k].count:=top;top:=k

END;

(6);END

END;writein;

IFi<nTHENwritein(‘thenetworkhasacycle!’)

END;

BEGIN

readdata;writein(‘outputtopolorder:topol

END.【复旦大学1995三(18分】

48.如下为拓扑排序的C程序，

(1).列出对右图执行该程序后的输出结果。

(2).在程序空白处填上适当语句。

voidtopsort(hdnodesgraph[],intn)

{inti,j,k,top;node_pointerptr;

top=T;

for(i=0;i<n;i++)

if(!graph[i].count){graph[i].count=top;top=i;}

for(i=0;i<n;i++)

if(1){fprintf(stderr,” graphhasacycle’n”);exit(l);}

else{.i=top;(2);printf(“v%d,,j);

for(ptr=graph[j].link;ptr;ptr=ptr->link)

{k=ptr->vertex;graph[k].count―;

if((3)){graph[k].count=top;top=k;}}}

)【浙江大学2000六(15分)】

四、应用题

1.(1).如果G1是个具有n个顶点的连通无向图，那么G1最多有多少条边？G1最少有

多少条边？

(2).如果G2是一个具有n个顶点的强连通有向图，那么G2最多有多少条边？G2最少

有多少条边？

(3).如果G3是一个具有n个顶点的弱连通有向图，那么G3最多有多少条边？G3最少

有多少条边？

【复旦大学1997…(9分】

2.n个顶点的无向连通图最少有多少条边？n个顶点的有向连通图最少有多少条边？

【山东大学2000—、3(4分)】

3.一个二部图的邻接矩阵A是一个什么类型的矩阵？【北京科技大学1999一、8(2分】

4.脚具有n个顶点和多于n-1条边的无向连通图G一定不是树。【东南大学1993四(10

分】

5.证明对有向图的顶点适当的编号，可使其邻接矩阵为下三角形且主对角线为全0的充要

条件是该图为无环图。【北京邮电大学2002三(10分】

6.用邻接矩阵表示图时，矩阵元素的个数与顶点个数是否相关？与边的条数是否有关？

【西安电子科技大学2000计应用一、6(5分】

7.请回答下列关于图(Graph)的一些问题：(每题4分)

(1).有n个顶点的有向强连通图最多有多少条边?最少有多少条边？

(2).表示有1000个顶点、1000条边的有向图的邻接矩阵有多少个矩阵元素？是否稀

疏矩阵？

(3).对于一个有向图，不用拓扑排序，如何判断图中是否存在环？【清华大学2000

一(12分】

8.解答问题。设有数据逻辑结构为：

B=(K,R),K={kl,k2,…，k9}

R={<kl,k3>,<kl,k8>,<k2,k3>,<k2,k4>,<k2,k5>,<k3,k9>,<k5,k6>,<k8,k9>,

<k9,k7>,<k4,k7>,<k4,k6>}

(1).画出这个逻辑结构的图示。(3分)

(2).相对于关系r,指出所有的开始接点和终端结点。(2分)

(3).分别对关系r中的开始结点，举出一个拓扑序列的例子。(4分)

(4).分别画出该逻辑结构的正向邻接表和逆向邻接表。(6分)【山东工业大学1999三

(15分】

9.有向图的邻接表存储如下：(1).画出其邻接矩阵存储