各章節(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è)概念。
總體來說，線性表一章可供考查的重要考點(diǎn)有以下幾個(gè)方面：
1.線性表的相關(guān)基本概念，如：前驅(qū)、后繼、表長、空表、首元結(jié)點(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)算：單鏈表、循環(huán)鏈表，雙向鏈表，雙向循環(huán)鏈表。其中，單鏈表的歸并算法、循環(huán)鏈表的歸并算法、雙向鏈表及雙向循環(huán)鏈表的插入和刪除算法等都是較為常見的考查方式。此外，近年來在不少學(xué)校中還多次出現(xiàn)要求用遞歸算法實(shí)現(xiàn)單鏈表輸出（可能是順序也可能是倒序）的問題。
在鏈表的小題型中，經(jīng)常考到一些諸如：判表空的題。在不同的鏈表中，其判表空的方式是不一樣的，請大家注意。
5.線性表的順序存儲(chǔ)及鏈?zhǔn)酱鎯?chǔ)情況下，其不同的優(yōu)缺點(diǎn)比較，即其各自適用的場合。單鏈表中設(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ù)（請注意包括：存和取兩部分）的特點(diǎn)。
2.遞歸算法。棧與遞歸的關(guān)系，以及借助棧將遞歸轉(zhuǎn)向于非遞歸的經(jīng)典算法：n!階乘問題，fib數(shù)列問題，hanoi問題，背包問題，二叉樹的遞歸和非遞歸遍歷問題，圖的深度遍歷與棧的關(guān)系等。其中，涉及到樹與圖的問題，多半會(huì)在樹與圖的相關(guān)章節(jié)中進(jìn)行考查。
3.棧的應(yīng)用：數(shù)值表達(dá)式的求解，括號的配對等的原理，只作原理性了解，具體要求考查此為題目的算法設(shè)計(jì)題不多。
4.循環(huán)隊(duì)列中判隊(duì)空、隊(duì)滿條件，循環(huán)隊(duì)列中入隊(duì)與出隊(duì)算法。
如果你已經(jīng)對上面的幾點(diǎn)了如指掌，棧與隊(duì)列一章可以不看書了。注意，我說的是可以不看書，并不是可以不作題哦。
第三章 串
經(jīng)歷了棧一章的痛苦煎熬后，終于迎來了串一章的柳暗花明。
串，在概念上是比較少的一個(gè)章節(jié)，也是最容易自學(xué)的章節(jié)之一，但正如每個(gè)過來人所了解的，KMP算法是這一章的重要關(guān)隘，突破此關(guān)隘后，走過去又是一馬平川的大好DS山河了，呵呵。
串一章需要攻破的主要堡壘有：
1.串的基本概念，串與線性表的關(guān)系（串是其元素均為字符型數(shù)據(jù)的特殊線性表），空串與空格串的區(qū)別，串相等的條件
2.串的基本操作，以及這些基本函數(shù)的使用，包括：取子串，串連接，串替換，求串長等等。運(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)之外。其中，理解算法是核心，會(huì)求數(shù)組是得分點(diǎn)。不用我多說，這一節(jié)內(nèi)容是本章的重中之重。可能進(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.多維數(shù)組中某數(shù)組元素的position求解。一般是給出數(shù)組元素的首元素地址和每個(gè)元素占用的地址空間并組給出多維數(shù)組的維數(shù)，然后要求你求出該數(shù)組中的某個(gè)元素所在的位置。
2.明確按行存儲(chǔ)和按列存儲(chǔ)的區(qū)別和聯(lián)系，并能夠按照這兩種不同的存儲(chǔ)方式求解1中類型的題。
3.將特殊矩陣中的元素按相應(yīng)的換算方式存入數(shù)組中。這些矩陣包括：對稱矩陣，三角矩陣，具有某種特點(diǎn)的稀疏矩陣等。熟悉稀疏矩陣的三種不同存儲(chǔ)方式：三元組，帶輔助行向量的二元組，十字鏈表存儲(chǔ)。掌握將稀疏矩陣的三元組或二元組向十字鏈表進(jìn)行轉(zhuǎn)換的算法。
4.廣義表的概念，特別應(yīng)該明確表頭與表尾的定義。這一點(diǎn)，是理解整個(gè)廣義表一節(jié)算法的基礎(chǔ)。近來，在一些學(xué)校中，出現(xiàn)了這樣一種題目類型：給出對某個(gè)廣義表L若干個(gè)求了若干次的取頭和取尾操作后的串值，要求求出原廣義表L。大家要留意。
5.與廣義表有關(guān)的遞歸算法。由于廣義表的定義就是遞歸的，所以，與廣義表有關(guān)的算法也常是遞歸形式的。比如：求表深度，復(fù)制廣義表等。這種題目，可以根據(jù)不同角度廣義表的表現(xiàn)形式運(yùn)用兩種不同的方式解答：一是把一個(gè)廣義表看作是表頭和表尾兩部分，分別對表頭和表尾進(jìn)行操作；二是把一個(gè)廣義表看作是若干個(gè)子表，分別對每個(gè)子表進(jìn)行操作。
第五章 樹與二叉樹
從對線性結(jié)構(gòu)的研究過度到對樹形結(jié)構(gòu)的研究，是數(shù)據(jù)結(jié)構(gòu)課程學(xué)習(xí)的一次躍變，此次躍變完成的好壞，將直接關(guān)系到你到實(shí)際的考試中是否可以拿到高分，而這所有的一切，將最終影響你的專業(yè)課總分。所以，樹這一章的重要性，已經(jīng)不說自明了。
總體來說，樹一章的知識點(diǎn)包括：
二叉樹的概念、性質(zhì)和存儲(chǔ)結(jié)構(gòu)，二叉樹遍歷的三種算法（遞歸與非遞歸），在三種基本遍歷算法的基礎(chǔ)上實(shí)現(xiàn)二叉樹的其它算法，線索二叉樹的概念和線索化算法以及線索化后的查找算法，最優(yōu)二叉樹的概念、構(gòu)成和應(yīng)用，樹的概念和存儲(chǔ)形式，樹與森林的遍歷算法及其與二叉樹遍歷算法的聯(lián)系，樹與森林和二叉樹的轉(zhuǎn)換。
下面我們來看考試中對以上知識的主要考查方法：
1.二叉樹的概念、性質(zhì)和存儲(chǔ)結(jié)構(gòu)
考查方法可有：直接考查二叉樹的定義，讓你說明二叉樹與普通雙分支樹的區(qū)別；考查滿二叉樹和完全二叉樹的性質(zhì)，普通二叉樹的五個(gè)性質(zhì)：第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)及適用場合，二叉樹的三叉鏈表表示方法。
2.二叉樹的三種遍歷算法
這一知識點(diǎn)掌握的好壞，將直接關(guān)系到樹一章的算法能否理解，進(jìn)而關(guān)系到樹一章的算法設(shè)計(jì)題能否順利完成。二叉樹的遍歷算法有三種：先序，中序和后序。其劃分的依據(jù)是視其每個(gè)算法中對根結(jié)點(diǎn)數(shù)據(jù)的訪問順序而定。不僅要熟練掌握三種遍歷的遞歸算法，理解其執(zhí)行的實(shí)際步驟，并且應(yīng)該熟練掌握三種遍歷的非遞歸算法。由于二叉樹一章的很多算法，可以直接根據(jù)三種遞歸算法改造而來（比如：求葉子個(gè)數(shù)），所以，掌握了三種遍歷的非遞歸算法后，對付諸如：“利用非遞歸算法求二叉樹葉子個(gè)數(shù)”這樣的題目就下筆如有神了。我會(huì)在另一篇系列文章（
http://bbs.kaoyan.com/ibbs.dll?bbsdisp?t_id=301583&bp=2&bt=0）里給出三種遍歷的遞歸和非遞歸算法的背記版，到時(shí)請大家一定熟記。
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í)的遞歸求解。眾所周知，遞歸雖然形式上比較好理解，但是消耗了大量的內(nèi)存資源，如果遞歸層次一多，勢必帶來資源耗盡的危險(xiǎn)，為了避免此類情況，線索二叉樹便堂而皇之地出現(xiàn)了。對于線索二叉樹，應(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)值之和，此類題目不難，屬送分題。
6.樹與森林：
二叉樹是一種特殊的樹，這種特殊不僅僅在于其分支最多為2以及其它特征，一個(gè)最重要的特殊之處是在于：二叉樹是有序的！即：二叉樹的左右孩子是不可交換的，如果交換了就成了另外一棵二叉樹，這樣交換之后的二叉樹與原二叉樹我們認(rèn)為是不相同的兩棵二叉樹。但是，對于普通的雙分支樹而言，不具有這種性質(zhì)。
樹與森林的遍歷，不像二叉樹那樣豐富，他們只有兩種遍歷算法：先根與后根（對于森林而言稱作：先序與后序遍歷）。在難度比較大的考試中，也有基于此二種算法的基礎(chǔ)上再進(jìn)行擴(kuò)展要求你利用這兩種算法設(shè)計(jì)其它算法的，但一般院校很少有這種考法，最多只是要求你根據(jù)先根或后根寫出他們的遍歷序列。此二者的先根與后根遍歷與二叉樹中的遍歷算法是有對應(yīng)關(guān)系的：先根遍歷對應(yīng)二叉樹的先序遍歷，而后根遍歷對應(yīng)二叉樹的中序遍歷。這一點(diǎn)成為很多學(xué)校的考點(diǎn)，考查的方式不一而足，有的直接考此句話，有的是先讓你求解遍歷序列然后回答這個(gè)問題。二叉樹、樹與森林之所以能有以上的對應(yīng)關(guān)系，全拜二叉鏈表所賜。二叉樹使用二叉鏈表分別存放他的左右孩子，樹利用二叉鏈表存儲(chǔ)孩子及兄弟（稱孩子兄弟鏈表），而森林也是利用二叉鏈表存儲(chǔ)孩子及兄弟。
樹一章，處處是重點(diǎn)，道道是考題，大家務(wù)必個(gè)個(gè)過關(guān)。
第六章 圖
如果說，從線性結(jié)構(gòu)向樹形結(jié)構(gòu)研究的轉(zhuǎn)變，是數(shù)據(jù)結(jié)構(gòu)學(xué)科對數(shù)據(jù)組織形式研究的一次升華，那么從樹形結(jié)構(gòu)的研究轉(zhuǎn)到圖形結(jié)構(gòu)的研究，則進(jìn)一步讓我們看到了數(shù)據(jù)結(jié)構(gòu)對于解決實(shí)際問題的重大推動(dòng)作用。
圖這一章的特點(diǎn)是：概念繁多，與離散數(shù)學(xué)中圖的概念聯(lián)系緊密，算法復(fù)雜，極易被考到，且容易出大題，尤其是名校，作為考研課程，如果不考查樹與圖兩章的知識，幾乎是不可想像的。
下面我們看一下圖這一章的主要考點(diǎn)以及這些考點(diǎn)的考查方式：
1.考查有關(guān)圖的基本概念問題：
這些概念是進(jìn)行圖一章學(xué)習(xí)的基礎(chǔ)，這一章的概念包括：圖的定義和特點(diǎn)，無向圖，有向圖，入度，出度，完全圖，生成子圖，路徑長度，回路，（強(qiáng)）連通圖，（強(qiáng)）連通分量等概念。與這些概念相聯(lián)系的相關(guān)計(jì)算題也應(yīng)該掌握。
2.考查圖的幾種存儲(chǔ)形式：
圖的存儲(chǔ)形式包括：鄰接矩陣，（逆）鄰接表，十字鏈表及鄰接多重表。在考查時(shí)，有的學(xué)校是給出一種存儲(chǔ)形式，要求考生用算法或手寫出與給定的結(jié)構(gòu)相對應(yīng)的該圖的另一種存儲(chǔ)形式。
3.考查圖的兩種遍歷算法：深度遍歷和廣度遍歷
深度遍歷和廣度遍歷是圖的兩種基本的遍歷算法，這兩個(gè)算法對圖一章的重要性等同于“先序、中序、后序遍歷”對于二叉樹一章的重要性。在考查時(shí)，圖一章的算法設(shè)計(jì)題常常是基于這兩種基本的遍歷算法而設(shè)計(jì)的，比如：“求最長的最短路徑問題”和“判斷兩頂點(diǎn)間是否存在長為K的簡單路徑問題”，就分別用到了廣度遍歷和深度遍歷算法。
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ù)溆行颉钡摹?BR>6.關(guān)鍵路徑問題：
這個(gè)問題是圖一章的難點(diǎn)問題。理解關(guān)鍵路徑的關(guān)鍵有三個(gè)方面：一是何謂關(guān)鍵路徑，二是最早時(shí)間是什么意思、如何求，三是最晚時(shí)間是什么意思、如何求。簡單地說，最早時(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)鍵路徑問題并稱為圖一章的兩只攔路虎。概念理解是比較容易的，關(guān)鍵是算法的理解。最短路徑問題分為兩種：一是求從某一點(diǎn)出發(fā)到其余各點(diǎn)的最短路徑；二是求圖中每一對頂點(diǎn)之間的最短路徑。這個(gè)問題也具有非常實(shí)用的背景特色，一個(gè)典型的應(yīng)該就是旅游景點(diǎn)及旅游路線的選擇問題。解決第一個(gè)問題用DIJSKTRA算法，解決第二個(gè)問題用FLOYD算法。注意區(qū)分。
第七章 查找
在不少數(shù)據(jù)結(jié)構(gòu)的教材中，是把查找與排序放入高級數(shù)據(jù)結(jié)構(gòu)中的。應(yīng)該說，查找和排序兩章是前面我們所學(xué)的知識的綜合運(yùn)用，用到了樹、也用到了鏈表等知識，對這些數(shù)據(jù)結(jié)構(gòu)某一方面的運(yùn)用就構(gòu)成了查找和排序。
現(xiàn)實(shí)生活中，search幾乎無處不在，特別是現(xiàn)在的網(wǎng)絡(luò)時(shí)代，萬事離不開search，小到文檔內(nèi)文字的搜索，大到INTERNET上的搜索，search占據(jù)了我們上網(wǎng)的大部分時(shí)間。
在復(fù)習(xí)這一章的知識時(shí)，你需要先弄清楚以下幾個(gè)概念：
關(guān)鍵字、主關(guān)鍵字、次關(guān)鍵字的含義；靜態(tài)查找與動(dòng)態(tài)查找的含義及區(qū)別；平均查找長度ASL的概念及在各種查找算法中的計(jì)算方法和計(jì)算結(jié)果，特別是一些典型結(jié)構(gòu)的ASL值，應(yīng)該記住。
在DS的教材中，一般將search分為三類：1st，在順序表上的查找；2nd，在樹表上的查找；3rd，在哈希表上的查找。下面詳細(xì)介紹其考查知識點(diǎn)及考查方式：
1.線性表上的查找：
主要分為三種線性結(jié)構(gòu)：順序表，有序順序表，索引順序表。對于第一種，我們采用傳統(tǒng)查找方法，逐個(gè)比較。對于及有序順序表我們采用二分查找法。對于第三種索引結(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é)果是一個(gè)遞增的有序序列。平衡二叉樹是二叉排序樹的優(yōu)化，其本質(zhì)也是一種二叉排序樹，只不過，平衡二叉樹對左右子樹的深度有了限定：深度之差的絕對值不得大于1。對于二叉排序樹，“判斷某棵二叉樹是否二叉排序樹”這一算法經(jīng)常被考到，可用遞歸，也可以用非遞歸。平衡二叉樹的建立也是一個(gè)常考點(diǎn)，但該知識點(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)之一。
鍵樹也稱字符樹，特別適用于查找英文單詞的場合。一般不要求能完整描述算法源碼，多是根據(jù)算法思想建立鍵樹及描述其大致查找過程。
3.基本哈希表的查找算法：
哈希一詞，是外來詞，譯自“hash”一詞，意為：散列或雜湊的意思。哈希表查找的基本思想是：根據(jù)當(dāng)前待查找數(shù)據(jù)的特征，以記錄關(guān)鍵字為自變量，設(shè)計(jì)一個(gè)function，該函數(shù)對關(guān)鍵字進(jìn)行轉(zhuǎn)換后，其解釋結(jié)果為待查的地址。基于哈希表的考查點(diǎn)有：哈希函數(shù)的設(shè)計(jì)，沖突解決方法的選擇及沖突處理過程的描述。
第八章 內(nèi)部排序
內(nèi)排是DS課程中最后一個(gè)重要的章節(jié)，建立在此章之上的考題可以有多種類型：填空，選擇，判斷乃至大型算法題。但是，歸結(jié)到一點(diǎn)，就是考查你對書本上的各種排序算法及其思想以及其優(yōu)缺點(diǎn)和性能指標(biāo)（時(shí)間復(fù)雜度）能否了如指掌。
這一章，我們對重點(diǎn)的規(guī)納將跟以上各章不同。我們將從以下幾個(gè)側(cè)面來對排序一章進(jìn)行不同的規(guī)納，以期能更全面的理解排序一章的總體結(jié)構(gòu)及各種算法。
從排序算法的種類來分，本章主要闡述了以下幾種排序方法：插入、選擇、交換、歸并、計(jì)數(shù)等五種排序方法。
其中，在插入排序中又可分為：直接插入、折半插入、2路插入、希爾排序。這幾種插入排序算法的最根本的不同點(diǎn)，說到底就是根據(jù)什么規(guī)則尋找新元素的插入點(diǎn)。直接插入是依次尋找，折半插入是折半尋找。希爾排序，是通過控制每次參與排序的數(shù)的總范圍“由小到大”的增量來實(shí)現(xiàn)排序效率提高的目的。
交換排序，又稱冒泡排序，在交換排序的基礎(chǔ)上改進(jìn)又可以得到快速排序。快速排序的思想，一語以敝之：用中間數(shù)將待排數(shù)據(jù)組一分為二。快速排序，在處理的“問題規(guī)模”這個(gè)概念上，與希爾有點(diǎn)相反，快速排序，是先處理一個(gè)較大規(guī)模，然后逐漸把處理的規(guī)模降低，最終達(dá)到排序的目的。
選擇排序，相對于前面幾種排序算法來說，難度大一點(diǎn)。具體來說，它可以分為：簡單選擇、樹選擇、堆排。這三種方法的不同點(diǎn)是，根據(jù)什么規(guī)則選取最小的數(shù)。簡單選擇，是通過簡單的數(shù)組遍歷方案確定最小數(shù)；樹選擇，是通過“錦標(biāo)賽”類似的思想，讓兩數(shù)相比，不斷淘汰較大（小）者，最終選出最小（大）數(shù)；而堆排序，是利用堆這種數(shù)據(jù)結(jié)構(gòu)的性質(zhì)，通過堆元素的刪除、調(diào)整等一系列操作將最小數(shù)選出放在堆頂。堆排序中的堆建立、堆調(diào)整是重要考點(diǎn)。樹選擇排序，也曾經(jīng)在一些學(xué)校中的大型算法題中出現(xiàn)，請大家注意。
歸并排序，故名思義，是通過“歸并”這種操作完成排序的目的，既然是歸并就必須是兩者以上的數(shù)據(jù)集合才可能實(shí)現(xiàn)歸并。所以，在歸并排序中，關(guān)注最多的就是2路歸并。算法思想比較簡單，有一點(diǎn)，要銘記在心：歸并排序是穩(wěn)定排序。
基數(shù)排序，是一種很特別的排序方法，也正是由于它的特殊，所以，基數(shù)排序就比較適合于一些特別的場合，比如撲克牌排序問題等。基數(shù)排序，又分為兩種：多關(guān)鍵字的排序（撲克牌排序），鏈?zhǔn)脚判颍ㄕ麛?shù)排序）。基數(shù)排序的核心思想也是利用“基數(shù)空間”這個(gè)概念將問題規(guī)模規(guī)范、變小，并且，在排序的過程中，只要按照基排的思想，是不用進(jìn)行關(guān)鍵字比較的，這樣得出的最終序列就是一個(gè)有序序列。
本章各種排序算法的思想以及偽代碼實(shí)現(xiàn)，及其時(shí)間復(fù)雜度都是必須掌握的，學(xué)習(xí)時(shí)要多注意規(guī)納、總結(jié)、對比。此外，對于教材中的10.7節(jié)，要求必須熟記，在理解的基礎(chǔ)上記憶，這一節(jié)幾乎成為很多學(xué)校每年的必考點(diǎn)。
至此，數(shù)據(jù)結(jié)構(gòu)所有章節(jié)的章節(jié)重點(diǎn)問題，我們已經(jīng)規(guī)納完畢，使用清華嚴(yán)版教材的同學(xué)，在復(fù)習(xí)的同時(shí)，可以參照本貼給出的重點(diǎn)進(jìn)行復(fù)習(xí)。但是，由于作者本人水平有限，可能有很多考點(diǎn)沒有規(guī)納出來，也可能有些考點(diǎn)規(guī)納有誤，在此，作者本人誠懇希望諸位朋友直面提出，我會(huì)不斷完善和發(fā)布新的關(guān)于數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)的總結(jié)以及筆記，請大家繼續(xù)支持作者以及kaoyan.com計(jì)算機(jī)版。
數(shù)據(jù)結(jié)構(gòu)試題分析和解決方法
數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)專業(yè)的核心課程之一，它主要研究的是數(shù)據(jù)的各種組織形式及建立在
這些結(jié)構(gòu)之上的各種操作的實(shí)現(xiàn)。在計(jì)算機(jī)專業(yè)課的學(xué)習(xí)中，數(shù)據(jù)結(jié)構(gòu)課程的作用如靈
魂似的，它不僅為用程序設(shè)計(jì)語言進(jìn)行程序設(shè)計(jì)提供了方法性的理論指導(dǎo)，還在一個(gè)更
高的層次上總結(jié)了程序設(shè)計(jì)的常見方法和常用技巧，可以說是程序設(shè)計(jì)人員的必修課程
。
由于數(shù)據(jù)結(jié)構(gòu)在教學(xué)和實(shí)際應(yīng)用中的重要作用，絕大多數(shù)院校的研究生入學(xué)考試的專業(yè)
課考核中，都把數(shù)據(jù)結(jié)構(gòu)列為必考科目，其考題難度因?yàn)樵盒５牟煌Р钊f別，但一
般高于該院校本科生的期末考試難度。
1．?dāng)?shù)據(jù)結(jié)構(gòu)課程及考題特點(diǎn)
首先，讓我們總結(jié)一下數(shù)據(jù)結(jié)構(gòu)課程及考題的特點(diǎn)，數(shù)據(jù)結(jié)構(gòu)具有以下特點(diǎn)：
=概念多，對比性強(qiáng)，易記憶
從最簡單的線性表到最復(fù)雜的圖，都有以下內(nèi)容：類型定義、結(jié)構(gòu)特點(diǎn)。在這些數(shù)據(jù)結(jié)
構(gòu)的操作中又都有：建立、撤消、插入、刪除、查找等基本操作，學(xué)習(xí)各章時(shí)的對比性
很強(qiáng)，使讀者很容易建立整體概念。
數(shù)據(jù)結(jié)構(gòu)中概念較多的章節(jié)是樹、圖、查找、排序等章節(jié)。這些章節(jié)中需要識記的概念
請讀者最好作好筆記，以備復(fù)習(xí)中隨時(shí)查閱之用。
=算法靈活，個(gè)性突出，不易把握
雖然各種數(shù)據(jù)結(jié)構(gòu)的基本算法都有相同的操作，但是因?yàn)槠浣⒃诓煌拇鎯?chǔ)結(jié)構(gòu)上，
所以實(shí)現(xiàn)的方法也就截然不同。舉個(gè)簡單的例子：
對于刪除結(jié)點(diǎn)的操作，在線性表中，由于其結(jié)點(diǎn)關(guān)系是“前后”關(guān)系這種單一的關(guān)系，
所以刪除時(shí)只需要考慮最多另外“兩個(gè)”（前驅(qū)與后繼）結(jié)點(diǎn)的位置；但是，在圖這種
數(shù)據(jù)結(jié)構(gòu)中，由于其結(jié)點(diǎn)關(guān)系是“多對多”的復(fù)雜關(guān)系，所以刪除結(jié)點(diǎn)時(shí)就需要考慮所
有與此結(jié)點(diǎn)相關(guān)結(jié)點(diǎn)信息的修改。
=抽象性強(qiáng)，過于形式化，難于聯(lián)系實(shí)際
數(shù)據(jù)結(jié)構(gòu)中的研究對象――數(shù)據(jù)元素，都是從現(xiàn)實(shí)生活中抽象出來的，在被組織成不同
形式時(shí)，都只是對單純的數(shù)據(jù)進(jìn)行操作，而忽略了其本身所代表的實(shí)際意義，比較抽象
。如果讀者能適時(shí)地很好地聯(lián)系實(shí)際來思考這些問題，就能較好的把握。
=歷年考題多有雷同，重復(fù)率高
對于同一所學(xué)校，在不同的年份中可能出現(xiàn)相同或相似的考題；對于不同的學(xué)校，也經(jīng)
常考一些在算法上極其相似或相同的題。關(guān)于這一點(diǎn)，在本書收錄的考研真 題中，大家
會(huì)很深刻的感受到。
2．?dāng)?shù)據(jù)結(jié)構(gòu)考試題型總結(jié)
下面讓我們來分析一下數(shù)據(jù)結(jié)構(gòu)考試題型，由于數(shù)據(jù)結(jié)構(gòu)的學(xué)科特點(diǎn)，概括起來，在考
試中可能出現(xiàn)的考題包括兩個(gè)方面：
=概念知識
其中概念知識類題的出題內(nèi)容大概為以下幾個(gè)方面：
各種結(jié)構(gòu)的定義、特點(diǎn)、適用場合，多種數(shù)據(jù)結(jié)構(gòu)之間的比較，多種算法性能的比較。
在這些內(nèi)容的基礎(chǔ)上，大體可以有以下幾種命題方式：填空、選擇、判斷等小分值的題
目，這些多是基礎(chǔ)題。
=算法分析與設(shè)計(jì)
算法設(shè)計(jì)與分析類題的出題內(nèi)容包括以下幾個(gè)方面：
算法設(shè)計(jì)，算法功能分析，算法功能完善。基于以上內(nèi)容可以出問答、設(shè)計(jì)等較大分值
的題。在這些題中，難度太高的很少，一般有1至2題是最難的，其他題目較易掌握。
從以上分析來看，基礎(chǔ)題加上較簡單的設(shè)計(jì)題，其總分值累計(jì)約為70到80分左右，也就
是說，70%到80%的題是基礎(chǔ)題。所以，只要我們努力打好基礎(chǔ)，把基本題的分拿到手，
不愁數(shù)據(jù)結(jié)構(gòu)不能順利過關(guān)。
3．解題方法分析
在進(jìn)行了數(shù)據(jù)結(jié)構(gòu)的題型分析之后，我們來探討一下各種類型題的解題方法
=基礎(chǔ)題
由于此類基礎(chǔ)題涉及范圍廣，含蓋信息量大，考生不可能或很難在較短時(shí)間內(nèi)掌握所有
概念。所以，請大家在平時(shí)的復(fù)習(xí)中，要認(rèn)真做好讀書筆記，及時(shí)歸納總結(jié)基本概念。
同時(shí)，由于此類題難度不大，但是要求考生必須細(xì)致入微，否則極易出錯(cuò)，喪失不該掉
的分值。
例1、（同濟(jì)大學(xué)1999年試題）
閱讀下面的程序并寫出程序執(zhí)行結(jié)果：
main()
{int x,y,z,w;
z=(x=−1)?(y=−1, y+=x+5):(x=7,y=3);
w=y*‘a(chǎn)’/4;
printf(“%d %d %d %c\n”,x,y,z,w);
}
本題的難度并不大，僅需知道C語言的基本知識就可以做對。但是大家做的時(shí)候，很多同
學(xué)會(huì)得出“－1 3 3 72”，而實(shí)際上正確答案為：“－1 3 3 H”，因?yàn)榇蠹覜]有
注意到w的輸出格式是：“%c”。在第一遍審題的時(shí)候，可能比較容易看出這里w的輸出
格式是“%c”，但是在解答過程中，經(jīng)過若干計(jì)算之后，得出了結(jié)果為72，心理上很容
易發(fā)生變化，產(chǎn)生“好啦！終于算出來了”的一瞬間的想法，而受到前三個(gè)都是整數(shù)的
思維慣性影響，忽視了第四個(gè)變量要轉(zhuǎn)換成字符來輸出。這就是這個(gè)題目的陷阱，大家
一定要重視！
此外，在考試過程中，得許多解題技巧，各個(gè)學(xué)科，各種考試，都是相通的，考研究生
的同學(xué)都是久經(jīng)沙場的老將了，對于這些技巧應(yīng)該是不陌生的，比如需選擇題的代入法
、排除法等等。比如下面這個(gè)選擇題，在你無法判斷或需很長時(shí)間才能判斷正確結(jié)果的
情況下，一種行之有效的方法就是把備選答案代入到題目中，以驗(yàn)證答案的正確性。
例2、中國科學(xué)院計(jì)算技術(shù)研究所1996年試題
字符串S滿足下式，其中Head和Tail的定義同廣義表類似，如Head(‘xyz’)=‘x’
，Tail(‘xyz’)=‘yz’，則S=_____。
Concat(Head(Tail(S))，Head(Tail(Tail(S))))=‘dc’
（A）abcd （B）acbd （C）acdb （D）adcb
選擇題可用代入法求解，把答案一個(gè)個(gè)代入即可驗(yàn)證，本題答案為D。
=算法分析類題
算法分析的有效工具是：D-F圖，PDL語言，程序流圖。由于目前的程序設(shè)計(jì)中，最終都
要使用面向過程的結(jié)構(gòu)化程序設(shè)計(jì)方法，程序或算法內(nèi)部具有很強(qiáng)的模塊化特性，所以
分析時(shí)可以按照模塊分解的方法，把具有獨(dú)立功能的相關(guān)語句看作一個(gè)整體，完成某種
功能。這樣就會(huì)站在算法的全局來看待問題，從而拓寬了思路。總體來說，一個(gè)完整的
算法大致分成三個(gè)模塊：一是輸入數(shù)據(jù)模塊，二是算法處理模塊，三是輸出結(jié)果模塊。
通常情況下，算法處理模塊中的語句是核心，難度也最大；而輸入模塊與輸出模塊難度
較小，讀者可以先攻克這兩個(gè)模塊。
由于算法分析類題目是遵循別人的思路進(jìn)行解題，所以難度較大，需要一定的算法經(jīng)驗(yàn)
積累。這種積累需要靠大量的練習(xí)而來。
比如：“兩個(gè)數(shù)的交換操作”，就有以下兩種不同的實(shí)現(xiàn)方法：
① temp=a;a=b;b=temp;
② x=x+y;y=x-y;x=x-y;
在第一種解法中，其思路是最普遍的思路，也是較易理解的，但思路二則是一種不常見
的思路，加大了算法的復(fù)雜性。在考試中，有的考題為了加大題目本身難度就可能使用
第二種方法（但讀者在自己設(shè)計(jì)算法時(shí)則應(yīng)該盡量避免使用非常見的算法）。所以，平
時(shí)練習(xí)時(shí)，應(yīng)積極尋求一題多解，探尋多種思路，并將好的方法記錄下來。但是，請讀
者放心，并不是所有的考題都如此怪異，其算法多數(shù)是常見的。
此外，在算法分析題中，讀者應(yīng)十分注意一些細(xì)節(jié)信息，例如算法的注釋、算法核心變
量的名稱，往往這都是一些提示性的信息。從這些提示信息中，讀者可以推算此變量的
含義及作用，由此推出其所在模塊的功能，再將該模塊放在整個(gè)算法中來理解，那么整
個(gè)算法的分析工作也就完成了。
=算法設(shè)計(jì)題
算法設(shè)計(jì)類題目是數(shù)據(jù)結(jié)構(gòu)分值最大的題，往往也是決定考生能否得高分的關(guān)鍵。
算法就是解決問題的方法。計(jì)算機(jī)算法具有以下特性：有窮性，確定性，可執(zhí)行性，0個(gè)
或多個(gè)輸入，1個(gè)或多個(gè)輸出。算法的主要類型分為兩類：數(shù)值算法與非數(shù)值算法。
算法設(shè)計(jì)的常用工具有：與算法分析題一樣，算法設(shè)計(jì)工具有N－F，流程圖，PDL語言。
算法設(shè)計(jì)的常用方法主要有兩種：
第一種，模塊化結(jié)構(gòu)化設(shè)計(jì)方法，即把問題分成幾個(gè)獨(dú)立的子模塊，然后把各子模塊組
合起來完成算法的功能
第二種，自頂向下、逐步求精的結(jié)構(gòu)化設(shè)計(jì)方法，即從上到下一層逐步細(xì)化求解過程，
直到寫出最終的算法來。
從對算法設(shè)計(jì)的要求來說，下面是4條重要的準(zhǔn)則:
（1）要確保算法的正確性；
（2）要使算法具有良好的可讀性；
（3）要使算法具有良好的健壯性；
（4）要使算法占用較少的時(shí)空資源。
在以上四點(diǎn)中，前兩者是極其重要的，往往是算法設(shè)計(jì)題取得高分的關(guān)鍵。正確性自不
必多說，關(guān)于算法的可讀性，一是必須寫上算法注釋，二是最好在寫算法前加上算法的
說明，這個(gè)說明包括算法功能，算法核心變量的含義，模塊的含義及其參數(shù)的作用。
值得注意的是，有些學(xué)校的考題為了增加難度，就要求考生寫出時(shí)間復(fù)雜度最小的
，或者是限制了額外的變量的使用。這樣就要求我們在平時(shí)的復(fù)習(xí)當(dāng)中，在第四個(gè)要求
上多下功夫，不僅要寫出正確的算法，而且要寫出最優(yōu)的算法來。
最后，從考試的角度來說，讀者在平時(shí)的練習(xí)中就應(yīng)該有意加強(qiáng)“規(guī)范”的意識和練習(xí)
，否則難以保證在考試中能寫出既清晰又不多余的算法注釋和算法說明來。從閱卷者批
改試卷的角度考慮，也應(yīng)該這樣做，因?yàn)槿绻喚碚呖吹揭环萁Y(jié)構(gòu)清晰、注釋明了的答
卷，必有賞心悅目的感覺，這樣即使有些許錯(cuò)誤，下手必然也會(huì)慎重；反之，如果算法
冗長而沒有注釋，Begin end等嵌套匹配混亂，即使解答是正確的，閱卷者看了也必定頭
疼！這里還須提醒考生一點(diǎn)的是，不要追求算法的新奇，最好按照普通的思維方式，通
常的解法來做，因?yàn)槿f一你的算法獨(dú)出心裁，雖然是個(gè)好算法，而閱卷者不能再一兩分
鐘內(nèi)理解，可能會(huì)因此而損失慘重，盡管通常來說閱卷者都會(huì)認(rèn)真對待每一份考卷，但
是大家還是不要冒險(xiǎn)。
4．復(fù)習(xí)方法指導(dǎo)
下面簡單說一下數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)方法和讀者可能會(huì)遇到的誤區(qū)。
我們認(rèn)為學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)這門課程至少要經(jīng)歷三個(gè)過程，方可真正的掌握這門課程，得到
一個(gè)滿意的成績。這個(gè)過程簡單來說就是三個(gè)字：活→死→活。
首先，是一個(gè)學(xué)“活”的過程，就要要求我們對書中的每一個(gè)算法，能夠在腦海中建立
起相應(yīng)的模型，而不是死板的算法。比如樹的遍歷非遞歸算法，在入棧與出棧的過程中
，我們就要在腦海中形成訪問樹每個(gè)結(jié)點(diǎn)的過程，真正掌握住這個(gè)算法。這樣，全書復(fù)
習(xí)下來，你的腦海中就有了整個(gè)數(shù)據(jù)結(jié)構(gòu)的模型概念，對任何一個(gè)陌生的算法，將不感
到生疏和害怕。
有些同學(xué)到了此處就覺得數(shù)據(jù)結(jié)構(gòu)已經(jīng)學(xué)好，可以萬事大吉了，其實(shí)這還遠(yuǎn)遠(yuǎn)不夠，如
果參加考試，往往會(huì)拿不到高分，甚至還會(huì)納悶，為何自己數(shù)據(jù)結(jié)構(gòu)學(xué)的這樣好，成績
卻不盡如人意，因此產(chǎn)生了批卷老師判錯(cuò)的想法。所以第二個(gè)過程，就是一個(gè)學(xué)“死”
的過程，這個(gè)過程要求，要記住書中的算法（功利一點(diǎn)就是要背誦會(huì)所報(bào)考學(xué)校的考試
要求的算法）。有的學(xué)校有別的特殊要求，也一并背會(huì)。如上海交通大學(xué)喜歡考平均復(fù)
雜度的分析這樣的題目，我們在書上可以找到這樣的分析一共十一個(gè)，全部背會(huì)，就免
去了在考場上分析的麻煩，如果連答案都能記住，那么，也不會(huì)因?yàn)榇中氖Х至恕＿@一
過程也許有些枯燥，但卻是最重要的過程，比如說背會(huì)了樹的后序遍歷非遞歸，遇到了
像求某個(gè)結(jié)點(diǎn)的所有祖先，兩個(gè)結(jié)點(diǎn)的共同祖先這樣的題，不用想，直接套用。這樣才
是考試的高分的關(guān)鍵：在考場上，遇到考題，不用思考，直接從腦海中找匹配的算法，
直接引用。
有了第二個(gè)過程的辛苦，我們就可以得到一個(gè)比較高的分?jǐn)?shù)了，如果還想提高，就要進(jìn)
行第三個(gè)過程，再學(xué)“活”的過程。這一個(gè)過程中就要要求我們，在第二步的基礎(chǔ)上，
多進(jìn)行思考，看看有哪些算法有共性，比如說：樹的前序非遞歸遍歷算法和圖的深度優(yōu)
先遍歷算法是不是類似啊，有些什么不同，有些什么相同，為什么會(huì)相同；森林轉(zhuǎn)化為
二叉樹和圖的生成樹的算法也是這樣，等等。總結(jié)出這種共性，這樣就能正確有效的記
憶算法，同時(shí)，遇到難題不至于慌亂，能夠從容下手解題。
對于總結(jié)共性問題上，這里舉一小個(gè)例子，比如樹的遍歷，不管是遞歸還是非遞歸，也
不管是線索樹，還是頭結(jié)點(diǎn)有父母信息的樹，它的遍歷其實(shí)就是一個(gè)尋找到遍歷的第一
個(gè)結(jié)點(diǎn)，然后再尋找它的后繼結(jié)點(diǎn)的過程，我們歸納到此處，就可以試著總結(jié)一下三種
遍歷的后繼結(jié)點(diǎn)是哪個(gè)，有幾種情況：
對于前序遍歷，它的后繼如下：
（１）若有左孩子，則后繼是左孩子；
（２）若無左孩子，有右孩子，則后繼是右孩子；
（３）若既無左孩子，又無右孩子，則是一片葉子；再討論：
（ａ）若是其父母的左孩子，且父母有右孩子，則后繼是父母的右孩子。
（ｂ）若是其父母的左孩子，且父母無右孩子；
（ｃ）若是其父母的右孩子。
ｂ，ｃ都表示這是某個(gè)節(jié)點(diǎn)的左子樹前序遍歷的最后一個(gè)節(jié)點(diǎn)，則需要找第一個(gè)有右子
樹的“左祖先”（定義“左祖先”，即找第一個(gè)使得當(dāng)前節(jié)點(diǎn)在這個(gè)祖先的左子樹上）
，然后后繼就是這個(gè)祖先的右孩子。
對于中序遍歷，它的后繼如下：
（１）如有右孩子，后繼是右孩子的最左下節(jié)點(diǎn)；
（２）若無右孩子，且是父母的左孩子，則后繼就是父母；
（３）若無右孩子，且是父母的右孩子，則一直上溯到第一個(gè)“左祖先”（定義如前）
則后繼就是這個(gè)祖先。若無這樣的祖先，說明已經(jīng)遍歷完畢。
對于后序遍歷，它的后繼如下：
（１）若是父母的右孩子，則后繼是父母；
（２）若是父母的左孩子，且父母無右子樹，則后繼是父母；
（３）若是父母的左孩子，父母有右子樹，則后繼是父母右子樹的最先訪問到的節(jié)點(diǎn)（
指向父母的右子樹后，一直往左，若不行的話，往右一步，一直到葉子）
總結(jié)完了，想一想，我們還能得到哪些提示？經(jīng)常有一類型題目，要求求某個(gè)結(jié)點(diǎn)的直
接前驅(qū)。其實(shí)求前序遍歷的前驅(qū)和求后序遍歷的后繼是一樣的，只不過把左換成右而已
，前序遍歷的求后繼和后序遍歷的求前驅(qū)、中序遍歷的求前驅(qū)和中序遍歷求后繼都有這
樣的對稱關(guān)系。因此，總結(jié)出共性的東西，許多題目就可以迎刃而解了。問一問讀到這
里的讀者，你現(xiàn)在能夠自己在腦子里面，非常輕松地像上面那樣，把這個(gè)例子里面的情
況都條理清楚地分析總結(jié)出來嗎？如果現(xiàn)在還不行，到考試之前，你必須掌握到這種程
度，才能得到一個(gè)自己很滿意的分?jǐn)?shù)。
經(jīng)過以上的三個(gè)過程復(fù)習(xí)，相信讀者對數(shù)據(jù)結(jié)構(gòu)的掌握就可以到達(dá)比較高的水平了，如
果參加研究生的如許考試，獲得一個(gè)比較滿意的成績也很有希望了。當(dāng)然，達(dá)到這一步
并不容易，大量的練習(xí)是真正掌握的必由之路。因此，我們建議大家能夠下功夫把本書
中的題目完整地做一遍。能夠真正把本書中的所有題都掌握，絕不僅僅意味著僅會(huì)了書
中這幾百道題目，而是意味著對數(shù)據(jù)結(jié)構(gòu)這門課程的理解，以及對問題的分析能力都有
很大的提高，這樣在考場上即使遇到未曾見過的題目，也就可以從容應(yīng)對了！