2011計(jì)算機(jī)考研備考之?dāng)?shù)據(jù)結(jié)構(gòu)（2）_跨考網(wǎng)

第六章 圖

如果說(shuō)，從線性結(jié)構(gòu)向樹形結(jié)構(gòu)研究的轉(zhuǎn)變，是數(shù)據(jù)結(jié)構(gòu)學(xué)科對(duì)數(shù)據(jù)組織形式研究的一次升華，那么從樹形結(jié)構(gòu)的研究轉(zhuǎn)到圖形結(jié)構(gòu)的研究，則進(jìn)一步讓我們看到了數(shù)據(jù)結(jié)構(gòu)對(duì)于解決實(shí)際問題的重大推動(dòng)作用。圖這一章的特點(diǎn)是：概念繁多，與離散數(shù)學(xué)中圖的概念聯(lián)系緊密，算法復(fù)雜，極易被考到，且容易出大題，尤其是名校，作為考研課程，如果不考查樹與圖兩章的知識(shí)，幾乎是不可想像的。下面我們看一下圖這一章的主要考點(diǎn)以及這些考點(diǎn)的考查方式：

1. 考查有關(guān)圖的基本概念問題：這些概念是進(jìn)行圖一章學(xué)習(xí)的基礎(chǔ)，這一章的概念包括：圖的定義和特點(diǎn)，無(wú)向圖，有向圖，入度，出度，完全圖，生成子圖，路徑長(zhǎng)度，回路，（強(qiáng)）連通圖，（強(qiáng)）連通分量等概念。與這些概念相聯(lián)系的相關(guān)計(jì)算題也應(yīng)該掌握。

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

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

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

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

6. 關(guān)鍵路徑問題：這個(gè)問題是圖一章的難點(diǎn)問題。理解關(guān)鍵路徑的關(guān)鍵有三個(gè)方面：一是何謂關(guān)鍵路徑，二是最早時(shí)間是什么意思、如何求，三是最晚時(shí)間是什么意思、如何求。簡(jiǎn)單地說(shuō)，最早時(shí)間是通過(guò)“從前向后”的方法求的，而最晚時(shí)間是通過(guò)“從后向前”的方法求解的，并且，要想求最晚時(shí)間必須是在所有的最早時(shí)間都已經(jīng)求出來(lái)之后才能進(jìn)行。這個(gè)問題拿來(lái)直接考算法源碼的不多，一般是要求按照書上的算法描述求解的過(guò)程和步驟。在實(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ū)分。

?

第七章 查找

在不少數(shù)據(jù)結(jié)構(gòu)的教材中，是把查找與排序放入高級(jí)數(shù)據(jù)結(jié)構(gòu)中的。應(yīng)該說(shuō)，查找和排序兩章是前面我們所學(xué)的知識(shí)的綜合運(yùn)用，用到了樹、也用到了鏈表等知識(shí)，對(duì)這些數(shù)據(jù)結(jié)構(gòu)某一方面的運(yùn)用就構(gòu)成了查找和排序?，F(xiàn)實(shí)生活中，search幾乎無(wú)處不在，特別是現(xiàn)在的網(wǎng)絡(luò)時(shí)代，萬(wàn)事離不開search，小到文檔內(nèi)文字的搜索，大到INTERNET上的搜索，search占據(jù)了我們上網(wǎng)的大部分時(shí)間。在復(fù)習(xí)這一章的知識(shí)時(shí)，你需要先弄清楚以下幾個(gè)概念：關(guān)鍵字、主關(guān)鍵字、次關(guān)鍵字的含義；靜態(tài)查找與動(dòng)態(tài)查找的含義及區(qū)別；平均查找長(zhǎng)度ASL的概念及在各種查找算法中的計(jì)算方法和計(jì)算結(jié)果，特別是一些典型結(jié)構(gòu)的ASL值，應(yīng)該記住。在DS的教材中，一般將search分為三類：1st，在順序表上的查找；2nd，在樹表上的查找；3rd，在哈希表上的查找。下面詳細(xì)介紹其考查知識(shí)點(diǎn)及考查方式：

1. 線性表上的查找：主要分為三種線性結(jié)構(gòu)：順序表，有序順序表，索引順序表。對(duì)于第一種，我們采用傳統(tǒng)查找方法，逐個(gè)比較。對(duì)于及有序順序表我們采用二分查找法。對(duì)于第三種索引結(jié)構(gòu)，我們采用索引查找算法。考生需要注意這三種表下的ASL值以及三種算法的實(shí)現(xiàn)。其中，二分查找還要特別注意適用條件以及其遞歸實(shí)現(xiàn)方法。

2. 樹表上的查找：這是本章的重點(diǎn)和難點(diǎn)。由于這一節(jié)介紹的內(nèi)容是使用樹表進(jìn)行的查找，所以很容易與樹一間的某些概念相混淆。本節(jié)內(nèi)容與樹一章的內(nèi)容有聯(lián)系，但也有很多不同，應(yīng)注意規(guī)納。樹表主要分為以下幾種：二叉排序樹，平衡二叉樹，B樹，鍵樹。其中，尤以前兩種結(jié)構(gòu)為重，也有部分名校偏愛考B樹的。由于二叉排序樹與平衡二叉樹是一種特殊的二叉樹，所以與二叉樹的聯(lián)系就更為緊密，二叉樹一章學(xué)好了，這里也就不難了。二叉排序樹，簡(jiǎn)言之，就是“左小右大”，它的中序遍歷結(jié)果是一個(gè)遞增的有序序列。平衡二叉樹是二叉排序樹的優(yōu)化，其本質(zhì)也是一種二叉排序樹，只不過(guò)，平衡二叉樹對(duì)左右子樹的深度有了限定：深度之差的絕對(duì)值不得大于1。對(duì)于二叉排序樹，“判斷某棵二叉樹是否二叉排序樹”這一算法經(jīng)常被考到，可用遞歸，也可以用非遞歸。平衡二叉樹的建立也是一個(gè)?？键c(diǎn)，但該知識(shí)點(diǎn)歸根結(jié)底還是關(guān)注的平衡二叉樹的四種調(diào)整算法，所以應(yīng)該掌握平衡二叉樹的四種調(diào)整算法，調(diào)整的一個(gè)參照是：調(diào)整前后的中序遍歷結(jié)果相同。B樹是二叉排序樹的進(jìn)一步改進(jìn)，也可以把B樹理解為三叉、四叉....排序樹。除B樹的查找算法外，應(yīng)該特別注意一下B樹的插入和刪除算法。因?yàn)檫@兩種算法涉及到B樹結(jié)點(diǎn)的分裂和合并，是一個(gè)難點(diǎn)。B樹是報(bào)考名校的同學(xué)應(yīng)該關(guān)注的焦點(diǎn)之一。鍵樹也稱字符樹，特別適用于查找英文單詞的場(chǎng)合。一般不要求能完整描述算法源碼，多是根據(jù)算法思想建立鍵樹及描述其大致查找過(guò)程。

3. 基本哈希表的查找算法：哈希一詞，是外來(lái)詞，譯自“hash”一詞，意為：散列或雜湊的意思。哈希表查找的基本思想是：根據(jù)當(dāng)前待查找數(shù)據(jù)的特征，以記錄關(guān)鍵字為自變量，設(shè)計(jì)一個(gè)function，該函數(shù)對(duì)關(guān)鍵字進(jìn)行轉(zhuǎn)換后，其解釋結(jié)果為待查的地址?；诠１淼目疾辄c(diǎn)有：哈希函數(shù)的設(shè)計(jì)，沖突解決方法的選擇及沖突處理過(guò)程的描述。

第八章 內(nèi)部排序

內(nèi)排是DS課程中最后一個(gè)重要的章節(jié)，建立在此章之上的考題可以有多種類型：填空，選擇，判斷乃至大型算法題。但是，歸結(jié)到一點(diǎn)，就是考查你對(duì)書本上的各種排序算法及其思想以及其優(yōu)缺點(diǎn)和性能指標(biāo)（時(shí)間復(fù)雜度）能否了如指掌。這一章，我們對(duì)重點(diǎn)的規(guī)納將跟以上各章不同。我們將從以下幾個(gè)側(cè)面來(lái)對(duì)排序一章進(jìn)行不同的規(guī)納，以期能更全面的理解排序一章的總體結(jié)構(gòu)及各種算法。

從排序算法的種類來(lái)分，本章主要闡述了以下幾種排序方法：插入、選擇、交換、歸并、計(jì)數(shù)等五種排序方法。

其中，在插入排序中又可分為：直接插入、折半插入、2路插入、希爾排序。這幾種插入排序算法的最根本的不同點(diǎn)，說(shuō)到底就是根據(jù)什么規(guī)則尋找新元素的插入點(diǎn)。直接插入是依次尋找，折半插入是折半尋找。希爾排序，是通過(guò)控制每次參與排序的數(shù)的總范圍“由小到大”的增量來(lái)實(shí)現(xiàn)排序效率提高的目的。

交換排序，又稱冒泡排序，在交換排序的基礎(chǔ)上改進(jìn)又可以得到快速排序?？焖倥判虻乃枷?，一語(yǔ)以敝之：用中間數(shù)將待排數(shù)據(jù)組一分為二?？焖倥判?，在處理的“問題規(guī)?！边@個(gè)概念上，與希爾有點(diǎn)相反，快速排序，是先處理一個(gè)較大規(guī)模，然后逐漸把處理的規(guī)模降低，最終達(dá)到排序的目的。

選擇排序，相對(duì)于前面幾種排序算法來(lái)說(shuō)，難度大一點(diǎn)。具體來(lái)說(shuō)，它可以分為：簡(jiǎn)單選擇、樹選擇、堆排。這三種方法的不同點(diǎn)是，根據(jù)什么規(guī)則選取最小的數(shù)。簡(jiǎn)單選擇，是通過(guò)簡(jiǎn)單的數(shù)組遍歷方案確定最小數(shù)；樹選擇，是通過(guò)“錦標(biāo)賽”類似的思想，讓兩數(shù)相比，不斷淘汰較大（?。┱?，最終選出最?。ù螅?shù)；而堆排序，是利用堆這種數(shù)據(jù)結(jié)構(gòu)的性質(zhì)，通過(guò)堆元素的刪除、調(diào)整等一系列操作將最小數(shù)選出放在堆頂。堆排序中的堆建立、堆調(diào)整是重要考點(diǎn)。樹選擇排序，也曾經(jīng)在一些學(xué)校中的大型算法題中出現(xiàn)，請(qǐng)大家注意。

歸并排序，故名思義，是通過(guò)“歸并”這種操作完成排序的目的，既然是歸并就必須是兩者以上的數(shù)據(jù)集合才可能實(shí)現(xiàn)歸并。所以，在歸并排序中，關(guān)注最多的就是2路歸并。算法思想比較簡(jiǎn)單，有一點(diǎn)，要銘記在心：歸并排序是穩(wěn)定排序。

基數(shù)排序，是一種很特別的排序方法，也正是由于它的特殊，所以，基數(shù)排序就比較適合于一些特別的場(chǎng)合，比如撲克牌排序問題等?；鶖?shù)排序，又分為兩種：多關(guān)鍵字的排序（撲克牌排序），鏈?zhǔn)脚判颍ㄕ麛?shù)排序）?；鶖?shù)排序的核心思想也是利用“基數(shù)空間”這個(gè)概念將問題規(guī)模規(guī)范、變小，并且，在排序的過(guò)程中，只要按照基排的思想，是不用進(jìn)行關(guān)鍵字比較的，這樣得出的最終序列就是一個(gè)有序序列。

本章各種排序算法的思想以及偽代碼實(shí)現(xiàn)，及其時(shí)間復(fù)雜度都是必須掌握的，學(xué)習(xí)時(shí)要多注意規(guī)納、總結(jié)、對(duì)比。此外，對(duì)于教材中的10.7節(jié)，要求必須熟記，在理解的基礎(chǔ)上記憶，這一節(jié)幾乎成為很多學(xué)校每年的必考點(diǎn)。

?