山東理工大學計算機學院 2019年碩士研究生自命題考試大綱

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

2、時間復雜性能分析的方法。二、線性表1、考核知識點線性表；順序表的表示、操作與實現(xiàn)；鏈表的表示、操作與實現(xiàn)；順序存儲結(jié)構與鏈式存儲結(jié)構的比較2、考核要求（1）理解線性表的定義和邏輯結(jié)構特性；（2）掌握線性表的順序存儲方法和基本操作算法實現(xiàn)；（3）掌握線性表的鏈式存儲方法和基本操作算法實現(xiàn)；（4）了解用線性表表示一元多項式和稀疏多項式的方法3、考核重點（1）順序存儲結(jié)構與鏈式存儲結(jié)構的區(qū)別；（2）順序表和單鏈表的算法實現(xiàn)。三、棧和隊列1、考

3、核知識點棧與隊列的特點；棧的遞歸算法；鏈隊列；循環(huán)隊列。2、考核要求（1）熟練掌握棧的類型定義、表示和基本操作的實現(xiàn)；（2）靈活運用棧的特性設計算法；（3）掌握遞歸算法的設計方法和設計思路；（4）熟練掌握隊列的類型定義、表示和基本操作的實現(xiàn)3、考核重點（1）棧和隊列的特性；（2）棧與隊列基本操作的實現(xiàn)；（3）棧的遞歸算法應用。（1）理解并掌握圖的基本概念、術語和基本邏輯結(jié)構特征；（2）理解并掌握圖的存儲結(jié)構；（3）掌握圖的深度優(yōu)先和廣度

4、優(yōu)先遍歷算法；（4）掌握圖結(jié)構的典型應用，如最小生成樹、拓撲排序、關鍵路徑、最短路徑等。3、考核重點（1）圖的邏輯結(jié)構與存儲方法；（2）圖的深度優(yōu)先、廣度優(yōu)先遍歷算法；（3）最小生成樹算法；（4）拓撲排序算法；（5）單源點最短路算法八、查找1、考核知識點順序查找；折半查找；分塊查找；二叉排序樹；平衡二叉樹；哈希表。2、考核要求（1）理解靜態(tài)查找表、動態(tài)查找表和哈希查找的基本概念；（2）掌握靜態(tài)查找表的各種查找方法如：順序查找、折半查找、

5、分塊查找；（3）掌握二叉排序樹與平衡二叉樹；（4）掌握哈希表的概念和查找方法和哈希函數(shù)的構造方法、解決沖突的基本方法；（5）掌握各種查找算法的效率分析。3、考核重點（1）折半查找算法；（2）二叉排序樹；（3）哈希表。九、排序1、考核知識點直接插入排序；希爾排序；冒泡排序；快速排序；堆排序；歸并排序；基數(shù)排序。2、考核要求（1）理解排序的基本概念；（2）掌握基于插入思想的排序算法如：直接插入排序、希爾排序；（3）掌握基于交換思想的排序算法