甘肅農(nóng)業(yè)大學(xué) 2021 年全國(guó)碩士研究生招生考試

初試自命題科目考試大綱

科目代碼： 849 科目名稱：《數(shù)據(jù)結(jié)構(gòu)和計(jì)算機(jī)網(wǎng)絡(luò)》“數(shù)據(jù)結(jié)構(gòu)”部分

考查目標(biāo)

“數(shù)據(jù)結(jié)構(gòu)”部分涵蓋了數(shù)據(jù)邏輯結(jié)構(gòu)、數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)和算法設(shè)計(jì)與分析三方面的內(nèi)容。

要求考生熟練掌握基本的線性和非線性數(shù)據(jù)的邏輯結(jié)構(gòu)特點(diǎn)、常見物理存儲(chǔ)實(shí)現(xiàn)方法以及各

自的優(yōu)缺點(diǎn)；基本掌握針對(duì)具體問題，分析其數(shù)據(jù)結(jié)構(gòu)特點(diǎn)，設(shè)計(jì)算法解決該問題的方法和

流程；初步掌握對(duì)算法進(jìn)行時(shí)間復(fù)雜度與空間復(fù)雜度分析的方法。

試題類型 主要包括選擇題、填空題、簡(jiǎn)答題、綜合題。

參考書目

[1]《數(shù)據(jù)結(jié)構(gòu)(C 語(yǔ)言版)》，嚴(yán)蔚敏主編，北京：清華大學(xué)出版社，2020 年

[2]《數(shù)據(jù)結(jié)構(gòu)教程》（第 5 版）， 李春葆主編，北京：清華大學(xué)出版社，2017 年

[3]《數(shù)據(jù)結(jié)構(gòu)精講與習(xí)題詳解（C 語(yǔ)言版）》（第2版），殷人昆主編.北京：清華大學(xué)出版社.2018

考查內(nèi)容范圍

考試內(nèi)容將涉及如下內(nèi)容：

（1）數(shù)據(jù)結(jié)構(gòu)及算法基本概念；

（2）線性表；

（3）棧和隊(duì)列；

（4）串；

（5）遞歸；

（6）數(shù)組和稀疏矩陣；

（7）樹和二叉樹；

（8）圖；

（9）查找；

（10）內(nèi)排序。

考查學(xué)生運(yùn)用上述知識(shí)的綜合分析能力，各部分的基本內(nèi)容如下：

（一）基本概念

1.數(shù)據(jù)結(jié)構(gòu)的基本概念；

2.算法的基本概念；

3.算法描述和基本特性；

4.算法時(shí)間復(fù)雜度和空間復(fù)雜度分析。

（二）線性表

1.線性表的邏輯結(jié)構(gòu)特點(diǎn)和線性表抽象數(shù)據(jù)類型的描述方法；

2.線性表的兩種存儲(chǔ)結(jié)構(gòu)（順序存儲(chǔ)結(jié)構(gòu)及鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)）以及各自的優(yōu)缺點(diǎn)；

3.順序表增加、刪除、插入節(jié)點(diǎn)的算法；

4.單鏈表、雙鏈表和循環(huán)鏈表中增加、刪除、插入節(jié)點(diǎn)的算法。

（三）棧和隊(duì)列

1.棧的邏輯結(jié)構(gòu)特性和棧抽象數(shù)據(jù)類型的描述方法；

2.棧的先進(jìn)后出特點(diǎn)；

3.棧的基本運(yùn)算在順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)下的實(shí)現(xiàn)算法；

4.棧在實(shí)際求解問題中的應(yīng)用方法（求解簡(jiǎn)單表達(dá)式值）；

共 3 頁(yè) 第 2 頁(yè)

5.隊(duì)列的邏輯結(jié)構(gòu)特性和隊(duì)列抽象數(shù)據(jù)類型的描述方法；

6.隊(duì)列的先進(jìn)先出特點(diǎn)；

7.隊(duì)列的基本運(yùn)算在順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)下的實(shí)現(xiàn)算法；

8.循環(huán)隊(duì)列的隊(duì)空、隊(duì)滿的條件及求解隊(duì)列元素個(gè)數(shù)。

（四）串

1.串的邏輯結(jié)構(gòu)特性和串抽象數(shù)據(jù)類型的描述方法；

2.串的兩類存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)方法以及各自的優(yōu)缺點(diǎn)；

3.串模式匹配的概念、BF 算法及 KMP 算法。

（五）遞歸

1.遞歸和遞歸模型的概念；

2.遞歸算法的執(zhí)行過程；

3.遞歸算法設(shè)計(jì)的一般步驟。

（六）數(shù)組和稀疏矩陣

1.數(shù)組的邏輯結(jié)構(gòu)特性和數(shù)組抽象數(shù)據(jù)類型的描述方法；

2.數(shù)組的順序存儲(chǔ)結(jié)構(gòu)及某節(jié)點(diǎn)存儲(chǔ)地址的求解；

3.對(duì)稱矩陣、上三角矩陣、下三角矩陣和三對(duì)角矩陣的壓縮存儲(chǔ)；

4.稀疏矩陣的兩種壓縮存儲(chǔ)方法（三元組表和十字鏈表）；

5.廣義表的概念及求廣義表的表頭、表尾及深度。

（七）樹和二叉樹

1.樹的定義及其邏輯結(jié)構(gòu)特性；

2.樹的遍歷方法和樹的存儲(chǔ)結(jié)構(gòu)；

3.二叉樹的定義及其主要的五種性質(zhì)；

4.二叉樹與樹、森林之間的轉(zhuǎn)換；

5.二叉樹的兩種存儲(chǔ)結(jié)構(gòu)（順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)）和二叉樹的基本運(yùn)算算

法設(shè)計(jì)（求某結(jié)點(diǎn)的雙親、孩子節(jié)點(diǎn)及二叉樹深度）；

6.二叉樹的遍歷過程、（前序、中序、后序遍歷）算法設(shè)計(jì)及其應(yīng)用；

7.線索的概念，線索二叉樹的特點(diǎn)及其構(gòu)造過程；

8.哈夫曼樹和哈夫曼編碼的構(gòu)造過程，WPL 的求值。

（八）圖

1.圖的定義及其邏輯結(jié)構(gòu)特性，圖抽象數(shù)據(jù)類型的描述方法；

2.圖的基本術(shù)語(yǔ)及其含義；

3.圖的兩種主要的存儲(chǔ)結(jié)構(gòu)（鄰接矩陣和鄰接表）及其特點(diǎn)；

4.圖的深度優(yōu)先和廣度優(yōu)先遍歷算法；

5.生成樹的概念和最小生成樹的定義和求最小生成樹的 Prim 和 Kruskal 算法；

6.最短路徑的概念和求最短路徑的 Dijkstra 和 Flody 算法；

7.拓?fù)渑判蜻^程；

8.關(guān)鍵路徑的定義及其構(gòu)造過程。

（九）查找

1.掌握查找的概念；

2.線性表的順序查找和折半查找算法，索引存儲(chǔ)結(jié)構(gòu)和分塊查找方法；

3.二叉排序樹的定義、查找和插入算法、刪除過程；

4.平衡二叉樹的特點(diǎn)及其調(diào)整方法；

5.B-樹的定義和插入刪除結(jié)點(diǎn)的操作過程，B+樹的定義；

6.哈希表的定義、特點(diǎn)；

7.哈希函數(shù)構(gòu)造方法和解決沖突的方法；

共 3 頁(yè) 第 3 頁(yè)

8.如何構(gòu)造哈希表；

9.各種不同查找方法的性能（時(shí)空復(fù)雜度）比較和分析。

（十）內(nèi)排序

1.排序的定義和相關(guān)概念；

2.插入排序算法，包括直接插入排序、折半插入排序和希爾排序；

3.交換排序算法，包括冒泡排序和快速排序；

4.選擇排序算法，包括簡(jiǎn)單選擇排序和堆排序；

5.歸并排序算法，包括二路歸并排序；

6.基數(shù)排序算法，包括最低位優(yōu)先和最高位優(yōu)先排序；

7.各種內(nèi)排序方法的性能（時(shí)空復(fù)雜度）分析和比較。

原文標(biāo)題：甘肅農(nóng)業(yè)大學(xué)2021年全國(guó)碩士研究生招生考試初試自命題科目考試大綱

原文鏈接：https://yjsy.gsau.edu.cn/info/1010/88143.htm