熱點推薦:
您现在的位置: 電腦知識網 >> 編程 >> 數據結構 >> 正文

數據結構考研分類復習真題 第七章 圖[22]

2013-11-15 15:15:42  來源: 數據結構 

   當一個AOV網用鄰接表表示時可按下列方法進行拓撲排序

  ().查鄰接表中入度為______的頂點並進棧

  ().若棧不空則①輸出棧頂元素Vj並退棧②查Vj的直接後繼Vk對Vk入度處理處理方法是______

  ().若棧空時輸出頂點數小於圖的頂點數說明有______否則拓撲排序完成【南京理工大學 (分)】

  .已知圖的鄰接表結構為

  CONST  vtxnum={圖的頂點數}
  TYPE vtxptr=vtxnum;
  arcptr=^arcnode;
  arcnode=RECORD adjvex:vtxptr; nextarc:arcptr END;
  vexnode=RECORD vexdata:{和頂點相關的信息}firstarc:arcptr  END;
  adjlist=ARRAY[vtxptr]OF  vexnode;

  本算法是實現圖的深度優先遍歷的非遞歸算法其中使用一個順序棧stack棧頂指針為topvisited為標志數組

  PROC dfs(g:adjlist;v:vtxptr);
  top=; write(v); visited[v]:=ture; p:=g[v]firstarc;
  WHILE (top<>)OR(p<>NIL)DO
  [WHILE()_______DO
  [v:=p^adjvex;
  IF()_______ THEN  p:=p^nextarc
  ELSE [write(v);  visited[v]:=true; top:=top+;  stack[top]:=p; ()_______] ]
  IF top<>  THEN[p:=stack[top]; top:=top; ()_______]
  ]
  ENDP 【同濟大學   (分)】

[]  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  


From:http://tw.wingwit.com/Article/program/sjjg/201311/23129.html
    推薦文章
    Copyright © 2005-2013 電腦知識網 Computer Knowledge   All rights reserved.