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

1、清華嚴蔚敏數(shù)據(jù)結(jié)構(gòu)C語言版復(fù)習(xí)歸納1一、數(shù)據(jù)結(jié)構(gòu)的章節(jié)結(jié)構(gòu)及重點構(gòu)成一、數(shù)據(jù)結(jié)構(gòu)的章節(jié)結(jié)構(gòu)及重點構(gòu)成數(shù)據(jù)結(jié)構(gòu)學(xué)科的章節(jié)劃分基本上為：概論，線性表，棧和隊列，串，多維數(shù)組和廣義表，樹和二叉樹，圖，查找，內(nèi)排，外排，文件，動態(tài)存儲分配。對于絕大多數(shù)的學(xué)校而言，“外排，文件，動態(tài)存儲分配”三章基本上是不考的，在大多數(shù)高校的計算機本科教學(xué)過程中，這三章也是基本上不作講授的。所以，大家在這三章上可以不必花費過多的精力，只要知道基本的概念即可。但是

2、，對于報考名校特別是該校又有在試卷中對這三章進行過考核的歷史，那么這部分朋友就要留意這三章了。按照以上我們給出的章節(jié)以及對后三章的介紹，數(shù)據(jù)結(jié)構(gòu)的章節(jié)比重大致為：概論：概論：內(nèi)容很少，概念簡單，分數(shù)大多只有幾分，有的學(xué)校甚至不考。線性表線性表：基礎(chǔ)章節(jié)，必考內(nèi)容之一?？碱}多數(shù)為基本概念題，名?？碱}中，鮮有大型算法設(shè)計題。如果有，也是與其它章節(jié)內(nèi)容相結(jié)合。棧和隊列：棧和隊列：基礎(chǔ)章節(jié)，容易出基本概念題，必考內(nèi)容之一。而棧常與其它章節(jié)配合考

3、查，也常與遞歸表達式的求值等概念相聯(lián)系進行考查。串：串：基礎(chǔ)章節(jié)，概念較為簡單。專門針對于此章的大型算法設(shè)計題很少，較常見的是根據(jù)KMP進行算法分析。多維數(shù)組及廣義表：多維數(shù)組及廣義表：基礎(chǔ)章節(jié)，基于數(shù)組的算法題也是常見的，分數(shù)比例波動較大，是出題的“可選單元”或“侯補單元”。一般如果要出題，多數(shù)不會作為大題出。數(shù)組常與“查找，排序”等章節(jié)結(jié)合來作為大題考查。樹和二叉樹：樹和二叉樹：重點難點章節(jié)，各校必考章節(jié)。各校在此章出題的不同之處在

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

5、一章類似，本章同屬于重點難點章節(jié)，且概念更多，聯(lián)系更為緊密，概念之間更容易混淆。在基本概念的考查中，尤愛考各種排序算法的優(yōu)劣比較此類的題。算法設(shè)計大題中，如果作為出題，那么常與數(shù)組結(jié)合來考查。二、數(shù)據(jù)結(jié)構(gòu)各章節(jié)重點勾劃二、數(shù)據(jù)結(jié)構(gòu)各章節(jié)重點勾劃第0章概述章概述本章主要起到總領(lǐng)作用，為讀者進行數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)進行了一些先期鋪墊。大家主要注意以下幾點：數(shù)據(jù)結(jié)構(gòu)的基本概念，時間和空間復(fù)雜度的概念及度量方法，算法設(shè)計時的注意事項。本章考點不多，只

6、要稍加注意理解即可。第一章第一章線性表線性表作為線性結(jié)構(gòu)的開篇章節(jié)，線性表一章在線性結(jié)構(gòu)的學(xué)習(xí)乃至整個數(shù)據(jù)結(jié)構(gòu)學(xué)科的學(xué)習(xí)中，其作用都是不可低估的。在這一章，第一次系統(tǒng)性地引入鏈?zhǔn)酱鎯Φ母拍?，鏈?zhǔn)酱鎯Ω拍顚⑹钦麄€數(shù)據(jù)結(jié)構(gòu)學(xué)科的重中之重，無論哪一章都涉及到了這個概念。總體來說，線性表一章可供考查的重要考點有以下幾個方面：1.線性表的相關(guān)基本概念，如：前驅(qū)、后繼、表長、空表、首元結(jié)點，頭結(jié)點，頭指針等概念。2.線性表的結(jié)構(gòu)特點，主要是指：除第

7、一及最后一個元素外，每個結(jié)點都只有一個前趨和只有一個后繼。清華嚴蔚敏數(shù)據(jù)結(jié)構(gòu)C語言版復(fù)習(xí)歸納3點可能與大學(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ù)，然后

8、要求你求出該數(shù)組中的某個元素所在的位置。2.明確按行存儲和按列存儲的區(qū)別和聯(lián)系，并能夠按照這兩種不同的存儲方式求解1中類型的題。3.將特殊矩陣中的元素按相應(yīng)的換算方式存入數(shù)組中。這些矩陣包括：對稱矩陣，三角矩陣，具有某種特點的稀疏矩陣等。熟悉稀疏矩陣的三種不同存儲方式：三元組，帶輔助行向量的二元組，十字鏈表存儲。掌握將稀疏矩陣的三元組或二元組向十字鏈表進行轉(zhuǎn)換的算法。4.廣義表的概念，特別應(yīng)該明確表頭與表尾的定義。這一點，是理解整個廣義

9、表一節(jié)算法的基礎(chǔ)。近來，在一些學(xué)校中，出現(xiàn)了這樣一種題目類型：給出對某個廣義表L若干個求了若干次的取頭和取尾操作后的串值，要求求出原廣義表L。大家要留意。5.與廣義表有關(guān)的遞歸算法。由于廣義表的定義就是遞歸的，所以，與廣義表有關(guān)的算法也常是遞歸形式的。比如：求表深度，復(fù)制廣義表等。這種題目，可以根據(jù)不同角度廣義表的表現(xiàn)形式運用兩種不同的方式解答：一是把一個廣義表看作是表頭和表尾兩部分，分別對表頭和表尾進行操作；二是把一個廣義表看作是若干

10、個子表，分別對每個子表進行操作。第五章第五章樹與二叉樹樹與二叉樹從對線性結(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)二叉樹的其它算法，線索二叉樹

11、的概念和線索化算法以及線索化后的查找算法，最優(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=n21的性質(zhì)，n個結(jié)

12、點的完全二叉樹的深度，順序存儲二叉樹時孩子結(jié)點與父結(jié)點之間的換算關(guān)系（左為：2i，右為：2i1）。二叉樹的順序存儲和二叉鏈表存儲的各自優(yōu)缺點及適用場合，二叉樹的三叉鏈表表示方法。2.二叉樹的三種遍歷算法二叉樹的三種遍歷算法這一知識點掌握的好壞，將直接關(guān)系到樹一章的算法能否理解，進而關(guān)系到樹一章的算法設(shè)計題能否順利完成。二叉樹的遍歷算法有三種：先序，中序和后序。其劃分的依據(jù)是視其每個算法中對根結(jié)點數(shù)據(jù)的訪問順序而定。不僅要熟練掌握三種遍歷