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开始遍历图，得到的序列为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分）】
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,5,100>,<0,2,10><1,2,5><0,4,30><4,5,60><3,5,10><2,3,50><4,3,20>}，则从源点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=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);
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 for(i=0,i for (j=0;j topsort (array,indegree,n) { count= ((4)_______) for (i=0;i { vex=pop( ); printf(vex); count++; for (i=0;i { k=array(6)_______