2021年碩士研究生考試復試 數據結構 科目考試大綱

一、考查目標

《數據結構》是計算機科學中的一門重要的基礎理論課，該課程考核的內容主要包括復雜度分析、鏈表、棧和隊列、遞歸、二叉樹、B-樹、圖、堆與優先級隊列、排序、哈希方法等。通過本課程學習，理解計算機加工的數據結構的特性，掌握各類數據結構的靈活應用，為應用涉及的數據選擇適當的邏輯結構、存儲結構及其相應的算法，并掌握算法的時間復雜度和空間復雜度的簡要分析技術。

二、考核形式與試卷結構

(一)試卷滿分及考試時間

滿分為100分，考試時間為2小時。

(二)答題方式

答題方式為閉卷、筆試。

(三)試卷內容結構

客觀題，包括選擇題、填空題、判斷題。主觀題，包括程序設計和代碼編寫題。

(四)試卷題型結構

客觀題20%—30%分，程序設計和代碼編寫題占70%—80%分。

三、考查內容及要求

(一)數據結構和算法簡介

1. 數據結構、邏輯結構、存儲結構和抽象數據類型的基本概念。

2. 各種算法描述方法和算法設計。

3. 算法的復雜度分析。

(二)線性結構

1. 線性表的概念、定義、邏輯結構和存儲結構。

2. 掌握線性表的順序結構及其各種基本運算。

3. 單鏈表、循環鏈表、雙向鏈表的存儲結構及其各種基本運算，鏈表的應用。

4. 棧的定義、表示、實現和應用。

5. 遞歸的概念和遞歸的實現過程。

6. 隊列的定義以及順序和鏈式存儲結構的實現。

7. 串的基本概念及順序和鏈式存儲結構，串的各種基本運算，串的模式匹配算法。

8. 數組的順序存儲結構。

9. 稀疏矩陣的三元組存儲結構和基本運算，十字鏈表存儲結構。

10. 廣義表的基本概念，廣義表的存儲結構。

(三)樹結構

1. 樹的基本概念及其存儲結構。

2. 掌握二叉樹的定義、性質以及各種存儲結構和遍歷算法。

3. 線索二叉樹的概念、存儲結構及線索化算法。

4. 哈夫曼樹的概念、存儲結構和應用。

(四)圖結構

1. 圖的基本概念，掌握圖的鄰接矩陣和鄰接表的存儲結構。

2. 十字鏈表，鄰接多重表等存儲結構。

3. 掌握圖的深度優先和廣度優先遍歷算法。

4. 圖的連通性、最小生成樹的概念。

5. 求最小生成樹算法。

(五)查找

1. 查找的概念及其效率的評價方法。

2. 靜態查找表的概念，熟練掌握順序、折半和分塊查找算法。

3. 動態查找表和二叉排序樹的概念。

4. 平衡二叉樹的概念。

5. 哈希表的含義，掌握哈希函數的構造和處理沖突的基本方法。

(六)排序

1. 插入類排序的算法：直接插入排序、希爾排序。

2. 交換類排序的算法：冒泡排序、快速排序。

3. 選擇類排序的算法：簡單選擇排序、堆排序。

4. 歸并排序、基數排序的思想，外排序的概念。

四、考試用具說明

考試時僅需要攜帶筆。

五、參考書目或參考資料

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