數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)重點(diǎn)歸納

1、一、數(shù)據(jù)結(jié)構(gòu)的章節(jié)結(jié)構(gòu)及重點(diǎn)構(gòu)成數(shù)據(jù)結(jié)構(gòu)學(xué)科的章節(jié)劃分基本上為：概論，線性表，棧和隊(duì)列，串，多維數(shù)組和廣義表，樹和二叉樹，圖，查找，內(nèi)排，外排，文件，動(dòng)態(tài)存儲(chǔ)分配。對(duì)于絕大多數(shù)的學(xué)校而言，“外排，文件，動(dòng)態(tài)存儲(chǔ)分配”三章基本上是不考的，在大多數(shù)高校的計(jì)算機(jī)本科教學(xué)過程中，這三章也是基本上不作講授的。所以，大家在這三章上可以不必花費(fèi)過多的精力，只要知道基本的概念即可。但是，對(duì)于報(bào)考名校特別是該校又有在試卷中對(duì)這三章進(jìn)行過考核的歷史，那么這部分朋友就要留意這三章了。按照以上我們給出的章節(jié)以及對(duì)后三章的介紹，數(shù)據(jù)結(jié)構(gòu)的章節(jié)比重大致為：概論：內(nèi)容很少，概念簡(jiǎn)單，分?jǐn)?shù)大多只有幾分，有的學(xué)校甚至不考。線性

2、表：基礎(chǔ)章節(jié)，必考內(nèi)容之一?？碱}多數(shù)為基本概念題，名?？碱}中，鮮有大型算法設(shè)計(jì)題。如果有，也是與其它章節(jié)內(nèi)容相結(jié)合。棧和隊(duì)列：基礎(chǔ)章節(jié)，容易出基本概念題，必考內(nèi)容之一。而棧常與其它章節(jié)配合考查，也常與遞歸,表達(dá)式的求值等概念相聯(lián)系進(jìn)行考查。串：基礎(chǔ)章節(jié)，概念較為簡(jiǎn)單。專門針對(duì)于此章的大型算法設(shè)計(jì)題很少，較常見的是根據(jù)KMP進(jìn)行算法分析。多維數(shù)組及廣義表：基礎(chǔ)章節(jié)，基于數(shù)組的算法題也是常見的，分?jǐn)?shù)比例波動(dòng)較大，是出題的“可選單元”或“侯補(bǔ)單元”。一般如果要出題，多數(shù)不會(huì)作為大題出。數(shù)組常與“查找，排序”等章節(jié)結(jié)合來作為大題考查。樹和二叉樹：重點(diǎn)難點(diǎn)章節(jié)，各校必考章節(jié)。各校在此章出題的不同之處在于

3、，是否在本章中出一到兩道大的算法設(shè)計(jì)題。通過對(duì)多所學(xué)校的試卷分析，絕大多數(shù)學(xué)校在本章都曾有過出大型算法設(shè)計(jì)題的歷史。圖：重點(diǎn)難點(diǎn)章節(jié)，名校尤愛考。如果作為重點(diǎn)來考，則多出現(xiàn)于分析與設(shè)計(jì)題型當(dāng)中，可與樹一章共同構(gòu)成算法設(shè)計(jì)大題的題型設(shè)計(jì)。查找：重點(diǎn)難點(diǎn)章節(jié)，概念較多，聯(lián)系較為緊密，容易混淆。出題時(shí)可以作為分析型題目給出，在基本概念型題目中也較為常見。算法設(shè)計(jì)型題中可以數(shù)組結(jié)合來考查，也可以與樹一章結(jié)合來考查。排序：與查找一章類似，本章同屬于重點(diǎn)難點(diǎn)章節(jié)，且概念更多，聯(lián)系更為緊密，概念之間更容易混淆。在基本概念的考查中，尤愛考各種排序算法的優(yōu)劣比較此類的題。算法設(shè)計(jì)大題中，如果作為出題，那么常與數(shù)

4、組結(jié)合來考查。二、數(shù)據(jù)結(jié)構(gòu)各章節(jié)重點(diǎn)勾劃第0章概述本章主要起到總領(lǐng)作用，為讀者進(jìn)行數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)進(jìn)行了一些先期鋪墊。大家主要注意以下幾點(diǎn)：數(shù)據(jù)結(jié)構(gòu)的基本概念，時(shí)間和空間復(fù)雜度的概念及度量方法，算法設(shè)計(jì)時(shí)的注意事項(xiàng)。本章考點(diǎn)不多，只要稍加注意理解即可。第一章 線性表作為線性結(jié)構(gòu)的開篇章節(jié)，線性表一章在線性結(jié)構(gòu)的學(xué)習(xí)乃至整個(gè)數(shù)據(jù)結(jié)構(gòu)學(xué)科的學(xué)習(xí)中，其作用都是不可低估的。在這一章，第一次系統(tǒng)性地引入鏈?zhǔn)酱鎯?chǔ)的概念，鏈?zhǔn)酱鎯?chǔ)概念將是整個(gè)數(shù)據(jù)結(jié)構(gòu)學(xué)科的重中之重，無論哪一章都涉及到了這個(gè)概念?？傮w來說，線性表一章可供考查的重要考點(diǎn)有以下幾個(gè)方面：1. 線性表的相關(guān)基本概念，如：前驅(qū)、后繼、表長(zhǎng)、空表、首元結(jié)

5、點(diǎn)，頭結(jié)點(diǎn)，頭指針等概念。2. 線性表的結(jié)構(gòu)特點(diǎn)，主要是指：除第一及最后一個(gè)元素外，每個(gè)結(jié)點(diǎn)都只有一個(gè)前趨和只有一個(gè)后繼。3. 線性表的順序存儲(chǔ)方式及其在具體語言環(huán)境下的兩種不同實(shí)現(xiàn)：表空間的靜態(tài)分配和動(dòng)態(tài)分配。靜態(tài)鏈表與順序表的相似及不同之處。4. 線性表的鏈?zhǔn)酱鎯?chǔ)方式及以下幾種常用鏈表的特點(diǎn)和運(yùn)算：?jiǎn)捂湵怼⒀h(huán)鏈表，雙向鏈表，雙向循環(huán)鏈表。其中，單鏈表的歸并算法、循環(huán)鏈表的歸并算法、雙向鏈表及雙向循環(huán)鏈表的插入和刪除算法等都是較為常見的考查方式。此外，近年來在不少學(xué)校中還多次出現(xiàn)要求用遞歸算法實(shí)現(xiàn)單鏈表輸出（可能是順序也可能是倒序）的問題。在鏈表的小題型中，經(jīng)?？嫉揭恍┲T如：判表空的題。在

6、不同的鏈表中，其判表空的方式是不一樣的，請(qǐng)大家注意。5. 線性表的順序存儲(chǔ)及鏈?zhǔn)酱鎯?chǔ)情況下，其不同的優(yōu)缺點(diǎn)比較，即其各自適用的場(chǎng)合。單鏈表中設(shè)置頭指針、循環(huán)鏈表中設(shè)置尾指針而不設(shè)置頭指針以及索引存儲(chǔ)結(jié)構(gòu)的各自好處。第二章 棧與隊(duì)列棧與隊(duì)列，是很多學(xué)習(xí)DS的同學(xué)遇到第一只攔路虎，很多人從這一章開始坐暈車，一直暈到現(xiàn)在。所以，理解棧與隊(duì)列，是走向DS高手的一條必由之路。學(xué)習(xí)此章前，你可以問一下自己是不是已經(jīng)知道了以下幾點(diǎn)：1. 棧、隊(duì)列的定義及其相關(guān)數(shù)據(jù)結(jié)構(gòu)的概念，包括：順序棧，鏈棧，共享?xiàng)＃h(huán)隊(duì)列，鏈隊(duì)等。棧與隊(duì)列存取數(shù)據(jù)（請(qǐng)注意包括：存和取兩部分）的特點(diǎn)。2. 遞歸算法。棧與遞歸的關(guān)系，以及

7、借助棧將遞歸轉(zhuǎn)向于非遞歸的經(jīng)典算法：n!階乘問題，fib數(shù)列問題，Hanoi問題，背包問題，二叉樹的遞歸和非遞歸遍歷問題，圖的深度遍歷與棧的關(guān)系等。其中，涉及到樹與圖的問題，多半會(huì)在樹與圖的相關(guān)章節(jié)中進(jìn)行考查。3. 棧的應(yīng)用：數(shù)值表達(dá)式的求解，括號(hào)的配對(duì)等的原理，只作原理性了解，具體要求考查此為題目的算法設(shè)計(jì)題不多。4. 循環(huán)隊(duì)列中判隊(duì)空、隊(duì)滿條件，循環(huán)隊(duì)列中入隊(duì)與出隊(duì)算法。如果你已經(jīng)對(duì)上面的幾點(diǎn)了如指掌，棧與隊(duì)列一章可以不看書了。注意，我說的是可以不看書，并不是可以不作題哦。第三章 串經(jīng)歷了棧一章的痛苦煎熬后，終于迎來了串一章的柳暗花明。串，在概念上是比較少的一個(gè)章節(jié)，也是最容易自學(xué)的章節(jié)之

8、一，但正如每個(gè)過來人所了解的，KMP算法是這一章的重要關(guān)隘，突破此關(guān)隘后，走過去又是一馬平川的大好DS山河了，呵呵。串一章需要攻破的主要堡壘有：1. 串的基本概念，串與線性表的關(guān)系（串是其元素均為字符型數(shù)據(jù)的特殊線性表），空串與空格串的區(qū)別，串相等的條件。2. 串的基本操作，以及這些基本函數(shù)的使用，包括：取子串，串連接，串替換，求串長(zhǎng)等等。運(yùn)用串的基本操作去完成特定的算法是很多學(xué)校在基本操作上的考查重點(diǎn)。3. 順序串與鏈串及塊鏈串的區(qū)別和聯(lián)系，實(shí)現(xiàn)方式。4. KMP算法思想。KMP中next數(shù)組以及nextval數(shù)組的求法。明確傳統(tǒng)模式匹配算法的不足，明確next數(shù)組需要改進(jìn)之外。其中，理解算

9、法是核心，會(huì)求數(shù)組是得分點(diǎn)。不用我多說，這一節(jié)內(nèi)容是本章的重中之重?？赡苓M(jìn)行的考查方式是：求next和nextval數(shù)組值，根據(jù)求得的next或nextval數(shù)組值給出運(yùn)用KMP算法進(jìn)行匹配的匹配過程。第四章 數(shù)組與廣義表學(xué)過程序語言的朋友，數(shù)組的概念我們已經(jīng)不是第一次見到了，應(yīng)該已經(jīng)“一回生，二回熟”了，所以，在概念上，不會(huì)存在太大障礙。但作為考研課程來說，本章的考查重點(diǎn)可能與大學(xué)里的程序語言所關(guān)注的不太一樣，下面會(huì)作介紹。廣義表的概念，是數(shù)據(jù)結(jié)構(gòu)里第一次出現(xiàn)的。它是線性表或表元素的有限序列，構(gòu)成該結(jié)構(gòu)的每個(gè)子表或元素也是線性結(jié)構(gòu)的，所以，這一章也歸入線性結(jié)構(gòu)中。本章的考查重點(diǎn)有：1. 多維

10、數(shù)組中某數(shù)組元素的position求解。一般是給出數(shù)組元素的首元素地址和每個(gè)元素占用的地址空間并組給出多維數(shù)組的維數(shù)，然后要求你求出該數(shù)組中的某個(gè)元素所在的位置。2. 明確按行存儲(chǔ)和按列存儲(chǔ)的區(qū)別和聯(lián)系，并能夠按照這兩種不同的存儲(chǔ)方式求解1中類型的題。3. 將特殊矩陣中的元素按相應(yīng)的換算方式存入數(shù)組中。這些矩陣包括：對(duì)稱矩陣，三角矩陣，具有某種特點(diǎn)的稀疏矩陣等。熟悉稀疏矩陣的三種不同存儲(chǔ)方式：三元組，帶輔助行向量的二元組，十字鏈表存儲(chǔ)。掌握將稀疏矩陣的三元組或二元組向十字鏈表進(jìn)行轉(zhuǎn)換的算法。4. 廣義表的概念，特別應(yīng)該明確表頭與表尾的定義。這一點(diǎn)，是理解整個(gè)廣義表一節(jié)算法的基礎(chǔ)。近來，在一些學(xué)

11、校中，出現(xiàn)了這樣一種題目類型：給出對(duì)某個(gè)廣義表L若干個(gè)求了若干次的取頭和取尾操作后的串值，要求求出原廣義表L。大家要留意。5. 與廣義表有關(guān)的遞歸算法。由于廣義表的定義就是遞歸的，所以，與廣義表有關(guān)的算法也常是遞歸形式的。比如：求表深度，復(fù)制廣義表等。這種題目，可以根據(jù)不同角度廣義表的表現(xiàn)形式運(yùn)用兩種不同的方式解答：一是把一個(gè)廣義表看作是表頭和表尾兩部分，分別對(duì)表頭和表尾進(jìn)行操作；二是把一個(gè)廣義表看作是若干個(gè)子表，分別對(duì)每個(gè)子表進(jìn)行操作。第五章 樹與二叉樹從對(duì)線性結(jié)構(gòu)的研究過度到對(duì)樹形結(jié)構(gòu)的研究，是數(shù)據(jù)結(jié)構(gòu)課程學(xué)習(xí)的一次躍變，此次躍變完成的好壞，將直接關(guān)系到你到實(shí)際的考試中是否可以拿到高分，而

12、這所有的一切，將最終影響你的專業(yè)課總分。所以，樹這一章的重要性，已經(jīng)不說自明了?？傮w來說，樹一章的知識(shí)點(diǎn)包括：二叉樹的概念、性質(zhì)和存儲(chǔ)結(jié)構(gòu)，二叉樹遍歷的三種算法（遞歸與非遞歸），在三種基本遍歷算法的基礎(chǔ)上實(shí)現(xiàn)二叉樹的其它算法，線索二叉樹的概念和線索化算法以及線索化后的查找算法，最優(yōu)二叉樹的概念、構(gòu)成和應(yīng)用，樹的概念和存儲(chǔ)形式，樹與森林的遍歷算法及其與二叉樹遍歷算法的聯(lián)系，樹與森林和二叉樹的轉(zhuǎn)換。下面我們來看考試中對(duì)以上知識(shí)的主要考查方法：1. 二叉樹的概念、性質(zhì)和存儲(chǔ)結(jié)構(gòu)考查方法可有：直接考查二叉樹的定義，讓你說明二叉樹與普通雙分支樹的區(qū)別；考查滿二叉樹和完全二叉樹的性質(zhì)，普通二叉樹的五個(gè)性質(zhì)

13、：第i層的最多結(jié)點(diǎn)數(shù)，深度為k的二叉樹的最多結(jié)點(diǎn)數(shù)，n0=n2+1的性質(zhì)，n個(gè)結(jié)點(diǎn)的完全二叉樹的深度，順序存儲(chǔ)二叉樹時(shí)孩子結(jié)點(diǎn)與父結(jié)點(diǎn)之間的換算關(guān)系（左為：2*i，右為：2*i+1）。二叉樹的順序存儲(chǔ)和二叉鏈表存儲(chǔ)的各自優(yōu)缺點(diǎn)及適用場(chǎng)合，二叉樹的三叉鏈表表示方法。2. 二叉樹的三種遍歷算法這一知識(shí)點(diǎn)掌握的好壞，將直接關(guān)系到樹一章的算法能否理解，進(jìn)而關(guān)系到樹一章的算法設(shè)計(jì)題能否順利完成。二叉樹的遍歷算法有三種：先序，中序和后序。其劃分的依據(jù)是視其每個(gè)算法中對(duì)根結(jié)點(diǎn)數(shù)據(jù)的訪問順序而定。不僅要熟練掌握三種遍歷的遞歸算法，理解其執(zhí)行的實(shí)際步驟，并且應(yīng)該熟練掌握三種遍歷的非遞歸算法。由于二叉樹一章的很多

14、算法，可以直接根據(jù)三種遞歸算法改造而來（比如：求葉子個(gè)數(shù)），所以，掌握了三種遍歷的非遞歸算法后，對(duì)付諸如：“利用非遞歸算法求二叉樹葉子個(gè)數(shù)”這樣的題目就下筆如有神了。我會(huì)在另一篇系列文章（http：/3. 可在三種遍歷算法的基礎(chǔ)上改造完成的其它二叉樹算法：求葉子個(gè)數(shù)，求二叉樹結(jié)點(diǎn)總數(shù)，求度為1或度為2的結(jié)點(diǎn)總數(shù)，復(fù)制二叉樹，建立二叉樹，交換左右子樹，查找值為n的某個(gè)指定結(jié)點(diǎn)，刪除值為n的某個(gè)指定結(jié)點(diǎn)，諸如此類等等等等。如果你可以熟練掌握二叉樹的遞歸和非遞歸遍歷算法，那么解決以上問題就是小菜一碟了。4. 線索二叉樹：線索二叉樹的引出，是為避免如二叉樹遍歷時(shí)的遞歸求解。眾所周知，遞歸雖然形式上比較

15、好理解，但是消耗了大量的內(nèi)存資源，如果遞歸層次一多，勢(shì)必帶來資源耗盡的危險(xiǎn)，為了避免此類情況，線索二叉樹便堂而皇之地出現(xiàn)了。對(duì)于線索二叉樹，應(yīng)該掌握：線索化的實(shí)質(zhì)，三種線索化的算法，線索化后二叉樹的遍歷算法，基本線索二叉樹的其它算法問題（如：查找某一類線索二叉樹中指定結(jié)點(diǎn)的前驅(qū)或后繼結(jié)點(diǎn)就是一類?？碱}）。？5. 最優(yōu)二叉樹（哈夫曼樹）：最優(yōu)二叉樹是為了解決特定問題引出的特殊二叉樹結(jié)構(gòu)，它的前提是給二叉樹的每條邊賦予了權(quán)值，這樣形成的二叉樹按權(quán)相加之和是最小的。最優(yōu)二叉樹一節(jié)，直接考查算法源碼的很少，一般是給你一組數(shù)據(jù)，要求你建立基于這組數(shù)據(jù)的最優(yōu)二叉樹，并求出其最小權(quán)值之和，此類題目不難，屬送

16、分題。6.二叉搜索樹(二叉排序樹)熟練掌握二叉搜索樹的構(gòu)造,以及節(jié)點(diǎn)的刪除操作,例如刪除其根節(jié)點(diǎn)時(shí)關(guān)鍵應(yīng)找出右子樹中最小的節(jié)點(diǎn)來替代其根節(jié)點(diǎn),然后進(jìn)行后續(xù)操作7. B樹和B+數(shù)同樣掌握B樹的構(gòu)建,添加節(jié)點(diǎn)與刪除節(jié)點(diǎn)等操作8. 樹與森林：二叉樹是一種特殊的樹，這種特殊不僅僅在于其分支最多為2以及其它特征，一個(gè)最重要的特殊之處是在于：二叉樹是有序的！即：二叉樹的左右孩子是不可交換的，如果交換了就成了另外一棵二叉樹，這樣交換之后的二叉樹與原二叉樹我們認(rèn)為是不相同的兩棵二叉樹。但是，對(duì)于普通的雙分支樹而言，不具有這種性質(zhì)。樹與森林的遍歷，不像二叉樹那樣豐富，他們只有兩種遍歷算法：先根與后根（對(duì)于森林而

17、言稱作：先序與后序遍歷）。在難度比較大的考試中，也有基于此二種算法的基礎(chǔ)上再進(jìn)行擴(kuò)展要求你利用這兩種算法設(shè)計(jì)其它算法的，但一般院校很少有這種考法，最多只是要求你根據(jù)先根或后根寫出他們的遍歷序列。此二者的先根與后根遍歷與二叉樹中的遍歷算法是有對(duì)應(yīng)關(guān)系的：先根遍歷對(duì)應(yīng)二叉樹的先序遍歷，而后根遍歷對(duì)應(yīng)二叉樹的中序遍歷。這一點(diǎn)成為很多學(xué)校的考點(diǎn)，考查的方式不一而足，有的直接考此句話，有的是先讓你求解遍歷序列然后回答這個(gè)問題。二叉樹、樹與森林之所以能有以上的對(duì)應(yīng)關(guān)系，全拜二叉鏈表所賜。二叉樹使用二叉鏈表分別存放他的左右孩子，樹利用二叉鏈表存儲(chǔ)孩子及兄弟（稱孩子兄弟鏈表），而森林也是利用二叉鏈表存儲(chǔ)孩子及

18、兄弟。樹一章，處處是重點(diǎn)，道道是考題，大家務(wù)必個(gè)個(gè)過關(guān)。第六章 圖如果說，從線性結(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)，無向圖，有向圖，入度，出度，完

19、全圖，生成子圖，路徑長(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. 考查圖的兩種遍歷算法：深度遍歷和廣度遍歷深度遍歷和廣度遍歷是圖的兩種基本的遍歷算法，其中深度遍歷相當(dāng)于二叉樹中的先序遍歷,而廣度遍歷相當(dāng)于二叉樹中的層次遍歷.這兩個(gè)算法對(duì)圖一章的重要性等同于“先序、中序、后序遍歷”對(duì)于二叉樹一章的重要性。在考查時(shí)，圖一章的算法設(shè)計(jì)題常常是基于這兩種基本的遍歷

20、算法而設(shè)計(jì)的，比如：“求最長(zhǎng)的最短路徑問題”和“判斷兩頂點(diǎn)間是否存在長(zhǎng)為K的簡(jiǎn)單路徑問題”，就分別用到了廣度遍歷和深度遍歷算法。4. 生成樹、最小生成樹的概念以及最小生成樹的構(gòu)造PRIM算法和KRUSKAL算法?？疾闀r(shí)，一般不要求寫出算法源碼，而是要求根據(jù)這兩種最小生成樹的算法思想寫出其構(gòu)造過程及最終生成的最小生成樹。5. 拓?fù)渑判騿栴}：拓?fù)渑判蛴袃煞N方法，一是無前趨的頂點(diǎn)優(yōu)先算法，二是無后繼的頂點(diǎn)優(yōu)先算法。換句話說，一種是“從前向后”的排序，一種是“從后向前”排。當(dāng)然，后一種排序出來的結(jié)果是“逆拓?fù)溆行颉钡摹?. 關(guān)鍵路徑問題：這個(gè)問題是圖一章的難點(diǎn)問題。理解關(guān)鍵路徑的關(guān)鍵有三個(gè)方面：一是何

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

22、。概念理解是比較容易的，關(guān)鍵是算法的理解。最短路徑問題分為兩種：一是求從某一點(diǎn)出發(fā)到其余各點(diǎn)的最短路徑；二是求圖中每一對(duì)頂點(diǎn)之間的最短路徑。這個(gè)問題也具有非常實(shí)用的背景特色，一個(gè)典型的應(yīng)該就是旅游景點(diǎn)及旅游路線的選擇問題。解決第一個(gè)問題用DIJSKTRA算法，解決第二個(gè)問題用FLOYD算法。注意區(qū)分。*注意區(qū)分關(guān)鍵路徑問題與最短路徑問題*第七章 查找在不少數(shù)據(jù)結(jié)構(gòu)的教材中，是把查找與排序放入高級(jí)數(shù)據(jù)結(jié)構(gòu)中的。應(yīng)該說，查找和排序兩章是前面我們所學(xué)的知識(shí)的綜合運(yùn)用，用到了樹、也用到了鏈表等知識(shí)，對(duì)這些數(shù)據(jù)結(jié)構(gòu)某一方面的運(yùn)用就構(gòu)成了查找和排序?，F(xiàn)實(shí)生活中，search幾乎無處不在，特別是現(xiàn)在的網(wǎng)絡(luò)時(shí)

23、代，萬事離不開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)查找

24、方法，逐個(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é)好了，這里也就不難了。二

25、叉排序樹，簡(jiǎn)言之，就是“左小右大”，它的中序遍歷結(jié)果是一個(gè)遞增的有序序列。平衡二叉樹是二叉排序樹的優(yōu)化，其本質(zhì)也是一種二叉排序樹，只不過，平衡二叉樹對(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)檫@兩

26、種算法涉及到B樹結(jié)點(diǎn)的分裂和合并，是一個(gè)難點(diǎn)。B樹是報(bào)考名校的同學(xué)應(yīng)該關(guān)注的焦點(diǎn)之一。鍵樹也稱字符樹，特別適用于查找英文單詞的場(chǎng)合。一般不要求能完整描述算法源碼，多是根據(jù)算法思想建立鍵樹及描述其大致查找過程。3. 基本哈希表的查找算法(應(yīng)掌握哈希表的用法)：哈希一詞，是外來詞，譯自“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ì)，沖突解決方法的選擇及沖突處理過程的描述。第八章 內(nèi)部排序內(nèi)排是DS課程中最后一個(gè)重要的章節(jié)

27、，建立在此章之上的考題可以有多種類型：填空，選擇，判斷乃至大型算法題。但是，歸結(jié)到一點(diǎn)，就是考查你對(duì)書本上的各種排序算法及其思想以及其優(yōu)缺點(diǎn)和性能指標(biāo)（時(shí)間復(fù)雜度）能否了如指掌。這一章，我們對(duì)重點(diǎn)的規(guī)納將跟以上各章不同。我們將從以下幾個(gè)側(cè)面來對(duì)排序一章進(jìn)行不同的規(guī)納，以期能更全面的理解排序一章的總體結(jié)構(gòu)及各種算法。從排序算法的種類來分，本章主要闡述了以下幾種排序方法：插入、(冒泡),選擇、希爾、歸并、快速等五種排序方法。其中，在插入排序中又可分為：直接插入、折半插入、2路插入、希爾排序。這幾種插入排序算法的最根本的不同點(diǎn)，說到底就是根據(jù)什么規(guī)則尋找新元素的插入點(diǎn)。直接插入是依次尋找，折半插入是折半尋找。希爾排序