東莞理工學院2022年全國碩士研究生入學考試《數據結構》考試大綱
第一部分 考試說明
一、考試性質
《數據結構》是報考電子信息專業的考試科目之一。為幫助考生明确考試複習範圍和有關要求,特制定出本考試大綱。
本考試大綱适用于報考東莞理工學院電子信息專業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)哈希沖突的解決方法
基本要求:掌握和理解哈希查找思想,掌握常用的哈希函數和哈希沖突的解決方法。