2020年臨沂大學數(shù)據(jù)結構研究生考試大綱 正文

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

臨沂大學

本文來源：http://zhangjiajieline.cn/lydx/cksm_354215.html