考試科目名稱： 數據結構

科目代碼：851

一、數據結構的一般概念

1.掌握數據結構的基本概念和術語。

2.了解抽象數據類型的概念。

3.掌握算法的特性，算法的描述和算法的分析。

二、線性表

1.理解線性表的邏輯結構。

2.掌握線性表的順序存貯結構和鏈式存貯結構;掌握線性表基本操作的實現。

3.了解線性表的應用。

三、其他線性結構

1.掌握棧的定義、棧的存貯結構及基本操作的實現。

2.理解用棧實現表達式的求值，遞歸過程及其實現。

3.掌握隊列的定義、存貯結構及基本操作的實現

4.理解串的邏輯定義及其基本操作;理解串的存貯結構。

5.理解數組的定義、數組的順序存貯結構及矩陣的存貯壓縮。

6.理解廣義表的定義及存貯結構。

四、樹和二叉樹

1.掌握樹型結構的定義。

2.掌握二叉樹的定義、性質及各種存貯結構。

3.掌握遍歷二叉樹、線索二叉樹及其他基本操作。

4.掌握樹、森林與二叉樹的相互轉換;理解樹的遍歷;掌握哈夫曼樹及其應用。

五、圖

1.掌握圖的定義和術語。

2.掌握圖的存貯結構;理解圖的基本操作。

3.掌握圖的遍歷算法;了解利用圖的遍歷解決圖的應用問題。

4.理解圖的有關應用：求最小生成樹、求最短路徑、拓撲排序及關鍵路徑等算法的基本思想。

六、查找

1.掌握靜態(tài)查找表。

2.掌握二叉排序樹和平衡二叉樹。

3.理解B-樹;了解B+樹。

4.掌握哈希表。

5.掌握各種查找方法的時間性能分析。

七、內部排序

1.掌握直接插入排序、希爾排序、冒泡排序、快速排序、簡單選擇排序、堆排序、歸并排序;理解基數排序。

2.學會各種內部排序方法的比較(時間復雜度、空間復雜度、穩(wěn)定性)。

。

參考書目：

1. 《數據結構》(C語言版)，嚴蔚敏 吳偉民編著，清華大學出版社，2006.3

2. 《數據結構實用教程》(C++版)，萬健主編，電子工業(yè)出版社，2011.1