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

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

　　一、考試要求

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

　　二、考試內(nèi)容

　　(一)緒論

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

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

　　(二)線性表

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

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

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

　　(三)鏈表

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

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

　　(四)棧和隊(duì)列

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

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

　　(五)數(shù)組和串

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

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

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

　　(六)遞歸

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

　　漢諾塔、迷宮等問(wèn)題的遞歸解法;

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

　　(七)樹(shù)和森林

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

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

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

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

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

　　基于霍夫曼樹(shù)生成霍夫曼編碼的方法。

　　(八)集合和搜索

　　集合的基本概念和各種存儲(chǔ)方法;

　　等價(jià)類的生成算法;

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

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

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

　　(九)圖

　　圖的各種基本概念和各種存儲(chǔ)方式;

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

　　兩種比較小生成樹(shù)的生成方法;

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

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

　　(十)排序

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

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

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

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

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

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

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

　　考試題型：填空題、選擇題、簡(jiǎn)答題、編程題