萍鄉(xiāng)學(xué)院2020年算法與數(shù)據(jù)結(jié)構(gòu)考試參考書目:1、《數(shù)據(jù)結(jié)構(gòu)》(C語言版)(嚴(yán)為民吳偉民著)，清華大學(xué)出版社，2018、2.《數(shù)據(jù)結(jié)構(gòu)教程(第五版)》(李春寶著)，清華大學(xué)出版社，2017、具體考試大綱如下

一、主要內(nèi)容

1.數(shù)據(jù)結(jié)構(gòu)概述

1)數(shù)據(jù)結(jié)構(gòu)的基本概念和術(shù)語

2)抽象數(shù)據(jù)類型的表示和實(shí)現(xiàn)

3)算法和算法分析

2.線性表格

1)線性表的類型定義

2)線性表的順序表示和實(shí)現(xiàn)

3)鏈表的表示和實(shí)現(xiàn)

3.堆棧和隊(duì)列

1)棧的基本概念

2)棧的表示和實(shí)現(xiàn)

3)堆棧應(yīng)用

4)隊(duì)列的基本概念

5)隊(duì)列的表示和實(shí)現(xiàn)

4.線

1)字符串類型的定義

2)字符串的表示和實(shí)現(xiàn)

3)字符串的模式匹配算法

5.數(shù)組和廣義表

1)數(shù)組的定義

2)數(shù)組的順序表示和實(shí)現(xiàn)

3)矩陣的壓縮存儲

4)廣義表的定義

5)廣義表的存儲結(jié)構(gòu)

6.樹和二叉樹

1)樹定義和基本術(shù)語

2)二叉樹

3)遍歷二叉樹和線索二叉樹

4)樹木和森林

5)霍夫曼樹及其應(yīng)用

7.數(shù)字

1)圖形的定義和術(shù)語

2)圖形的存儲結(jié)構(gòu)

3)圖的遍歷

4)生成樹和最小生成樹

5)有向無環(huán)圖及其應(yīng)用

6)最短路徑

8.找到

1)搜索的基本概念

2)靜態(tài)查找表

3)動態(tài)查找表

4)哈希表

9.內(nèi)部分類

1)排序的基本概念

2)插入排序

3)快速排序

4)選擇排序

5)合并和排序

6)基數(shù)排序

7)各種內(nèi)部排序方法的比較

二、基本要求

1.數(shù)據(jù)結(jié)構(gòu)概述

1)理解數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)、數(shù)據(jù)對象、數(shù)據(jù)結(jié)構(gòu)和抽象數(shù)據(jù)類型的含義

2)了解數(shù)據(jù)結(jié)構(gòu)的四種基本結(jié)構(gòu)

3)掌握邏輯結(jié)構(gòu)、物理(存儲)結(jié)構(gòu)、順序映像和鏈映像的含義

4)理解算法的定義，掌握算法的五個重要特征和算法設(shè)計(jì)的四個要求

5)了解算法效率的度量方法

6)掌握時(shí)間復(fù)雜度和空之間復(fù)雜度的分析方法

2.線性表格

1)了解線性結(jié)構(gòu)的概念和線性表上的基本操作

2)掌握順序表的存儲結(jié)構(gòu)特點(diǎn)和順序表基本操作的實(shí)現(xiàn)

3)了解單鏈表的概念，掌握單鏈表的存儲結(jié)構(gòu)特點(diǎn)，單鏈表的搜索、插入、刪除操作，

一種建立單鏈表的方法

4)了解循環(huán)鏈表和雙向鏈表的概念，掌握雙向鏈表的存儲結(jié)構(gòu)特征和雙向鏈表的插入

和刪除操作

3.堆棧和隊(duì)列

1)了解棧的定義和基本操作

2)掌握順序棧的存儲結(jié)構(gòu)特點(diǎn)和順序棧基本操作的實(shí)現(xiàn)

3)了解棧在數(shù)制轉(zhuǎn)換、括號匹配測試、行編輯程序、表達(dá)式求值、迷宮求解中的應(yīng)用

4)了解隊(duì)列的定義和基本操作

5)掌握循環(huán)隊(duì)列的存儲結(jié)構(gòu)特點(diǎn)和循環(huán)隊(duì)列基本操作的實(shí)現(xiàn)

6)掌握鏈?zhǔn)疥?duì)列的存儲結(jié)構(gòu)特點(diǎn)和鏈?zhǔn)疥?duì)列基本操作的實(shí)現(xiàn)

4.線

1)了解字符串的定義和基本操作

2)了解固定長度順序存儲表示、堆分配存儲表示和區(qū)塊鏈存儲表示

3)掌握字符串的模式匹配算法

5.數(shù)組和廣義表

1)理解數(shù)組的定義

2)理解數(shù)組的順序表示和實(shí)現(xiàn)

3)掌握對稱矩陣、上下三角矩陣、對角矩陣的壓縮存儲

4)了解稀疏矩陣的特點(diǎn)、稀疏矩陣的三重性和鏈表的表示

5)了解廣義表的定義和存儲結(jié)構(gòu)

6.樹和二叉樹

1)了解樹的定義和基本術(shù)語

2)了解二叉樹的定義和性質(zhì)

3)掌握二叉樹的順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)

4)掌握二叉樹的一階遍歷、中階遍歷、末階遍歷、層次遍歷的過程

5)了解線索二叉樹的概念、構(gòu)造和遍歷過程

6)掌握樹的父表示、子表示和子兄弟表示

7)了解將森林和樹木轉(zhuǎn)化為二叉樹以及將二叉樹恢復(fù)為森林和樹木的過程

8)掌握樹的靠前次根遍歷和第二次根遍歷

9)掌握森林前序遍歷和中間序遍歷的過程

10)掌握Hoeffmann樹的概念和構(gòu)造過程，以及產(chǎn)生Huffman碼的過程

7.數(shù)字

1)理解圖形的定義和基本術(shù)語

2)了解圖的數(shù)組表示、鄰接表、交叉鏈表方法和鄰接多重表

3)掌握深度優(yōu)先搜索遍歷和廣度優(yōu)先搜索遍歷算法

4)理解生成樹和最小生成樹的概念，掌握構(gòu)造最小生成樹的prim算法和Kruskar算法

5)了解拓?fù)渑判虻母拍詈瓦^程

6)了解AOE網(wǎng)絡(luò)和關(guān)鍵路徑的概念以及求解關(guān)鍵路徑的過程

7)了解最短路徑的概念，掌握構(gòu)造最短路徑的Dijkstra算法和弗洛伊德算法

8.找到

1)了解查找表和平均查找長度的定義

2)掌握順序搜索、二分搜索法和塊搜索的算法設(shè)計(jì)和算法分析

3)掌握二叉排序樹的算法設(shè)計(jì)，了解平衡二叉樹的定義和搜索過程

4)掌握哈希表、哈希函數(shù)構(gòu)造方法、哈希沖突解決方法和哈希搜索過程的基本概念

9.內(nèi)部分類

1)了解排序的定義，排序算法的穩(wěn)定性，排序算法的分類

2)掌握直接插入排序、分裂插入排序和Hill排序的基本思想、排序算法和算法分析

3)掌握冒泡排序和快速排序的基本思想、排序算法和算法分析

4)掌握簡單選擇排序和堆排序的基本思想、排序算法和算法分析

5)了解合并排序算法的基本思想，掌握雙向合并算法

6)掌握基數(shù)排序算法的基本思想、排序算法和算法分析

7)了解各種內(nèi)部排序方法的對比分析

三、試卷題

本課程試卷總分為100分，考試時(shí)間為120分鐘，試題為:

專升本算法與數(shù)據(jù)結(jié)構(gòu)考試大綱" alt="2020萍鄉(xiāng)學(xué)院專升本算法與數(shù)據(jù)結(jié)構(gòu)考試大綱" width="365" height="188" border="0" vspace="0" style="width: 365px; height: 188px;"/>

部分內(nèi)容來源于網(wǎng)絡(luò)轉(zhuǎn)載、學(xué)生投稿，如有侵權(quán)或?qū)Ρ菊居腥魏我庖姟⒔ㄗh或者投訴，請聯(lián)系郵箱（1296178999@qq.com）反饋。 未經(jīng)本站授權(quán)，不得轉(zhuǎn)載、摘編、復(fù)制或者建立鏡像， 如有違反，本站將追究法律責(zé)任！