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

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

2013-11-15 15:13:47  來源: 數據結構 

  .設計算法求出無向連通圖中距離頂點V的最短路徑長度(最短路徑長度以邊數為單位計算)為K的所有的結點要求盡可能地節省時間【西北大學 七】

  .自由樹(即無環連通圖)T=(VE)的直徑是樹中所有點對間最短路徑長度的最大值即T的直徑定義為MAX D(uv) 這裡D(uv) (uv∈V)表示頂點u到頂點v的最短路徑長度(路徑長度為路徑中所包含的邊數)寫一算法求T的直徑並分析算法的時間復雜度(時間復雜度越小得分越高)【中科院 (分)】

  .求圖的中心點的算法設V是有向圖G的一個頂點我們把V的偏心度定義為max{從w到v的最短距離|w是g中所有頂點}如果v是有向圖G中具有最小偏心度的頂點則稱頂點v是G的中心點【長沙鐵道學院 (分)】

  .設G是含有n頂點(設頂點編號為n)的有向無環圖將G用如下定義的鄰接表存儲

  TYPE   arcptr=↑arcnode;
  arcnode=RECORD{鄰接表中的結點}
  adjvex:n;  nextarc:arcptr; END;
  vexnode=RECORD{鄰接表的表頭結點}
  vexnum: n;  firstarc:arcptr;  mpl:integer  END;
  Hnodes=ARRAY[n] OF  vexnode;

  請編寫一個非遞歸算法求G的每個頂點出發的最長路徑的長度(每條弧的長度均為)並存入mpl域中 要求首先寫出算法思想然後寫算法過程【山東科技大學 六 (分)】

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


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