軟件工程專業(yè)綜合(數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)、計算機(jī)網(wǎng)絡(luò))考研大綱

　　第一部分 數(shù)據(jù)結(jié)構(gòu)(60/150)

　　一、考試要求

　　要求考生比較系統(tǒng)地理解數(shù)據(jù)結(jié)構(gòu)的基本概念和基本理論，掌握各種數(shù)據(jù)結(jié)構(gòu)的特點和基本方法，著重考察考生綜合運(yùn)用所學(xué)知識分析問題和解決問題的能力。要求考生能夠用C或C++語言描述數(shù)據(jù)結(jié)構(gòu)中的算法。

　　二、考試內(nèi)容

　　(一)緒論

　　數(shù)據(jù)結(jié)構(gòu)的基本概念，數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu);

　　算法的定義，算法的基本特征及算法分析的基本概念。

　　(二)線性表

　　線性關(guān)系、線性表的定義，線性表的基本操作;

　　線性表的順序存儲結(jié)構(gòu)的構(gòu)造原理;

　　對線性表實施的比較主要的操作(包括三種鏈表的建立、插入和刪除、檢索等)的算法設(shè)計。

　　(三)鏈表

　　單鏈表、雙向鏈表和循環(huán)鏈表三種鏈表形式的存儲結(jié)構(gòu)和特點以及基本操作;

　　稀疏矩陣的存儲結(jié)構(gòu)和特點以及基本操作。

　　(四)棧和隊列

　　棧的定義、結(jié)構(gòu)特點及其存儲方式(順序存儲與鏈接存儲)和基本操作的實現(xiàn)算法;

　　隊列的結(jié)構(gòu)、特點及其存儲方式(順序存儲與鏈接存儲)和基本操作的實現(xiàn)算法。

　　(五)數(shù)組和串

　　串的基本概念、串的存儲結(jié)構(gòu)和相關(guān)的操作算法;

　　數(shù)組的存儲結(jié)構(gòu)，在順序存儲的情況下，數(shù)組元素與存儲單元的對應(yīng)關(guān)系;

　　字符串比較的基本算法(包括KMP算法)。

　　(六)遞歸

　　遞歸的基本概念和實現(xiàn)原理以及用遞歸的思想描述問題和書寫算法的方法;

　　漢諾塔、迷宮等問題的遞歸解法;

　　用棧實現(xiàn)遞歸問題的非遞歸解法。

　　(七)樹和森林

　　樹的結(jié)構(gòu)和主要概念，各種二叉樹的結(jié)構(gòu)及其特點;

　　二叉樹的三種遍歷方法的實現(xiàn)原理和性質(zhì)，能將二叉樹的遍歷方法應(yīng)用于求解二叉樹的葉子結(jié)點個數(shù)、二叉樹計數(shù)等問題，遍歷的非遞歸實現(xiàn)方法;

　　線索化二叉樹的結(jié)構(gòu)和基本操作;

　　堆的原理和基本操作的實現(xiàn)方法;

　　森林的定義和存儲結(jié)構(gòu)，森林的遍歷等方法的實現(xiàn);

　　基于霍夫曼樹生成霍夫曼編碼的方法。

　　(八)集合和搜索

　　集合的基本概念和各種存儲方法;

　　等價類的生成算法;

　　針對有序順序表的折半搜索、斐波那契等搜索方法;

　　AVL樹的定義和特點以及AVL樹調(diào)整操作的實現(xiàn)原理;

　　比較優(yōu)二叉樹的構(gòu)造原理和相關(guān)算法。

　　(九)圖

　　圖的各種基本概念和各種存儲方式;

　　圖的兩種搜索方法和連通分量的生成方法;

　　兩種比較小生成樹的生成方法;

　　各種求比較短路徑的方法;

　　用頂點表示活動和用邊表示活動的兩種網(wǎng)絡(luò)結(jié)構(gòu)特點和相關(guān)操作的實現(xiàn)算法。

　　(十)排序

　　插入排序法(含折半插入排序法)、選擇排序法、泡排序法、快速排序法、堆積排序法、歸并排序、基數(shù)排序等排序方法排序的原理、規(guī)律和特點;

　　各種排序算法的時空復(fù)雜度簡單分析。

　　(十一)索引結(jié)構(gòu)與散列

　　線性索引結(jié)構(gòu)、倒排表、靜態(tài)搜索樹的結(jié)構(gòu)和特點;

　　B樹的結(jié)構(gòu)和各種操作的實現(xiàn)算法;

　　散列的實現(xiàn)原理和各種操作的實現(xiàn)算法。

　　三、試卷結(jié)構(gòu)：

　　考試題型：填空題、選擇題、簡答題、編程題