第一部分 考試說明
一、考試性質
《數據結構》課程是報考計算機科學與技術專業的考試科目之一。為幫助考生明確考試復習范圍和有關要求，特制定出本考試大綱。
本考試大綱適用于報考東莞理工學院計算機科學與技術2023年全國碩士研究生入學考試的準考考生。
二、考試形式與試卷結構
(一)答題時間：180分鐘;
(二)答題方式：閉卷，筆試;
(三)總分：150分;
(四)試卷結構：填空題10%，選擇題20%，判斷題10%，解析題40%，程序設計題20%。
三、參考書目
嚴蔚敏、吳偉民主編：《數據結構(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)稀疏矩陣的壓縮存儲。
基本要求：掌握和理解特殊矩陣(比如對稱矩陣，三角矩陣等)的壓縮方法，掌握和理解稀疏矩陣的壓縮存儲方法。
