南京郵電大學

811--《數據結構》考研大綱

一、考核內容：

1 緒論

1.1算法的基本概念

1.2數據結構的基本概念

1.3數據抽象和抽象數據類型

1.4描述數據結構和算法

1.5算法分析的基本方法

2 線性表

2.1線性表的定義及基本操作

2.2線性表的順序存儲

2.3線性表的鏈接存儲

3 棧和隊列

3.1棧和隊列的基本概念

3.2棧和隊列的順序存儲結構

3.3棧和隊列的鏈式存儲結構

3.4表達式計算

3.5遞歸

數組

4.1數組的基本概念

4.2特殊矩陣

4.3稀疏矩陣

5 樹和二叉樹

5.1樹的基本概念

5.2二叉樹

5.2.1二叉樹的定義及主要特征

5.2.2二叉樹的順序存儲和鏈式存儲

5.2.3二叉樹的遍歷

5.2.4 線索二叉樹的基本概念和構造

5.3樹和森林

5.3.1樹的存儲結構

5.3.2森林和二叉樹的轉換

5.3.3樹和森林的遍歷

5.4樹和二叉樹的應用

5.4.1二叉排序樹

5.4.2二叉平衡樹

5.4.3哈夫曼(Huffman)樹和哈夫曼編碼

6 圖

6.1圖的基本概念

6.2圖的存儲及基本操作

6.2.1鄰接矩陣法

6.2.2鄰接表表示法

6.3圖的遍歷

6.3.1深度優先搜索

6.3.2廣度優先搜索

6.4圖的基本應用

6.4.1拓撲排序

6.4.2關鍵路徑

6.4.3 最小代價生成樹

6.4.4最短路徑

7 搜索(Search)

7.1搜索的基本概念

7.2順序搜索法

7.3二分搜索法

7.4 B-樹及其基本操作

7.5散列(Hash)表

7.6搜索算法的分析及應用

8 內排序

8.1排序的基本概念

8.2簡單選擇排序

8.3直接插入排序

8.4冒泡排序(bubble sort)

8.5希爾排序(shell sort)

8.6快速排序

8.7堆排序

8.8兩路合并排序(merge sort)

8.9基數排序

8.10各種內部排序算法的比較

8.11內部排序算法的應用