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

第二章 棧與隊列
棧與隊列，是很多學(xué)習(xí)DS的同學(xué)遇到第一只攔路虎，很多人從這一章開始坐暈車，一直暈到現(xiàn)在。所以，理解棧與隊列，是走向DS高手的一條必由之路。學(xué)習(xí)此章前，你可以問一下自己是不是已經(jīng)知道了以下幾點：
1. 棧、隊列的定義及其相關(guān)數(shù)據(jù)結(jié)構(gòu)的概念，包括：順序棧，鏈棧，共享棧，循環(huán)隊列，鏈隊等。棧與隊列存取數(shù)據(jù)（請注意包括：存和取兩部分）的特點。
2. 遞歸算法。棧與遞歸的關(guān)系，以及借助棧將遞歸轉(zhuǎn)向于非遞歸的經(jīng)典算法：n!階乘問題，fib數(shù)列問題，Hanoi問題，背包問題，二叉樹的遞歸和非遞歸遍歷問題，圖的深度遍歷與棧的關(guān)系等。其中，涉及到樹與圖的問題，多半會在樹與圖的相關(guān)章節(jié)中進(jìn)行考查。
3. 棧的應(yīng)用：數(shù)值表達(dá)式的求解，括號的配對等的原理，只作原理性了解，具體要求考查此為題目的算法設(shè)計題不多。
4. 循環(huán)隊列中判隊空、隊滿條件，循環(huán)隊列中入隊與出隊算法。如果你已經(jīng)對上面的幾點了如指掌，棧與隊列一章可以不看書了。注意，我說的是可以不看書，并不是可以不作題哦。

第三章 串
經(jīng)歷了棧一章的痛苦煎熬后，終于迎來了串一章的柳暗花明。串，在概念上是比較少的一個章節(jié)，也是最容易自學(xué)的章節(jié)之一，但正如每個過來人所了解的，KMP算法是這一章的重要關(guān)隘，突破此關(guān)隘后，走過去又是一馬平川的大好DS山河了，呵呵。串一章需要攻破的主要堡壘有：
1. 串的基本概念，串與線性表的關(guān)系（串是其元素均為字符型數(shù)據(jù)的特殊線性表），空串與空格串的區(qū)別，串相等的條件。
2. 串的基本操作，以及這些基本函數(shù)的使用，包括：取子串，串連接，串替換，求串長等等。運用串的基本操作去完成特定的算法是很多學(xué)校在基本操作上的考查重點。
3. 順序串與鏈串及塊鏈串的區(qū)別和聯(lián)系，實現(xiàn)方式。
4. KMP算法思想。KMP中next數(shù)組以及nextval數(shù)組的求法。明確傳統(tǒng)模式匹配算法的不足，明確next數(shù)組需要改進(jìn)之外。其中，理解算法是核心，會求數(shù)組是得分點。不用我多說，這一節(jié)內(nèi)容是本章的重中之重?？赡苓M(jìn)行的考查方式是：求next和nextval數(shù)組值，根據(jù)求得的next或nextval數(shù)組值給出運用KMP算法進(jìn)行匹配的匹配過程。

第四章 數(shù)組與廣義表
學(xué)過程序語言的朋友，數(shù)組的概念我們已經(jīng)不是第一次見到了，應(yīng)該已經(jīng)“一回生，二回熟”了，所以，在概念上，不會存在太大障礙。但作為考研課程來說，本章的考查重點可能與大學(xué)里的程序語言所關(guān)注的不太一樣，下面會作介紹。廣義表的概念，是數(shù)據(jù)結(jié)構(gòu)里第一次出現(xiàn)的。它是線性表或表元素的有限序列，構(gòu)成該結(jié)構(gòu)的每個子表或元素也是線性結(jié)構(gòu)的，所以，這一章也歸入線性結(jié)構(gòu)中。本章的考查重點有：
1. 多維數(shù)組中某數(shù)組元素的position求解。一般是給出數(shù)組元素的首元素地址和每個元素占用的地址空間并組給出多維數(shù)組的維數(shù)，然后要求你求出該數(shù)組中的某個元素所在的位置。
2. 明確按行存儲和按列存儲的區(qū)別和聯(lián)系，并能夠按照這兩種不同的存儲方式求解1中類型的題。
3. 將特殊矩陣中的元素按相應(yīng)的換算方式存入數(shù)組中。這些矩陣包括：對稱矩陣，三角矩陣，具有某種特點的稀疏矩陣等。熟悉稀疏矩陣的三種不同存儲方式：三元組，帶輔助行向量的二元組，十字鏈表存儲。掌握將稀疏矩陣的三元組或二元組向十字鏈表進(jìn)行轉(zhuǎn)換的算法。
4. 廣義表的概念，特別應(yīng)該明確表頭與表尾的定義。這一點，是理解整個廣義表一節(jié)算法的基礎(chǔ)。近來，在一些學(xué)校中，出現(xiàn)了這樣一種題目類型：給出對某個廣義表L若干個求了若干次的取頭和取尾操作后的串值，要求求出原廣義表L。大家要留意。
5. 與廣義表有關(guān)的遞歸算法。由于廣義表的定義就是遞歸的，所以，與廣義表有關(guān)的算法也常是遞歸形式的。比如：求表深度，復(fù)制廣義表等。這種題目，可以根據(jù)不同角度廣義表的表現(xiàn)形式運用兩種不同的方式解答：一是把一個廣義表看作是表頭和表尾兩部分，分別對表頭和表尾進(jìn)行操作；二是把一個廣義表看作是若干個子表，分別對每個子表進(jìn)行操作。

第五章 樹與二叉樹
從對線性結(jié)構(gòu)的研究過度到對樹形結(jié)構(gòu)的研究，是數(shù)據(jù)結(jié)構(gòu)課程學(xué)習(xí)的一次躍變，此次躍變完成的好壞，將直接關(guān)系到你到實際的考試中是否可以拿到高分，而這所有的一切，將最終影響你的專業(yè)課總分。所以，樹這一章的重要性，已經(jīng)不說自明了?？傮w來說，樹一章的知識點包括：二叉樹的概念、性質(zhì)和存儲結(jié)構(gòu)，二叉樹遍歷的三種算法（遞歸與非遞歸），在三種基本遍歷算法的基礎(chǔ)上實現(xiàn)二叉樹的其它算法，線索二叉樹的概念和線索化算法以及線索化后的查找算法，最優(yōu)二叉樹的概念、構(gòu)成和應(yīng)用，樹的概念和存儲形式，樹與森林的遍歷算法及其與二叉樹遍歷算法的聯(lián)系，樹與森林和二叉樹的轉(zhuǎn)換。下面我們來看考試中對以上知識的主要考查方法：
1. 二叉樹的概念、性質(zhì)和存儲結(jié)構(gòu)考查方法可有：直接考查二叉樹的定義，讓你說明二叉樹與普通雙分支樹的區(qū)別；考查滿二叉樹和完全二叉樹的性質(zhì)，普通二叉樹的五個性質(zhì)：第i層的最多結(jié)點數(shù)，深度為k的二叉樹的最多結(jié)點數(shù)，n0=n2+1的性質(zhì)，n個結(jié)點的完全二叉樹的深度，順序存儲二叉樹時孩子結(jié)點與父結(jié)點之間的換算關(guān)系（左為：2*i，右為：2*i+1）。二叉樹的順序存儲和二叉鏈表存儲的各自優(yōu)缺點及適用場合，二叉樹的三叉鏈表表示方法。
2. 二叉樹的三種遍歷算法這一知識點掌握的好壞，將直接關(guān)系到樹一章的算法能否理解，進(jìn)而關(guān)系到樹一章的算法設(shè)計題能否順利完成。二叉樹的遍歷算法有三種：先序，中序和后序。其劃分的依據(jù)是視其每個算法中對根結(jié)點數(shù)據(jù)的訪問順序而定。不僅要熟練掌握三種遍歷的遞歸算法，理解其執(zhí)行的實際步驟，并且應(yīng)該熟練掌握三種遍歷的非遞歸算法。由于二叉樹一章的很多算法，可以直接根據(jù)三種遞歸算法改造而來（比如：求葉子個數(shù)），所以，掌握了三種遍歷的非遞歸算法后，對付諸如：“利用非遞歸算法求二叉樹葉子個數(shù)”這樣的題目就下筆如有神了。我會在另一篇系列文章（http：//bbs.kaoyan.com/ibbs.dll?b...3&bp=2&bt=0）里給出三種遍歷的遞歸和非遞歸算法的背記版，到時請大家一定熟記。

3. 可在三種遍歷算法的基礎(chǔ)上改造完成的其它二叉樹算法：求葉子個數(shù)，求二叉樹結(jié)點總數(shù)，求度為1或度為2的結(jié)點總數(shù)，復(fù)制二叉樹，建立二叉樹，交換左右子樹，查找值為n的某個指定結(jié)點，刪除值為n的某個指定結(jié)點，諸如此類等等等等。如果你可以熟練掌握二叉樹的遞歸和非遞歸遍歷算法，那么解決以上問題就是小菜一碟了。
4. 線索二叉樹：線索二叉樹的引出，是為避免如二叉樹遍歷時的遞歸求解。眾所周知，遞歸雖然形式上比較好理解，但是消耗了大量的內(nèi)存資源，如果遞歸層次一多，勢必帶來資源耗盡的危險，為了避免此類情況，線索二叉樹便堂而皇之地出現(xiàn)了。對于線索二叉樹，應(yīng)該掌握：線索化的實質(zhì)，三種線索化的算法，線索化后二叉樹的遍歷算法，基本線索二叉樹的其它算法問題（如：查找某一類線索二叉樹中指定結(jié)點的前驅(qū)或后繼結(jié)點就是一類?？碱}）。
5. 最優(yōu)二叉樹（哈夫曼樹）：最優(yōu)二叉樹是為了解決特定問題引出的特殊二叉樹結(jié)構(gòu)，它的前提是給二叉樹的每條邊賦予了權(quán)值，這樣形成的二叉樹按權(quán)相加之和是最小的。最優(yōu)二叉樹一節(jié)，直接考查算法源碼的很少，一般是給你一組數(shù)據(jù)，要求你建立基于這組數(shù)據(jù)的最優(yōu)二叉樹，并求出其最小權(quán)值之和，此類題目不難，屬送分題。
6. 樹與森林：二叉樹是一種特殊的樹，這種特殊不僅僅在于其分支最多為2以及其它特征，一個最重要的特殊之處是在于：二叉樹是有序的！即：二叉樹的左右孩子是不可交換的，如果交換了就成了另外一棵二叉樹，這樣交換之后的二叉樹與原二叉樹我們認(rèn)為是不相同的兩棵二叉樹。但是，對于普通的雙分支樹而言，不具有這種性質(zhì)。樹與森林的遍歷，不像二叉樹那樣豐富，他們只有兩種遍歷算法：先根與后根（對于森林而言稱作：先序與后序遍歷）。在難度比較大的考試中，也有基于此二種算法的基礎(chǔ)上再進(jìn)行擴(kuò)展要求你利用這兩種算法設(shè)計其它算法的，但一般院校很少有這種考法，最多只是要求你根據(jù)先根或后根寫出他們的遍歷序列。此二者的先根與后根遍歷與二叉樹中的遍歷算法是有對應(yīng)關(guān)系的：先根遍歷對應(yīng)二叉樹的先序遍歷，而后根遍歷對應(yīng)二叉樹的中序遍歷。這一點成為很多學(xué)校的考點，考查的方式不一而足，有的直接考此句話，有的是先讓你求解遍歷序列然后回答這個問題。二叉樹、樹與森林之所以能有以上的對應(yīng)關(guān)系，全拜二叉鏈表所賜。二叉樹使用二叉鏈表分別存放他的左右孩子，樹利用二叉鏈表存儲孩子及兄弟（稱孩子兄弟鏈表），而森林也是利用二叉鏈表存儲孩子及兄弟。樹一章，處處是重點，道道是考題，大家務(wù)必個個過關(guān)。