2011年軟考程序員考試復習筆試知識點整理(4)

　　7、圖

　　1. 圖的基本概念：圖的定義和特點，無向圖，有向圖，入度，出度，完全圖，生成子圖，路徑長度，回路，(強)連通圖，(強)連通分量等概念。

　　2. 圖的幾種存儲形式：鄰接矩陣，(逆)鄰接表，十字鏈表及鄰接多重表。在考查時，有的學校是給出一種存儲形式，要求考生用算法或手寫出與給定的結構相對應的該圖的另一種存儲形式。

　　3. 考查圖的兩種遍歷算法：深度遍歷和廣度遍歷

　　深度遍歷和廣度遍歷是圖的兩種基本的遍歷算法，這兩個算法對圖一章的重要性等同于“先序、中序、后序遍歷”對于二叉樹一章的重要性。在考查時，圖一章的算法設計題常常是基于這兩種基本的遍歷算法而設計的，比如：“求最長的最短路徑問題”和“判斷兩頂點間是否存在長為K的簡單路徑問題”，就分別用到了廣度遍歷和深度遍歷算法。

　　4. 生成樹、最小生成樹的概念以及最小生成樹的構造：PRIM算法和KRUSKAL算法。

　　考查時，一般不要求寫出算法源碼，而是要求根據(jù)這兩種最小生成樹的算法思想寫出其構造過程及最終生成的最小生成樹。

　　5. 拓撲排序問題：

　　拓撲排序有兩種方法，一是無前趨的頂點優(yōu)先算法，二是無后繼的頂點優(yōu)先算法。換句話說，一種是“從前向后”的排序，一種是“從后向前”排。當然，后一種排序出來的結果是“逆拓撲有序”的。

　　6. 關鍵路徑問題：

　　這個問題是圖一章的難點問題。理解關鍵路徑的關鍵有三個方面：

　　一是何謂關鍵路徑;

　　二是最早時間是什么意思、如何求;

　　三是最晚時間是什么意思、如何求。

　　簡單地說，最早時間是通過“從前向后”的方法求的，而最晚時間是通過“從后向前”的方法求解的，并且，要想求最晚時間必須是在所有的最早時間都已經求出來之后才能進行。

　　在實際設計關鍵路徑的算法時，還應該注意以下這一點：采用鄰接表的存儲結構，求最早時間和最晚時間要采用不同的處理方法，即：在算法初始時，應該首先將所有頂點的最早時間全部置為0。關鍵路徑問題是工程進度控制的重要方法，具有很強的實用性。

　　7. 最短路徑問題：

　　與關鍵路徑問題并稱為圖一章的兩只攔路虎。概念理解是比較容易的，關鍵是算法的理解。最短路徑問題分為兩種：一是求從某一點出發(fā)到其余各點的最短路徑(單源最短路徑);二是求圖中每一對頂點之間的最短路徑。這個問題也具有非常實用的背景特色，一個典型的應該就是旅游景點及旅游路線的選擇問題。解決第一個問題用DIJSKTRA算法，解決第二個問題用FLOYD算法，注意區(qū)分。

　　軟考程序員考試歷年真題重點題總結及答案

　　2011年上半年軟考報名時間及方式匯總

　　軟考程序員考試歷年真題匯總(2007年-2010年)