? 湘潭大學2014數據結構考研大綱
(一)考試對象
參加全日制專業(yè)學位研究生《計算機技術》和《軟件工程》專業(yè)復試考生。
(二)考試目的
考核學生對本課程知識的掌握和運用能力，屬水平測試。
(三)考試的內容、要求
第一章 緒論
考試內容
數據結構的基本概念和術語; 算法的描述; 算法設計的要求; 算法效率的度量; 算法的存儲空間需求。
考試要求
1.有關數據的基本概念;
2.領會抽象數據類型與數據結構的關系及抽象數據類型在算法設計中的意義和作用;
3.掌握數據的邏輯結構及有關術語的定義，掌握數據結構的表示方法，能用序偶集合表示關系;
4.了解數據的邏輯結構和存儲結構的分類;
5.掌握描述算法的語言;
6.算法的存儲空間需求;
7.領會算法設計的要求 算法效率度量的意義和作用，懂得算法分析原理，掌握算法分析技術;
第二章 線性表
考試內容
線性表的邏輯結構; 線性表的順序存儲結構; 線性表的鏈式存儲結構; 一元多項式的表示及相加和相乘算法。
考試要求
1.熟練掌握順序存儲的線性表的基本操作的實現，熟練掌握鏈式存儲的線性表的動態(tài)存儲和靜態(tài)存儲的方法及其算法;
2.循環(huán)鏈表的應用，一元多項式的表示及相加和相乘算法;
3.掌握順序存儲的線性表和鏈式存儲的線性表的主要優(yōu)缺點;
4.掌握對順序存儲的線性表和鏈式存儲的線性表的各種算法的評價;
第三章 棧與隊列
考試內容
棧;表達式求值; 棧與遞歸過程; 隊列。
考試要求
1.順序棧與鏈棧的結構及操作，要求達到綜合應用層次;
2.順序棧與鏈棧的比較;
3.順序隊與鏈隊的結構及操作，要求達到綜合應用層次;
4.順序隊與鏈隊的比較;
5.弄清隊與棧及線性表的異同。掌握循環(huán)隊的組織方法及有關算法;
6.遞歸過程的模擬。
第四章 串
考試內容
串及其操作; 串的存儲結構; 串基本操作的實現。
考試要求
1.領會串的邏輯結構定義，掌握串的基本操作;
2.掌握串的存儲結構及其算法實現;
3.掌握模式匹配的原理及其KMP算法。
第五章 數組和廣義表
考試內容
數組的定義和數組分量的地址計算; 數組的順序存儲結構; 矩陣的壓縮存儲; 廣義表的定義; 廣義表的存儲結構; 廣義表的遞歸算法。
考試要求
1.領會數組是一種復雜的數據結構，數組元素之間的關系，既不是線性的，也不是樹形的;
2.掌握數組分量的地址計算方法、當矩陣壓縮存儲于一維數組中時，矩陣元素與數組分量的對應關系;
3.使用三元組表示稀疏矩陣的方法及其算法;
4.對特定的存儲結構，任給一廣義表，給出其存儲模式;
5.掌握用廣義表表示m元多項式的方法;
6.掌握廣義表的幾種遞歸算法;
7.數組的綜合應用能力。
第六章 樹和二叉樹
考試內容
樹的結構定義和基本操作; 二叉樹及完全二叉樹的性質; 樹和二叉樹的存儲結構; 遍歷二叉樹的遞歸與非遞歸算法; 線索二叉樹的建立及插入算法; 森林與二叉樹的轉換; 哈夫曼樹及其應用。
考試要求
1.領會樹和二叉樹是兩個完全不同的概念;
2.深刻理解和掌握二叉樹及完全二叉樹的性質以及遍歷二叉樹的遞歸與非遞歸算法;
3.領會線索二叉樹的作用以及它的建立、遍歷及插入算法;
4.掌握數的存儲結構以及森林與樹的轉換方法;
5.二叉樹的各種操作的效率評價;
6.掌握建立哈夫曼編碼樹的算法、哈夫曼編碼及其應用;
7.掌握回溯法的算法設計思想和方法。
第七章 圖
考試內容
圖的定義和術語; 圖的存儲結構; 圖的遍歷; 最小生成樹; 有向無環(huán)圖及其應用; 最短路徑; 關鍵路徑。
考試要求
1.熟知圖的術語，理解圖的概念;
2.熟練掌握圖的數組表示法和鄰接表表示法及其算法;
3.熟練掌握圖的深度優(yōu)先搜索法和廣度優(yōu)先搜索法及其算法;
4.掌握貪心算法，并用貪心算法求解連通圖的最小生成樹;
5.熟練掌握有向無環(huán)圖的拓撲排序及求關鍵路徑的算法;
6.熟練掌握求圖的最短路徑的算法;
7.掌握各種算法的效率評價;
8.圖的應用能力。
第八章 查找
考試內容
順序查找法; 折半查找法;靜態(tài)樹表的查找; 索引表的查找; 二叉排序樹的查找;平衡二叉樹的平衡方法及查找; B-和B+樹的查找;哈希技術的概念;哈希函數的構造方法; 沖突處理技術; 哈希表的查找。
考試要求
1.熟練掌握順序查找法和折半查找法及其算法，領會靜態(tài)樹表的查找和索引表的查找的思想;
2.熟練掌握二叉排序樹的查找、插入和刪除算法，掌握二叉樹的平衡方法;
3.熟練掌握B樹的查找、插入和刪除算法，領會B+樹的思想;
4.理解哈希技術的概念，熟練掌握哈希函數的構造方法和沖突處理技術，掌握哈希表的查找算法;
5.根據所給條件求裝填因子并設計合適的哈希表結構;
6.各種查找算法的性能分析及比較;
7.能根據不同情況靈活應用不同的查找方法。
第九章 內部排序
考試內容
有關概念; 直接插入排序; 折半插入排序; 2-路插入排序; 希爾排序;快速排序; 堆排序; 歸并排序; 分配排序與基數排序; 各種內部排序方法的比較。
考試要求
1.熟練掌握直接插入排序算法，領會其它插入排序方法;
2.深刻領會快速排序的思想，熟練掌握快速排序算法,弄清楚影響快速排序速度的瓶頸，掌握快速排序的遞歸算法;
3.深刻領會堆排序的思想，熟練掌握堆排序算法;
4.深刻領會分配排序和基數排序的思想，熟練掌握其排序算法，并改寫該算法使得排序僅在一維數組內完成而無須通過鏈隊實現;
5.各種內部排序方法的比較及排序算法的性能分析和評價;
6.能靈活應用各種排序方法解決實際問題
? ? 編輯推薦：
? ??2014年考研招生信息——全國院校匯總?
(一)考試對象
參加全日制專業(yè)學位研究生《計算機技術》和《軟件工程》專業(yè)復試考生。
(二)考試目的
考核學生對本課程知識的掌握和運用能力，屬水平測試。
(三)考試的內容、要求
第一章 緒論
考試內容
數據結構的基本概念和術語; 算法的描述; 算法設計的要求; 算法效率的度量; 算法的存儲空間需求。
考試要求
1.有關數據的基本概念;
2.領會抽象數據類型與數據結構的關系及抽象數據類型在算法設計中的意義和作用;
3.掌握數據的邏輯結構及有關術語的定義，掌握數據結構的表示方法，能用序偶集合表示關系;
4.了解數據的邏輯結構和存儲結構的分類;
5.掌握描述算法的語言;
6.算法的存儲空間需求;
7.領會算法設計的要求 算法效率度量的意義和作用，懂得算法分析原理，掌握算法分析技術;
第二章 線性表
考試內容
線性表的邏輯結構; 線性表的順序存儲結構; 線性表的鏈式存儲結構; 一元多項式的表示及相加和相乘算法。
考試要求
1.熟練掌握順序存儲的線性表的基本操作的實現，熟練掌握鏈式存儲的線性表的動態(tài)存儲和靜態(tài)存儲的方法及其算法;
2.循環(huán)鏈表的應用，一元多項式的表示及相加和相乘算法;
3.掌握順序存儲的線性表和鏈式存儲的線性表的主要優(yōu)缺點;
4.掌握對順序存儲的線性表和鏈式存儲的線性表的各種算法的評價;
第三章 棧與隊列
考試內容
棧;表達式求值; 棧與遞歸過程; 隊列。
考試要求
1.順序棧與鏈棧的結構及操作，要求達到綜合應用層次;
2.順序棧與鏈棧的比較;
3.順序隊與鏈隊的結構及操作，要求達到綜合應用層次;
4.順序隊與鏈隊的比較;
5.弄清隊與棧及線性表的異同。掌握循環(huán)隊的組織方法及有關算法;
6.遞歸過程的模擬。
第四章 串
考試內容
串及其操作; 串的存儲結構; 串基本操作的實現。
考試要求
1.領會串的邏輯結構定義，掌握串的基本操作;
2.掌握串的存儲結構及其算法實現;
3.掌握模式匹配的原理及其KMP算法。
第五章 數組和廣義表
考試內容
數組的定義和數組分量的地址計算; 數組的順序存儲結構; 矩陣的壓縮存儲; 廣義表的定義; 廣義表的存儲結構; 廣義表的遞歸算法。
考試要求
1.領會數組是一種復雜的數據結構，數組元素之間的關系，既不是線性的，也不是樹形的;
2.掌握數組分量的地址計算方法、當矩陣壓縮存儲于一維數組中時，矩陣元素與數組分量的對應關系;
3.使用三元組表示稀疏矩陣的方法及其算法;
4.對特定的存儲結構，任給一廣義表，給出其存儲模式;
5.掌握用廣義表表示m元多項式的方法;
6.掌握廣義表的幾種遞歸算法;
7.數組的綜合應用能力。
第六章 樹和二叉樹
考試內容
樹的結構定義和基本操作; 二叉樹及完全二叉樹的性質; 樹和二叉樹的存儲結構; 遍歷二叉樹的遞歸與非遞歸算法; 線索二叉樹的建立及插入算法; 森林與二叉樹的轉換; 哈夫曼樹及其應用。
考試要求
1.領會樹和二叉樹是兩個完全不同的概念;
2.深刻理解和掌握二叉樹及完全二叉樹的性質以及遍歷二叉樹的遞歸與非遞歸算法;
3.領會線索二叉樹的作用以及它的建立、遍歷及插入算法;
4.掌握數的存儲結構以及森林與樹的轉換方法;
5.二叉樹的各種操作的效率評價;
6.掌握建立哈夫曼編碼樹的算法、哈夫曼編碼及其應用;
7.掌握回溯法的算法設計思想和方法。
第七章 圖
考試內容
圖的定義和術語; 圖的存儲結構; 圖的遍歷; 最小生成樹; 有向無環(huán)圖及其應用; 最短路徑; 關鍵路徑。
考試要求
1.熟知圖的術語，理解圖的概念;
2.熟練掌握圖的數組表示法和鄰接表表示法及其算法;
3.熟練掌握圖的深度優(yōu)先搜索法和廣度優(yōu)先搜索法及其算法;
4.掌握貪心算法，并用貪心算法求解連通圖的最小生成樹;
5.熟練掌握有向無環(huán)圖的拓撲排序及求關鍵路徑的算法;
6.熟練掌握求圖的最短路徑的算法;
7.掌握各種算法的效率評價;
8.圖的應用能力。
第八章 查找
考試內容
順序查找法; 折半查找法;靜態(tài)樹表的查找; 索引表的查找; 二叉排序樹的查找;平衡二叉樹的平衡方法及查找; B-和B+樹的查找;哈希技術的概念;哈希函數的構造方法; 沖突處理技術; 哈希表的查找。
考試要求
1.熟練掌握順序查找法和折半查找法及其算法，領會靜態(tài)樹表的查找和索引表的查找的思想;
2.熟練掌握二叉排序樹的查找、插入和刪除算法，掌握二叉樹的平衡方法;
3.熟練掌握B樹的查找、插入和刪除算法，領會B+樹的思想;
4.理解哈希技術的概念，熟練掌握哈希函數的構造方法和沖突處理技術，掌握哈希表的查找算法;
5.根據所給條件求裝填因子并設計合適的哈希表結構;
6.各種查找算法的性能分析及比較;
7.能根據不同情況靈活應用不同的查找方法。
第九章 內部排序
考試內容
有關概念; 直接插入排序; 折半插入排序; 2-路插入排序; 希爾排序;快速排序; 堆排序; 歸并排序; 分配排序與基數排序; 各種內部排序方法的比較。
考試要求
1.熟練掌握直接插入排序算法，領會其它插入排序方法;
2.深刻領會快速排序的思想，熟練掌握快速排序算法,弄清楚影響快速排序速度的瓶頸，掌握快速排序的遞歸算法;
3.深刻領會堆排序的思想，熟練掌握堆排序算法;
4.深刻領會分配排序和基數排序的思想，熟練掌握其排序算法，并改寫該算法使得排序僅在一維數組內完成而無須通過鏈隊實現;
5.各種內部排序方法的比較及排序算法的性能分析和評價;
6.能靈活應用各種排序方法解決實際問題
? ? 編輯推薦：
? ??2014年考研招生信息——全國院校匯總?
| 考研大綱匯總 | 考研英語大綱 | 考研政治大綱 | 考研數學大綱 | 考研專業(yè)課大綱 |