09計算機考研專業課考試知識點分析：數據結構

編者按：2009年是計算機專業考研專業基礎課首次實行全國統考，面對今年的改變，想報考計算機專業的考生可能對復習的準備有很多的疑問。為了幫助考生正確的做好準備工作，學賽網研究生院特訪問了我國著名的計算機教育專家、湖南師范大學計算機軟件與理論/計算機應用技術碩士點專業課試題命題人張友生博士，請張博士對考試大綱進行全面的解析。本文為大綱解析的第二篇：數據結構知識點分析。
訪問本系列文章第一篇：2009年計算機專業考研專業課大綱解析
在計算機考研專業基礎課統考科目中，一共考查數據結構、操作系統、計算機組成原理、計算機網絡四門課程，滿分為150分，其中數據結構占45分。
一、考查目標
(1)理解數據結構的基本概念，掌握數據的邏輯結構、存儲結構及其差異，以及各種基本操作的實現。
(2)掌握基本的數據處理原理和方法的基礎上，能夠對算法進行設計與分析。
(3)能夠選擇合適的數據結構和方法進行問題求解。
二、知識點解析
1.線性表
線性表是一種最簡單的數據結構，在線性表方面，主要考查線性表的定義和基本操作、線性表的實現。在線性表實現方面，要掌握的是線性表的存儲結構，包括順序存儲結構和鏈式存儲結構，特別是鏈式存儲結構，是考查的重點。另外，還要掌握線性表的基本應用。
2.棧、隊列和數組
棧和隊列是兩種特殊的線性表，在這方面，要求我們掌握棧和隊列的基本概念，以及他們之間的區別。對于棧和隊列的存儲結構(包括順序存儲結構、鏈式存儲結構)要有較深的理解，對于棧和隊列的應用，例如，排隊問題、子程序調用問題、表達式問題等，要搞清楚。
一維數組屬于線性表范疇，但多維數組不屬于線性表。在這方面，主要掌握數組的存儲結構，例如按行優先、按列優先等，某個元素存在的地址是什么。對于特殊矩陣(二維數組)的壓縮存儲原理也要搞清楚。
3、樹與二叉樹
二叉樹和樹是兩種不同的概念，這一點是必須要搞清楚的。在這個部分，我們要掌握樹的定義、二叉樹的定義及主要特征(特殊的二叉樹、二叉樹的性質)。在二叉樹的順序存儲結構和鏈式存儲結構方面，特別是鏈式存儲結構，因為很多應用都是建立在鏈式存儲基礎上，例如，二叉樹的遍歷(前序遍歷、中序遍歷、后序遍歷)就是一種典型的應用。
在特殊的二叉樹中，完全二叉樹的概念是必須要搞清楚的，其次，線索二叉樹的基本概念和構造、二叉排序樹、平衡二叉樹的基本概念和應用，特別是二叉排序樹的基本性質和特點要能很好地理解。
多棵獨立的樹就組成了森林，樹的存儲結構和遍歷、森林的遍歷、樹和二叉樹的轉換、森林和二叉樹的轉換等知識，也要有了了解。
最后就是樹的應用，通常會作為綜合應用類試題出現，包括等價類問題、哈夫曼(Huffman)樹和哈夫曼編碼等。
4、圖
在數據結構中，圖的結構是最復雜的，這里的概念也是最多的。我們要掌握圖的基本概念(有向圖、無向圖、連通、路徑、子圖、出度、入度、生成樹、最短路徑、關鍵路徑等)。
圖的存儲及基本操作主要有鄰接矩陣法和鄰接表法，我們要掌握這有向圖和無向圖的這2種存儲方法，要清楚圖的連通和存儲方法之間的關系。例如，一個頂點的出度和臨界矩陣中1的個數有什么關系，等等。
圖的遍歷方法有深度優先搜索和廣度優先搜索，我們要掌握這2種遍歷方法的算法實現。給出一個具體的圖，要能知道它的遍歷次序。
在數據結構課程中，圖的基本應用是最多的，也是最復雜的，我們要掌握這些應用的復雜度分析。要掌握的具體應用主要包括最小(代價)生成樹、最短路徑、拓撲排序、關鍵路徑。在給出的一個具體的圖中，我們要會利用已知條件，求出上述應用的結果。
5、查找
在給定的數據集合中查找某個關鍵值就是查找，查找的基本方法主要有順序查找法、折半查找法、B-樹、散列(Hash)表及其查找?？嫉谋容^多的是折半查找和散列表，我們要掌握它們的基本概念和方法，例如散列表的碰撞如何解決，裝載因子的概念等。
　　另外，我們要掌握各種查找算法的分析及應用，最好能把各種查找在查找成功、查找失敗的情況下的最好、平均、最壞的平均查找次數的計算方法搞清楚。

原文轉自：http://www.kjueaiud.com