【文章內(nèi)容簡介】 于圖的頂點(diǎn)數(shù)，說明有______，否則拓?fù)渑判蛲瓿?。【南京理工大學(xué) 1996 二、3 （6分）】44．已知圖的鄰接表結(jié)構(gòu)為： CONST vtxnum={圖的頂點(diǎn)數(shù)} TYPE vtxptr=1..vtxnum。 arcptr=^arode。 arode=RECORD adjvex:vtxptr。 nextarc:arcptr END。 vexnode=RECORD vexdata:{和頂點(diǎn)相關(guān)的信息}；firstarc:arcptr END。adjlist=ARRAY[vtxptr]OF vexnode。 本算法是實(shí)現(xiàn)圖的深度優(yōu)先遍歷的非遞歸算法。其中，使用一個順序棧stack。棧頂指針為top。visited為標(biāo)志數(shù)組。PROC dfs(g:adjlist。v0:vtxptr)。 top=0。 write(v0)。 visited[v0]:=ture。 p:=g[v0].firstarc。 WHILE (top0)OR(pNIL)DO[WHILE(1)_______DO[v:=p^.adjvex。IF(2)_______ THEN p:=p^.nextarcELSE [write(v)。 visited[v]:=true。 top:=top+1。 stack[top]:=p。 (3)_______] ]IF top0 THEN[p:=stack[top]。 top:=top1。 (4)_______] ] 2000 二、2 (10分)】45．下面的算法完成圖的深度優(yōu)先遍歷，請?zhí)羁铡?PROGRAM graph_traver。 CONST nl=max_node_number。 TYPE vtxptr=1..nl。 vtxptr0=0..nl。 arcptr=^arode。 arode=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].vexdatav DO i:=i1。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:=jp^.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 pNIL 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(pNIL ) AND (p^.vexjj) 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 w0 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。BEGINcreat(ga)。 traver(ga)。END. 【北方交通大學(xué) 1999 三 （20分）】46．n個頂點(diǎn)的有向圖用鄰接矩陣array表示，下面是其拓?fù)渑判蛩惴?，試補(bǔ)充完整。注：（1）．圖的頂點(diǎn)號從 0開始計(jì)； （2）．indegree 是有n個分量的一維數(shù)組，放頂點(diǎn)的入度；（3）．函數(shù) crein 用于算頂點(diǎn)入度； （4）．有三個函數(shù)push(data),pop( ),check( )其含義為數(shù)據(jù) data進(jìn)棧，退棧和測試棧是否空（不空返回1，否則0）。 crein( array ,indegree,n) { for (i=0。in。i++) indegree[i]= ((1)_______) for(i=0,in。i++) for (j=0。jn。 j++) indegree[i]+=array[(2)_______][(3)_______]。 } topsort (array,indegree,n) { count= ((4)_______) for (i=0。in。i++) if ((5)_______) push(i) while (check( )) { vex=pop( )。 printf(vex)。 count++。 for (i=0。in。i++) { k=array(6)_______ if ((7)_______ ) { indegree[i]。 if ((8)_______ ) push(i)。 } } } if( countn) printf(““圖有回路”)； } 【南京理工大學(xué) 2000 三、4 （6分）】 47．假設(shè)給定的有向圖是用鄰接表表示，作為輸入的是圖中頂點(diǎn)個數(shù)n和邊的個數(shù)m, 以及圖的m條邊。在下面的程序中，我們用readdata程序過程輸入圖的信息，并建立該圖的鄰接表；利用topol程序過程獲得圖中頂點(diǎn)的一個拓?fù)湫蛄?。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) __。 ENDEND 。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 tNIL 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 in THEN writeln (′the network has a cycle!′) END。BEGIN readdata 。 writeln (′output topol order : ′)。 topolEND. 【復(fù)旦大學(xué) 1995 三 （18分）】V1V2V3V4V5V648．如下為拓?fù)渑判虻腃程序，（1）．列出對右圖執(zhí)行該程序后的輸出結(jié)果。（2）．在程序空白處填上適當(dāng)語句。void topsort(hdnodes graph [],int n){int i,j,k,top。 node_pointer ptr 。 top=1。 for (i=0。 in。 i++) if (!graph[i].count){graph[i].count=top。 top=i。 } for (i=0。 in。 i++) if(1)____ {fprintf(stderr, \ngraph has a cycle \n)。 exit(1)。 } else {j=top。(2)_____。 printf( v%d, ,j) 。for (ptr=graph[j].link。 ptr。 ptr=ptrlink){k=ptrvertex。 graph[k].count。 if((3)_____) {graph[k].count=top。 top=k。 } } } } 【浙江大學(xué) 2000 六(15分)】四、 應(yīng)用題1．（1）．如果G1是一個具有n個頂點(diǎn)的連通無向圖，那么G1最多有多少條邊？G1最少有多少條邊？（2）．如果G2是一個具有n個頂點(diǎn)的強(qiáng)連通有向圖，那么G2最多有多少條邊？G2最少有多少條邊？（3）．如果G3是一個具有n個頂點(diǎn)的弱連通有向圖，那么G3最多有多少條邊？G3最少有多少條邊？ 【復(fù)旦大學(xué) 1997 一 （9分）】2．n個頂點(diǎn)的無向連通圖最少有多少條邊？n個頂點(diǎn)的有向連通圖最少有多少條邊？【山東大學(xué) 2000 一、3 (4分)】3．一個二部圖的鄰