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 ENDE42．在 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；