山東理工大學

計算機科學與技術學院碩士研究生招生考試考試大綱

科目代碼：880 科目名稱：數據結構

考試范圍：

一、緒論

1、考核知識點

數據的邏輯結構與物理結構;抽象數據類型;算法及其度量。

2、考核要求

(1)理解數據結構的基本概念和術語;

(2)掌握抽象數據類型的表示與實現;

(3)掌握算法的基本概念和算法的性能分析方法。

3、考核重點

(1)數據的邏輯結構與物理結構;

(2)算法時間復雜度性能分析的方法。

二、線性表

1、考核知識點

線性表;順序表的表示與實現;鏈表的表示與實現;順序與鏈式存儲的比較。

2、考核要求

(1)理解線性表的定義和邏輯結構特性;

(2)掌握線性表的順序存儲方法和常用算法;

(3)掌握線性表的鏈式存儲方法和常用算法;

(4)了解用線性表表示一元多項式和稀疏多項式的方法

3、考核重點

(1)順序存儲結構與鏈式存儲結構的區別;

(2)順序表和單鏈表的常用經典算法。

三、棧和隊列

1、考核知識點

棧與隊列的特點;棧的遞歸算法;鏈隊列;循環隊列。

2、考核要求

(1)熟練掌握棧的類型定義、表示和基本操作的實現;

(2)靈活運用棧的特性設計算法;

(3)掌握遞歸算法的設計方法和設計思路;

(4)熟練掌握隊列的類型定義、表示和基本操作的實現

3、考核重點

(1)棧和隊列的特性;

(2)棧與隊列基本操作的實現;

(3)棧的遞歸算法應用。

四、串

1、考核知識點

串，模式匹配算法。

2、考核要求

(1)掌握串類型的定義及其表示方法;

(2)掌握串基本算法的實現方法;

(3)掌握KMP算法。

3、考核重點

KMP算法

五、數組和廣義表

1、考核知識點

數組;稀疏矩陣的壓縮存儲;廣義表。

2、考核要求

(1)了解數組的定義和數組的順序表示方法;

(2)數組元素順序存儲的地址計算;

(3)掌握特殊矩陣和稀疏矩陣的壓縮存儲方法;

(4)了解廣義表的定義和存儲結構。

3、考核重點

(1)數組元素的地址計算方法;

(2)矩陣的壓縮存儲;

(3)廣義表的基本性質。

六、樹和二叉樹

1、考核知識點

二叉樹的定義、性質與存儲結構;二叉樹的遍歷及其應用;樹與森林的表示與遍歷;哈夫曼樹與哈夫曼編碼。

2、考核要求

(1)理解樹和二叉樹的定義、術語;

(2)理解二叉樹的基本性質;

(3)理解二叉樹存儲結構;

(4)理解二叉樹的遍歷算法思想，掌握遞歸和非遞歸遍歷算法實現;

(5)掌握二叉樹遍歷算法的應用;

(6)了解樹、森林的存儲方法及與二叉樹間的轉換方法;

(7)掌握哈夫曼樹及其應用。

3、考核重點

(1)二叉樹的基本特性;

(2)二叉樹的遍歷及其應用算法;

(3)哈夫曼樹及哈夫曼編碼

七、圖

1、考核知識點

圖的邏輯結構;鄰接表與鄰接矩陣;深度優先遍歷;廣度優先遍歷;最小生成樹、拓撲排序、關鍵路徑、最短路徑。

2、考核要求

(1)理解并掌握圖的基本概念、術語和基本邏輯結構特征;

(2)理解并掌握圖的存儲結構;

(3)掌握圖的深度優先和廣度優先遍歷算法;

(4)掌握圖結構的典型應用，如最小生成樹、拓撲排序、關鍵路徑、最短路徑等。

3、考核重點

(1)圖的邏輯結構與存儲方法;

(2)圖的深度優先、廣度優先遍歷算法;

(3)最小生成樹算法;

(4)拓撲排序算法;

(5)單源點最短路算法

八、查找

1、考核知識點

順序查找;折半查找;分塊查找;二叉排序樹;平衡二叉樹;哈希表。

2、考核要求

(1)理解靜態查找表、動態查找表和哈希查找的基本概念;

(2)掌握靜態查找表的各種查找方法如：順序查找、折半查找、分塊查找;

(3)掌握二叉排序樹與平衡二叉樹;

(4)掌握哈希表的概念、查找以及哈希函數的構造方與解決沖突的基本方法;

(5)掌握各種查找算法的效率分析。

3、考核重點

(1)折半查找算法;

(2)二叉排序樹;

(3)哈希表。

九、排序

1、考核知識點

直接插入排序;希爾排序;冒泡排序;快速排序;堆排序;歸并排序;基數排序。

2、考核要求

(1)理解排序的基本概念;

(2)掌握基于插入思想的排序算法如：直接插入排序、希爾排序;

(3)掌握基于交換思想的排序算法如：冒泡排序、快速排序;

(4)掌握基于選擇思想的排序算法如：簡單選擇排序、堆排序;

(5)掌握其它排序算法如：歸并排序、基數排序;

(6)能夠對各種排序算法進行分析比較。

3、考核重點

(1)快速排序算法及其應用;

(2)堆排序算法;

(3)歸并排序算法。

參考書目：

數據結構(C語言版) 嚴蔚敏 吳偉民 編著 清華大學出版社