2011年軟考程序員考試復(fù)習(xí)筆試知識(shí)點(diǎn)整理(4)

　　7、圖

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

　　2. 圖的幾種存儲(chǔ)形式：鄰接矩陣，(逆)鄰接表，十字鏈表及鄰接多重表。在考查時(shí)，有的學(xué)校是給出一種存儲(chǔ)形式，要求考生用算法或手寫出與給定的結(jié)構(gòu)相對(duì)應(yīng)的該圖的另一種存儲(chǔ)形式。

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

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

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

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

　　5. 拓?fù)渑判騿栴}：

　　拓?fù)渑判蛴袃煞N方法，一是無前趨的頂點(diǎn)優(yōu)先算法，二是無后繼的頂點(diǎn)優(yōu)先算法。換句話說，一種是“從前向后”的排序，一種是“從后向前”排。當(dāng)然，后一種排序出來的結(jié)果是“逆拓?fù)溆行颉钡摹?/P>

　　6. 關(guān)鍵路徑問題：

　　這個(gè)問題是圖一章的難點(diǎn)問題。理解關(guān)鍵路徑的關(guān)鍵有三個(gè)方面：

　　一是何謂關(guān)鍵路徑;

　　二是最早時(shí)間是什么意思、如何求;

　　三是最晚時(shí)間是什么意思、如何求。

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

　　在實(shí)際設(shè)計(jì)關(guān)鍵路徑的算法時(shí)，還應(yīng)該注意以下這一點(diǎn)：采用鄰接表的存儲(chǔ)結(jié)構(gòu)，求最早時(shí)間和最晚時(shí)間要采用不同的處理方法，即：在算法初始時(shí)，應(yīng)該首先將所有頂點(diǎn)的最早時(shí)間全部置為0。關(guān)鍵路徑問題是工程進(jìn)度控制的重要方法，具有很強(qiáng)的實(shí)用性。

　　7. 最短路徑問題：

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

　　軟考程序員考試歷年真題重點(diǎn)題總結(jié)及答案

　　2011年上半年軟考報(bào)名時(shí)間及方式匯總

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