計算機考研專業(yè)課知識點分析：數(shù)據(jù)結構_跨考網(wǎng)

????? 在計算機考研專業(yè)基礎課統(tǒng)考科目中，一共考查數(shù)據(jù)結構、操作系統(tǒng)、計算機組成原理、計算機網(wǎng)絡四門課程，滿分為150分，其中數(shù)據(jù)結構占45分。

????? 一、考查目標

????? (1)理解數(shù)據(jù)結構的基本概念，掌握數(shù)據(jù)的邏輯結構、存儲結構及其差異，以及各種基本操作的實現(xiàn)。

????? (2)掌握基本的數(shù)據(jù)處理原理和方法的基礎上，能夠對算法進行設計與分析。

??????(3)能夠選擇合適的數(shù)據(jù)結構和方法進行問題求解。

?????? 二、知識點解析

??????? 1.線性表

??????? 線性表是一種最簡單的數(shù)據(jù)結構，在線性表方面，主要考查線性表的定義和基本操作、線性表的實現(xiàn)。在線性表實現(xiàn)方面，要掌握的是線性表的存儲結構，包括順序存儲結構和鏈式存儲結構，特別是鏈式存儲結構，是考查的重點。另外，還要掌握線性表的基本應用。

???????? 2.棧、隊列和數(shù)組

??????? 棧和隊列是兩種特殊的線性表，在這方面，要求我們掌握棧和隊列的基本概念，以及他們之間的區(qū)別。對于棧和隊列的存儲結構(包括順序存儲結構、鏈式存儲結構)要有較深的理解，對于棧和隊列的應用，例如，排隊問題、子程序調用問題、表達式問題等，要搞清楚。

??????? 一維數(shù)組屬于線性表范疇，但多維數(shù)組不屬于線性表。在這方面，主要掌握數(shù)組的存儲結構，例如按行優(yōu)先、按列優(yōu)先等，某個元素存在的地址是什么。對于特殊矩陣(二維數(shù)組)的壓縮存儲原理也要搞清楚。

??????? 3、樹與二叉樹

??????? 二叉樹和樹是兩種不同的概念，這一點是必須要搞清楚的。在這個部分，我們要掌握樹的定義、二叉樹的定義及主要特征(特殊的二叉樹、二叉樹的性質)。在二叉樹的順序存儲結構和鏈式存儲結構方面，特別是鏈式存儲結構，因為很多應用都是建立在鏈式存儲基礎上，例如，二叉樹的遍歷(前序遍歷、中序遍歷、后序遍歷)就是一種典型的應用。

??????? 在特殊的二叉樹中，完全二叉樹的概念是必須要搞清楚的，其次，線索二叉樹的基本概念和構造、二叉排序樹、平衡二叉樹的基本概念和應用，特別是二叉排序樹的基本性質和特點要能很好地理解。

??????? 多棵獨立的樹就組成了森林，樹的存儲結構和遍歷、森林的遍歷、樹和二叉樹的轉換、森林和二叉樹的轉換等知識，也要有了了解。

??????? 最后就是樹的應用，通常會作為綜合應用類試題出現(xiàn)，包括等價類問題、哈夫曼(Huffman)樹和哈夫曼編碼等。

???????? 4、圖

??????? 在數(shù)據(jù)結構中，圖的結構是最復雜的，這里的概念也是最多的。我們要掌握圖的基本概念(有向圖、無向圖、連通、路徑、子圖、出度、入度、生成樹、最短路徑、關鍵路徑等)。

??????? 圖的存儲及基本操作主要有鄰接矩陣法和鄰接表法，我們要掌握這有向圖和無向圖的這2種存儲方法，要清楚圖的連通和存儲方法之間的關系。例如，一個頂點的出度和臨界矩陣中1的個數(shù)有什么關系，等等。

??????? 圖的遍歷方法有深度優(yōu)先搜索和廣度優(yōu)先搜索，我們要掌握這2種遍歷方法的算法實現(xiàn)。給出一個具體的圖，要能知道它的遍歷次序。

??????? 在數(shù)據(jù)結構課程中，圖的基本應用是最多的，也是最復雜的，我們要掌握這些應用的復雜度分析。要掌握的具體應用主要包括最小(代價)生成樹、最短路徑、拓撲排序、關鍵路徑。在給出的一個具體的圖中，我們要會利用已知條件，求出上述應用的結果。

???????? 5、查找

??????? 在給定的數(shù)據(jù)集合中查找某個關鍵值就是查找，查找的基本方法主要有順序查找法、折半查找法、B-樹、散列(Hash)表及其查找?？嫉谋容^多的是折半查找和散列表，我們要掌握它們的基本概念和方法，例如散列表的碰撞如何解決，裝載因子的概念等。

　　另外，我們要掌握各種查找算法的分析及應用，最好能把各種查找在查找成功、查找失敗的情況下的最好、平均、最壞的平均查找次數(shù)的計算方法搞清楚。

???????? 6、內部排序

???????? 根據(jù)考試大綱，只考查內部排序。所謂內部排序，就是在內存中進行排序。在這一部分中，主要要掌握直接插入排序、折半插入排序、冒泡排序(bubble sort)、簡單選擇排序、希爾排序(shell sort)、快速排序、堆排序、二路歸并排序(merge sort)、基數(shù)排序的基本概念和方法。搞清楚這些排序方法的流程，以及它們之間的區(qū)別。

??????? 在這個知識點，一個很重要的考查點就是各種內部排序算法的比較，一般的書上都會有這樣的一個表格，列出了所有排序在各種情況下(最好、最壞、平均)的時間復雜度和空間復雜度，這個表是需要我們記下來的。當然，如果我們能掌握復雜度的計算方法，自己能推算出來，那就更好了。

??????? 最后，就是要掌握內部排序算法的基本應用，以及算法的實現(xiàn)。

???????? 三、復習方法

????????? 1、教材的選擇

??????? 從考試大綱來看，所要求的知識在一般的大學數(shù)據(jù)結構教材中都已經(jīng)包含，所以，選擇哪本書并不是最重要的事情。不過，根據(jù)希賽教育推薦，對于數(shù)據(jù)結構的復習，可以選擇清華大學出版社的《數(shù)據(jù)結構(第二版)》(嚴蔚敏主編)。這本書有多種語言的版本，建議選擇C語言的版本，在復習的過程中，還可以配以相應的習題集。

???????? 2、學習方法

??????? 對于數(shù)據(jù)結構的學習，難在其中的算法及實現(xiàn)。有條件的考生，可以在計算機上編寫程序，自己實現(xiàn)教材上的算法(要注意，書上的算法通常都采用偽代碼編寫，需要我們自己用某種程序設計語言去具體實現(xiàn))。如果沒有條件，那就只有在心里進行推導了，可以使用實際的例子，手工“實現(xiàn)”算法。

??????? 3、在線測試

??????? 因為研究生考試基本上是靠我們自己學習，那么學習完之后，如何知道學習的效果呢?這就需要多參加測試，特別是在線測試會對我們有很大的幫助。計算機考研專業(yè)課中有80分的單項選擇題，這是與軟考的考法一致的，從考試大綱來看，所考查的知識點比軟考要窄一些，要求也低一些。因此，在沒有看到真實試題之前，建議考生拿軟考上午試題作為模擬測試。

??????? 從理想狀況來講，能夠靠自己的努力，就能學習好數(shù)據(jù)結構課程，就能考好計算機專業(yè)研究生入學考試的專業(yè)基礎綜合課程，那是再好不過的了。但是，現(xiàn)實是殘酷的，特別是一些邊遠地區(qū)的考生，學校師資條件比較差，靠自己學習有一定難度。因此，大家就想到，找個地方培訓下。目前，進行研究生培訓的基本上都是面授，老師講幾十節(jié)課，分到數(shù)據(jù)結構學科，也就是十來節(jié)課。十來節(jié)課就能讓你學好數(shù)據(jù)結構?即使是神仙，都做不到!所以，我們還得靠自己學習。

??????? 不過，有一種方法，倒是值得推薦的，那就是在線輔導，考生根據(jù)老師指定的學習計劃進行學習，在學習的過程中，遇到什么問題，可隨時向老師提問，老師實時解答。所以，這是一個長期的學習的過程。而且，在線輔導還提供很多模擬試題，這些模擬試題是老師根據(jù)考試大綱來命題的，符合考試要求，對考生進行考前練習，起到十分關鍵的作用。目前，只有希賽教育才提供這種在線輔導服務，希賽教育具有多年的在線教育經(jīng)驗，在IT教育方面具有較高的權威性。