在計(jì)算機(jī)考研專業(yè)基礎(chǔ)課統(tǒng)考科目中，一共考查數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)、計(jì)算機(jī)組成原理、計(jì)算機(jī)網(wǎng)絡(luò)四門課程，滿分為150分，其中數(shù)據(jù)結(jié)構(gòu)占45分。
一、考查目標(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)行問題求解。
二、知識點(diǎn)解析
1.線性表
線性表是一種簡單的數(shù)據(jù)結(jié)構(gòu)，在線性表方面，主要考查線性表的定義和基本操作、線性表的實(shí)現(xiàn)。在線性表實(shí)現(xiàn)方面，要掌握的是線性表的存儲結(jié)構(gòu)，包括順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)，特別是鏈?zhǔn)酱鎯Y(jié)構(gòu)，是考查的重點(diǎn)。另外，還要掌握線性表的基本應(yīng)用。
2.棧、隊(duì)列和數(shù)組
棧和隊(duì)列是兩種特殊的線性表，在這方面，要求我們掌握棧和隊(duì)列的基本概念，以及他們之間的區(qū)別。對于棧和隊(duì)列的存儲結(jié)構(gòu)(包括順序存儲結(jié)構(gòu)、鏈?zhǔn)酱鎯Y(jié)構(gòu))要有較深的理解，對于棧和隊(duì)列的應(yīng)用，例如，排隊(duì)問題、子程序調(diào)用問題、表達(dá)式問題等，要搞清楚。
一維數(shù)組屬于線性表范疇，但多維數(shù)組不屬于線性表。在這方面，主要掌握數(shù)組的存儲結(jié)構(gòu)，例如按行優(yōu)先、按列優(yōu)先等，某個(gè)元素存在的地址是什么。對于特殊矩陣(二維數(shù)組)的壓縮存儲原理也要搞清楚。
3、樹與二叉樹
二叉樹和樹是兩種不同的概念，這一點(diǎn)是必須要搞清楚的。在這個(gè)部分，我們要掌握樹的定義、二叉樹的定義及主要特征(特殊的二叉樹、二叉樹的性質(zhì))。在二叉樹的順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)方面，特別是鏈?zhǔn)酱鎯Y(jié)構(gòu)，因?yàn)楹芏鄳?yīng)用都是建立在鏈?zhǔn)酱鎯A(chǔ)上，例如，二叉樹的遍歷(前序遍歷、中序遍歷、后序遍歷)就是一種典型的應(yīng)用。
在特殊的二叉樹中，完全二叉樹的概念是必須要搞清楚的，其次，線索二叉樹的基本概念和構(gòu)造、二叉排序樹、平衡二叉樹的基本概念和應(yīng)用，特別是二叉排序樹的基本性質(zhì)和特點(diǎn)要能很好地理解。
多棵獨(dú)立的樹就組成了森林，樹的存儲結(jié)構(gòu)和遍歷、森林的遍歷、樹和二叉樹的轉(zhuǎn)換、森林和二叉樹的轉(zhuǎn)換等知識，也要有了了解。
后就是樹的應(yīng)用，通常會作為綜合應(yīng)用類試題出現(xiàn)，包括等價(jià)類問題、哈夫曼(Huffman)樹和哈夫曼編碼等。
4、圖
在數(shù)據(jù)結(jié)構(gòu)中，圖的結(jié)構(gòu)是復(fù)雜的，這里的概念也是多的。我們要掌握圖的基本概念(有向圖、無向圖、連通、路徑、子圖、出度、入度、生成樹、短路徑、關(guān)鍵路徑等)。
圖的存儲及基本操作主要有鄰接矩陣法和鄰接表法，我們要掌握這有向圖和無向圖的這2種存儲方法，要清楚圖的連通和存儲方法之間的關(guān)系。例如，一個(gè)頂點(diǎn)的出度和臨界矩陣中1的個(gè)數(shù)有什么關(guān)系，等等。
圖的遍歷方法有深度優(yōu)先搜索和廣度優(yōu)先搜索，我們要掌握這2種遍歷方法的算法實(shí)現(xiàn)。給出一個(gè)具體的圖，要能知道它的遍歷次序。
在數(shù)據(jù)結(jié)構(gòu)課程中，圖的基本應(yīng)用是多的，也是復(fù)雜的，我們要掌握這些應(yīng)用的復(fù)雜度分析。要掌握的具體應(yīng)用主要包括小(代價(jià))生成樹、短路徑、拓?fù)渑判颉㈥P(guān)鍵路徑。在給出的一個(gè)具體的圖中，我們要會利用已知條件，求出上述應(yīng)用的結(jié)果。
5、查找
在給定的數(shù)據(jù)集合中查找某個(gè)關(guān)鍵值就是查找，查找的基本方法主要有順序查找法、折半查找法、B-樹、散列(Hash)表及其查找?？嫉谋容^多的是折半查找和散列表，我們要掌握它們的基本概念和方法，例如散列表的碰撞如何解決，裝載因子的概念等。
另外，我們要掌握各種查找算法的分析及應(yīng)用，好能把各種查找在查找成功、查找失敗的情況下的好、平均、壞的平均查找次數(shù)的計(jì)算方法搞清楚。
6、內(nèi)部排序
根據(jù)考試大綱，只考查內(nèi)部排序。所謂內(nèi)部排序，就是在內(nèi)存中進(jìn)行排序。在這一部分中，主要要掌握直接插入排序、折半插入排序、冒泡排序(bubble sort)、簡單選擇排序、希爾排序(shell sort)、快速排序、堆排序、二路歸并排序(merge sort)、基數(shù)排序的基本概念和方法。搞清楚這些排序方法的流程，以及它們之間的區(qū)別。
在這個(gè)知識點(diǎn)，一個(gè)很重要的考查點(diǎn)就是各種內(nèi)部排序算法的比較，一般的書上都會有這樣的一個(gè)表格，列出了所有排序在各種情況下(好、壞、平均)的時(shí)間復(fù)雜度和空間復(fù)雜度，這個(gè)表是需要我們記下來的。當(dāng)然，如果我們能掌握復(fù)雜度的計(jì)算方法，自己能推算出來，那就更好了。
后，就是要掌握內(nèi)部排序算法的基本應(yīng)用，以及算法的實(shí)現(xiàn)。
三、復(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é)習(xí)，難在其中的算法及實(shí)現(xiàn)。有條件的考生，可以在計(jì)算機(jī)上編寫程序，自己實(shí)現(xiàn)教材上的算法(要注意，書上的算法通常都采用偽代碼編寫，需要我們自己用某種程序設(shè)計(jì)語言去具體實(shí)現(xiàn))。如果沒有條件，那就只有在心里進(jìn)行推導(dǎo)了，可以使用實(shí)際的例子，手工“實(shí)現(xiàn)”算法。
一、考查目標(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)行問題求解。
二、知識點(diǎn)解析
1.線性表
線性表是一種簡單的數(shù)據(jù)結(jié)構(gòu)，在線性表方面，主要考查線性表的定義和基本操作、線性表的實(shí)現(xiàn)。在線性表實(shí)現(xiàn)方面，要掌握的是線性表的存儲結(jié)構(gòu)，包括順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)，特別是鏈?zhǔn)酱鎯Y(jié)構(gòu)，是考查的重點(diǎn)。另外，還要掌握線性表的基本應(yīng)用。
2.棧、隊(duì)列和數(shù)組
棧和隊(duì)列是兩種特殊的線性表，在這方面，要求我們掌握棧和隊(duì)列的基本概念，以及他們之間的區(qū)別。對于棧和隊(duì)列的存儲結(jié)構(gòu)(包括順序存儲結(jié)構(gòu)、鏈?zhǔn)酱鎯Y(jié)構(gòu))要有較深的理解，對于棧和隊(duì)列的應(yīng)用，例如，排隊(duì)問題、子程序調(diào)用問題、表達(dá)式問題等，要搞清楚。
一維數(shù)組屬于線性表范疇，但多維數(shù)組不屬于線性表。在這方面，主要掌握數(shù)組的存儲結(jié)構(gòu)，例如按行優(yōu)先、按列優(yōu)先等，某個(gè)元素存在的地址是什么。對于特殊矩陣(二維數(shù)組)的壓縮存儲原理也要搞清楚。
3、樹與二叉樹
二叉樹和樹是兩種不同的概念，這一點(diǎn)是必須要搞清楚的。在這個(gè)部分，我們要掌握樹的定義、二叉樹的定義及主要特征(特殊的二叉樹、二叉樹的性質(zhì))。在二叉樹的順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)方面，特別是鏈?zhǔn)酱鎯Y(jié)構(gòu)，因?yàn)楹芏鄳?yīng)用都是建立在鏈?zhǔn)酱鎯A(chǔ)上，例如，二叉樹的遍歷(前序遍歷、中序遍歷、后序遍歷)就是一種典型的應(yīng)用。
在特殊的二叉樹中，完全二叉樹的概念是必須要搞清楚的，其次，線索二叉樹的基本概念和構(gòu)造、二叉排序樹、平衡二叉樹的基本概念和應(yīng)用，特別是二叉排序樹的基本性質(zhì)和特點(diǎn)要能很好地理解。
多棵獨(dú)立的樹就組成了森林，樹的存儲結(jié)構(gòu)和遍歷、森林的遍歷、樹和二叉樹的轉(zhuǎn)換、森林和二叉樹的轉(zhuǎn)換等知識，也要有了了解。
后就是樹的應(yīng)用，通常會作為綜合應(yīng)用類試題出現(xiàn)，包括等價(jià)類問題、哈夫曼(Huffman)樹和哈夫曼編碼等。
4、圖
在數(shù)據(jù)結(jié)構(gòu)中，圖的結(jié)構(gòu)是復(fù)雜的，這里的概念也是多的。我們要掌握圖的基本概念(有向圖、無向圖、連通、路徑、子圖、出度、入度、生成樹、短路徑、關(guān)鍵路徑等)。
圖的存儲及基本操作主要有鄰接矩陣法和鄰接表法，我們要掌握這有向圖和無向圖的這2種存儲方法，要清楚圖的連通和存儲方法之間的關(guān)系。例如，一個(gè)頂點(diǎn)的出度和臨界矩陣中1的個(gè)數(shù)有什么關(guān)系，等等。
圖的遍歷方法有深度優(yōu)先搜索和廣度優(yōu)先搜索，我們要掌握這2種遍歷方法的算法實(shí)現(xiàn)。給出一個(gè)具體的圖，要能知道它的遍歷次序。
在數(shù)據(jù)結(jié)構(gòu)課程中，圖的基本應(yīng)用是多的，也是復(fù)雜的，我們要掌握這些應(yīng)用的復(fù)雜度分析。要掌握的具體應(yīng)用主要包括小(代價(jià))生成樹、短路徑、拓?fù)渑判颉㈥P(guān)鍵路徑。在給出的一個(gè)具體的圖中，我們要會利用已知條件，求出上述應(yīng)用的結(jié)果。
5、查找
在給定的數(shù)據(jù)集合中查找某個(gè)關(guān)鍵值就是查找，查找的基本方法主要有順序查找法、折半查找法、B-樹、散列(Hash)表及其查找?？嫉谋容^多的是折半查找和散列表，我們要掌握它們的基本概念和方法，例如散列表的碰撞如何解決，裝載因子的概念等。
另外，我們要掌握各種查找算法的分析及應(yīng)用，好能把各種查找在查找成功、查找失敗的情況下的好、平均、壞的平均查找次數(shù)的計(jì)算方法搞清楚。
6、內(nèi)部排序
根據(jù)考試大綱，只考查內(nèi)部排序。所謂內(nèi)部排序，就是在內(nèi)存中進(jìn)行排序。在這一部分中，主要要掌握直接插入排序、折半插入排序、冒泡排序(bubble sort)、簡單選擇排序、希爾排序(shell sort)、快速排序、堆排序、二路歸并排序(merge sort)、基數(shù)排序的基本概念和方法。搞清楚這些排序方法的流程，以及它們之間的區(qū)別。
在這個(gè)知識點(diǎn)，一個(gè)很重要的考查點(diǎn)就是各種內(nèi)部排序算法的比較，一般的書上都會有這樣的一個(gè)表格，列出了所有排序在各種情況下(好、壞、平均)的時(shí)間復(fù)雜度和空間復(fù)雜度，這個(gè)表是需要我們記下來的。當(dāng)然，如果我們能掌握復(fù)雜度的計(jì)算方法，自己能推算出來，那就更好了。
后，就是要掌握內(nèi)部排序算法的基本應(yīng)用，以及算法的實(shí)現(xiàn)。
三、復(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é)習(xí)，難在其中的算法及實(shí)現(xiàn)。有條件的考生，可以在計(jì)算機(jī)上編寫程序，自己實(shí)現(xiàn)教材上的算法(要注意，書上的算法通常都采用偽代碼編寫，需要我們自己用某種程序設(shè)計(jì)語言去具體實(shí)現(xiàn))。如果沒有條件，那就只有在心里進(jìn)行推導(dǎo)了，可以使用實(shí)際的例子，手工“實(shí)現(xiàn)”算法。