課程名稱數 據 結 構
參考書目：嚴蔚敏,吳偉民 《數據結構》(C語言版)，清華大學出版社，2012.5
復習的總體要求
數據結構是計算機各專業的專業基礎課。本課程包括：算法的基本概念、分析和設計方法;軟件設計中常用的各類結構即線性結構、樹結構、圖結構等;查找、排序等各類常用算法。主要考察學生對數據結構基礎知識的理解、是否具備對現有常用結構和算法的應用能力、是否具備針對具體應用設計合適數據結構的能力?？傮w要求如下：
1、理解數據結構的基本概念;
2、掌握數據結構中邏輯結構、存儲結構的基本概念和差異，以及各種基本操作的實現;
3、熟悉各種基本數據結構及其操作，學會根據實際問題要求來選擇數據結構;
4、掌握設計算法的步驟和算法分析方法;
5、掌握數據結構在排序和查找等常用算法中的應用;
6、具備采用類C或C++或JAVA語言設計與實現算法的能力。
復習內容及知識點
一、 數據結構基本概念及算法定義與分析
1、什么是數據結構;
2、抽象數據類型：數據類型、數據抽象與抽象數據類型的概念;用于描述數據結構的語言;
3、數據結構的抽象層次 ;
4、算法定義及算法效率的度量指標：時間復雜度與空間復雜度的計算方法、常見時間復雜度類型與性能優劣比較。
二、線性表
1、線性表的概念、定義、邏輯結構和存儲結構;
2、線性表的順序結構及其各種基本運算;
3、單鏈表、循環鏈表、雙向鏈表的存儲結構及其各種基本運算;
4、棧：棧的抽象數據類型定義、棧的存儲表示及基本操作實現、棧的應用;
5、隊列：隊列的抽象數據類型定義、隊列的存儲表示與基本操作實現;
6、鏈表的應用：稀疏多項式存儲和運算。
三、串
1、串類型的定義;
2、串的定長順序存儲、塊鏈存儲表示和實現;
3、串的模式匹配算法;
4、串的常見應用。
四、數組和廣義表
1、數組的定義;
2、二維數組的兩種存儲方式(以行序為主、以列序為主)及其數組元素存儲位置計算;
3、特殊矩陣與稀疏矩陣的壓縮存儲方式;
4、廣義表的定義和存儲結構。
五、樹和二叉樹
1、樹和森林的概念：樹的定義、樹的術語、樹的抽象數據類型 ;
2、二叉樹：二叉樹的定義、二叉樹的性質、二叉樹的抽象數據類型;
3、二叉樹的表示：數組表示、鏈表存儲表示 ;
4、二叉樹遍歷：中序、前序、后序遍歷、不用棧的二叉樹中序遍歷算法;
5、線索化二叉樹：中序線索化二叉樹、前序與后序的線索化 ;
6、堆：堆的定義、堆的建立 ;
7、樹與森林：樹的存儲表示、森林與二叉樹的轉換、樹的遍歷、二叉樹的計數;
8、霍夫曼樹：路徑長度、霍夫曼樹、霍夫曼編碼。
六、 圖
1、圖的基本概念：圖的基本概念、圖的抽象數據類型 ;
2、圖的存儲表示：鄰接矩陣、鄰接表、鄰接多重表;
3、圖的遍歷與連通性：深度優先搜索、廣度優先搜索、連通分量;
4、最小生成樹：克魯斯卡爾算法、普里姆算法;
5、最短路徑、關鍵路徑。
七、查找
1、順序表的查找;
2、有序表的查找;
3、索引順序表的查找;
4、二叉排序樹和平衡二叉樹;
5、B-樹和B+樹概念;
6、哈希表概念;哈希函數的構造方法、處理沖突的方法、哈希表的查找及分析。
八、內部排序
1、插入排序：直接插入排序、希爾排序;
2、交換排序：起泡排序、快速排序;
3、選擇排序：直接選擇排序、堆排序;
4、歸并排序：歸并;迭代的歸并排序算法、遞歸的表歸并排序;
5、各種內部排序方法的分析比較(時間復雜度和空間占用情況)。
試卷題型說明：(考試題型可能根據實際情況進行調整，以下考試題型僅供參考)
1、單項選擇題：每個問題都只有一個選擇，根據題目內容選擇正確答案。
2、填空題：根據題目要求，填充對應位置的內容。
3、判斷題：根據題目內容判斷其描述問題的正確性。
4、應用題：根據題目內容完成相應問題的求解，要求給出具體求解過程。
5、算法設計題：根據題目要求，采用C或C++或Java完成算法的編寫。
