甘肅農(nóng)業(yè)大學(xué) 2021 年全國碩士研究生招生考試
初試自命題科目考試大綱
科目代碼: 849 科目名稱:《數(shù)據(jù)結(jié)構(gòu)和計算機(jī)網(wǎng)絡(luò)》“數(shù)據(jù)結(jié)構(gòu)”部分
考查目標(biāo)
“數(shù)據(jù)結(jié)構(gòu)”部分涵蓋了數(shù)據(jù)邏輯結(jié)構(gòu)、數(shù)據(jù)存儲結(jié)構(gòu)和算法設(shè)計與分析三方面的內(nèi)容。
要求考生熟練掌握基本的線性和非線性數(shù)據(jù)的邏輯結(jié)構(gòu)特點、常見物理存儲實現(xiàn)方法以及各
自的優(yōu)缺點;基本掌握針對具體問題,分析其數(shù)據(jù)結(jié)構(gòu)特點,設(shè)計算法解決該問題的方法和
流程;初步掌握對算法進(jìn)行時間復(fù)雜度與空間復(fù)雜度分析的方法。
試題類型 主要包括選擇題、填空題、簡答題、綜合題。
參考書目
[1]《數(shù)據(jù)結(jié)構(gòu)(C 語言版)》,嚴(yán)蔚敏主編,北京:清華大學(xué)出版社,2020 年
[2]《數(shù)據(jù)結(jié)構(gòu)教程》(第 5 版), 李春葆主編,北京:清華大學(xué)出版社,2017 年
[3]《數(shù)據(jù)結(jié)構(gòu)精講與習(xí)題詳解(C 語言版)》(第2版),殷人昆主編.北京:清華大學(xué)出版社.2018
考查內(nèi)容范圍
考試內(nèi)容將涉及如下內(nèi)容:
(1)數(shù)據(jù)結(jié)構(gòu)及算法基本概念;
(2)線性表;
(3)棧和隊列;
(4)串;
(5)遞歸;
(6)數(shù)組和稀疏矩陣;
(7)樹和二叉樹;
(8)圖;
(9)查找;
(10)內(nèi)排序。
考查學(xué)生運用上述知識的綜合分析能力,各部分的基本內(nèi)容如下:
(一)基本概念
1.數(shù)據(jù)結(jié)構(gòu)的基本概念;
2.算法的基本概念;
3.算法描述和基本特性;
4.算法時間復(fù)雜度和空間復(fù)雜度分析。
(二)線性表
1.線性表的邏輯結(jié)構(gòu)特點和線性表抽象數(shù)據(jù)類型的描述方法;
2.線性表的兩種存儲結(jié)構(gòu)(順序存儲結(jié)構(gòu)及鏈?zhǔn)酱鎯Y(jié)構(gòu))以及各自的優(yōu)缺點;
3.順序表增加、刪除、插入節(jié)點的算法;
4.單鏈表、雙鏈表和循環(huán)鏈表中增加、刪除、插入節(jié)點的算法。
(三)棧和隊列
1.棧的邏輯結(jié)構(gòu)特性和棧抽象數(shù)據(jù)類型的描述方法;
2.棧的先進(jìn)后出特點;
3.棧的基本運算在順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)下的實現(xiàn)算法;
4.棧在實際求解問題中的應(yīng)用方法(求解簡單表達(dá)式值);
共 3 頁 第 2 頁
5.隊列的邏輯結(jié)構(gòu)特性和隊列抽象數(shù)據(jù)類型的描述方法;
6.隊列的先進(jìn)先出特點;
7.隊列的基本運算在順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)下的實現(xiàn)算法;
8.循環(huán)隊列的隊空、隊滿的條件及求解隊列元素個數(shù)。
(四)串
1.串的邏輯結(jié)構(gòu)特性和串抽象數(shù)據(jù)類型的描述方法;
2.串的兩類存儲結(jié)構(gòu)設(shè)計方法以及各自的優(yōu)缺點;
3.串模式匹配的概念、BF 算法及 KMP 算法。
(五)遞歸
1.遞歸和遞歸模型的概念;
2.遞歸算法的執(zhí)行過程;
3.遞歸算法設(shè)計的一般步驟。
(六)數(shù)組和稀疏矩陣
1.數(shù)組的邏輯結(jié)構(gòu)特性和數(shù)組抽象數(shù)據(jù)類型的描述方法;
2.數(shù)組的順序存儲結(jié)構(gòu)及某節(jié)點存儲地址的求解;
3.對稱矩陣、上三角矩陣、下三角矩陣和三對角矩陣的壓縮存儲;
4.稀疏矩陣的兩種壓縮存儲方法(三元組表和十字鏈表);
5.廣義表的概念及求廣義表的表頭、表尾及深度。
(七)樹和二叉樹
1.樹的定義及其邏輯結(jié)構(gòu)特性;
2.樹的遍歷方法和樹的存儲結(jié)構(gòu);
3.二叉樹的定義及其主要的五種性質(zhì);
4.二叉樹與樹、森林之間的轉(zhuǎn)換;
5.二叉樹的兩種存儲結(jié)構(gòu)(順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu))和二叉樹的基本運算算
法設(shè)計(求某結(jié)點的雙親、孩子節(jié)點及二叉樹深度);
6.二叉樹的遍歷過程、(前序、中序、后序遍歷)算法設(shè)計及其應(yīng)用;
7.線索的概念,線索二叉樹的特點及其構(gòu)造過程;
8.哈夫曼樹和哈夫曼編碼的構(gòu)造過程,WPL 的求值。
(八)圖
1.圖的定義及其邏輯結(jié)構(gòu)特性,圖抽象數(shù)據(jù)類型的描述方法;
2.圖的基本術(shù)語及其含義;
3.圖的兩種主要的存儲結(jié)構(gòu)(鄰接矩陣和鄰接表)及其特點;
4.圖的深度優(yōu)先和廣度優(yōu)先遍歷算法;
5.生成樹的概念和最小生成樹的定義和求最小生成樹的 Prim 和 Kruskal 算法;
6.最短路徑的概念和求最短路徑的 Dijkstra 和 Flody 算法;
7.拓?fù)渑判蜻^程;
8.關(guān)鍵路徑的定義及其構(gòu)造過程。
(九)查找
1.掌握查找的概念;
2.線性表的順序查找和折半查找算法,索引存儲結(jié)構(gòu)和分塊查找方法;
3.二叉排序樹的定義、查找和插入算法、刪除過程;
4.平衡二叉樹的特點及其調(diào)整方法;
5.B-樹的定義和插入刪除結(jié)點的操作過程,B+樹的定義;
6.哈希表的定義、特點;
7.哈希函數(shù)構(gòu)造方法和解決沖突的方法;
共 3 頁 第 3 頁
8.如何構(gòu)造哈希表;
9.各種不同查找方法的性能(時空復(fù)雜度)比較和分析。
(十)內(nèi)排序
1.排序的定義和相關(guān)概念;
2.插入排序算法,包括直接插入排序、折半插入排序和希爾排序;
3.交換排序算法,包括冒泡排序和快速排序;
4.選擇排序算法,包括簡單選擇排序和堆排序;
5.歸并排序算法,包括二路歸并排序;
6.基數(shù)排序算法,包括最低位優(yōu)先和最高位優(yōu)先排序;
7.各種內(nèi)排序方法的性能(時空復(fù)雜度)分析和比較。
原文標(biāo)題:甘肅農(nóng)業(yè)大學(xué)2021年全國碩士研究生招生考試初試自命題科目考試大綱
原文鏈接:https://yjsy.gsau.edu.cn/info/1010/88143.htm
以上就是研線網(wǎng)小編整理“2021考研參考書目:甘肅農(nóng)業(yè)大學(xué)《數(shù)據(jù)結(jié)構(gòu)和計算機(jī)網(wǎng)絡(luò)》“數(shù)據(jù)結(jié)構(gòu)”部分2021年碩士研究生招生參考書目”的全部內(nèi)容,更多參考書目信息,請持續(xù)關(guān)注研線網(wǎng)!