第一部分 數(shù)據(jù)結(jié)構(gòu)
【復(fù)習(xí)方法】
09年的統(tǒng)考大綱對(duì)數(shù)據(jù)結(jié)構(gòu)的考查目標(biāo)定位為理解數(shù)據(jù)結(jié)構(gòu)的基本概念，掌握數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及其差異，以及各種基本操作的實(shí)現(xiàn);掌握基本的數(shù)據(jù)處理原理和方法的基礎(chǔ)上，能夠?qū)λ惴ㄟM(jìn)行設(shè)計(jì)與分析;能夠選擇合適的數(shù)據(jù)結(jié)構(gòu)和方法進(jìn)行問(wèn)題求解。這個(gè)考查目標(biāo)跟以往各個(gè)學(xué)校的考研大綱的考查目標(biāo)并沒(méi)有什么實(shí)質(zhì)性的區(qū)別，這說(shuō)明數(shù)據(jù)結(jié)構(gòu)科目考查的指導(dǎo)思想并沒(méi)有發(fā)生變化，同學(xué)們可以在不影響已有復(fù)習(xí)成果的基礎(chǔ)上繼續(xù)進(jìn)行復(fù)習(xí)計(jì)劃，只是在數(shù)據(jù)結(jié)構(gòu)的考點(diǎn)有了些調(diào)整。
從考試大綱來(lái)看，所要求的知識(shí)在一般的大學(xué)數(shù)據(jù)結(jié)構(gòu)教材中都已經(jīng)包含，所以，選擇哪本書(shū)并不是最重要的事情。建議對(duì)于數(shù)據(jù)結(jié)構(gòu)的復(fù)習(xí)，可以選擇清華大學(xué)出版社的《數(shù)據(jù)結(jié)構(gòu)(第二版)》(嚴(yán)蔚敏主編)。這本書(shū)有多種語(yǔ)言的版本，建議選擇C語(yǔ)言的版本，在復(fù)習(xí)的過(guò)程中，還可以配以相應(yīng)的習(xí)題集進(jìn)行練習(xí)，來(lái)加深對(duì)知識(shí)點(diǎn)的理解。
對(duì)于數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)，難在其中的算法及實(shí)現(xiàn)。有條件的考生，可以在計(jì)算機(jī)上編寫(xiě)程序，自己實(shí)現(xiàn)教材上的算法(要注意，書(shū)上的算法通常都采用偽代碼編寫(xiě)，需要我們自己用某種程序設(shè)計(jì)語(yǔ)言去具體實(shí)現(xiàn))。數(shù)據(jù)結(jié)構(gòu)的核心就是算法，首先必須理解經(jīng)典算法，然后才能創(chuàng)造性的發(fā)明簡(jiǎn)單的算法解決遇到的問(wèn)題。所以不管是上機(jī)實(shí)現(xiàn)，還是在紙上寫(xiě)出來(lái)，都一定要注意規(guī)范性和程序的一些基本規(guī)范，這個(gè)對(duì)于應(yīng)試是非常重要的。
【考綱考查目標(biāo)】
1.理解數(shù)據(jù)結(jié)構(gòu)的基本概念;掌握數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及其差異，以及各種基本操作的實(shí)現(xiàn)?？荚嚧?。
2.掌握基本的數(shù)據(jù)處理原理和方法的基礎(chǔ)上，能夠?qū)λ惴ㄟM(jìn)行設(shè)計(jì)與分析。
3.能夠選擇合適的數(shù)據(jù)結(jié)構(gòu)和方法進(jìn)行問(wèn)題求解。
一、線性表
(一)線性表的定義和基本操作
(二)線性表的實(shí)現(xiàn)
1.順序存儲(chǔ)結(jié)構(gòu)
2.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)
3.線性表的應(yīng)用
二、棧、隊(duì)列和數(shù)組
(一)棧和隊(duì)列的基本概念
(二)棧和隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)
(三)棧和隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)
(四)棧和隊(duì)列的應(yīng)用
(五)特殊矩陣的壓縮存儲(chǔ)
三、樹(shù)與二叉樹(shù)
(一)樹(shù)的概念
(二)二叉樹(shù)
1.二叉樹(shù)的定義及其主要特征
2.二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)
3.二叉樹(shù)的遍歷
4.線索二叉樹(shù)的基本概念和構(gòu)造
5.二叉排序樹(shù)
6.平衡二叉樹(shù)
(三)樹(shù)、森林
1.書(shū)的存儲(chǔ)結(jié)構(gòu)
2.森林與二叉樹(shù)的轉(zhuǎn)換
3.樹(shù)和森林的遍歷
(四)樹(shù)的應(yīng)用
1.等價(jià)類問(wèn)題
2.哈夫曼(Huffman)樹(shù)和哈夫曼編碼
四、 圖
(一)圖的概念
(二)圖的存儲(chǔ)及基本操作
1. 鄰接矩陣法
2. 鄰接表法
(三)圖的遍歷
1. 深度優(yōu)先搜索
2. 廣度優(yōu)先搜索
(四)圖的基本應(yīng)用及其復(fù)雜度分析
1. 最小(代價(jià))生成樹(shù)
2. 最短路徑
3. 拓?fù)渑判?BR> 4. 關(guān)鍵路徑
五、查找
(一)查找的基本概念
(二)順序查找法
(三)折半查找法
(四)B-樹(shù)
(五)散列(Hash)表及其查找
(六)查找算法的分析及應(yīng)用
六、內(nèi)部排序
(一)排序的基本概念
(二)插入排序
1. 直接插入排序
2. 折半插入排序
(三)氣泡排序(bubble sort)
(四)簡(jiǎn)單選擇排序
(五)希爾排序(shell sort)
(六)快速排序
(七)堆排序
(八)二路歸并排序(merge sort)
(九)基數(shù)排序
(十)各種內(nèi)部排序算法的比較
(十一)內(nèi)部排序算法的應(yīng)用
【復(fù)習(xí)方法】
09年的統(tǒng)考大綱對(duì)數(shù)據(jù)結(jié)構(gòu)的考查目標(biāo)定位為理解數(shù)據(jù)結(jié)構(gòu)的基本概念，掌握數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及其差異，以及各種基本操作的實(shí)現(xiàn);掌握基本的數(shù)據(jù)處理原理和方法的基礎(chǔ)上，能夠?qū)λ惴ㄟM(jìn)行設(shè)計(jì)與分析;能夠選擇合適的數(shù)據(jù)結(jié)構(gòu)和方法進(jìn)行問(wèn)題求解。這個(gè)考查目標(biāo)跟以往各個(gè)學(xué)校的考研大綱的考查目標(biāo)并沒(méi)有什么實(shí)質(zhì)性的區(qū)別，這說(shuō)明數(shù)據(jù)結(jié)構(gòu)科目考查的指導(dǎo)思想并沒(méi)有發(fā)生變化，同學(xué)們可以在不影響已有復(fù)習(xí)成果的基礎(chǔ)上繼續(xù)進(jìn)行復(fù)習(xí)計(jì)劃，只是在數(shù)據(jù)結(jié)構(gòu)的考點(diǎn)有了些調(diào)整。
從考試大綱來(lái)看，所要求的知識(shí)在一般的大學(xué)數(shù)據(jù)結(jié)構(gòu)教材中都已經(jīng)包含，所以，選擇哪本書(shū)并不是最重要的事情。建議對(duì)于數(shù)據(jù)結(jié)構(gòu)的復(fù)習(xí)，可以選擇清華大學(xué)出版社的《數(shù)據(jù)結(jié)構(gòu)(第二版)》(嚴(yán)蔚敏主編)。這本書(shū)有多種語(yǔ)言的版本，建議選擇C語(yǔ)言的版本，在復(fù)習(xí)的過(guò)程中，還可以配以相應(yīng)的習(xí)題集進(jìn)行練習(xí)，來(lái)加深對(duì)知識(shí)點(diǎn)的理解。
對(duì)于數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)，難在其中的算法及實(shí)現(xiàn)。有條件的考生，可以在計(jì)算機(jī)上編寫(xiě)程序，自己實(shí)現(xiàn)教材上的算法(要注意，書(shū)上的算法通常都采用偽代碼編寫(xiě)，需要我們自己用某種程序設(shè)計(jì)語(yǔ)言去具體實(shí)現(xiàn))。數(shù)據(jù)結(jié)構(gòu)的核心就是算法，首先必須理解經(jīng)典算法，然后才能創(chuàng)造性的發(fā)明簡(jiǎn)單的算法解決遇到的問(wèn)題。所以不管是上機(jī)實(shí)現(xiàn)，還是在紙上寫(xiě)出來(lái)，都一定要注意規(guī)范性和程序的一些基本規(guī)范，這個(gè)對(duì)于應(yīng)試是非常重要的。
【考綱考查目標(biāo)】
1.理解數(shù)據(jù)結(jié)構(gòu)的基本概念;掌握數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及其差異，以及各種基本操作的實(shí)現(xiàn)?？荚嚧?。
2.掌握基本的數(shù)據(jù)處理原理和方法的基礎(chǔ)上，能夠?qū)λ惴ㄟM(jìn)行設(shè)計(jì)與分析。
3.能夠選擇合適的數(shù)據(jù)結(jié)構(gòu)和方法進(jìn)行問(wèn)題求解。
一、線性表
(一)線性表的定義和基本操作
(二)線性表的實(shí)現(xiàn)
1.順序存儲(chǔ)結(jié)構(gòu)
2.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)
3.線性表的應(yīng)用
二、棧、隊(duì)列和數(shù)組
(一)棧和隊(duì)列的基本概念
(二)棧和隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)
(三)棧和隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)
(四)棧和隊(duì)列的應(yīng)用
(五)特殊矩陣的壓縮存儲(chǔ)
三、樹(shù)與二叉樹(shù)
(一)樹(shù)的概念
(二)二叉樹(shù)
1.二叉樹(shù)的定義及其主要特征
2.二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)
3.二叉樹(shù)的遍歷
4.線索二叉樹(shù)的基本概念和構(gòu)造
5.二叉排序樹(shù)
6.平衡二叉樹(shù)
(三)樹(shù)、森林
1.書(shū)的存儲(chǔ)結(jié)構(gòu)
2.森林與二叉樹(shù)的轉(zhuǎn)換
3.樹(shù)和森林的遍歷
(四)樹(shù)的應(yīng)用
1.等價(jià)類問(wèn)題
2.哈夫曼(Huffman)樹(shù)和哈夫曼編碼
四、 圖
(一)圖的概念
(二)圖的存儲(chǔ)及基本操作
1. 鄰接矩陣法
2. 鄰接表法
(三)圖的遍歷
1. 深度優(yōu)先搜索
2. 廣度優(yōu)先搜索
(四)圖的基本應(yīng)用及其復(fù)雜度分析
1. 最小(代價(jià))生成樹(shù)
2. 最短路徑
3. 拓?fù)渑判?BR> 4. 關(guān)鍵路徑
五、查找
(一)查找的基本概念
(二)順序查找法
(三)折半查找法
(四)B-樹(shù)
(五)散列(Hash)表及其查找
(六)查找算法的分析及應(yīng)用
六、內(nèi)部排序
(一)排序的基本概念
(二)插入排序
1. 直接插入排序
2. 折半插入排序
(三)氣泡排序(bubble sort)
(四)簡(jiǎn)單選擇排序
(五)希爾排序(shell sort)
(六)快速排序
(七)堆排序
(八)二路歸并排序(merge sort)
(九)基數(shù)排序
(十)各種內(nèi)部排序算法的比較
(十一)內(nèi)部排序算法的應(yīng)用