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

    考查目標“數(shù)據(jù)結構”部分涵蓋了數(shù)據(jù)邏輯結構、數(shù)據(jù)存儲結構和算法設計與分析三方面的內容。要求考生熟練掌握基本的線性和非線性數(shù)據(jù)的邏輯結構特點、常見物理存儲實現(xiàn)方法以及各自的優(yōu)缺點；基本掌握針對具體問題，分析其數(shù)據(jù)結構特點，設計算法解決該問題的方法和

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

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

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

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

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

    社.2018

    考查

    內容

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

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

    （2）線性表；

    （3）棧和隊列；

    （4）串；

    （5）遞歸；

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

    （7）樹和二叉樹；

    （8）圖；

    （9）查找；

    （10）內排序。

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

    （一）基本概念

    1.數(shù)據(jù)結構的基本概念；

    2.算法的基本概念；

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

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

    （二）線性表

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

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

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

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

    （三）棧和隊列

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

    2.棧的先進后出特點；

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

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

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

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

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

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

    （四）串

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

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

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

    （五）遞歸

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

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

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

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

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

    2.數(shù)組的順序存儲結構及某節(jié)點存儲地址的求解；

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

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

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

    （七）樹和二叉樹

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

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

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

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

    5.二叉樹的兩種存儲結構（順序存儲結構和鏈式存儲結構）和二叉樹的基本運算算法設計（求某結點的雙親、孩子節(jié)點及二叉樹深度）；

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

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

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

    （八）圖

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

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

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

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

    5.生成樹的概念和最小生成樹的定義和求最小生成樹的Prim和Kruskal算法；6.最短路徑的概念和求最短路徑的Dijkstra和Flody算法；

    7.拓撲排序過程；

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

    （九）查找

    1.掌握查找的概念；

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

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

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

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

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

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

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