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