第一部分 考試說明
一、考試性質
《數據結構》是報考電子信息專業的考試科目之一。為幫助考生明確考試復習范圍和有關要求，特制定出本考試大綱。
本考試大綱適用于報考東莞理工學院電子信息專業2022年全國碩士研究生入學考試的準考考生。
二、考試形式與試卷結構
(一)答題時間：180分鐘
(二)答題方式：閉卷，筆試
(三)總分：150分
(四)試卷結構：填空題20分，選擇題45分，解析題60分，程序設計題25分。
三、參考書目
《數據結構（C語言版）》，嚴蔚敏等，清華大學出版社，2018年
第二部分 考查要點
一、考試要求
要求學生能夠掌握數據的邏輯結構、存儲結構以及其它結構定義的各種運算及應用。具體要求如下：
（1）掌握算法的空間復雜度和時間復雜度分析的基本算法；
（2）掌握堆棧、隊列、表、樹、圖等的數據結構；
（3）掌握分類和查找等算法的實現和分析；
（4）掌握算法設計的常用技術和應用。
二、考試內容
第1篇 緒論
1．數據結構基本概念：（1）數據、數據元素、數據類型（2）數據的邏輯結構和存儲結構（3）數據的操作
基本要求：掌握和理解數據結構相關的基本概念。
2．算法和算法的時間復雜度：（1）算法的概念和性質（2）算法的時間效率分析
基本要求：掌握和理解算法的概念和性質，掌握和理解算法的時間效率分析，初步能夠分析簡單算法的時間效率。
第2篇 線性表
1．線性表的概念
基本要求：掌握和理解線性表的定義和特性。
2．順序表:（1）順序表的存儲結構（2）順序表操作的實現（3）順序表的效率分析（4）順序表的應用
基本要求：掌握和理解順序表的存儲結構，會實現順序表的基本操作，對順序表的基本操作能夠進行時間效率分析，能夠用順序表進行簡單的應用設計和實現。
3．鏈表:（1）單鏈表的存儲結構（2）單鏈表的基本操作（3）單鏈表的應用（4）循環單鏈表（5）雙向鏈表（6）靜態鏈表
基本要求：掌握和理解單鏈表的存儲結構，能夠實現單鏈表的基本操作，能夠使用單鏈表實現初步應用，能夠分析單鏈表操作的時間復雜度，掌握和理解循環單鏈表，雙向鏈表和靜態鏈表的概念和特點，能夠實現簡單的循環單鏈表，雙向鏈表和靜態鏈表的基本操作。
第3篇 堆棧和隊列
1．堆棧（1）堆棧的概念（2）堆棧的順序和鏈式實現
基本要求：掌握堆棧的概念和特點，能實現順序堆棧和鏈式堆棧的基本操作。
2．隊列（1）隊列的基本概念（2）順序循環隊列（3）鏈式隊列（4）優先級隊列
基本要求：掌握隊列的概念和特點，掌握順序循環隊列的概念和特點，能夠實現隊列的基本操作，掌握優先級隊列的概念。
3．堆棧和隊列的應用
基本要求：理解堆棧和隊列的經典應用：括號匹配問題，算術表達式計算問題，迷宮問題，調度問題。
第4篇 串
1．串的概念和存儲結構（1）串的概念（2）串的存儲結構和基本算法的實現
基本要求：掌握串的概念，串的存儲結構（靜態存儲結構和動態存儲結構），能夠實現串的基本操作。
2．串的匹配算法（1）BF算法（2）KMP算法（3）鏈式隊列（4）優先級隊列
基本要求：掌握和理解串的匹配算法：BF算法和KMP算法。
第5篇 數組
1．數組的概念（1）數組概念（2）數組的實現
基本要求：掌握數組的概念和數組的內存分配和實現。
2．特殊矩陣和稀疏矩陣的壓縮存儲（1）特殊矩陣的壓縮存儲（2）稀疏矩陣的壓縮存儲。
基本要求：掌握和理解特殊矩陣（比如對稱矩陣，三角矩陣等）的壓縮方法，掌握和理解稀疏矩陣的壓縮存儲方法。
第6篇 遞歸算法和廣義表
1．遞歸算法（1）遞歸算法概念（2）遞歸算法的設計
基本要求：掌握遞歸算法的概念，遞歸算法的執行過程，初步能夠使用遞歸算法設計和解決問題。
2．廣義表（1）廣義表的概念（2）廣義表的存儲結構和操作實現。
基本要求：掌握和理解廣義表概念，掌握和理解廣義表的存儲結構和基本操作算法的實現。
第7篇 樹和二叉樹
1．樹的概念（1）樹的概念（2）樹的存儲結構
基本要求：掌握和理解有關樹的概念，掌握和理解樹的常用存儲結構。
2．二叉樹（1）二叉樹的概念和性質（2）二叉樹的存儲結構和基本算法實現。
基本要求：掌握和理解二叉樹的概念和基本性質，掌握和理解二叉樹的存儲結構（特別是鏈式存儲結構），能夠實現二叉樹的基本算法。
3．二叉樹的遍歷算法（1）深度遞歸和廣度遞歸算法（2）遍歷算法的應用
基本要求：掌握理解二叉樹深度遍歷（前序，中序和后序）的遞歸和非遞歸算法，能夠用二叉樹遍歷思想解決一些樹的問題。
4．線索二叉樹
基本要求：掌握和理解線索二叉樹的概念。
5．哈夫曼樹（1）哈夫曼樹的概念（2）哈夫曼編碼問題。
基本要求：掌握和理解哈夫曼樹的概念，掌握和理解哈夫曼編碼問題的實現。
6．樹與二叉樹的轉換（1）樹的遍歷（2）樹和二叉樹的轉換
基本要求：掌握和理解樹的遍歷方法，能夠進行樹和二叉樹的轉換。
第8篇 圖
1．圖的概念和存儲結構（1）樹的相關概念（2）圖的存儲結構 （3）圖的基本算法實現
基本要求：掌握和理解有關圖的相關概念，掌握和理解圖的常用存儲結構，掌握和理解圖的基本操作算法的實現。
2．圖的遍歷算法
基本要求：掌握和理解圖的深度遍歷和廣度遍歷的算法以及算法的實現。
3．最小生成樹（1）最小生成樹概念（2）普利姆算法（3）克魯斯卡爾算法
基本要求：掌握理解最小生成樹概念和性質，掌握和理解最小生成樹的兩種經典算法：普利姆算法和克魯斯卡爾算法。
4．最短路徑、拓撲排序和關鍵路徑
基本要求：掌握和理解求最短路徑算法，拓撲算法和關鍵路徑算法。
第9篇 排序
1．排序的概念
基本要求：掌握和理解排序的概念，掌握和理解各類排序算法的特點和時空復雜度分析。
2．插入排序（1）直接插入排序（2）希爾排序
基本要求：掌握和理解插入排序思想，能夠實現插入排序算法，能夠分析插入排序算法的時空復雜度。
3．選擇排序（1）直接選擇排序（2）堆排序
基本要求：掌握和理解選擇排序思想，能夠實現選擇排序算法，能夠分析選擇排序算法的時空復雜度。
4．交換排序（1）冒泡排序（2）快速排序
基本要求：掌握和理解交換排序思想，能夠實現交換排序算法，能夠分析交換排序算法的時空復雜度。
5．歸并排序
基本要求：掌握和理解歸并排序思想，能夠實現歸并排序算法，能夠分析歸并排序算法的時空復雜度。
6．基數排序
基本要求：掌握和理解基數排序思想，能夠實現基數排序算法，能夠分析基數排序算法的時空復雜度。
第10篇 查找
1．查找的概念
基本要求：掌握和理解查找的相關概念，掌握和理解各類查找算法的特點和時空復雜度分析。
2．靜態查找（1）順序查找（2）二分查找（3）索引查找
基本要求：掌握和理解靜態查找思想，能夠實現順序查找和二分查找算法，能夠分析靜態查找算法的時空復雜度。
3．動態查找（1）二叉排序樹。
基本要求：掌握和理解動態查找思想，能夠實現二叉排序樹的創建，插入，查找和刪除算法，能夠分析動態查找算法的時空復雜度。
4．哈希查找（1）哈希查找的概念（2）哈希函數（3）哈希沖突的解決方法
基本要求：掌握和理解哈希查找思想，掌握常用的哈希函數和哈希沖突的解決方法。
029-68569100
精品直播課
