2015考研計(jì)算機(jī)復(fù)習(xí)：數(shù)據(jù)結(jié)構(gòu)重點(diǎn)歸納_跨考網(wǎng)

　? 計(jì)算機(jī)專業(yè)數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)重點(diǎn)歸納(適于清華嚴(yán)版教材)

　　一、數(shù)據(jù)結(jié)構(gòu)的章節(jié)結(jié)構(gòu)及重點(diǎn)構(gòu)成

　　數(shù)據(jù)結(jié)構(gòu)學(xué)科的章節(jié)劃分基本上為：概論，線性表，棧和隊(duì)列，串，多維數(shù)組和廣義表，樹(shù)和二叉樹(shù)，圖，查找，內(nèi)排，外排，文件，動(dòng)態(tài)存儲(chǔ)分配。

　　對(duì)于絕大多數(shù)的學(xué)校而言， 外排，文件，動(dòng)態(tài)存儲(chǔ)分配 三章基本上是不考的，在大多數(shù)高校的計(jì)算機(jī)本科教學(xué)過(guò)程中，這三章也是基本上不作講授的。所以，大家在這三章上可以不必花費(fèi)過(guò)多的精力，只要知道基本的概念即可。但是，對(duì)于報(bào)考名校特別是該校又有在試卷中對(duì)這三章進(jìn)行過(guò)考核的歷史，那么這部分朋友就要留意這三章了。

　　按照以上我們給出的章節(jié)以及對(duì)后三章的介紹，數(shù)據(jù)結(jié)構(gòu)的章節(jié)比重大致為：

　　概論：內(nèi)容很少，概念簡(jiǎn)單，分?jǐn)?shù)大多只有幾分，有的學(xué)校甚至不考。

　　線性表：基礎(chǔ)章節(jié)，必考內(nèi)容之一?？碱}多數(shù)為基本概念題，名?？碱}中，鮮有大型算法設(shè)計(jì)題。如果有，也是與其它章節(jié)內(nèi)容相結(jié)合。

　　棧和隊(duì)列：基礎(chǔ)章節(jié)，容易出基本概念題，必考內(nèi)容之一。而棧常與其它章節(jié)配合考查，也常與遞歸等概念相聯(lián)系進(jìn)行考查。

　　串 ：基礎(chǔ)章節(jié)，概念較為簡(jiǎn)單。專門針對(duì)于此章的大型算法設(shè)計(jì)題很少，較常見(jiàn)的是根據(jù)KMP進(jìn)行算法分析。

　　多維數(shù)組及廣義表 ：基礎(chǔ)章節(jié)，基于數(shù)組的算法題也是常見(jiàn)的，分?jǐn)?shù)比例波動(dòng)較大，是出題的 可選單元 或 侯補(bǔ)單元 。一般如果要出題，多數(shù)不會(huì)作為大題出。數(shù)組常與 查找，排序 等章節(jié)結(jié)合來(lái)作為大題考查。

　　樹(shù)和二叉樹(shù) ：重點(diǎn)難點(diǎn)章節(jié)，各校必考章節(jié)。各校在此章出題的不同之處在于，是否在本章中出一到兩道大的算法設(shè)計(jì)題。通過(guò)對(duì)多所學(xué)校的試卷分析，絕大多數(shù)學(xué)校在本章都曾有過(guò)出大型算法設(shè)計(jì)題的歷史。

　　圖 ：重點(diǎn)難點(diǎn)章節(jié)，名校尤愛(ài)考。如果作為重點(diǎn)來(lái)考，則多出現(xiàn)于分析與設(shè)計(jì)題型當(dāng)中，可與樹(shù)一章共同構(gòu)成算法設(shè)計(jì)大題的題型設(shè)計(jì)。

　　查找 ：重點(diǎn)難點(diǎn)章節(jié)，概念較多，聯(lián)系較為緊密，容易混淆。出題時(shí)可以作為分析型題目給出，在基本概念型題目中也較為常見(jiàn)。算法設(shè)計(jì)型題中可以數(shù)組結(jié)合來(lái)考查，也可以與樹(shù)一章結(jié)合來(lái)考查。

　　排序 ：與查找一章類似，本章同屬于重點(diǎn)難點(diǎn)章節(jié)，且概念更多，聯(lián)系更為緊密，概念之間更容易混淆。在基本概念的考查中，尤愛(ài)考各種排序算法的優(yōu)劣比較此類的題。算法設(shè)計(jì)大題中，如果作為出題，那么常與數(shù)組結(jié)合來(lái)考查。

　　二、數(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)的開(kāi)篇章節(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é)科的重中之重，無(wú)論哪一章都涉及到了這個(gè)概念。

　　總體來(lái)說(shuō)，線性表一章可供考查的重要考點(diǎn)有以下幾個(gè)方面：

　　1.線性表的相關(guān)基本概念，如：前驅(qū)、后繼、表長(zhǎng)、空表、首元結(jié)點(diǎn)，頭結(jié)點(diǎn)，頭指針等概念。

　　2.線性表的結(jié)構(gòu)特點(diǎn)，主要是指：除第一及最后一個(gè)元素外，每個(gè)結(jié)點(diǎn)都只有一個(gè)前趨和只有一個(gè)后繼。

　　3.線性表的順序存儲(chǔ)方式及其在具體語(yǔ)言環(huán)境下的兩種不同實(shí)現(xiàn)：表空間的靜態(tài)分配和動(dòng)態(tài)分配。靜態(tài)鏈表與順序表的相似及不同之處。

　　4.線性表的鏈?zhǔn)酱鎯?chǔ)方式及以下幾種常用鏈表的特點(diǎn)和運(yùn)算：?jiǎn)捂湵?、循環(huán)鏈表，雙向鏈表，雙向循環(huán)鏈表。其中，單鏈表的歸并算法、循環(huán)鏈表的歸并算法、雙向鏈表及雙向循環(huán)鏈表的插入和刪除算法等都是較為常見(jiàn)的考查方式。此外，近年來(lái)在不少學(xué)校中還多次出現(xiàn)要求用遞歸算法實(shí)現(xiàn)單鏈表輸出(可能是順序也可能是倒序)的問(wèn)題。

　　在鏈表的小題型中，經(jīng)常考到一些諸如：判表空的題。在不同的鏈表中，其判表空的方式是不一樣的，請(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é)遇到第一只攔路虎，很多人從這一章開(kāi)始坐暈車，一直暈到現(xiàn)在。所以，理解棧與隊(duì)列，是走向DS高手的一條必由之路，。

　　學(xué)習(xí)此章前，你可以問(wèn)一下自己是不是已經(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)系，以及借助棧將遞歸轉(zhuǎn)向于非遞歸的經(jīng)典算法：n!階乘問(wèn)題，fib數(shù)列問(wèn)題，hanoi問(wèn)題，背包問(wèn)題，二叉樹(shù)的遞歸和非遞歸遍歷問(wèn)題，圖的深度遍歷與棧的關(guān)系等。其中，涉及到樹(shù)與圖的問(wèn)題，多半會(huì)在樹(shù)與圖的相關(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ì)列一章可以不看書(shū)了。注意，我說(shuō)的是可以不看書(shū)，并不是可以不作題哦。

　　第三章　串

　　經(jīng)歷了棧一章的痛苦煎熬后，終于迎來(lái)了串一章的柳暗花明。

　　串，在概念上是比較少的一個(gè)章節(jié)，也是最容易自學(xué)的章節(jié)之一，但正如每個(gè)過(guò)來(lái)人所了解的，KMP算法是這一章的重要關(guān)隘，突破此關(guān)隘后，走過(guò)去又是一馬平川的大好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)之外。其中，理解算法是核心，會(huì)求數(shù)組是得分點(diǎn)。不用我多說(shuō)，這一節(jié)內(nèi)容是本章的重中之重?？赡苓M(jìn)行的考查方式是：求next和nextval數(shù)組值，根據(jù)求得的next或nextval數(shù)組值給出運(yùn)用KMP算法進(jìn)行匹配的匹配過(guò)程。

　　第四章　數(shù)組與廣義表

　　學(xué)過(guò)程序語(yǔ)言的朋友，數(shù)組的概念我們已經(jīng)不是第一次見(jiàn)到了，應(yīng)該已經(jīng) 一回生，二回熟 了，所以，在概念上，不會(huì)存在太大障礙。但作為考研課程來(lái)說(shuō)，本章的考查重點(diǎn)可能與大學(xué)里的程序語(yǔ)言所關(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ù)組中。這些矩陣包括：對(duì)稱矩陣，三角矩陣，具有某種特點(diǎn)的稀疏矩陣等。熟悉稀疏矩陣的三種不同存儲(chǔ)方式：三元組，帶輔助行向量的二元組，十字鏈表存儲(chǔ)。掌握將稀疏矩陣的三元組或二元組向十字鏈表進(jìn)行轉(zhuǎn)換的算法。

　　4.廣義表的概念，特別應(yīng)該明確表頭與表尾的定義。這一點(diǎn)，是理解整個(gè)廣義表一節(jié)算法的基礎(chǔ)。近來(lái)，在一些學(xué)校中，出現(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)行操作。

　　第五章　樹(shù)與二叉樹(shù)

　　從對(duì)線性結(jié)構(gòu)的研究過(guò)度到對(duì)樹(shù)形結(jié)構(gòu)的研究，是數(shù)據(jù)結(jié)構(gòu)課程學(xué)習(xí)的一次躍變，此次躍變完成的好壞，將直接關(guān)系到你到實(shí)際的考試中是否可以拿到高分，而這所有的一切，將最終影響你的專業(yè)課總分。所以，樹(shù)這一章的重要性，已經(jīng)不說(shuō)自明了。

　　總體來(lái)說(shuō)，樹(shù)一章的知識(shí)點(diǎn)包括：

　　二叉樹(shù)的概念、性質(zhì)和存儲(chǔ)結(jié)構(gòu)，二叉樹(shù)遍歷的三種算法(遞歸與非遞歸)，在三種基本遍歷算法的基礎(chǔ)上實(shí)現(xiàn)二叉樹(shù)的其它算法，線索二叉樹(shù)的概念和線索化算法以及線索化后的查找算法，最優(yōu)二叉樹(shù)的概念、構(gòu)成和應(yīng)用，樹(shù)的概念和存儲(chǔ)形式，樹(shù)與森林的遍歷算法及其與二叉樹(shù)遍歷算法的聯(lián)系，樹(shù)與森林和二叉樹(shù)的轉(zhuǎn)換。

　　更多2015復(fù)習(xí)攻略>>

　　歷年考研英語(yǔ)真題下載