甘肅農業大學 2021 年全國碩士研究生招生考試

初試自命題科目考試大綱

科目代碼： 849 科目名稱：《數據結構和計算機網絡》“數據結構”部分

考查目標

“數據結構”部分涵蓋了數據邏輯結構、數據存儲結構和算法設計與分析三方面的內容。

要求考生熟練掌握基本的線性和非線性數據的邏輯結構特點、常見物理存儲實現方法以及各

自的優缺點；基本掌握針對具體問題，分析其數據結構特點，設計算法解決該問題的方法和

流程；初步掌握對算法進行時間復雜度與空間復雜度分析的方法。

試題類型 主要包括選擇題、填空題、簡答題、綜合題。

參考書目

[1]《數據結構(C 語言版)》，嚴蔚敏主編，北京：清華大學出版社，2020 年

[2]《數據結構教程》（第 5 版）， 李春葆主編，北京：清華大學出版社，2017 年

[3]《數據結構精講與習題詳解（C 語言版）》（第2版），殷人昆主編.北京：清華大學出版社.2018

考查內容范圍

考試內容將涉及如下內容：

（1）數據結構及算法基本概念；

（2）線性表；

（3）棧和隊列；

（4）串；

（5）遞歸；

（6）數組和稀疏矩陣；

（7）樹和二叉樹；

（8）圖；

（9）查找；

（10）內排序。

考查學生運用上述知識的綜合分析能力，各部分的基本內容如下：

（一）基本概念

1.數據結構的基本概念；

2.算法的基本概念；

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

4.算法時間復雜度和空間復雜度分析。

（二）線性表

1.線性表的邏輯結構特點和線性表抽象數據類型的描述方法；

2.線性表的兩種存儲結構（順序存儲結構及鏈式存儲結構）以及各自的優缺點；

3.順序表增加、刪除、插入節點的算法；

4.單鏈表、雙鏈表和循環鏈表中增加、刪除、插入節點的算法。

（三）棧和隊列

1.棧的邏輯結構特性和棧抽象數據類型的描述方法；

2.棧的先進后出特點；

3.棧的基本運算在順序存儲結構和鏈式存儲結構下的實現算法；

4.棧在實際求解問題中的應用方法（求解簡單表達式值）；

共 3 頁 第 2 頁

5.隊列的邏輯結構特性和隊列抽象數據類型的描述方法；

6.隊列的先進先出特點；

7.隊列的基本運算在順序存儲結構和鏈式存儲結構下的實現算法；

8.循環隊列的隊空、隊滿的條件及求解隊列元素個數。

（四）串

1.串的邏輯結構特性和串抽象數據類型的描述方法；

2.串的兩類存儲結構設計方法以及各自的優缺點；

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

（五）遞歸

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

2.遞歸算法的執行過程；

3.遞歸算法設計的一般步驟。

（六）數組和稀疏矩陣

1.數組的邏輯結構特性和數組抽象數據類型的描述方法；

2.數組的順序存儲結構及某節點存儲地址的求解；

3.對稱矩陣、上三角矩陣、下三角矩陣和三對角矩陣的壓縮存儲；

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

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

（七）樹和二叉樹

1.樹的定義及其邏輯結構特性；

2.樹的遍歷方法和樹的存儲結構；

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

4.二叉樹與樹、森林之間的轉換；

5.二叉樹的兩種存儲結構（順序存儲結構和鏈式存儲結構）和二叉樹的基本運算算

法設計（求某結點的雙親、孩子節點及二叉樹深度）；

6.二叉樹的遍歷過程、（前序、中序、后序遍歷）算法設計及其應用；

7.線索的概念，線索二叉樹的特點及其構造過程；

8.哈夫曼樹和哈夫曼編碼的構造過程，WPL 的求值。

（八）圖

1.圖的定義及其邏輯結構特性，圖抽象數據類型的描述方法；

2.圖的基本術語及其含義；

3.圖的兩種主要的存儲結構（鄰接矩陣和鄰接表）及其特點；

4.圖的深度優先和廣度優先遍歷算法；

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

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

7.拓撲排序過程；

8.關鍵路徑的定義及其構造過程。

（九）查找

1.掌握查找的概念；

2.線性表的順序查找和折半查找算法，索引存儲結構和分塊查找方法；

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

4.平衡二叉樹的特點及其調整方法；

5.B-樹的定義和插入刪除結點的操作過程，B+樹的定義；

6.哈希表的定義、特點；

7.哈希函數構造方法和解決沖突的方法；

共 3 頁 第 3 頁

8.如何構造哈希表；

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

（十）內排序

1.排序的定義和相關概念；

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

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

4.選擇排序算法，包括簡單選擇排序和堆排序；

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

6.基數排序算法，包括最低位優先和最高位優先排序；

7.各種內排序方法的性能（時空復雜度）分析和比較。

原文標題：甘肅農業大學2021年全國碩士研究生招生考試初試自命題科目考試大綱

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