2022年考研，東莞理工學院入學考試《數(shù)據(jù)結構》考試大綱

東莞理工學院2022年全國碩士研究生入學考試《數(shù)據(jù)結構》考試大綱

第一部分 考試說明

一、考試性質

《數(shù)據(jù)結構》是報考電子信息專業(yè)的考試科目之一。為幫助考生明確考試復習范圍和有關要求，特制定出本考試大綱。

本考試大綱適用于報考東莞理工學院電子信息專業(yè)2022年全國碩士研究生入學考試的準考考生。

二、考試形式與試卷結構

(一)答題時間：180分鐘

(二)答題方式：閉卷，筆試

(三)總分：150分

(四)試卷結構：填空題20分，選擇題45分，解析題60分，程序設計題25分。

三、參考書目

《數(shù)據(jù)結構(C語言版)》，嚴蔚敏等，清華大學出版社，2018年

第二部分 考查要點

一、考試要求

要求學生能夠掌握數(shù)據(jù)的邏輯結構、存儲結構以及其它結構定義的各種運算及應用。具體要求如下：

(1)掌握算法的空間復雜度和時間復雜度分析的基本算法;

(2)掌握堆棧、隊列、表、樹、圖等的數(shù)據(jù)結構;

(3)掌握分類和查找等算法的實現(xiàn)和分析;

(4)掌握算法設計的常用技術和應用。

二、考試內容

第1篇 緒論

1.數(shù)據(jù)結構基本概念：(1)數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)類型(2)數(shù)據(jù)的邏輯結構和存儲結構(3)數(shù)據(jù)的操作

基本要求：掌握和理解數(shù)據(jù)結構相關的基本概念。

2.算法和算法的時間復雜度：(1)算法的概念和性質(2)算法的時間效率分析

基本要求：掌握和理解算法的概念和性質，掌握和理解算法的時間效率分析，初步能夠分析簡單算法的時間效率。

第2篇 線性表

1.線性表的概念

基本要求：掌握和理解線性表的定義和特性。

2.順序表:(1)順序表的存儲結構(2)順序表操作的實現(xiàn)(3)順序表的效率分析(4)順序表的應用

基本要求：掌握和理解順序表的存儲結構，會實現(xiàn)順序表的基本操作，對順序表的基本操作能夠進行時間效率分析，能夠用順序表進行簡單的應用設計和實現(xiàn)。

3.鏈表:(1)單鏈表的存儲結構(2)單鏈表的基本操作(3)單鏈表的應用(4)循環(huán)單鏈表(5)雙向鏈表(6)靜態(tài)鏈表

基本要求：掌握和理解單鏈表的存儲結構，能夠實現(xiàn)單鏈表的基本操作，能夠使用單鏈表實現(xiàn)初步應用，能夠分析單鏈表操作的時間復雜度，掌握和理解循環(huán)單鏈表，雙向鏈表和靜態(tài)鏈表的概念和特點，能夠實現(xiàn)簡單的循環(huán)單鏈表，雙向鏈表和靜態(tài)鏈表的基本操作。

第3篇 堆棧和隊列

1.堆棧(1)堆棧的概念(2)堆棧的順序和鏈式實現(xiàn)

基本要求：掌握堆棧的概念和特點，能實現(xiàn)順序堆棧和鏈式堆棧的基本操作。

2.隊列(1)隊列的基本概念(2)順序循環(huán)隊列(3)鏈式隊列(4)優(yōu)先級隊列

基本要求：掌握隊列的概念和特點，掌握順序循環(huán)隊列的概念和特點，能夠實現(xiàn)隊列的基本操作，掌握優(yōu)先級隊列的概念。

3.堆棧和隊列的應用

基本要求：理解堆棧和隊列的經典應用：括號匹配問題，算術表達式計算問題，迷宮問題，調度問題。

第4篇 串

1.串的概念和存儲結構(1)串的概念(2)串的存儲結構和基本算法的實現(xiàn)

基本要求：掌握串的概念，串的存儲結構(靜態(tài)存儲結構和動態(tài)存儲結構)，能夠實現(xiàn)串的基本操作。

2.串的匹配算法(1)BF算法(2)KMP算法(3)鏈式隊列(4)優(yōu)先級隊列

基本要求：掌握和理解串的匹配算法：BF算法和KMP算法。

第5篇 數(shù)組

1.數(shù)組的概念(1)數(shù)組概念(2)數(shù)組的實現(xiàn)

基本要求：掌握數(shù)組的概念和數(shù)組的內存分配和實現(xiàn)。

2.特殊矩陣和稀疏矩陣的壓縮存儲(1)特殊矩陣的壓縮存儲(2)稀疏矩陣的壓縮存儲。

基本要求：掌握和理解特殊矩陣(比如對稱矩陣，三角矩陣等)的壓縮方法，掌握和理解稀疏矩陣的壓縮存儲方法。

第6篇 遞歸算法和廣義表

1.遞歸算法(1)遞歸算法概念(2)遞歸算法的設計

基本要求：掌握遞歸算法的概念，遞歸算法的執(zhí)行過程，初步能夠使用遞歸算法設計和解決問題。

2.廣義表(1)廣義表的概念(2)廣義表的存儲結構和操作實現(xiàn)。

基本要求：掌握和理解廣義表概念，掌握和理解廣義表的存儲結構和基本操作算法的實現(xiàn)。

第7篇 樹和二叉樹

1.樹的概念(1)樹的概念(2)樹的存儲結構

基本要求：掌握和理解有關樹的概念，掌握和理解樹的常用存儲結構。

2.二叉樹(1)二叉樹的概念和性質(2)二叉樹的存儲結構和基本算法實現(xiàn)。

基本要求：掌握和理解二叉樹的概念和基本性質，掌握和理解二叉樹的存儲結構(特別是鏈式存儲結構)，能夠實現(xiàn)二叉樹的基本算法。

3.二叉樹的遍歷算法(1)深度遞歸和廣度遞歸算法(2)遍歷算法的應用

基本要求：掌握理解二叉樹深度遍歷(前序，中序和后序)的遞歸和非遞歸算法，能夠用二叉樹遍歷思想解決一些樹的問題。

4.線索二叉樹

基本要求：掌握和理解線索二叉樹的概念。

5.哈夫曼樹(1)哈夫曼樹的概念(2)哈夫曼編碼問題。

基本要求：掌握和理解哈夫曼樹的概念，掌握和理解哈夫曼編碼問題的實現(xiàn)。

6.樹與二叉樹的轉換(1)樹的遍歷(2)樹和二叉樹的轉換

基本要求：掌握和理解樹的遍歷方法，能夠進行樹和二叉樹的轉換。

第8篇 圖

1.圖的概念和存儲結構(1)樹的相關概念(2)圖的存儲結構 (3)圖的基本算法實現(xiàn)

基本要求：掌握和理解有關圖的相關概念，掌握和理解圖的常用存儲結構，掌握和理解圖的基本操作算法的實現(xiàn)。

2.圖的遍歷算法

基本要求：掌握和理解圖的深度遍歷和廣度遍歷的算法以及算法的實現(xiàn)。

3.最小生成樹(1)最小生成樹概念(2)普利姆算法(3)克魯斯卡爾算法

基本要求：掌握理解最小生成樹概念和性質，掌握和理解最小生成樹的兩種經典算法：普利姆算法和克魯斯卡爾算法。

4.最短路徑、拓撲排序和關鍵路徑

基本要求：掌握和理解求最短路徑算法，拓撲算法和關鍵路徑算法。

第9篇 排序

1.排序的概念

基本要求：掌握和理解排序的概念，掌握和理解各類排序算法的特點和時空復雜度分析。

2.插入排序(1)直接插入排序(2)希爾排序

基本要求：掌握和理解插入排序思想，能夠實現(xiàn)插入排序算法，能夠分析插入排序算法的時空復雜度。

3.選擇排序(1)直接選擇排序(2)堆排序

基本要求：掌握和理解選擇排序思想，能夠實現(xiàn)選擇排序算法，能夠分析選擇排序算法的時空復雜度。

4.交換排序(1)冒泡排序(2)快速排序

基本要求：掌握和理解交換排序思想，能夠實現(xiàn)交換排序算法，能夠分析交換排序算法的時空復雜度。

5.歸并排序

基本要求：掌握和理解歸并排序思想，能夠實現(xiàn)歸并排序算法，能夠分析歸并排序算法的時空復雜度。

6.基數(shù)排序

基本要求：掌握和理解基數(shù)排序思想，能夠實現(xiàn)基數(shù)排序算法，能夠分析基數(shù)排序算法的時空復雜度。

第10篇 查找

1.查找的概念

基本要求：掌握和理解查找的相關概念，掌握和理解各類查找算法的特點和時空復雜度分析。

2.靜態(tài)查找(1)順序查找(2)二分查找(3)索引查找

基本要求：掌握和理解靜態(tài)查找思想，能夠實現(xiàn)順序查找和二分查找算法，能夠分析靜態(tài)查找算法的時空復雜度。

3.動態(tài)查找(1)二叉排序樹。

基本要求：掌握和理解動態(tài)查找思想，能夠實現(xiàn)二叉排序樹的創(chuàng)建，插入，查找和刪除算法，能夠分析動態(tài)查找算法的時空復雜度。

4.哈希查找(1)哈希查找的概念(2)哈希函數(shù)(3)哈希沖突的解決方法

基本要求：掌握和理解哈希查找思想，掌握常用的哈希函數(shù)和哈希沖突的解決方法。

以上就是今天的內容“2022年考研，東莞理工學院入學考試《數(shù)據(jù)結構》考試大綱”，希望對2022年考研備考的考生有所幫助。有需要的話請使用環(huán)球網(wǎng)校提供的 免費預約短信提醒，幫助你更快的獲取考試報名時間、準考證打印時間、筆試時間、成績查詢等多方面信息，快來點擊短信提醒吧。點擊下方免費下載按鈕，還可下載考研相關備考資料。