五算法設計題
．(單獨命題考生做)設無向圖G有n個頂點m條邊試編寫用鄰接表存儲該圖的算法(設頂點值用～n或～n編號) 【南京航空航天大學 十二 (分)】
．請用流程圖或類高級語言(pascal或c)表示算法已知有向圖有n個頂點請寫算法根據用戶輸入的偶對建立該有向圖的鄰接表即接受用戶輸入的<vivj>(以其中之一為標志結束)對於每條這樣的邊申請一個結點並插入到的單鏈表中如此反復直到將圖中所有邊處理完畢提示先產生鄰接表的n個頭結點(其結點數值域從到n)【上海大學 四 (分)】
．設無向圖G有n個點e條邊寫一算法建立G的鄰接多表要求該算法時間復雜性為O(n+e)且除鄰接多表本身所占空間之外只用O()輔助空間【東南大學 六(分) 二 (分)】
．給出以十字鏈表作存儲結構建立圖的算法輸入(ijv)其中ij為頂點號v為權值【河海大學 六 (分)】
．設有向G圖有n個點(用…n表示)e條邊寫一算法根據其鄰接表生成其反向鄰接表要求算法復雜性為O(n+e)【東南大學 三 (分)】
類似本題的另外敘述有
()下圖(編者略)是有向圖按出度建立的鄰接表試寫一算法將此出度鄰接表改成入度建立的鄰接表【北京郵電大學 五 (分)】
()編寫算法實現以下功能根據含有n個頂點的有向圖鄰接表構造相應的逆鄰接表【東南大學 六(分)】
[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []
From:http://tw.wingwit.com/Article/program/sjjg/201311/23098.html
