華北水利水電大學(xué)

2021 年碩士研究生入學(xué)考試初試科目考試大綱

數(shù)據(jù)結(jié)構(gòu)（科目代碼：967）考試大綱

考試形式和試卷結(jié)構(gòu)

一、試卷分值及考試時間

考試時間 180 分鐘（3 個小時），滿分 150 分。

二、考試基本要求

數(shù)據(jù)結(jié)構(gòu)是軟件工程、計算機(jī)技術(shù)、農(nóng)業(yè)信息化專業(yè)碩士研究生入學(xué)考試中專業(yè)課考試內(nèi)容，主要考

查：（1）掌握數(shù)據(jù)結(jié)構(gòu)的基本概念、基本原理和基本方法；（2）掌握數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及基本操

作的實現(xiàn)，能夠?qū)λ惴ㄟM(jìn)行基本的時間復(fù)雜度與空間復(fù)雜度的分析；（3）能夠運用數(shù)據(jù)結(jié)構(gòu)的基本原理和

方法進(jìn)行問題的分析與求解，具備采用 C、C++語言設(shè)計與實現(xiàn)算法的能力。

三、試卷內(nèi)容及結(jié)構(gòu)

（一）數(shù)據(jù)結(jié)構(gòu)和算法

1．?dāng)?shù)據(jù)結(jié)構(gòu)的基本概念

2．抽象數(shù)據(jù)結(jié)構(gòu)類型的表示與實現(xiàn)

3．算法的重要特性

4．算法時間復(fù)雜度、空間復(fù)雜度的分析方法

（二）線性表

1．線性表的定義和基本操作

2．線性表的順序表示和實現(xiàn)

3．線性表的鏈?zhǔn)奖硎竞蛯崿F(xiàn)

4．線性表的應(yīng)用

（三）棧和隊列

1．棧和隊列的基本概念

2．棧和隊列的順序存儲結(jié)構(gòu)

3．棧和隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)

4．棧和隊列的應(yīng)用

（四）串和數(shù)組

1．串的基本概念

2．串的存儲結(jié)構(gòu)和基本運算

3．?dāng)?shù)組的順序存儲

4．特殊矩陣的壓縮存儲

（五）樹和二叉樹

1．樹的基本概念

2．二叉樹

3．遍歷二叉樹

4．線索二叉樹

5．樹和森林與二叉樹的轉(zhuǎn)換，樹和森林的遍歷

6．哈夫曼樹和哈夫曼編碼

（六）圖1．圖的基本概念

2．圖的存儲結(jié)構(gòu)（鄰接矩陣和鄰接表）

3．圖的遍歷

4．最小生成樹

5．拓?fù)渑判蚺c關(guān)鍵路徑

6．最短路徑

（七）查找

1．查找的基本概念

2．順序查找

3．折半查找

4．動態(tài)查找表，二叉排序樹和平衡二叉樹

5．哈希表

（八）內(nèi)部排序

1．排序的基本概念

2．插入排序：直接插入排序、折半插入排序、希爾排序

3．交換排序：冒泡排序、快速排序

4．選擇排序：簡單選擇排序、堆排序

5．歸并排序

6．基數(shù)排序

7．各種排序方法的比較

四、試卷題型結(jié)構(gòu)

主要題型有：選擇題（20 分）、簡答題（20 分）、應(yīng)用題（50 分）、算法題（60 分）。試卷滿分為 150

分。

命題學(xué)院（簽蓋）：

年

月

日

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