数据结构考研分类复习真题 第七章 图[23]

数据结构考研分类复习真题 第七章 图[23]  

　　 ．下面的算法完成图的深度优先遍历 请填空

　　PROGRAM graph_traver;　　CONST nl=max_node_number;　　TYPE vtxptr= nl; vtxptr = nl;　　arcptr=^arcnode;　　arcnode=RECORD vexi vexj: vtxptr; nexti nextj: arcptr; END;;　　vexnode=RECORD vexdata: char; firstin firstout: arcptr; END;　　graph=ARRAY[vtxptr ] OF vexnode ;　　VAR ga:graph; n: integer;　　visited: ARRAY[vtxptr ] OF boolean ;　　FUNC order (g: graph; v: char): vtxptr;　　( )_______; i:=n;　　WHILE g[i] vexdata<>v DO i:=i ;　　order:=i;　　ENDF 　　PROC  creat(var g: graph);　　readln(n e);　　FOR i:= TO n DO [readln(g[i] vexdata); g[i] firstin :=NIL ; g[i] firstout:=NIL;]　　FOR k:= TO e DO [readln (vt vh);　　i:=order (g vt); j:=order (g vh);  new (p); p^ vexi:=i ;  p^ vexj:=j　　p^ nextj:= ____( )____;   ___( )____ :=p;　　p^ nexti:=: ____( )____;  ___( )____ :=p;]　　ENDP;　　FUNC firstadj(g:graph; v:char): vtxptr ;　　i:=order(g v); p:=g[i] firstout;　　IF p<>NIL THEN firstadj:=( )_______ELSE firstadj:= ;　　ENDF;　　FUNC nextadj(g:graph; v:char; w:char): vtxptr ;　　i:=order(g v); j:=order(g w); p:=( )_______;　　WHILE(p<>NIL ) AND (p^ vexj<>j) DO( )______;　　IF ( )______AND( )______THEN  nextadj:=p^ nexti^ vexj  ELSE  nextadj:= ;　　ENDF;　　PROC dfs(g:graph; v :char);　　write(v : ); visited[order(g v )]:=true;  w:=( )_______;　　WHILE w<> DO　　[IF ( )______ THEN dfs(g g[w] vexdata);　　w:=( )_______;]　　ENDP;　　PROC traver(g:graph);　　FOR i:= TO n DO visited[i]:=false;　　FOR i:= TO n DO IF NOT visited[i] THEN  dfs(g g[i] vexdata);　　ENDP;　　BEGIN　　creat(ga); traver(ga);　　END 【北方交通大学 三( 分)】