北京郵電大學2012年軟件工程專業綜合考研大綱

　　軟件工程專業綜合(數據結構、操作系統、計算機網絡)考研大綱

　　第一部分 數據結構(60/150)

　　一、考試要求

　　要求考生比較系統地理解數據結構的基本概念和基本理論，掌握各種數據結構的特點和基本方法，著重考察考生綜合運用所學知識分析問題和解決問題的能力。要求考生能夠用C或C++語言描述數據結構中的算法。

　　二、考試內容

　　(一)緒論

　　數據結構的基本概念，數據的邏輯結構、存儲結構;

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

　　(二)線性表

　　線性關系、線性表的定義，線性表的基本操作;

　　線性表的順序存儲結構的構造原理;

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

　　(三)鏈表

　　單鏈表、雙向鏈表和循環鏈表三種鏈表形式的存儲結構和特點以及基本操作;

　　稀疏矩陣的存儲結構和特點以及基本操作。

　　(四)棧和隊列

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

　　隊列的結構、特點及其存儲方式(順序存儲與鏈接存儲)和基本操作的實現算法。

　　(五)數組和串

　　串的基本概念、串的存儲結構和相關的操作算法;

　　數組的存儲結構，在順序存儲的情況下，數組元素與存儲單元的對應關系;

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

　　(六)遞歸

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

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

　　用棧實現遞歸問題的非遞歸解法。

　　(七)樹和森林

　　樹的結構和主要概念，各種二叉樹的結構及其特點;

　　二叉樹的三種遍歷方法的實現原理和性質，能將二叉樹的遍歷方法應用于求解二叉樹的葉子結點個數、二叉樹計數等問題，遍歷的非遞歸實現方法;

　　線索化二叉樹的結構和基本操作;

　　堆的原理和基本操作的實現方法;

　　森林的定義和存儲結構，森林的遍歷等方法的實現;

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

　　(八)集合和搜索

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

　　等價類的生成算法;

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

　　AVL樹的定義和特點以及AVL樹調整操作的實現原理;

　　比較優二叉樹的構造原理和相關算法。

　　(九)圖

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

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

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

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

　　用頂點表示活動和用邊表示活動的兩種網絡結構特點和相關操作的實現算法。

　　(十)排序

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

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

　　(十一)索引結構與散列

　　線性索引結構、倒排表、靜態搜索樹的結構和特點;

　　B樹的結構和各種操作的實現算法;

　　散列的實現原理和各種操作的實現算法。

　　三、試卷結構：

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