科目代碼：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á)式值）；

    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)造方法和解決沖突的方法；

添加甘肅農(nóng)業(yè)大學(xué)學(xué)姐微信，或微信搜索公眾號(hào)“考研派小站”，關(guān)注[考研派小站]微信公眾號(hào)，在考研派小站微信號(hào)輸入[甘肅農(nóng)業(yè)大學(xué)考研分?jǐn)?shù)線、甘肅農(nóng)業(yè)大學(xué)報(bào)錄比、甘肅農(nóng)業(yè)大學(xué)考研群、甘肅農(nóng)業(yè)大學(xué)學(xué)姐微信、甘肅農(nóng)業(yè)大學(xué)考研真題、甘肅農(nóng)業(yè)大學(xué)專業(yè)目錄、甘肅農(nóng)業(yè)大學(xué)排名、甘肅農(nóng)業(yè)大學(xué)保研、甘肅農(nóng)業(yè)大學(xué)公眾號(hào)、甘肅農(nóng)業(yè)大學(xué)研究生招生）]即可在手機(jī)上查看相對(duì)應(yīng)甘肅農(nóng)業(yè)大學(xué)考研信息或資源。