五邑大學2021年碩士研究生招生考試

《數據結構》考試大綱

一、        基本要求

掌握數據結構的基本概念、基本分析方法和基本算法，包括數據結構的基本概念、線性表、棧和隊列、樹和二叉樹、圖、查找技術以及排序技術。

二、        考試范圍

第1章 緒論

1.1 數據結構在程序設計中的作用（C）

1.2 不作要求

1.3 數據結構的基本概念（B）

1.4 算法及算法分析（A）

第2章 線性表

2.1 線性表的邏輯結構（B）

2.2 線性表的順序存儲結構及其實現（A）

2.3 線性表的鏈接存儲結構及其實現（A）

2.4 順序表和鏈表的比較（C）

第3章 棧和隊列

3.1 棧

3.1.1 棧的邏輯結構 （B）

3.1.2 棧的順序存儲結構及其實現（A）

3.1.3 棧的鏈接存儲結構及其實現（B）

3.1.4 順序棧和鏈棧的比較 （B）

3.2 隊列

3.2.1 隊列的邏輯結構 （B）

3.2.2 隊列的順序存儲結構及其實現（A）

3.2.3 隊列的鏈接存儲結構及其實現（B）

3.2.4 循環隊列和鏈隊列的比較 （C）

3.3 應用舉例

3.3.1 棧的應用—表達式求值 （A）

3.3.2 隊列的應用—火車車廂重排（B）

第4章 字符串和多維數組

4.1 字符串（B）

4.2 多維數組（B）

4.3 矩陣的壓縮存儲（A）

4.4 應用舉例（C）

第5章 樹和二叉樹

5.1 樹的邏輯結構（B）

5.2 樹的存儲結構（C）

5.3 二叉樹的邏輯結構（A）

5.4 二叉樹的存儲結構及實現

5.4.1 順序存儲結構 （B）

5.4.2 二叉鏈表（A）

5.4.3 三叉鏈表（C）

5.4.4 線索鏈表（C）

5.5 二叉樹的遍歷非遞歸算法（B）

5.6 樹、森林與二叉樹的轉換（A）

5.7 應用舉例

5.7.1 二叉樹的應用舉例—哈夫曼樹及哈夫曼編碼 （A）

5.7.2 樹的應用舉例—八枚硬幣問題（C）

第6章 圖

6.1 圖的邏輯結構（A）

6.2 圖的存儲結構及實現

6.2.1 鄰接矩陣 （A）

6.2.2 鄰接表（A）

6.2.3 十字鏈表（C）

6.2.4 鄰接多重表（C）

6.2.5鄰接矩陣和鄰接表的比較（C）

6.3 最小生成樹（A）

6.4 最短路徑（B）

6.5 有向無環圖及其應用（A）

第7章 查找技術

7.1 概述：查找的基本概念（A）

7.2 線性表的查找技術（B）

7.3 樹表的查找技術（A）

7.4 散列表的查找技術（A）

第8章 排序技術

8.1概述：排序的基本概念（A）

8.2 插入排序 （A）

8.3 交換排序 （B）

8.4 選擇排序 （A）

8.5 歸并排序 （A）

8.6 分配排序 （C）

8.7 各種排序方法的比較 （B）

（上述內容中，A的內容是重點，要求學生掌握；B的內容要求學生熟悉；C的內容要求學生了解。）

三、        參考書目

1. 王紅梅等編，數據結構（C++版）（第2版） [M]. 北京：清華大學出版社，2011.06

2. 王紅梅等編，數據結構（C++版）學習輔導與實驗指導（第2版） [M]. 北京：清華大學出版社，2011.09

3. 嚴蔚敏，數據結構（C語言）[M]. 北京：清華大學出版社，2015.03

4. 周桂紅，數據結構[M]。 天津：南開大學出版社，2016.09