2021年贛南師范大學碩士研究生入學考試考研大綱

《電子信息》專業復試考試大綱

一、    考試形式

筆試。

二、    考試科目

《數據結構基礎》。

三、    試卷滿分及考試時間

試卷滿分：100分

考試時間：2小時

四、    考試題型

選擇題、綜合應用題、算法設計題

五、    不同性質考試內容所占比重

選擇題（30%）、綜合應用題（50%）、算法設計題（20%）

六、    參考書目

李春葆.數據結構教程(第4版).清華大學出版社

七、    考試大綱

第1章  緒論

本章重點： 數據結構的相關基本概念，算法的概念以及評價標準。

考核要求：

1、掌握數據結構的基本概念和術語；

2、掌握抽象數據類型的表示與實現；

3、理解算法的概念和算法的相關分析。

第2章  線性表

本章重點： 線性表的定義和特點，線性表的順序存儲結構、線性表的鏈式存儲結構。

考核要求：

1、掌握線性表的類型定義；

2、掌握線性表的邏輯結構和相關基本概念；

3、掌握順序表的定義和數據元素的存儲位置的計算；

4、掌握線性鏈表的定義及其存儲結構；

5、掌握單循環鏈表的相關定義和運算操作；

6、理解雙向鏈表的相關定義和雙向循環鏈表的相關定義。

第3章  棧和隊列

本章重點：棧和隊列的邏輯概念和特點，棧和隊列的存儲結構及其基本操作，循環隊列。

考核要求：

1、掌握棧的相關定義和表示；

2、掌握順序棧的存儲結構和基本操作；

3、掌握鏈棧的定義和基本操作；

4、了解棧的應用；

5、掌握的隊列的定義和抽象類型；

6、理解隊列的表示和實現。

  第4章 字符串

本章重點： 串的定義、存儲結構和基本操作。

考核要求：

1、掌握串的相關定義及其表示和實現；

2、掌握串的基本操作；

3、了解串的模式匹配。

第5章 數組和廣義表*

本章重量： 數組的定義、基本運算和存儲結構，特殊矩陣的壓縮存儲，廣義表的定義、存儲結構及運算。

考核要求：

1、掌握數組的基本概念；

2、掌握數組的存儲結構、隨機存取方法；

3、了解特殊矩陣的壓縮存儲

4、掌握稀疏矩陣的三元組表示

5、了解稀疏矩陣的十字鏈表表示

6、了解廣義表的定義、廣義表的存儲結構及基本運算

第6章  二叉樹和樹

本章重點：二叉樹的概念，二叉樹的性質，二叉樹的周游，哈夫曼樹及其應用。

考核要求：

1、掌握樹的定義和基本概念；

2、掌握二叉樹的定義及其相關概念；

3、掌握二叉樹的周游和線索二叉樹的操作和周游；

4、掌握樹和樹林的存儲結構和周游；

5、掌握樹林與二叉樹的轉換；

6、理解哈夫曼樹及其應用。

第7章  圖

本章重點： 圖的基本概念及存儲結構，圖的遍歷操作，最小生成樹，拓樸排序、關鍵路徑。

考核要求：

1、掌握圖的基本概念和存儲結構；

2、掌握圖的周游；

3、掌握圖的最小生成樹的性質及構造方法；

4、了解Dijkstra算法和Floyd算法；

5、掌握拓樸排序的方法和求關鍵路徑的方法。

第8章  查找

本章重點：折半查找、二叉排序樹、散列表及查找算法。

考核要求：

1、掌握查找的基本概念；

2、順序查找和折半查找；

3、掌握哈希表的相關概念；

4、掌握處理沖突的方法；

5、掌握哈希表的查找及其分析；

6、掌握最佳二叉排序的構造方法；熟練掌握二叉排序樹的檢索、插入和刪除；

7、了解調整平衡的模式；

8、了解Ｂ樹和Ｂ＋樹。

第9章  內排序

本章重點：排序的基本概念，快速排序、堆排序、歸并排序、希爾排序、基數排序的方法。

考核要求：

1、掌握排序的定義和分類；

2、掌握插入排序和折半插入排序的思想；

3、掌握希爾排序的思想和方法實現；

4、熟練掌握冒泡排序和快速排序的思想和算法實現；

5、熟練掌握選擇排序，堆排序的思想和算法實現；

6、了解歸并排序的思想。