• 2025考研復(fù)試伴學(xué)班
• 2025考研復(fù)試標(biāo)準(zhǔn)班
• 2026考研英語(yǔ)全程班
• 26考研全科上岸規(guī)劃營(yíng)「擇校▪規(guī)劃▪備考」
• 遼寧工程技術(shù)大學(xué)2025考研專(zhuān)業(yè)課復(fù)習(xí)資料「真題▪筆記▪講義▪題庫(kù)」

初試《數(shù)據(jù)結(jié)構(gòu)》科目考試大綱

一、考查目標(biāo)

考查學(xué)生對(duì)數(shù)據(jù)結(jié)構(gòu)及算法分析相關(guān)基礎(chǔ)知識(shí)及技能的掌握水平，并對(duì)學(xué)生利用有關(guān)基礎(chǔ)知識(shí)和技能分析研究計(jì)算機(jī)加工的數(shù)據(jù)結(jié)構(gòu)特性，進(jìn)一步為實(shí)際應(yīng)用涉及的數(shù)據(jù)選擇及設(shè)計(jì)適當(dāng)?shù)倪壿嫿Y(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及其相應(yīng)的算法能力進(jìn)行考核。

二、考試形式與試卷結(jié)構(gòu)

（一）試卷滿分及考試時(shí)間
滿分為150分，考試時(shí)間為3小時(shí)。
（二）答題方式
答題方式為閉卷、筆試。
（三）試卷內(nèi)容結(jié)構(gòu)
內(nèi)容結(jié)構(gòu)為各部分知識(shí)點(diǎn)在試卷中所占的比例。
（四）試卷題型結(jié)構(gòu)
選擇題10分、簡(jiǎn)答題20分、解答題80分、算法設(shè)計(jì)題40分，合計(jì)150分。

三、考查內(nèi)容及要求

（一）數(shù)據(jù)結(jié)構(gòu)概述
1、基本概念及術(shù)語(yǔ)
數(shù)據(jù)結(jié)構(gòu)、邏輯結(jié)構(gòu)、物理結(jié)構(gòu)、抽象數(shù)據(jù)類(lèi)型的概念；數(shù)據(jù)結(jié)構(gòu)的分類(lèi)、兩種物理結(jié)構(gòu)的特點(diǎn)。
2、ADT的表示與實(shí)現(xiàn)
ADT的定義、作用及類(lèi)C語(yǔ)言實(shí)現(xiàn)方法。
3、算法和算法分析
算法的概念、特性和評(píng)判標(biāo)準(zhǔn)、算法時(shí)間復(fù)雜度的概念、簡(jiǎn)單的算法時(shí)間復(fù)雜度分析。
（二）線性表
1、線性表的類(lèi)型定義
線性表的抽象數(shù)據(jù)類(lèi)型定義、線性結(jié)構(gòu)的特點(diǎn)。
2、線性表的順序表示和實(shí)現(xiàn)
順序表的含義、特點(diǎn)和相關(guān)算法。
3、線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)
鏈表的含義、特點(diǎn)和相關(guān)算法。
4、一元多項(xiàng)式表示與相加
一元多項(xiàng)式表示與相加的方法、順序結(jié)構(gòu)和鏈?zhǔn)浇Y(jié)構(gòu)的區(qū)別和選擇。
（三）棧與隊(duì)列
1、棧
棧結(jié)構(gòu)的抽象數(shù)據(jù)類(lèi)型定義、特點(diǎn)、存儲(chǔ)結(jié)構(gòu)和相關(guān)算法。
2、棧的應(yīng)用舉例
棧的應(yīng)用及相關(guān)算法。
3、隊(duì)列
隊(duì)列結(jié)構(gòu)的抽象數(shù)據(jù)類(lèi)型定義、特點(diǎn)、存儲(chǔ)結(jié)構(gòu)和相關(guān)算法。
（四）串
1、串類(lèi)型的定義、表示和實(shí)現(xiàn)
串的定義、串的三種主要表示和實(shí)現(xiàn)方式。
2、串的模式匹配
串的常見(jiàn)模式匹配算法。
（五）數(shù)組與廣義表
1、數(shù)組的定義
數(shù)組概念、特點(diǎn)。
2、數(shù)組的順序表示和實(shí)現(xiàn)
數(shù)組順序存儲(chǔ)結(jié)構(gòu)表示和實(shí)現(xiàn)。
3、數(shù)組的壓縮存儲(chǔ)
特殊矩陣的壓縮存儲(chǔ)、稀疏矩陣的壓縮存儲(chǔ)的實(shí)現(xiàn)方法。
4、廣義表的定義和實(shí)現(xiàn)
廣義表的定義及運(yùn)算、廣義表的存儲(chǔ)結(jié)構(gòu)。
（六）樹(shù)和二叉樹(shù)
1、樹(shù)的定義和基本術(shù)語(yǔ)
樹(shù)的定義、常用術(shù)語(yǔ)。
2、二叉樹(shù)
二叉樹(shù)的定義、二叉樹(shù)的性質(zhì)、存儲(chǔ)結(jié)構(gòu)。
3、數(shù)組的壓縮存儲(chǔ)
特殊矩陣的壓縮存儲(chǔ)、稀疏矩陣的壓縮存儲(chǔ)的實(shí)現(xiàn)方法。
4、遍歷二叉樹(shù)和線索二叉樹(shù)
二叉樹(shù)遍歷及線索化的概念、方法和算法。
5、樹(shù)和森林
樹(shù)的存儲(chǔ)結(jié)構(gòu)，樹(shù)、森林、二叉樹(shù)間相互轉(zhuǎn)換方法、樹(shù)和森林遍歷方法。
6、赫夫曼樹(shù)及其應(yīng)用
赫夫曼樹(shù)和赫夫曼編碼構(gòu)造方法。
（七）圖
1、圖的定義和術(shù)語(yǔ)
圖的定義和術(shù)語(yǔ)。
2、圖的存儲(chǔ)結(jié)構(gòu)
圖的鄰接矩陣表示法、鄰接表表示法、十字鏈表表示法。
3、圖的遍歷
圖的深度優(yōu)先及廣度優(yōu)先遍歷方法和算法。
4、圖的連通性問(wèn)題
連通子圖、生成樹(shù)、最小生成樹(shù)的定義和構(gòu)造方法。
5、拓?fù)渑判?br /> 拓?fù)渑判蚍椒�、算法及�?yīng)用。
6、最短路徑
最短路徑問(wèn)題求解方法、算法及應(yīng)用。
7、關(guān)鍵路徑
關(guān)鍵路徑問(wèn)題求解方法、算法及應(yīng)用。
（八）查找
1、靜態(tài)查找表
查找的概念、順序查找和折半查找的方法和算法。
2、動(dòng)態(tài)查找表
二叉查找樹(shù)和二叉平衡概念及作用、二叉查找樹(shù)和二叉平衡樹(shù)相關(guān)算法。
3、哈希表
哈希表的概念、沖突的概念、常見(jiàn)哈希函數(shù)構(gòu)造方法、哈希表的處理沖突的常用方法。
（九）排序
1、排序的概念
排序的有關(guān)概念、排序的類(lèi)型。
2、排序方法及算法
掌握插入排序、快速排序、選擇排序、歸并排序、基數(shù)排序的方法、算法及相關(guān)算法時(shí)間、空間復(fù)雜度分析過(guò)程。

四、考試用具說(shuō)明

考試使用黑色筆作答,考試時(shí)需要攜帶計(jì)算器、直尺、筆。