2021青島理工大學813數(shù)據(jù)結(jié)構(gòu)研究生考試大綱 正文

813數(shù)據(jù)結(jié)構(gòu)  考試大綱

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

一、緒論

1．考核知識點

數(shù)據(jù)結(jié)構(gòu)；抽象數(shù)據(jù)類型；算法；算法的時間復雜度；算法的空間復雜度。

2．考核要求

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

二、線性表

1．考核知識點

線性表；順序表；鏈表；順序存儲結(jié)構(gòu)；鏈式存儲結(jié)構(gòu)。

2．考核要求

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

三、棧和隊列

1．考核知識點

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

2．考核要求

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

四、串

1．考核知識點

串，模式匹配算法。

2．考核要求

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

五、數(shù)組和廣義表

1．考核知識點

數(shù)組；稀疏矩陣；壓縮存儲；廣義表。

2．考核要求

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

六、樹和二叉樹

1．考核知識點

二叉樹的存儲結(jié)構(gòu)及其遍歷的方法；二叉樹的線索化；哈夫曼樹的構(gòu)造方法及其編碼的生成。

2．考核要求

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

七、圖

1．考核知識點

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

2．考核要求

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

八、查找

1．考核知識點

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

2．考核要求

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

九、排序

1．考核知識點

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

2．考核要求

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

青島理工大學

添加青島理工大學學姐微信，或微信搜索公眾號“考研派小站”，關注[考研派小站]微信公眾號，在考研派小站微信號輸入[青島理工大學考研分數(shù)線、青島理工大學報錄比、青島理工大學考研群、青島理工大學學姐微信、青島理工大學考研真題、青島理工大學專業(yè)目錄、青島理工大學排名、青島理工大學保研、青島理工大學公眾號、青島理工大學研究生招生）]即可在手機上查看相對應青島理工大學考研信息或資源。