2021湖南農業大學數據結構專業研究生考試大綱 正文

I.考試性質
《數據結構》是一門專業基礎課，要求考生能夠理解數據結構的基本概念;掌握數據結構中邏輯結構、存儲結構的基本概念和差異，以及各種基本操作的實現；在掌握基本的數據處理原理和方法的基礎上，能夠對算法進行設計與分析；能夠選擇合適的數據結構和方法進行問題求解；能夠針對具體問題設計正確的數據結構加以應用；具備采用類c或c++或JAVA語言設計與實現算法的能力。
本課程包括：算法的基本概念、分析和設計方法；軟件開發中常用的各類結構，包括線性結構、樹結構、圖結構；查找、排序等各類常用算法。主要考察學生對數據結構基礎知識的理解、是否具備對現有常用結構和算法的應用能力、是否具備針對具體應用設計合適數據結構的能力。
II.考查目標
  考試目標是了解常見數據結構的概念，掌握數據結構的構造方法以及相應的算法思想，會對重點數據結構的操作方法和算法進行簡單的偽代碼編寫。
III.考試形式和試卷結構
一、試卷總分及考試時間
  試卷總分為150分，考試時間180分鐘。
二、答題方式
  答題方式為閉卷、筆試。
三、試卷內容結構
   基本概念理解 70%
   算法的應用 50%
   算法設計 30%
四、試卷題型結構
⑴選擇: 40分；
    (2)填空題 20分
⑶簡答題:30分；
⑷算法應用題:30分；
⑸算法設計題:30分。

Ⅳ．考查內容
第一章、線性表
1.線性表的邏輯結構
2.線性表的順序存儲結構
3.線性表的鏈式存儲結構
3.1單鏈表
3.2循環鏈表
3.3雙向鏈表
第二章、棧與隊列
1.棧
1.1棧的基本概念
1.2順序棧
1.3鏈式棧
2.隊列
2.1隊列的基本概念
2.2鏈隊列
2.3循環隊列——隊列的順序存儲結構
第三章、串
1.串類型的定義
2.字符串的實現
3.字符串模式匹配算法
3.1簡單字符串模式匹配算法
3.2首尾字符串模式匹配算法
3.3KMP模式匹配算法
第四章、數組和廣義表
1.數組
1.1數組的基本概念
1.2數組的順序存儲方式
2.矩陣
2.1矩陣的定義和操作
2.2特殊矩陣
2.3稀疏矩陣
3.廣義表
3.1基本概念
3.2廣義表的存儲結構
第五章、 樹和二叉樹
1.樹的基本概念
1.1樹的定義
1.2基本術語
2.二叉樹
2.1二叉樹的定義
2.2二叉樹的性質
2.3二叉樹的存儲結構
3.二叉樹的遍歷
3.1遍歷的定義
3.2遍歷算法
4.樹和森林
4.1樹的存儲表示
4.2森林的存儲表示
4.3樹和森林的遍歷
4.4樹和森林與二叉樹的轉換
5.哈夫曼樹與哈夫曼編碼
5.1哈夫曼樹的基本概念
5.2哈夫曼樹構造算法
5.3哈夫曼樹編碼
第六章、圖
1.圖的定義和術語
2.圖的存儲表示
2.1鄰接矩陣
2.2鄰接表
3.圖的遍歷
3.1深度優先搜索
3.2廣度優先搜索
4.圖的最小代價生成樹
4.1Prim算法
4.2Kruskal算法
5.有向無環圖的應用
5.1拓撲排序
5.2關鍵路徑
6.最短路徑問題
6.1單源點最短路徑
6.2所有頂點之間的最短路徑
第七章、 查找
1. 查找的基本概念
2. 靜態表的查找
2.1 順序查找
2.2 有序表的查找
3. 動態查找表
3.1 二叉排序樹
4. 散列表
4.1 散列表的概念
4.2 構造散列函數的方法
4.3 處理沖突的方法
第八章、 排序
1.排序概述
2.插入排序
2.1直接插入排序
2.2Shell排序
3.交換排序
3.1冒泡排序
3.2快速排序
4.選擇排序
4.1普通選擇排序
4.2堆排序
5.歸并排序

Ⅴ主要參考書籍
[1] 李春葆、尹為民、蔣晶玨、喻丹丹、蔣林 數據結構（第5版）。北京，清華大學出版，2017
[2] 嚴蔚敏, 吳偉民. 數據結構。 北京：清華大學出版社 ，2015

湖南農業大學

本文來源：http://m.sacvlig.cn/hunau/cankaoshumu_382148.html