发布时间 : 星期五 文章数据结构历年考研试题第7章图更新完毕开始阅读
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 while (check( )) { vex=pop( ); printf(vex); count++; for (i=0;i { k=array(6)_______ if ((7)_______ ) { indegree[i]--; if ((8)_______ ) push(i); } } } if( count 47.假设给定的有向图是用邻接表表示,作为输入的是图中顶点个数n和边的个数m, 以及图的m条边。在下面的程序中,我们用readdata程序过程输入图的信息,并建立该图的邻接表;利用topol程序过程获得图中顶点的一个拓扑序列。 PROGRAM topol_order(input , output) ; CONST maxn=20 ; TYPE nodeptr=^nltype ; nltype=RECORD num : integer ; link : nodeptr END ; chtype=RECORD count : integer ; head : nodeptr END ; VAR ch : ARRAY [1 .. maxn] OF chtype ; m , n , top : integer ; PROCEDURE readdata ; VAR i , j , u , v : integer ; p : nodeptr ; BEGIN write (′input vertex number n= ′); readln (n) ; write (′input edge number m= ′); readln(m) ; FOR i:=1 TO n DO BEGIN ch[i].count:= 0; ch[i].head:=NIL END; writeln(′input edges :′); FOR j:= 1 TO m DO BEGIN write( j :3 , ′: ′) ; readln( u , v ) ; new( p ) ; ch[v].count:=ch[v].count+1; p^.num:=v; (1) ___ ; (2) __; END END ; PROCEDURE topol ; VAR i, j, k: integer; t: nodeptr ; BEGIN top:= 0 ; FOR i := 1 TO n DO IF ch[i].count=0 THEN BEGIN ch[i].count := top ;top := i END; i:= 0 ; WHILE (3) ___ DO BEGIN (4) __; (5) __ ; write(j : 5) ;i:= i + 1 ;t:=ch[j].head ; WHILE t<>NIL DO BEGIN k := t^.num ; ch[k].count:=ch[k].count–1 ; IF ch[k].count=0 THEN BEGIN ch[k].count:=top; top:=k END; (6) ______ ; END END ; writeln; IF i readdata ; writeln (′output topol order : ′); topol END. 【复旦大学 1995 三 (18分)】 48.如下为拓扑排序的C程序, V2 (1).列出对右图执行该程序后的输出结果。 (2).在程序空白处填上适当语句。 V1 V3 V5 void topsort(hdnodes graph [],int n) V4 V6 {int i,j,k,top; node_pointer ptr ; top=-1; for (i=0; i if (!graph[i].count){graph[i].count=top; top=i; } for (i=0; i if(1)____ {fprintf(stderr, \ else {j=top;(2)_____; printf( \ 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个顶点、l000条边的有向图的邻接矩阵有多少个矩阵元素?是否稀 疏矩阵? (3).对于一个有向图,不用拓扑排序,如何判断图中是否存在环?【清华大学2000一(12分)】