2020山東理工大學(xué)碩士考試大綱之計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院

1、計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院碩士研究生招生考試計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院碩士研究生招生考試考試大綱考試大綱科目代碼：科目代碼：880科目名稱：數(shù)據(jù)結(jié)構(gòu)科目名稱：數(shù)據(jù)結(jié)構(gòu)考試范圍：考試范圍：一、緒論1、考核知識(shí)點(diǎn)數(shù)據(jù)的邏輯結(jié)構(gòu)與物理結(jié)構(gòu)；抽象數(shù)據(jù)類型；算法及其度量。2、考核要求（1）理解數(shù)據(jù)結(jié)構(gòu)的基本概念和術(shù)語(yǔ)；（2）掌握抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)；（3）掌握算法的基本概念和算法的性能分析方法。3、考核重點(diǎn)（1）數(shù)據(jù)的邏輯結(jié)構(gòu)與物理結(jié)構(gòu)；（2）算法時(shí)間復(fù)

2、雜度性能分析的方法。二、線性表1、考核知識(shí)點(diǎn)線性表；順序表的表示與實(shí)現(xiàn)；鏈表的表示與實(shí)現(xiàn)；順序與鏈?zhǔn)酱鎯?chǔ)的比較。2、考核要求（1）理解線性表的定義和邏輯結(jié)構(gòu)特性；（2）掌握線性表的順序存儲(chǔ)方法和常用算法；（3）掌握線性表的鏈?zhǔn)酱鎯?chǔ)方法和常用算法；（4）了解用線性表表示一元多項(xiàng)式和稀疏多項(xiàng)式的方法3、考核重點(diǎn)（1）順序存儲(chǔ)結(jié)構(gòu)與鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的區(qū)別；（2）順序表和單鏈表的常用經(jīng)典算法。三、棧和隊(duì)列1、考核知識(shí)點(diǎn)棧與隊(duì)列的特點(diǎn)；棧的遞歸算法；

3、鏈隊(duì)列；循環(huán)隊(duì)列。2、考核要求（1）熟練掌握棧的類型定義、表示和基本操作的實(shí)現(xiàn)；（2）靈活運(yùn)用棧的特性設(shè)計(jì)算法；（3）掌握遞歸算法的設(shè)計(jì)方法和設(shè)計(jì)思路；（4）熟練掌握隊(duì)列的類型定義、表示和基本操作的實(shí)現(xiàn)3、考核重點(diǎn)（1）棧和隊(duì)列的特性；（2）棧與隊(duì)列基本操作的實(shí)現(xiàn)；（3）棧的遞歸算法應(yīng)用。四、串1、考核知識(shí)點(diǎn)串，模式匹配算法。2、考核要求（1）掌握串類型的定義及其表示方法；（3）最小生成樹算法；（4）拓?fù)渑判蛩惴?；?）單源點(diǎn)最短路算法

4、八、查找1、考核知識(shí)點(diǎn)順序查找；折半查找；分塊查找；二叉排序樹；平衡二叉樹；哈希表。2、考核要求（1）理解靜態(tài)查找表、動(dòng)態(tài)查找表和哈希查找的基本概念；（2）掌握靜態(tài)查找表的各種查找方法如：順序查找、折半查找、分塊查找；（3）掌握二叉排序樹與平衡二叉樹；（4）掌握哈希表的概念、查找以及哈希函數(shù)的構(gòu)造方與解決沖突的基本方法；（5）掌握各種查找算法的效率分析。3、考核重點(diǎn)（1）折半查找算法；（2）二叉排序樹；（3）哈希表。九、排序1、考核知識(shí)

5、點(diǎn)直接插入排序；希爾排序；冒泡排序；快速排序；堆排序；歸并排序；基數(shù)排序。2、考核要求（1）理解排序的基本概念；（2）掌握基于插入思想的排序算法如：直接插入排序、希爾排序；（3）掌握基于交換思想的排序算法如：冒泡排序、快速排序；（4）掌握基于選擇思想的排序算法如：簡(jiǎn)單選擇排序、堆排序；（5）掌握其它排序算法如：歸并排序、基數(shù)排序；（6）能夠?qū)Ω鞣N排序算法進(jìn)行分析比較。3、考核重點(diǎn)（1）快速排序算法及其應(yīng)用；（2）堆排序算法；（3）歸并排