2011計(jì)算機(jī)考研大綱預(yù)測(cè)篇（1）_跨考網(wǎng)

編者按：2011年仍是計(jì)算機(jī)專(zhuān)業(yè)考研專(zhuān)業(yè)基礎(chǔ)課實(shí)行全國(guó)統(tǒng)考，二七日暑假備考期間。新的考試大綱也會(huì)公布，跨考教育考研部希望通過(guò)回顧10年考試大綱幫助積極備考的同學(xué)梳理知識(shí)、順便參加考試！

在計(jì)算機(jī)考研專(zhuān)業(yè)基礎(chǔ)課統(tǒng)考科目中，一共考查數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)、計(jì)算機(jī)組成原理、計(jì)算機(jī)網(wǎng)絡(luò)四門(mén)課程，滿(mǎn)分為150分，其中數(shù)據(jù)結(jié)構(gòu)占45分。

　　一、考查目標(biāo)

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

　　(2)掌握基本的數(shù)據(jù)處理原理和方法的基礎(chǔ)上，能夠?qū)λ惴ㄟM(jìn)行設(shè)計(jì)與分析。

　　(3)能夠選擇合適的數(shù)據(jù)結(jié)構(gòu)和方法進(jìn)行問(wèn)題求解。

1.線性表

　　線性表是一種最簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)，在線性表方面，主要考查線性表的定義和基本操作、線性表的實(shí)現(xiàn)。在線性表實(shí)現(xiàn)方面，要掌握的是線性表的存儲(chǔ)結(jié)構(gòu)，包括順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，特別是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，是考查的重點(diǎn)。另外，還要掌握線性表的基本應(yīng)用。

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

　　棧和隊(duì)列是兩種特殊的線性表，在這方面，要求我們掌握棧和隊(duì)列的基本概念，以及他們之間的區(qū)別。對(duì)于棧和隊(duì)列的存儲(chǔ)結(jié)構(gòu)(包括順序存儲(chǔ)結(jié)構(gòu)、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu))要有較深的理解，對(duì)于棧和隊(duì)列的應(yīng)用，例如，排隊(duì)問(wèn)題、子程序調(diào)用問(wèn)題、表達(dá)式問(wèn)題等，要搞清楚。

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

3、樹(shù)與二叉樹(shù)

　　二叉樹(shù)和樹(shù)是兩種不同的概念，這一點(diǎn)是必須要搞清楚的。在這個(gè)部分，我們要掌握樹(shù)的定義、二叉樹(shù)的定義及主要特征(特殊的二叉樹(shù)、二叉樹(shù)的性質(zhì))。在二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)方面，特別是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，因?yàn)楹芏鄳?yīng)用都是建立在鏈?zhǔn)酱鎯?chǔ)基礎(chǔ)上，例如，二叉樹(shù)的遍歷(前序遍歷、中序遍歷、后序遍歷)就是一種典型的應(yīng)用。

　　在特殊的二叉樹(shù)中，完全二叉樹(shù)的概念是必須要搞清楚的，其次，線索二叉樹(shù)的基本概念和構(gòu)造、二叉排序樹(shù)、平衡二叉樹(shù)的基本概念和應(yīng)用，特別是二叉排序樹(shù)的基本性質(zhì)和特點(diǎn)要能很好地理解。

　　多棵獨(dú)立的樹(shù)就組成了森林，樹(shù)的存儲(chǔ)結(jié)構(gòu)和遍歷、森林的遍歷、樹(shù)和二叉樹(shù)的轉(zhuǎn)換、森林和二叉樹(shù)的轉(zhuǎn)換等知識(shí)，也要有了了解。

　　最后就是樹(shù)的應(yīng)用，通常會(huì)作為綜合應(yīng)用類(lèi)試題出現(xiàn)，包括等價(jià)類(lèi)問(wèn)題、哈夫曼(Huffman)樹(shù)和哈夫曼編碼等。

　　4、圖

　　在數(shù)據(jù)結(jié)構(gòu)中，圖的結(jié)構(gòu)是最復(fù)雜的，這里的概念也是最多的。我們要掌握?qǐng)D的基本概念(有向圖、無(wú)向圖、連通、路徑、子圖、出度、入度、生成樹(shù)、最短路徑、關(guān)鍵路徑等)。

　　圖的存儲(chǔ)及基本操作主要有鄰接矩陣法和鄰接表法，我們要掌握這有向圖和無(wú)向圖的這2種存儲(chǔ)方法，要清楚圖的連通和存儲(chǔ)方法之間的關(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à))生成樹(shù)、最短路徑、拓?fù)渑判?、關(guān)鍵路徑。在給出的一個(gè)具體的圖中，我們要會(huì)利用已知條件，求出上述應(yīng)用的結(jié)果。