2020河南工業(yè)大學(xué)碩士考試大綱之830.數(shù)據(jù)結(jié)構(gòu).大綱

1、830數(shù)據(jù)結(jié)構(gòu)考研大綱數(shù)據(jù)結(jié)構(gòu)考研大綱【考查目標(biāo)】【考查目標(biāo)】1.理解數(shù)據(jù)結(jié)構(gòu)的基本概念；掌握數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及其差異，以及各種基本操作的實(shí)現(xiàn)。2.掌握基本的數(shù)據(jù)處理原理和方法的基礎(chǔ)上，能夠?qū)λ惴ㄟM(jìn)行設(shè)計(jì)與分析。3.能夠選擇合適的數(shù)據(jù)結(jié)構(gòu)和方法進(jìn)行問題求解。一、線性表（一）線性表的定義和基本操作（二）線性表的實(shí)現(xiàn)1.順序存儲結(jié)構(gòu)2.鏈?zhǔn)酱鎯Y(jié)構(gòu)3.線性表的應(yīng)用二、棧、隊(duì)列和數(shù)組（一）棧和隊(duì)列的基本概念（二）棧和隊(duì)列的順序存儲結(jié)構(gòu)

2、（三）棧和隊(duì)列的鏈?zhǔn)酱鎯Y(jié)構(gòu)（四）棧和隊(duì)列的應(yīng)用（五）特殊矩陣的壓縮存儲三、樹與二叉樹（一）樹的概念（二）二叉樹1.二叉樹的定義及其主要特征2.二叉樹的順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)3.二叉樹的遍歷4.線索二叉樹的基本概念和構(gòu)造5.二叉排序樹6.平衡二叉樹（三）樹、森林1.書的存儲結(jié)構(gòu)2.森林與二叉樹的轉(zhuǎn)換3.樹和森林的遍歷（四）樹的應(yīng)用1.等價(jià)類問題2.哈夫曼（Huffman）樹和哈夫曼編碼四、圖（一）圖的概念（二）圖的存儲及基本操作1.

3、鄰接矩陣法2.鄰接表法（三）圖的遍歷1.深度優(yōu)先搜索2.廣度優(yōu)先搜索（四）圖的基本應(yīng)用及其復(fù)雜度分析1.最小（代價(jià)）生成樹2.最短路徑3.拓?fù)渑判蛟跀?shù)據(jù)結(jié)構(gòu)中，圖的結(jié)構(gòu)是最復(fù)雜的，這里的概念也是最多的。我們要掌握圖的基本概念(有向圖、無向圖、連通、路徑、子圖、出度、入度、生成樹、最短路徑、關(guān)鍵路徑等)。圖的存儲及基本操作主要有鄰接矩陣法和鄰接表法，我們要掌握這有向圖和無向圖的這2種存儲方法，要清楚圖的連通和存儲方法之間的關(guān)系。例如，一個

4、頂點(diǎn)的出度和臨界矩陣中1的個數(shù)有什么關(guān)系，等等。圖的遍歷方法有深度優(yōu)先搜索和廣度優(yōu)先搜索，我們要掌握這2種遍歷方法的算法實(shí)現(xiàn)。給出一個具體的圖，要能知道它的遍歷次序。在數(shù)據(jù)結(jié)構(gòu)課程中，圖的基本應(yīng)用是最多的，也是最復(fù)雜的，我們要掌握這些應(yīng)用的復(fù)雜度分析。要掌握的具體應(yīng)用主要包括最小(代價(jià))生成樹、最短路徑、拓?fù)渑判?、關(guān)鍵路徑。在給出的一個具體的圖中，我們要會利用已知條件，求出上述應(yīng)用的結(jié)果。5、查找在給定的數(shù)據(jù)集合中查找某個關(guān)鍵值就是查找

5、，查找的基本方法主要有順序查找法、折半查找法、B樹、散列(Hash)表及其查找。考的比較多的是折半查找和散列表，我們要掌握它們的基本概念和方法，例如散列表的碰撞如何解決，裝載因子的概念等。另外，我們要掌握各種查找算法的分析及應(yīng)用，最好能把各種查找在查找成功、查找失敗的情況下的最好、平均、最壞的平均查找次數(shù)的計(jì)算方法搞清楚。6、內(nèi)部排序根據(jù)考試大綱，只考查內(nèi)部排序。所謂內(nèi)部排序，就是在內(nèi)存中進(jìn)行排序。在這一部分中，主要要掌握直接插入排序、

6、折半插入排序、冒泡排序(bubblest)、簡單選擇排序、希爾排序(shellst)、快速排序、堆排序、二路歸并排序(mergest)、基數(shù)排序的基本概念和方法。搞清楚這些排序方法的流程，以及它們之間的區(qū)別。在這個知識點(diǎn)，一個很重要的考查點(diǎn)就是各種內(nèi)部排序算法的比較，一般的書上都會有這樣的一個表格，列出了所有排序在各種情況下(最好、最壞、平均)的時(shí)間復(fù)雜度和空間復(fù)雜度，這個表是需要我們記下來的。當(dāng)然，如果我們能掌握復(fù)雜度的計(jì)算方法，自己

7、能推算出來，那就更好了。最后，就是要掌握內(nèi)部排序算法的基本應(yīng)用，以及算法的實(shí)現(xiàn)?！緩?fù)習(xí)方法】【復(fù)習(xí)方法】1、教材的選擇從考試大綱來看，所要求的知識在一般的大學(xué)數(shù)據(jù)結(jié)構(gòu)教材中都已經(jīng)包含，所以，選擇哪本書并不是最重要的事情。不過，根據(jù)希賽教育推薦，對于數(shù)據(jù)結(jié)構(gòu)的復(fù)習(xí)，可以選擇清華大學(xué)出版社的《數(shù)據(jù)結(jié)構(gòu)(第二版)》(嚴(yán)蔚敏主編)。這本書有多種語言的版本，建議選擇C語言的版本，在復(fù)習(xí)的過程中，還可以配以相應(yīng)的習(xí)題集。2、學(xué)習(xí)方法對于數(shù)據(jù)結(jié)構(gòu)的學(xué)