2021東北電力大學(xué)數(shù)據(jù)結(jié)構(gòu)研究生考試大綱 正文

初試科目考試大綱
 
“數(shù)據(jù)結(jié)構(gòu)”考試大綱
一、考試的學(xué)科范圍
數(shù)據(jù)結(jié)構(gòu)課程教學(xué)（大綱）基本要求的所有內(nèi)容。
二、評價目標(biāo)
主要考查考生對數(shù)據(jù)結(jié)構(gòu)課程的基礎(chǔ)理論、基本知識掌握和運用的情況，要求考生應(yīng)掌握以下有關(guān)知識：
1. 數(shù)據(jù)結(jié)構(gòu)的基本概念：理解數(shù)據(jù)結(jié)構(gòu)的基本概念和常用術(shù)語，掌握算法的定義及特性，了解分析算法的時間復(fù)雜度和空間復(fù)雜度的方法。
2. 線性表：理解線性表的基本概念；掌握順序表的各種基本操作；掌握單鏈表、雙向鏈表的特點及各種基本操作；會運用線性表解決實際問題。
3. 棧和隊列：理解棧的定義及其基本運算；掌握順序棧和鏈棧的特點及各種操作實現(xiàn)；理解隊列的定義及其基本運算；掌握循環(huán)隊列的特點和各種操作實現(xiàn)；會運用棧和隊列解決實際問題。
4. 數(shù)組和廣義表：理解數(shù)組和廣義表的基本概念；掌握二維數(shù)組的存儲結(jié)構(gòu)和稀疏矩陣的壓縮存儲方法。
5. 樹和二叉樹：理解樹和二叉樹的概念；掌握二叉樹的性質(zhì)；掌握二叉樹的存儲結(jié)構(gòu)以及在該存儲結(jié)構(gòu)下各種基本操作的實現(xiàn)；掌握樹、森林與二叉樹之間的轉(zhuǎn)換關(guān)系；掌握哈夫曼樹的定義與應(yīng)用。
6. 圖：理解圖的基本概念；掌握圖的鄰接矩陣和鄰接表的存儲結(jié)構(gòu)；掌握圖的深度、廣度優(yōu)先搜索算法的基本思想；理解最小生成樹的概念；掌握最短路徑算法的實現(xiàn)思想；掌握拓?fù)渑判虻母拍罴八惴▽崿F(xiàn)思想。
7. 查找：理解查找的基本概念；掌握順序查找、折半查找、分塊查找的特點和方法；掌握二叉排序樹的構(gòu)造和查找方法；了解平衡二叉樹的構(gòu)造和查找方法；掌握哈希表的構(gòu)造和查找方法。
8. 排序：理解內(nèi)部排序、外部排序、穩(wěn)定排序、不穩(wěn)定排序等概念；掌握直接插入排序、冒泡排序、直接選擇排序等簡單的排序方法和特點；掌握希爾排序、快速排序、堆排序和歸并排序等高效排序方法和特點；了解基數(shù)排序的基本思想。
三、試題主要類型
1.答題時間：180分鐘
2.試題主要類型：選擇題，簡答題，解答題，算法題
四、考查要點
（一）數(shù)據(jù)結(jié)構(gòu)的基本概念：
1.數(shù)據(jù)結(jié)構(gòu)的基本概念。
2.算法的概念
3.算法分析方法（算法的時間、空間復(fù)雜度）
（二）線性表：
1.線性表的概念
2.線性表順序存儲結(jié)構(gòu)特點及運算算法
3.線性表鏈?zhǔn)酱鎯Y(jié)構(gòu)特點及運算算法
4.線性表的典型應(yīng)用
（三）棧和隊列：
1.棧的定義及基本運算算法
2.隊列的定義及基本運算算法
3.棧的典型應(yīng)用
4.隊列的典型應(yīng)用
（四）數(shù)組和廣義表：
1.數(shù)組的順序表示和實現(xiàn)
2.矩陣的壓縮存儲
3.廣義表的定義及其存儲結(jié)構(gòu)
（五）樹和二叉樹：
1.樹的定義及基本術(shù)語
2.樹的表示
3.樹的存儲結(jié)構(gòu)
4.二叉樹的定義及性質(zhì)
5.二叉樹的存儲結(jié)構(gòu)
6.二叉樹的遍歷算法
7.線索二叉樹
8.樹、森林與二叉樹的轉(zhuǎn)換
9.哈夫曼樹的構(gòu)造方法及應(yīng)用
（六）圖：
1.圖的定義及基本術(shù)語
2.圖的存儲結(jié)構(gòu)
3.圖的遍歷方法
4.圖的聯(lián)通性
5.圖的最短路徑算法
6.AOV網(wǎng)與拓?fù)渑判?br /> 7.AOE網(wǎng)與關(guān)鍵路徑
（七）查找：
1.查找的基本概念
2.靜態(tài)查找的順序查找、折半查找、分塊查找算法
3.動態(tài)查找表的基本概念
4.二叉排序樹的構(gòu)造方法及查找
5.平衡二叉樹查找
6.哈希法查找
（八）排序：
1.排序的基本概念
2.直接插入排序的基本思想和特點
3.希爾排序的基本思想和特點
4.折半插入排序的基本思想和特點
5.冒泡排序的基本思想和特點
6.快速排序的基本思想和特點
7.簡單選擇排序的基本思想和特點
8.堆排序的基本思想和特點
9.歸并排序的基本思想和特點
10.基數(shù)排序的基本思想和特點
11.各類排序算法的時間空、間復(fù)雜度的比較
五、主要參考書目
1.曲朝陽主編，數(shù)據(jù)結(jié)構(gòu)，北京：中國電力出版社 2016
2.嚴(yán)蔚敏主編，數(shù)據(jù)結(jié)構(gòu)，北京：清華大學(xué)出版社
 
 
 
 
 
 
 
 
 

東北電力大學(xué)

本文來源：http://www.qiang-kai.com/dbdldx/cksm_398977.html