807數據結構考試大綱

一、考試總體要求

《數據結構》是一門專業基礎課，要求考生理解數據結構的基本概念，掌握數據的邏輯結構、存儲結構及其差異，以及各種基本操作的實現；在掌握基本的數據處理原理和方法的基礎上，能夠對算法進行時間復雜度和空間復雜度分析；能夠選擇合適的數據結構和方法進行問題求解。具備采用C、C++設計與實現算法的能力。

二、考試內容

本課程主要考試主要包括的內容：基本概念和算法分析、線性表、棧和隊列、串、數組和廣義表、樹和二叉樹、圖、查找、排序。

1.基本概念和算法分析

本部分主要介紹數據結構的基本概念和常用術語，算法和算法分析方法。重點要求理解數據結構的基本概念、理解抽象數據結構的定義、算法的基本要素和算法分析方法，掌握算法的時間復雜度和空間復雜度分析方法。

2.線性表

本部分主要介紹線性表的邏輯結構和各種存儲表示方法，以及運算的實現。重點要求掌握線性表的定義、特點和基本操作，熟練掌握線性表的存儲表示，包括順序存儲和鏈式存儲，以及在這兩種存儲結構上的插入、刪除、查找等運算的實現，理解其異同點和優缺點。掌握特殊鏈表的定義和基本運算的實現，包括循環鏈表和雙向鏈表，掌握線性表的應用，包括一元多項式的組織和操作以及其它應用等。

3.棧和隊列

本部分主要介紹棧和隊列的邏輯結構定義，以及在兩種存儲結構上基本運算的實現。重點要求熟練掌握棧和隊列的基本概念，以及棧和隊列的兩種實現方法（順序存儲結構實現和鏈式存儲結構實現）及其操作的實現。能夠掌握棧和隊列的基本應用。

4.串

本部分主要介紹串的基本概念、存儲結構和運算。重點要求掌握串的基本概念，掌握串模式匹配KMP及改進算法。

5.數組和廣義表

本部分主要介紹數組和廣義表的定義、存儲及運算。重點要求掌握數組的特點及存儲表示方法。掌握特殊矩陣的存儲表示方法，包括對稱矩陣、對角線矩陣、稀疏矩陣。掌握廣義表的定義、存儲表示方法以及對廣義表的分解操作。

6.樹和二叉樹

本部分主要介紹二叉樹的定義、性質、存儲結構、遍歷、線索化；樹的定義、存儲結構、遍歷、樹和森林的轉換，赫夫曼樹及其赫夫曼編碼等內容。要求掌握樹與二叉樹的定義、性質，掌握二叉樹的存儲表示，包括順序存儲和鏈式存儲。掌握二叉樹的遍歷及其應用，包括先序、中序、后序和層次序遍歷。理解線索二叉樹的定義、存儲表示和尋找前驅、后繼。掌握樹和森林的存儲表示、樹、森林與二叉樹的轉換、樹和森林的遍歷。掌握赫夫曼樹和赫夫曼編碼及其應用。

7.圖

本部分主要介紹介紹圖的基本概念、兩種常用的存儲結構、兩種遍歷方法以及圖的應用算法。重點要求掌握圖的基本概念，基本性質。掌握圖的存儲方法，重點掌握鄰接矩陣法和鄰接表法。掌握圖的兩種遍歷方法：深度優先遍歷和廣度優先遍歷算法及實現，掌握拓撲排序算法及算法實現。理解基于圖的最小(代價)生成樹算法、最短路徑算法、關鍵路徑算法。

8.查找

本部分主要介紹線性表、樹和哈希表的查找方法、算法實現以及各種查找方法的時間性能（平均查找長度）分析。重點要求掌握順序查找、折半查找、二叉排序樹和哈希表查找的基本思想和算法實現。掌握平衡二叉樹的基本操作，理解B-樹和B+樹的基本概念。能夠理解各種不同查找算法的特點及其適用情況，分析不同查找算法的性能。

9.內部排序

本部分主要介紹幾種內部排序方法的基本思想、排序過程、算法實現、時間和空間性能的分析；并且對各種排序方法進行比較。重點要求掌握直接插入排序、折半插入排序、起泡排序、快速排序、直接選擇排序、堆排序、歸并排序、基數排序的基本思想和排序過程。掌握各類排序方法的時間/空間復雜度，以及穩定性。