2020年臨沂大學(xué)數(shù)據(jù)結(jié)構(gòu)研究生考試大綱 正文

考試科目名稱：數(shù)據(jù)結(jié)構(gòu)    考試時間：180分鐘，滿分：150分
一、 考試要求
1.掌握邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)、算法、數(shù)據(jù)類型等基本概念及算法時間復(fù)雜度求法。
2.掌握線性表、樹、圖等基本數(shù)據(jù)結(jié)構(gòu)的有關(guān)概念以及相關(guān)算法。
3.掌握順序查找、折半查找、二叉排序樹和哈希表查找算法的基本思想及性能分析。
4.掌握內(nèi)部排序算法的基本思想、特點(diǎn)及性能分析。
二、考試內(nèi)容
1.基本概念和算法分析
（1）數(shù)據(jù)結(jié)構(gòu)的基本概念及它們之間的關(guān)系；
（2）算法的概念以及基本要求；
（3）算法時間復(fù)雜度的分析。
2.線性表
（1）線性表的邏輯結(jié)構(gòu)；
（2）線性表的順序存儲結(jié)構(gòu)以及基本算法編寫；
（3）線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)以及基本算法編寫；
（4）線性表的兩種存儲結(jié)構(gòu)、操作實(shí)現(xiàn)的異同點(diǎn)和優(yōu)缺點(diǎn)。
3.棧和隊(duì)列
（1）棧的定義和實(shí)現(xiàn)；
（2）棧的應(yīng)用；
（3）隊(duì)列定義以及實(shí)現(xiàn)。
4.樹和二叉樹
（1）樹、二叉樹的定義及二叉樹性質(zhì)；
（2）二叉樹的存儲結(jié)構(gòu)；
（3）二叉樹的遍歷操作以及常見遞歸算法編寫；
（4）樹與森林的存儲結(jié)構(gòu)及和二叉樹的轉(zhuǎn)換；
（5）哈夫曼樹的構(gòu)造及編碼。
5.圖
（1）圖的基本概念與術(shù)語；
（2）圖的存儲結(jié)構(gòu)（鄰接矩陣、鄰接表）；
（3）圖的遍歷方法（深度優(yōu)先遍歷、廣度優(yōu)先遍歷）；
（4）求連通圖的最小生成樹；
（5）對有向無環(huán)圖進(jìn)行拓?fù)渑判蚝颓箨P(guān)鍵路徑；
（6）求圖的最短路徑。
6.查找
（1）查找的基本概念；
（2）順序查找法；
（3）折半查找法；
（4）二叉排序樹及平衡二叉樹；
（5）B-樹概念及插入、刪除操作；
（6）散列（Hash）查找；
（6）各種查找算法的時間復(fù)雜度、平均查找長度的分析。
7.內(nèi)部排序
（1）排序的基本概念；
（2）插入類排序（直接插入排序、希爾排序）；
（3）交換類排序（冒泡排序、快速排序）；
（4）選擇類排序（簡單選擇排序、堆排序）；
（5）歸并類排序（二路歸并排序）；
（6）各種常用內(nèi)部排序算法的特點(diǎn)及排序性能分析。
三、參考書目
《數(shù)據(jù)結(jié)構(gòu)（C語言版）》( 第2版），嚴(yán)蔚敏、李冬梅、吳偉民著，人民郵電出版社，2015年。

臨沂大學(xué)

本文來源：http://www.lyhuahuisp.com/lydx/cksm_354215.html