2021河南工業(yè)大學數(shù)據(jù)結(jié)構(gòu)專業(yè)研究生考試大綱 正文

【考查目標】
1.理解數(shù)據(jù)結(jié)構(gòu)的基本概念；掌握數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及其差異，以及各種基本操作的實現(xiàn)。
2.掌握基本的數(shù)據(jù)處理原理和方法的基礎(chǔ)上，能夠?qū)λ惴ㄟM行設(shè)計與分析。
3.能夠選擇合適的數(shù)據(jù)結(jié)構(gòu)和方法進行問題求解。

一、線性表
（一）線性表的定義和基本操作
（二）線性表的實現(xiàn)
1.順序存儲結(jié)構(gòu)
2.鏈式存儲結(jié)構(gòu)
3.線性表的應(yīng)用

二、棧、隊列和數(shù)組
（一）棧和隊列的基本概念
（二）棧和隊列的順序存儲結(jié)構(gòu)
（三）棧和隊列的鏈式存儲結(jié)構(gòu)
（四）棧和隊列的應(yīng)用
（五）特殊矩陣的壓縮存儲

三、樹與二叉樹
（一）樹的概念
（二）二叉樹
1.二叉樹的定義及其主要特征
2.二叉樹的順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)
3.二叉樹的遍歷
4.線索二叉樹的基本概念和構(gòu)造
5.二叉排序樹
6.平衡二叉樹
（三）樹、森林
1.書的存儲結(jié)構(gòu)
2.森林與二叉樹的轉(zhuǎn)換
3.樹和森林的遍歷
（四）樹的應(yīng)用
1.等價類問題
2.哈夫曼（Huffman）樹和哈夫曼編碼

四、圖
（一）圖的概念
（二）圖的存儲及基本操作
1.鄰接矩陣法
2.鄰接表法
（三）圖的遍歷
1.深度優(yōu)先搜索
2.廣度優(yōu)先搜索
（四）圖的基本應(yīng)用及其復雜度分析
1.最小（代價）生成樹
2.最短路徑
3.拓撲排序
4.關(guān)鍵路徑

五、查找
（一）查找的基本概念
（二）順序查找法
（三）折半查找法
（四）B-樹
（五）散列（Hash）表及其查找
（六）查找算法的分析及應(yīng)用

六、內(nèi)部排序
（一）排序的基本概念
（二）插入排序
1.直接插入排序
2.折半插入排序
（三）氣泡排序（bubble sort）
（四）簡單選擇排序
（五）希爾排序（shell sort）
（六）快速排序
（七）堆排序
（八）二路歸并排序（merge sort）
（九）基數(shù)排序
（十）各種內(nèi)部排序算法的比較
（十一）內(nèi)部排序算法的應(yīng)用
【知識點解析】
  1.線性表
  線性表是一種最簡單的數(shù)據(jù)結(jié)構(gòu)，在線性表方面，主要考查線性表的定義和基本操作、線性表的實現(xiàn)。在線性表實現(xiàn)方面，要掌握的是線性表的存儲結(jié)構(gòu)，包括順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)，特別是鏈式存儲結(jié)構(gòu)，是考查的重點。另外，還要掌握線性表的基本應(yīng)用。
  2.棧、隊列和數(shù)組
  棧和隊列是兩種特殊的線性表，在這方面，要求我們掌握棧和隊列的基本概念，以及他們之間的區(qū)別。對于棧和隊列的存儲結(jié)構(gòu)(包括順序存儲結(jié)構(gòu)、鏈式存儲結(jié)構(gòu))要有較深的理解，對于棧和隊列的應(yīng)用，例如，排隊問題、子程序調(diào)用問題、表達式問題等，要搞清楚。
  一維數(shù)組屬于線性表范疇，但多維數(shù)組不屬于線性表。在這方面，主要掌握數(shù)組的存儲結(jié)構(gòu)，例如按行優(yōu)先、按列優(yōu)先等，某個元素存在的地址是什么。對于特殊矩陣(二維數(shù)組)的壓縮存儲原理也要搞清楚。
  3、樹與二叉樹
  二叉樹和樹是兩種不同的概念，這一點是必須要搞清楚的。在這個部分，我們要掌握樹的定義、二叉樹的定義及主要特征(特殊的二叉樹、二叉樹的性質(zhì))。在二叉樹的順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)方面，特別是鏈式存儲結(jié)構(gòu)，因為很多應(yīng)用都是建立在鏈式存儲基礎(chǔ)上，例如，二叉樹的遍歷(前序遍歷、中序遍歷、后序遍歷)就是一種典型的應(yīng)用。
  在特殊的二叉樹中，完全二叉樹的概念是必須要搞清楚的，其次，線索二叉樹的基本概念和構(gòu)造、二叉排序樹、平衡二叉樹的基本概念和應(yīng)用，特別是二叉排序樹的基本性質(zhì)和特點要能很好地理解。
  多棵獨立的樹就組成了森林，樹的存儲結(jié)構(gòu)和遍歷、森林的遍歷、樹和二叉樹的轉(zhuǎn)換、森林和二叉樹的轉(zhuǎn)換等知識，也要有了了解。
  最后就是樹的應(yīng)用，通常會作為綜合應(yīng)用類試題出現(xiàn)，包括等價類問題、哈夫曼(Huffman)樹和哈夫曼編碼等。
  4、圖
  在數(shù)據(jù)結(jié)構(gòu)中，圖的結(jié)構(gòu)是最復雜的，這里的概念也是最多的。我們要掌握圖的基本概念(有向圖、無向圖、連通、路徑、子圖、出度、入度、生成樹、最短路徑、關(guān)鍵路徑等)。
  圖的存儲及基本操作主要有鄰接矩陣法和鄰接表法，我們要掌握這有向圖和無向圖的這2種存儲方法，要清楚圖的連通和存儲方法之間的關(guān)系。例如，一個頂點的出度和臨界矩陣中1的個數(shù)有什么關(guān)系，等等。
  圖的遍歷方法有深度優(yōu)先搜索和廣度優(yōu)先搜索，我們要掌握這2種遍歷方法的算法實現(xiàn)。給出一個具體的圖，要能知道它的遍歷次序。
  在數(shù)據(jù)結(jié)構(gòu)課程中，圖的基本應(yīng)用是最多的，也是最復雜的，我們要掌握這些應(yīng)用的復雜度分析。要掌握的具體應(yīng)用主要包括最小(代價)生成樹、最短路徑、拓撲排序、關(guān)鍵路徑。在給出的一個具體的圖中，我們要會利用已知條件，求出上述應(yīng)用的結(jié)果。
  5、查找
  在給定的數(shù)據(jù)集合中查找某個關(guān)鍵值就是查找，查找的基本方法主要有順序查找法、折半查找法、B-樹、散列(Hash)表及其查找。考的比較多的是折半查找和散列表，我們要掌握它們的基本概念和方法，例如散列表的碰撞如何解決，裝載因子的概念等。
  另外，我們要掌握各種查找算法的分析及應(yīng)用，最好能把各種查找在查找成功、查找失敗的情況下的最好、平均、最壞的平均查找次數(shù)的計算方法搞清楚。
  6、內(nèi)部排序
  根據(jù)考試大綱，只考查內(nèi)部排序。所謂內(nèi)部排序，就是在內(nèi)存中進行排序。在這一部分中，主要要掌握直接插入排序、折半插入排序、冒泡排序(bubble sort)、簡單選擇排序、希爾排序(shell sort)、快速排序、堆排序、二路歸并排序(merge sort)、基數(shù)排序的基本概念和方法。搞清楚這些排序方法的流程，以及它們之間的區(qū)別。
  在這個知識點，一個很重要的考查點就是各種內(nèi)部排序算法的比較，一般的書上都會有這樣的一個表格，列出了所有排序在各種情況下(最好、最壞、平均)的時間復雜度和空間復雜度，這個表是需要我們記下來的。當然，如果我們能掌握復雜度的計算方法，自己能推算出來，那就更好了。
  最后，就是要掌握內(nèi)部排序算法的基本應(yīng)用，以及算法的實現(xiàn)。
  【復習方法】
  1、教材的選擇
  從考試大綱來看，所要求的知識在一般的大學數(shù)據(jù)結(jié)構(gòu)教材中都已經(jīng)包含，所以，選擇哪本書并不是最重要的事情。不過，根據(jù)希賽教育推薦，對于數(shù)據(jù)結(jié)構(gòu)的復習，可以選擇清華大學出版社的《數(shù)據(jù)結(jié)構(gòu)(第二版)》(嚴蔚敏主編)。這本書有多種語言的版本，建議選擇C語言的版本，在復習的過程中，還可以配以相應(yīng)的習題集。
  2、學習方法
  對于數(shù)據(jù)結(jié)構(gòu)的學習，難在其中的算法及實現(xiàn)。有條件的考生，可以在計算機上編寫程序，自己實現(xiàn)教材上的算法(要注意，書上的算法通常都采用偽代碼編寫，需要我們自己用某種程序設(shè)計語言去具體實現(xiàn))。如果沒有條件，那就只有在心里進行推導了，可以使用實際的例子，手工“實現(xiàn)”算法。

河南工業(yè)大學

本文來源：http://www.scstrans.com/henangongyedaxue/cankaoshumu_374765.html