2021青島理工大學813數據結構研究生考試大綱 正文

813數據結構  考試大綱

【考核目標】
1.理解數據結構的基本概念，比較系統(tǒng)地掌握數據結構的理論基礎知識；
2.熟悉并掌握線性表、棧、隊列、串、數組、廣義表、樹和二叉樹、圖等的邏輯結構、存儲結構和對數據的基本運算；
3.熟悉并掌握抽象數據類型的表示、實現和在程序設計中的作用；
4.理解算法的基本概念、特性、設計要求以及性能分析；
5.理解查找和排序的基本概念，掌握各種查找和排序操作的基本思想和算法實現；
6.學會根據計算機所處理數據對象的特性，確定與之相適應的數據結構和存儲結構，并設計相應的應用算法。
【考核內容】

一、緒論

1．考核知識點

數據結構；抽象數據類型；算法；算法的時間復雜度；算法的空間復雜度。

2．考核要求

(1)理解數據結構的基本概念和術語；
(2)掌握抽象數據類型的表示與實現；
(3)掌握算法的基本概念和算法的性能分析方法。
必須重點掌握抽象數據類型的表示；算法的時間復雜性能分析的方法。

二、線性表

1．考核知識點

線性表；順序表；鏈表；順序存儲結構；鏈式存儲結構。

2．考核要求

(1)理解線性表的定義和邏輯結構特性；
(2)掌握線性表的順序存儲方法和基本操作算法實現；
(3)掌握線性表的鏈式存儲方法和基本操作算法實現；
(4)了解用線性表表示一元多項式和稀疏多項式的方法，并理解稀疏多項式的基本操作實現。
必須重點掌握線性表的順序存儲結構、鏈式存儲結構和順序表和各種鏈表的算法實現。

三、棧和隊列

1．考核知識點

棧；遞歸；鏈隊列；循環(huán)隊列。

2．考核要求

(1)熟練掌握棧的類型定義、表示和基本操作的實現；
(2)靈活運用棧的特性設計算法；
(3)掌握遞歸算法的設計方法和設計思路；
(4)熟練掌握隊列的類型定義、表示和基本操作的實現
必須重點掌握棧和隊列的特性、基本算法的實現以及應用。

四、串

1．考核知識點

串，模式匹配算法。

2．考核要求

(1)掌握串類型的定義及其表示方法；
(2)掌握串基本算法的實現方法；
(3)了解串的應用算法。
必須重點掌握串的表示方法、串的基本算法的實現。

五、數組和廣義表

1．考核知識點

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

2．考核要求

(1)了解數組的定義和數組的順序表示方法；
(2)數組元素順序存儲的地址計算；
(3)掌握特殊矩陣和稀疏矩陣的壓縮存儲方法；
(4)了解廣義表的定義和存儲結構。
必須重點掌握數組元素的地址計算方法；特殊矩陣的壓縮存儲；稀疏矩陣的壓縮存儲。

六、樹和二叉樹

1．考核知識點

二叉樹的存儲結構及其遍歷的方法；二叉樹的線索化；哈夫曼樹的構造方法及其編碼的生成。

2．考核要求

(1)理解樹和二叉樹的定義、術語和基本邏輯結構特性；
(2)理解二叉樹的基本性質；
(3)理解二叉樹存儲結構；
(4)理解二叉樹的遍歷算法思想，掌握遞歸和非遞歸遍歷算法實現；
(5)掌握線索二叉樹的基本概念和相應算法；
(6)了解樹和森林的存儲方法及與二叉樹的之間的轉換方法；
(7)掌握哈夫曼樹及其應用。
必須重點掌握二叉樹的特性；二叉樹的遍歷；二叉樹的線索化；哈夫曼樹及哈夫曼編碼算法實現。

七、圖

1．考核知識點

圖的邏輯結構；鄰接表；深度優(yōu)先遍歷；廣度優(yōu)先遍歷；最小生成樹、拓撲排序、關鍵路徑、最短路徑。

2．考核要求

(1)理解并掌握圖的基本概念、術語和基本邏輯結構特征；
(2)理解并掌握圖的存儲結構；
(3)掌握圖的深度優(yōu)先和廣度優(yōu)先遍歷算法；
(4)了解并掌握圖結構的典型應用，如最小生成樹、拓撲排序、關鍵路徑、最短路徑等。
必須重點掌握圖的邏輯結構；圖的存儲方法；圖的深度優(yōu)先、廣度優(yōu)先遍歷算法；圖的應用。
 

八、查找

1．考核知識點

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

2．考核要求

(1)理解靜態(tài)查找表、動態(tài)查找表和哈希查找的基本概念；
(2)掌握靜態(tài)查找表的各種查找方法如：順序查找、折半查找、分塊查找；
(3)掌握動態(tài)查找表的各種查找方法如二叉排序樹與平衡二叉樹，B樹等；
(4)掌握哈希表的概念和查找方法和哈希函數的構造方法、解決沖突的基本方法；
(5)掌握各種查找算法的效率分析。
必須重點掌握折半查找、二叉排序樹、平衡二叉樹和哈希表的查找算法的實現。

九、排序

1．考核知識點

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

2．考核要求

(1)理解排序的基本概念；
(2)掌握基于插入思想的排序算法如：直接插入排序、希爾排序；
(3)掌握基于交換思想的排序算法如：冒泡排序、快速排序；
(4)掌握基于選擇思想的排序算法如：簡單選擇排序、堆排序；
(5)掌握其它排序算法如：歸并排序、基數排序；
(6)能夠對各種排序算法進行分析比較。
必須重點掌握插入排序、快速排序、堆排序、合并排序、基數排序等算法的設計思想。
 
【考核方式】 筆試 

青島理工大學

本文來源：http://www.upcoffee.cn/qdlgdx/cksm_380384.html