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

初試科目考試大綱
 
“數(shù)據(jù)結(jié)構(gòu)”考試大綱
一、考試的學(xué)科范圍
數(shù)據(jù)結(jié)構(gòu)課程教學(xué)（大綱）基本要求的所有內(nèi)容。
二、評價目標
主要考查考生對數(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)思想；掌握拓撲排序的概念及算法實現(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.線性表鏈式存儲結(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)與拓撲排序
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.嚴蔚敏主編，數(shù)據(jù)結(jié)構(gòu)，北京：清華大學(xué)出版社
 
 
 
 
 
 
 
 
 

東北電力大學(xué)

本文來源：http://zhangjiajieline.cn/dbdldx/cksm_398977.html