|
友情提示：本站提供全國400多所高等院校招收碩士、博士研究生入學考試歷年考研真題、考博真題、答案，部分學校更新至2012年，2013年；均提供收費下載。 下載流程： 考研真題 點擊“考研試卷””下載; 考博真題 點擊“考博試卷庫” 下載
830 數據結構考研大綱
【考查目標】
1.理解數據結構的基本概念；掌握數據的邏輯結構、存儲結構及其差異，以及各種基本操作
的實現。
2.掌握基本的數據處理原理和方法的基礎上，能夠對算法進行設計與分析。
3.能夠選擇合適的數據結構和方法進行問題求解。
一、線性表
（一）線性表的定義和基本操作
（二）線性表的實現
1.順序存儲結構
2.鏈式存儲結構
3.線性表的應用
二、棧、隊列和數組
（一）棧和隊列的基本概念
（二）棧和隊列的順序存儲結構
（三）棧和隊列的鏈式存儲結構
（四）棧和隊列的應用
（五）特殊矩陣的壓縮存儲
三、樹與二叉樹
（一）樹的概念
（二）二叉樹
1.二叉樹的定義及其主要特征
2.二叉樹的順序存儲結構和鏈式存儲結構
3.二叉樹的遍歷
4.線索二叉樹的基本概念和構造
5.二叉排序樹
6.平衡二叉樹
（三）樹、森林
1.書的存儲結構
2.森林與二叉樹的轉換
3.樹和森林的遍歷
（四）樹的應用
1.等價類問題
2.哈夫曼（Huffman）樹和哈夫曼編碼
四、 圖
（一） 圖的概念
（二） 圖的存儲及基本操作
1. 鄰接矩陣法
2. 鄰接表法
（三） 圖的遍歷
1. 深度優先搜索
2. 廣度優先搜索
（四） 圖的基本應用及其復雜度分析
1. 最?。ù鷥r）生成樹
2. 最短路徑
3. 拓撲排序
4. 關鍵路徑
五、 查找
（一） 查找的基本概念
（二） 順序查找法
（三） 折半查找法
（四） B-樹
（五） 散列（Hash）表及其查找
（六） 查找算法的分析及應用
六、 內部排序
（一） 排序的基本概念
（二） 插入排序
1. 直接插入排序
2. 折半插入排序
（三） 氣泡排序（bubble sort）
（四） 簡單選擇排序
（五） 希爾排序（shell sort）
（六） 快速排序
（七） 堆排序
（八） 二路歸并排序（merge sort）
（九） 基數排序
（十） 各種內部排序算法的比較
（十一） 內部排序算法的應用
【知識點解析】
1.線性表
線性表是一種最簡單的數據結構，在線性表方面，主要考查線性表的定義和基本操作、線
性表的實現。在線性表實現方面，要掌握的是線性表的存儲結構，包括順序存儲結構和鏈式
存儲結構，特別是鏈式存儲結構，是考查的重點。另外，還要掌握線性表的基本應用。
2.棧、隊列和數組
棧和隊列是兩種特殊的線性表，在這方面，要求我們掌握棧和隊列的基本概念，以及他們
之間的區別。對于棧和隊列的存儲結構(包括順序存儲結構、鏈式存儲結構)要有較深的理解，
對于棧和隊列的應用，例如，排隊問題、子程序調用問題、表達式問題等，要搞清楚。
一維數組屬于線性表范疇，但多維數組不屬于線性表。在這方面，主要掌握數組的存儲結
構，例如按行優先、按列優先等，某個元素存在的地址是什么。對于特殊矩陣(二維數組)
的壓縮存儲原理也要搞清楚。
3、樹與二叉樹
二叉樹和樹是兩種不同的概念，這一點是必須要搞清楚的。在這個部分，我們要掌握樹的
定義、二叉樹的定義及主要特征(特殊的二叉樹、二叉樹的性質)。在二叉樹的順序存儲結構
和鏈式存儲結構方面，特別是鏈式存儲結構，因為很多應用都是建立在鏈式存儲基礎上，例
如，二叉樹的遍歷(前序遍歷、中序遍歷、后序遍歷)就是一種典型的應用。
在特殊的二叉樹中，完全二叉樹的概念是必須要搞清楚的，其次，線索二叉樹的基本概念
和構造、二叉排序樹、平衡二叉樹的基本概念和應用，特別是二叉排序樹的基本性質和特點
要能很好地理解。
多棵獨立的樹就組成了森林，樹的存儲結構和遍歷、森林的遍歷、樹和二叉樹的轉換、森
林和二叉樹的轉換等知識，也要有了了解。
最后就是樹的應用，通常會作為綜合應用類試題出現，包括等價類問題、哈夫曼(Huffman)
樹和哈夫曼編碼等。
4、圖
在數據結構中，圖的結構是最復雜的，這里的概念也是最多的。我們要掌握圖的基本概念
(有向圖、無向圖、連通、路徑、子圖、出度、入度、生成樹、最短路徑、關鍵路徑等)。
圖的存儲及基本操作主要有鄰接矩陣法和鄰接表法，我們要掌握這有向圖和無向圖的這 2
種存儲方法，要清楚圖的連通和存儲方法之間的關系。例如，一個頂點的出度和臨界矩陣中
1 的個數有什么關系，等等。
圖的遍歷方法有深度優先搜索和廣度優先搜索，我們要掌握這 2 種遍歷方法的算法實現。
給出一個具體的圖，要能知道它的遍歷次序。
在數據結構課程中，圖的基本應用是最多的，也是最復雜的，我們要掌握這些應用的復雜
度分析。要掌握的具體應用主要包括最小(代價)生成樹、最短路徑、拓撲排序、關鍵路徑。
在給出的一個具體的圖中，我們要會利用已知條件，求出上述應用的結果。
5、查找
在給定的數據集合中查找某個關鍵值就是查找，查找的基本方法主要有順序查找法、折半
查找法、B-樹、散列(Hash)表及其查找?？嫉谋容^多的是折半查找和散列表，我們要掌握它
們的基本概念和方法，例如散列表的碰撞如何解決，裝載因子的概念等。
另外，我們要掌握各種查找算法的分析及應用，最好能把各種查找在查找成功、查找失敗
的情況下的最好、平均、最壞的平均查找次數的計算方法搞清楚。
6、內部排序
根據考試大綱，只考查內部排序。所謂內部排序，就是在內存中進行排序。在這一部分中，
主要要掌握直接插入排序、折半插入排序、冒泡排序(bubble sort)、簡單選擇排序、希爾
排序(shell sort)、快速排序、堆排序、二路歸并排序(merge sort)、基數排序的基本概念
和方法。搞清楚這些排序方法的流程，以及它們之間的區別。
在這個知識點，一個很重要的考查點就是各種內部排序算法的比較，一般的書上都會有這
樣的一個表格，列出了所有排序在各種情況下(最好、最壞、平均)的時間復雜度和空間復雜
度，這個表是需要我們記下來的。當然，如果我們能掌握復雜度的計算方法，自己能推算出
來，那就更好了。
最后，就是要掌握內部排序算法的基本應用，以及算法的實現。
【復習方法】
1、教材的選擇
從考試大綱來看，所要求的知識在一般的大學數據結構教材中都已經包含，所以，選擇哪
本書并不是最重要的事情。不過，根據希賽教育推薦，對于數據結構的復習，可以選擇清華
大學出版社的《數據結構(第二版)》(嚴蔚敏主編)。這本書有多種語言的版本，建議選擇 C
語言的版本，在復習的過程中，還可以配以相應的習題集。
2、學習方法
對于數據結構的學習，難在其中的算法及實現。有條件的考生，可以在計算機上編寫程序，
自己實現教材上的算法(要注意，書上的算法通常都采用偽代碼編寫，需要我們自己用某種
程序設計語言去具體實現)。如果沒有條件，那就只有在心里進行推導了，可以使用實際的
例子，手工“實現”算法。
免責聲明：本文系轉載自網絡，如有侵犯，請聯系我們立即刪除，另：本文僅代表作者個人觀點，與本網站無關。其原創性以及文中陳述文字和內容未經本站證實，對本文以及其中全部或者部分內容、文字的真實性、完整性、及時性本站不作任何保證或承諾，請讀者僅作參考，并請自行核實相關內容。
|
文章搜索
您現在的位置： 
