如何備考數(shù)據(jù)結(jié)構(gòu)

如何備考數(shù)據(jù)結(jié)構(gòu)？一、考試大綱概況

二、復(fù)習(xí)重點(diǎn)難點(diǎn)

三、復(fù)習(xí)規(guī)劃建議

一、考試大綱概況

二、復(fù)習(xí)重點(diǎn)難點(diǎn)

三、復(fù)習(xí)規(guī)劃建議

大綱要求：

考生比較系統(tǒng)地掌握專業(yè)基礎(chǔ)課程的基本概念、基本原理和基本方法，能夠綜合運(yùn)用所學(xué)的基本原理和基本方法分析、判斷和解決有關(guān)理論問題和實(shí)際問題。統(tǒng)考：數(shù)據(jù)結(jié)構(gòu)45分自主命題：絕大多數(shù)院校的考核科目數(shù)據(jù)結(jié)構(gòu)課程考查目標(biāo)：1.掌握數(shù)據(jù)結(jié)構(gòu)的基本概念、基本原理和基本方法。2.掌握數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及基本操作的實(shí)現(xiàn)，能夠?qū)λ惴ㄟM(jìn)行基本的時(shí)間復(fù)雜度與空間復(fù)雜度的分析。3.能夠數(shù)據(jù)結(jié)構(gòu)基本原理和方法進(jìn)行問題的分析與求解，具備采用C或C++或JAVA語言設(shè)計(jì)與實(shí)現(xiàn)算法的能力。

一、考試大綱概況

二、復(fù)習(xí)重點(diǎn)難點(diǎn)

三、復(fù)習(xí)規(guī)劃建議

復(fù)習(xí)要點(diǎn)1.數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)知識(shí)。2.從數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和數(shù)據(jù)的運(yùn)算三個(gè)方面去掌握線性表、棧、隊(duì)列、數(shù)組、樹和二叉樹、圖等常用的數(shù)據(jù)結(jié)構(gòu)。3.掌握在各種常用的數(shù)據(jù)結(jié)構(gòu)上實(shí)現(xiàn)查找和排序運(yùn)算，從基本思想、具體算法描述、性能等方面掌握不同的查找、內(nèi)部排序方法，還需注意不同查找方法和不同排序方法之間的比較。具體章節(jié)：

(1)緒論

(2)線性表

(3)棧、隊(duì)列和數(shù)組

(4)樹與二叉樹

(5)圖

(6)查找

(7)排序第1章緒論對(duì)后續(xù)章節(jié)的學(xué)習(xí)非常重要，其中時(shí)間復(fù)雜度和空間復(fù)雜度的分析是考查的重點(diǎn)，并可以結(jié)合后續(xù)內(nèi)容進(jìn)行考查。本章?？键c(diǎn)：算法的性能分析，主要包括時(shí)間復(fù)雜度和空間復(fù)雜度的分析，是數(shù)據(jù)結(jié)構(gòu)課程教學(xué)的基本要求，常以選擇題的形式單獨(dú)出現(xiàn)，另外在算法設(shè)計(jì)題中也會(huì)涉及到。應(yīng)試技巧與方法：對(duì)于算法的時(shí)間復(fù)雜度分析的考核，需要考生注意兩點(diǎn)：第一，需要理解并記住教材中經(jīng)典算法的時(shí)間復(fù)雜度；第二，會(huì)分析簡(jiǎn)單算法的時(shí)間復(fù)雜度。第2章線性表

對(duì)于線性結(jié)構(gòu)乃至整個(gè)數(shù)據(jù)結(jié)構(gòu)課程的學(xué)習(xí)都是非常重要的，是進(jìn)行算法設(shè)計(jì)的基礎(chǔ)。本章重點(diǎn)是順序表和鏈表上實(shí)現(xiàn)的各種基本算法及相關(guān)的時(shí)間和空間性能分析，難點(diǎn)是能夠使用本章所學(xué)到的基本知識(shí)設(shè)計(jì)有效算法解決與線性表相關(guān)的應(yīng)用問題。（一）線性表的定義和基本操作（二）線性表的實(shí)現(xiàn)1.順序存儲(chǔ)結(jié)構(gòu)(1)線性表的順序存儲(chǔ)結(jié)構(gòu)，靠元素存儲(chǔ)的先后位置反映出數(shù)據(jù)元素的邏輯關(guān)系。(2)用一維數(shù)組表示，給定下標(biāo)，可以存取相應(yīng)元素，屬于隨機(jī)存取結(jié)構(gòu)。(3)線性表的順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)插入、刪除、定位等運(yùn)算的算法。2.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)(1)線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，靠指針來反映數(shù)據(jù)元素的邏輯關(guān)系。(2)鏈表的存取需要從頭指針開始，順鏈而行，不屬于隨機(jī)存取結(jié)構(gòu)，而是順序存取結(jié)構(gòu)。(3)幾種常用鏈表的特點(diǎn)和相關(guān)算法設(shè)計(jì)，即單鏈表、單循環(huán)鏈表、雙向鏈表、雙向循環(huán)鏈表的生成、檢索、插入、刪除、遍歷、逆置、分解、歸并等操作。(4)從時(shí)間復(fù)雜度和空間復(fù)雜度的角度綜合比較線性表在順序和鏈?zhǔn)絻煞N存儲(chǔ)結(jié)構(gòu)下的特點(diǎn)及其各自適用的場(chǎng)合。3.線性表的應(yīng)用運(yùn)用順序表和鏈表的特點(diǎn)解決復(fù)雜的應(yīng)用問題。本章常考點(diǎn)：順序表、鏈表應(yīng)用的綜合應(yīng)用題，主要是以算法設(shè)計(jì)題的形式出現(xiàn)。應(yīng)試方法與技巧：算法設(shè)計(jì)題是很多考生的軟肋，對(duì)這個(gè)題目如何備考？建議：1、需要熟練掌握順序表、鏈表的基本操作的實(shí)現(xiàn)；2、考生應(yīng)該清楚“復(fù)雜的操作都是由一種或幾種基本操作的組合來實(shí)現(xiàn)的”，因此對(duì)于這些復(fù)雜的操作首先要分析它是由哪些基本操作實(shí)現(xiàn)的；3、考試時(shí)，如果不具備拿全部分值的能力，就要考慮如何盡可能拿到較多的部分分值，也就是說，題目中“時(shí)間和空間上盡可能高效的算法”這一點(diǎn)要求，考生若不能寫出最優(yōu)的算法或是花費(fèi)時(shí)間過長(zhǎng)而影響后面題目的作答時(shí)間，那么次優(yōu)的或者較笨的算法能寫出來也會(huì)拿到部分分值；4、當(dāng)然需要考生平時(shí)也多積累算法設(shè)計(jì)的經(jīng)驗(yàn)。本章對(duì)于整個(gè)數(shù)據(jù)結(jié)構(gòu)課程的學(xué)習(xí)都非常重要，是進(jìn)行算法設(shè)計(jì)的基礎(chǔ)。第3章棧、隊(duì)列和數(shù)組棧和隊(duì)列是受限運(yùn)算的線性表，數(shù)組是數(shù)據(jù)元素為線性表的線性表。本章是考研的重點(diǎn)之一。本章的重點(diǎn)是掌握棧和隊(duì)列在兩種存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)的基本運(yùn)算、多維數(shù)組的存儲(chǔ)方式、矩陣的壓縮存儲(chǔ)方式。（一）棧和隊(duì)列的基本概念棧、隊(duì)列的定義及其相關(guān)數(shù)據(jù)結(jié)構(gòu)的概念，棧與隊(duì)列存取數(shù)據(jù)的特點(diǎn)。（二）棧和隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)1.順序棧的進(jìn)棧和退棧的算法，判斷?？?、棧滿的條件。2.順序隊(duì)列的入隊(duì)和出隊(duì)的算法，特別是循環(huán)隊(duì)列的入隊(duì)和出隊(duì)算法以及判斷隊(duì)空、隊(duì)滿的條件。（三）棧和隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

1.鏈棧上的進(jìn)棧和退棧的算法，注意因棧在一端操作，故通常鏈棧不設(shè)頭結(jié)點(diǎn)。2.鏈隊(duì)列的入隊(duì)和出隊(duì)的算法，注意對(duì)僅剩一個(gè)元素的鏈隊(duì)列刪除元素時(shí)的處理。（四）棧和隊(duì)列的應(yīng)用

1.在程序設(shè)計(jì)中，常需要棧這樣的數(shù)據(jù)結(jié)構(gòu)，使得與保存數(shù)據(jù)時(shí)相反順序來使用這些數(shù)據(jù)。2.在后續(xù)章節(jié)中多處有棧和隊(duì)列的應(yīng)用。（五）特殊矩陣的壓縮存儲(chǔ)

1.數(shù)組（主要是二維）在以行序?yàn)橹骱土行驗(yàn)橹鞯拇鎯?chǔ)中的地址計(jì)算方法。2.特殊矩陣（對(duì)稱矩陣、對(duì)角矩陣、三角矩陣）在壓縮存儲(chǔ)時(shí)的下標(biāo)變換公式。本章常考點(diǎn)：棧和隊(duì)列的定義、基本操作及應(yīng)用，主要是以選擇題的形式出現(xiàn)。其中某些應(yīng)用題雖然涉及到了特殊矩陣的壓縮存儲(chǔ)問題，但重點(diǎn)不在此，而是其他。應(yīng)試方法與技巧：棧的先進(jìn)后出和隊(duì)列的先進(jìn)先出的操作特性，幾乎每年必考，題目比較靈活。第4章樹和二叉樹主要內(nèi)容有二叉樹的定義、性質(zhì)、存儲(chǔ)結(jié)構(gòu)、遍歷、線索化，樹的定義、存儲(chǔ)結(jié)構(gòu)、遍歷、樹和森林與二叉樹的轉(zhuǎn)換，哈夫曼樹及哈夫曼編碼等。本章重點(diǎn)是二叉樹的遍歷算法及其有關(guān)應(yīng)用，難點(diǎn)是使用有關(guān)知識(shí)設(shè)計(jì)出有效算法解決與樹或二叉樹相關(guān)的應(yīng)用問題。（一）樹的概念

（二）二叉樹

1.二叉樹的定義及其主要特征

（1）理解二叉樹與普通雙分支樹的區(qū)別；（2）滿二叉樹和完全二叉樹的概念；（3）二叉樹的五個(gè)性質(zhì)及其證明方法，以及這些性質(zhì)的推廣。2.二叉樹的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

3.二叉樹的遍歷

（1）二叉樹的先序，中序和后序遍歷算法以及按層次遍歷。（2）遍歷是基礎(chǔ)，在三種基本遍歷算法的基礎(chǔ)上實(shí)現(xiàn)二叉樹的其它算法。4.線索二叉樹的基本概念和構(gòu)造

（三）樹、森林

1.樹的存儲(chǔ)結(jié)構(gòu)2.森林與二叉樹的轉(zhuǎn)換

3.樹和森林的遍歷

（四）樹的應(yīng)用

1.二叉排序樹

二叉排序樹的定義及建立、查找、插入、刪除等算法。2.平衡二叉樹

平衡二叉樹的定義及平衡二叉樹的四種調(diào)整方式。3.哈夫曼（Huffman）樹和哈夫曼編碼

本章?？键c(diǎn)：二叉樹的性質(zhì)及推廣、二叉樹的遍歷、線索二叉樹、森林和二叉樹的轉(zhuǎn)換、二叉排序樹、平衡二叉樹、哈夫曼樹和哈夫曼編碼。應(yīng)試方法與技巧：樹和二叉樹的相關(guān)知識(shí)比較零散，又都很重要。雖然已有的統(tǒng)考題中本章全部以選擇題的考核形式出現(xiàn)，但是本章完全可以出綜合題，例如：二叉樹遍歷的應(yīng)用以算法設(shè)計(jì)題的形式出現(xiàn)，哈夫曼樹和哈夫曼編碼也可以以算法應(yīng)用題的大題形式考核，希望廣大考生對(duì)于本章內(nèi)容要充分重視。第5章圖圖形結(jié)構(gòu)是最具有普遍性的數(shù)據(jù)結(jié)構(gòu)，樹形結(jié)構(gòu)可以看成是圖形結(jié)構(gòu)的特例，而線性結(jié)構(gòu)可以看成是樹形結(jié)構(gòu)的特例，因此圖形結(jié)構(gòu)的算法設(shè)計(jì)難度最大。本章重點(diǎn)是在圖的兩種存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)的遍歷算法。本章難點(diǎn)是圖的應(yīng)用算法：最小生成樹、拓?fù)渑判?、關(guān)鍵路徑、最短路徑，要求掌握這些算法的基本思想及時(shí)間空間性能。（一）圖的概念

圖的定義和特點(diǎn)、無向圖、有向圖、入度、出度、完全圖、生成樹、路徑、路徑長(zhǎng)度、回路、（強(qiáng)）連通圖、（強(qiáng)）連通分量等概念。（二）圖的存儲(chǔ)及基本操作

1.鄰接矩陣法

2.鄰接表法

（三）圖的遍歷

1.深度優(yōu)先搜索

2.廣度優(yōu)先搜索

（四）圖的基本應(yīng)用及其復(fù)雜度分析

1.最?。ù鷥r(jià)）生成樹

2.最短路徑

3.拓?fù)渑判?/p>

4.關(guān)鍵路徑

本章?？键c(diǎn)：圖的概念及相關(guān)術(shù)語的理解、圖的存儲(chǔ)及遍歷、以及基本上每年都考的圖的4個(gè)基本應(yīng)用（最小生成樹、最短路徑、拓?fù)渑判?、關(guān)鍵路徑）。應(yīng)試方法與技巧：圖的基本概念和性質(zhì)主要是以選擇題的形式考核，對(duì)于圖的這4個(gè)應(yīng)用，要求掌握算法（Prim算法、Kruskal算法、Dijsktra算法、Floyd算法、拓?fù)渑判蛩惴ê完P(guān)鍵路徑算法）的基本思想，一般不要求寫出具體算法，但是需要能用這些算法思想來求解具體題目，因此，這些算法要深刻理解。第6章查找查找指的是按關(guān)鍵字查找，它與數(shù)據(jù)組織方式和關(guān)鍵字順序有關(guān)。數(shù)據(jù)組織方式有線性表、樹表和散列表，關(guān)鍵字順序存在有序和無序之分。本章重點(diǎn)掌握順序查找、二分查找以及散列表上查找的基本思想和算法實(shí)現(xiàn)。（一）查找的基本概念

（二）順序查找法

采用順序查找方法，逐個(gè)比較，設(shè)置監(jiān)視哨使查找效率大大提高。（三）折半查找法

對(duì)于有序順序表采用折半查找法，其判定樹是唯一的。注意該方法的適用條件以及其遞歸實(shí)現(xiàn)方法。（四）B樹及其基本操作、B+樹的基本概念B-樹是多路平衡外查找樹，用于文件系統(tǒng)。B+樹是應(yīng)文件系統(tǒng)所需而產(chǎn)生的一種B樹的變形樹。（五）散列表

散列函數(shù)的設(shè)計(jì)、處理沖突的方法、散列表的查找及分析。（六）查找算法的分析及應(yīng)用本章常考點(diǎn)：折半查找法及性能分析、B樹的定義及其基本操作、散列表的查找及性能分析。應(yīng)試方法與技巧：順序查找法比較簡(jiǎn)單，折半查找比較重要，需掌握折半查找的適用條件、折半查找算法和查找過程、判定樹的構(gòu)造、查找長(zhǎng)度分析等。B樹和B+樹是本章難點(diǎn)，一般不要求掌握算法，對(duì)于B樹要求能夠執(zhí)行插入、刪除和查找操作，對(duì)于B+樹，僅需了解基本概念和性質(zhì)即可。散列查找也比較重要，容易出綜合題。第7章排序排序指的是按關(guān)鍵字有序排列數(shù)據(jù)表中的記錄，和查找一章不同，這里關(guān)鍵字可以重復(fù)出現(xiàn)。為了簡(jiǎn)單，設(shè)定排序的數(shù)據(jù)采用線性表方式進(jìn)行組織，并且遞增排序。本章重點(diǎn)是快速排序、堆排序、歸并排序和基數(shù)排序的基本思想及排序過程，難點(diǎn)是這四個(gè)排序算法的實(shí)現(xiàn)。

另外統(tǒng)考的同學(xué)注意外部排序。（一）排序的基本概念

（二）插入排序

1.直接插入排序

2.折半插入排序

（三）起泡排序

（四）簡(jiǎn)單選擇排序

（五）希爾排序

（六）快速排序

（七）堆排序

（八）二路歸并排序

（九）基數(shù)排序（十）外部排序（十一）

各種內(nèi)部排序算法的比較各種排序方法的算法思想、排序過程、算法實(shí)現(xiàn)以及性能分析（包括時(shí)間復(fù)雜度、空間復(fù)雜度、穩(wěn)定性）。（十二）排序算法的應(yīng)用本章?？键c(diǎn)：各種排序的算法思想、排序過程、性能分析及各種排序方法的綜合比較。應(yīng)試方法與技巧：本章最常見的出題方式是給定一個(gè)數(shù)據(jù)序列，要求選出其所用的排序方法；或給定一個(gè)數(shù)據(jù)序列，求用某種排序方法一次排序后所得序列。因此，對(duì)于每一種排序需要從以下四個(gè)方面掌握：（1）理解算法的基本思想；（2）該排序算法的手工排序過程；（3）算法描述；（4）算法性能：時(shí)間復(fù)雜度（最好、最壞、平均），空間復(fù)雜度，穩(wěn)定性。一、考試大綱概況

二、復(fù)習(xí)重點(diǎn)難點(diǎn)

三、復(fù)習(xí)規(guī)劃建議

第一階段：基礎(chǔ)復(fù)習(xí)階段(開始復(fù)習(xí)—7月)第二階段：強(qiáng)化提高階段(8月—11月初)第三階段：沖刺階段(11月－考前)第一階段：基礎(chǔ)復(fù)習(xí)階段(開始復(fù)習(xí)—7月)階段目標(biāo)：對(duì)指定參考書目通讀一遍，對(duì)考試情況有個(gè)基本的印象。細(xì)讀一遍參考書目，理解書中的每一個(gè)知識(shí)點(diǎn)。對(duì)各門課程有深入了解，弄清每本書的大綱，內(nèi)在邏輯結(jié)構(gòu)，重點(diǎn)章節(jié)所在等，但不要求記住。1．細(xì)讀一遍參考書，指的是對(duì)參考書每個(gè)知識(shí)點(diǎn)的徹底理解，要注意復(fù)習(xí)的全面性。2．本階段學(xué)習(xí)重在理解，不在強(qiáng)記。3．每本書每章節(jié)學(xué)完后要做到能閉上眼在腦海中列出一個(gè)知識(shí)點(diǎn)的提綱，這樣可以方便以后對(duì)需要記憶的內(nèi)容進(jìn)行復(fù)習(xí)。4．注意把握復(fù)習(xí)進(jìn)度，不要拖，有不懂的要盡快和同學(xué)老師交流，避免拖慢整個(gè)復(fù)習(xí)進(jìn)度。5．如果復(fù)習(xí)過程中有條件，可以有選擇地去聽學(xué)校開設(shè)的相關(guān)專業(yè)課程或翻看相關(guān)課件，加深印象。

第二階段：強(qiáng)化提高階段(8月—11月初)階段目標(biāo)：對(duì)指定參考書進(jìn)行深入復(fù)習(xí)，加強(qiáng)知識(shí)點(diǎn)的前后聯(lián)系，建立整體框架結(jié)構(gòu)。分清、整理、掌握重難點(diǎn)，完成參考書配有的習(xí)題訓(xùn)練。做歷年真題，弄清考試形式、題型設(shè)置和難易程度等內(nèi)容，整理真題答案。8月：要關(guān)注新出臺(tái)的本年度招生簡(jiǎn)章和專業(yè)目錄，與往年的情況進(jìn)行對(duì)比，新增考點(diǎn)往往是出題點(diǎn)，刪改了的考點(diǎn)可以在復(fù)習(xí)過程中節(jié)省復(fù)習(xí)時(shí)間。9-10月：研究生開始網(wǎng)上報(bào)名，謹(jǐn)慎填報(bào)志愿，牢記自己的報(bào)名信息。11月：研究生考試報(bào)名確認(rèn)工作開始，考生到指定的地點(diǎn)進(jìn)行現(xiàn)場(chǎng)確認(rèn)，繳費(fèi)并照相。（一）參考書深入復(fù)習(xí)計(jì)劃1.將參考書中的概念、原理要注意理解記憶，書中的例題要做會(huì)。2.完成相關(guān)的課后習(xí)題，要在紙面上按照考試要求一步步寫出解答過程，加深解題思路的印象，提升解題速度。3．把書上可能考到的名詞解釋、問答、論述等文字性的題目都整理在筆記本上。4．將全書的重點(diǎn)歸納成一系列的知識(shí)點(diǎn)，一定要有系統(tǒng)性。這樣做的好處是加深印象，并且對(duì)知識(shí)有更加系統(tǒng)的理解。5.通過相關(guān)習(xí)題分析，總結(jié)知識(shí)點(diǎn)的出題方向，特別是對(duì)于大題，應(yīng)融會(huì)貫通，舉一反三。（二）歷年真題學(xué)習(xí)計(jì)劃做歷年真題，整理真題答案。試做真題，弄清每一道題屬于書中的哪一章、哪個(gè)知識(shí)點(diǎn)。通過做真題要了解考試形式、考試重點(diǎn)、題型設(shè)置和難易程度等內(nèi)容，揣摩出題人思路。整理所有真題的答案。真題答案一定要完整。整理過程中，每道真題，尤其是比較復(fù)雜的計(jì)算/分析題目要多做幾遍。第三階段：沖刺階段(11月－考前)階段目標(biāo)：總結(jié)所有重點(diǎn)知識(shí)點(diǎn)，包括重點(diǎn)概念、理論和模型等，查漏補(bǔ)缺，回歸教材。溫習(xí)專業(yè)課筆記和歷年真題，分析真題的