2020萍鄉(xiāng)學(xué)院專升本《算法與數(shù)據(jù)結(jié)構(gòu)》考試大綱

一、主要內(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) 線性表的鏈?zhǔn)奖硎竞蛯?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) 矩陣的壓縮存儲(chǔ)

4) 廣義表的定義

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

6. 樹和二叉樹

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

2) 二叉樹

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

4) 樹和森林

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

7. 圖

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

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

3) 圖的遍歷

4) 生成樹和最小生成樹

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

6) 最短路徑

8. 查找

1) 查找的基本概念

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

3) 動(dòng)態(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ù)對(duì)象、數(shù)據(jù)結(jié)構(gòu)和抽象數(shù)據(jù)類型的含義

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

3) 掌握邏輯結(jié)構(gòu)、物理(存儲(chǔ))結(jié)構(gòu)、順序映像和鏈?zhǔn)接诚竦暮x

4) 了解算法的定義，掌握算法的5個(gè)重要特性和算法設(shè)計(jì)的4個(gè)要求

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

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

2. 線性表

1) 了解線性結(jié)構(gòu)的概念及線性表上的基本運(yùn)算

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

3) 理解單鏈表的概念，掌握單鏈表的存儲(chǔ)結(jié)構(gòu)特點(diǎn)，單鏈表的查找、插入和刪除操作，

單鏈表的建表方法

4) 理解循環(huán)鏈表和雙向鏈表的概念，掌握雙向鏈表的存儲(chǔ)結(jié)構(gòu)特點(diǎn)、雙向鏈表的插入

和刪除操作

3. 棧和隊(duì)列

1) 了解棧的定義及基本運(yùn)算

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

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

4) 了解隊(duì)列的定義和基本運(yùn)算

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

6) 掌握鏈隊(duì)列的存儲(chǔ)結(jié)構(gòu)特點(diǎn)和鏈隊(duì)列基本運(yùn)算的實(shí)現(xiàn)

4. 串

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

2) 理解串的定長順序存儲(chǔ)表示、堆分配存儲(chǔ)表示、塊鏈存儲(chǔ)表示

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

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

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

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

3) 掌握對(duì)稱矩陣、上下三角矩陣和對(duì)角矩陣的壓縮存儲(chǔ)

4) 了解稀疏矩陣的特點(diǎn)、稀疏矩陣的三元組和十字鏈表表示

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

6. 樹和二叉樹

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

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

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

4) 掌握二叉樹的先序遍歷、中序遍歷、后序遍歷和層次遍歷過程

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

6) 掌握樹的雙親表示法、孩子表示法和孩子兄弟表示法

7) 了解森林、樹轉(zhuǎn)換為二叉樹以及二叉樹還原為森林、樹的過程

8) 掌握樹的先根遍歷和后根遍歷過程

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

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

7. 圖

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

2) 理解圖的數(shù)組表示法、鄰接表、十字鏈表法、鄰接多重表

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

4) 了解生成樹和最小生成樹的概念，掌握構(gòu)造最小生成樹的普里姆算法和克魯斯卡爾算法

5) 了解拓?fù)渑判虻母拍詈屯負(fù)渑判蜻^程

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

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

8. 查找

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

2) 掌握順序查找、折半查找和分塊查找的算法設(shè)計(jì)和算法分析

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

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

9. 內(nèi)部排序

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

2) 掌握直接插入排序、折半插入排序、希爾排序的基本思想、排序算法和算法分析

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

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

5) 理解歸并排序算法的基本思路，掌握2-路歸并算法

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

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

三、試卷題型

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

四、參考書目

1、《數(shù)據(jù)結(jié)構(gòu)(C語言版）》（嚴(yán)蔚敏，吳偉民著），清華大學(xué)出版社，2018。

2、《數(shù)據(jù)結(jié)構(gòu)教程（第5版）》（李春葆著），清華大學(xué)出版社，2017。

推薦閱讀

2020萍鄉(xiāng)學(xué)院專升本《數(shù)字媒體技術(shù)導(dǎo)論》考試大綱