2021吉首大學數據結構研究生考試大綱

發布時間：2020-12-07 編輯：考研派小莉 推薦訪問：
2021吉首大學數據結構研究生考試大綱

2021吉首大學數據結構研究生考試大綱內容如下，更多考研資訊請關注我們網站的更新！敬請收藏本站，或下載我們的考研派APP和考研派微信公眾號（里面有非常多的免費考研資源可以領取，有各種考研問題，也可直接加我們網站上的研究生學姐微信，全程免費答疑，助各位考研一臂之力，爭取早日考上理想中的研究生院校。）

2021吉首大學數據結構研究生考試大綱 正文

吉首大學碩士研究生入學考試自命題考試大綱（同等學力加試科目）
考試科目名稱：數據結構
一、考試形式與試卷結構
1) 試卷成績及考試時間
本試卷滿分為 100 分，考試時間為 120 分鐘。
2) 答題方式：閉卷、筆試。
3) 試卷內容結構
數據結構基本概念、算法特點及分析 5%，常用數據結構（線性表、棧、隊
列、串、數組、廣義表、樹、二叉樹、圖）的定義、表示、實現及應用 65%， 查
找和內部排序算法及分析 30%。
4) 題型結構
a: 單選題，10 小題，每小題 2 分，共 20 分。
b: 填空題，10 小題，每小題 2 空，每空 1 分，共 20 分。
c: 名詞解釋，3 小題，每小題 5 分，共 15 分。
d: 簡答題，3 小題，每小題 5 分，共 15 分。
e: 綜合應用題，2 小題，每小題 15 分，共 30 分。
二、考試內容與考試要求
1、數據結構基本概念、算法特點與分析
考試內容
數據和數據結構概念，數據結構分類，算法的定義及特性，算法效率的度量。
考試要求
（1）掌握數據結構的基本概念、相關術語
（2）掌握常用數據結構的分類。
（3）了解抽象數據類型的表示與實現方法。
1（4）掌握算法的定義、特性和度量方法。
（5）掌握算法的時間效率和空間效率的分析方法。
2、線性表表示與實現
考試內容
線性表的概念，線性表的順序表示和實現，線性表的鏈式表示及其實現方法。
考試要求
（1）掌握線性表的類型定義。
（2）掌握線性表的順序表示及其實現方法。
（3）掌握線性表的鏈式表示及其實現方法。
（4）了解線性鏈表、循環鏈表、雙向鏈表在表示、實現及應用方面的區別。
3、棧和隊列的表示與實現
考試內容
棧和隊列的概念，棧和隊列的表示及實現，棧和隊列的應用。
考試要求
（1）掌握棧的抽象數據類型定義。
（2）掌握棧的表示及其實現方法。
（3）了解棧在數制轉換、表達式求值、遞歸實現等方面的應用。
（4）掌握隊列的抽象數據類型定義。
（5）掌握隊列的鏈式表示（鏈隊列）及其實現方法。
（6）掌握隊列的順序表示（循環隊列）及其實現方法。
（7）了解隊列在事件模擬方面的應用。
4、串、數組與廣義表的表示與實現
考試內容
串類型的定義，串的表示和實現，串的模式匹配算法，數組和廣義表的定義，
數組的順序表示與實現，矩陣的壓縮存儲，廣義表的存儲結構。
考試要求
（1）掌握串類型、數組和廣義表的定義。
（2）掌握串的定長順序存儲、堆分配存儲和塊鏈存儲的表示表示及其實現
方法。
2（3）掌握串的模式匹配算法及其改進 KMP 算法。
（4）了解串操作在文本編輯、建立詞索引表等方面的應用。
（5）掌握數組的順序表示及其實現方法。
（6）了解特殊矩陣、稀疏矩陣的壓縮存儲方法。
（7）掌握廣義表的存儲結構建立方法。
（8）了解求廣義表的深度、復制廣義表等廣義表的遞歸算法。
5、樹和二叉樹的表示與實現
考試內容
樹與二叉樹的定義，二叉樹性質與存儲結構，二叉樹的遍歷，樹和森林存儲
結構與遍歷，赫夫曼樹及其應用。
考試要求
（1）掌握樹和二叉樹的定義、基本術語和性質。
（2）掌握二叉樹的存儲結構。
（3）掌握二叉樹遍歷算法。
（4）了解線索二叉樹的相關概念。
（5）了解樹和森林的定義。
（6）了解樹的存儲結構。
（7）了解森林與二叉樹的轉換算法，樹與二叉樹的等價轉換算法，樹和森
林的遍歷算法。
（8）掌握最優二叉樹（赫夫曼樹）的構造方法及其應用方法。
6、圖的表示與實現
考試內容
圖的定義與基本概念，圖的存儲結構，圖的遍歷方法，拓撲排序，關鍵路徑。
考試要求
（1）掌握圖的定義和相關術語。
（2）掌握圖的數組存儲結構和鄰接表存儲結構。
（3）掌握圖的深度優先和廣度優先搜索遍歷算法。
（4）了解無向圖的連通分量、生成樹，以及有向圖的強連通分量的概念。
（5）掌握最小生成樹構造算法。
3（6）掌握有向無環圖在拓撲排序、關鍵路徑獲取方面的應用。
（7）掌握從某個源點到其余各頂點的最短路徑求解算法。
（8）掌握每一對頂點之間的最短路徑求解算法。
7、查找算法及分析
考試內容
靜態表（順序表、有序表）的查找，動態表（二叉排序樹、平衡二叉樹、B
－樹）的查找，哈希表查找（哈希函數構造、沖突處理方法，哈希表查找分析）。
考試要求
（1）掌握順序表查找算法和有序表查找算法。
（2）了解靜態樹表查找算法和索引順序表查找算法
（3）掌握二叉排序樹和平衡二叉樹的相關概念。
（4）了解 B 樹、B+樹、鍵樹的相關概念。
（5）掌握哈希函數的構造方法、沖突處理方法。
（6）掌握哈希表的查找算法及其效率分析方法。
8、內部排序算法及分析
考試內容
插入排序算法及分析，交換排序算法及分析，快速排序算法及分析，選擇排
序算法及分析，歸并排序算法及分析，各種排序算法的比較。
考試要求
（1）掌握以希爾排序算法為代表的插入排序類算法的基本思想、排序過程
及時間復雜度分析。
（2）掌握以快速排序算法為代表的交換排序類算法的基本思想、排序過程
及時間復雜度分析。
（3）掌握以堆排序算法為代表的選擇排序類算法的基本思想、排序過程及
時間復雜度分析。
（4）掌握歸并排序算法的基本思想、排序過程及時間復雜度分析。
（5）了解基數排序（多關鍵字的排序、鏈式基數排序）算法的基本思想、
排序過程及時間復雜度分析。
（6）了解上述各種內部排序算法在算法原理及時空效率方面的區別。
4三、參考書目
[1] 嚴蔚敏、吳偉民編著，數據結構(C 語言版)，清華大學出版社，2012 年 7 月
5
吉首大學

添加吉首大學學姐微信，或微信搜索公眾號“考研派小站”，關注[考研派小站]微信公眾號，在考研派小站微信號輸入[吉首大學考研分數線、吉首大學報錄比、吉首大學考研群、吉首大學學姐微信、吉首大學考研真題、吉首大學專業目錄、吉首大學排名、吉首大學保研、吉首大學公眾號、吉首大學研究生招生）]即可在手機上查看相對應吉首大學考研信息或資源。

吉首大學考研公眾號 考研派小站公眾號

本文來源：http://www.sacvlig.cn/jsu/cankaoshumu_389313.html

推薦閱讀