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

一、主要內(nèi)容

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

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

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

3) 算法和算法分析

2. 線(xiàn)性表

1) 線(xiàn)性表的類(lèi)型定義

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

3) 線(xiàn)性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)

3. 棧和隊(duì)列

1) 棧的基本概念

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

3) 棧的應(yīng)用

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

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

4. 串

1) 串類(lèi)型的定義

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

3) 串的模式匹配算法

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

1) 數(shù)組的定義

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

3) 矩陣的壓縮存儲(chǔ)

4) 廣義表的定義

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

6. 樹(shù)和二叉樹(shù)

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

2) 二叉樹(shù)

3) 遍歷二叉樹(shù)和線(xiàn)索二叉樹(shù)

4) 樹(shù)和森林

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

7. 圖

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

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

3) 圖的遍歷

4) 生成樹(shù)和最小生成樹(shù)

5) 有向無(wú)環(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ù)類(lèi)型的含義

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. 線(xiàn)性表

1) 了解線(xiàn)性結(jié)構(gòu)的概念及線(xiàn)性表上的基本運(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) 理解串的定長(zhǎng)順序存儲(chǔ)表示、堆分配存儲(chǔ)表示、塊鏈存儲(chǔ)表示

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

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

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

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

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

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

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

6. 樹(shù)和二叉樹(shù)

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

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

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

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

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

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

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

8) 掌握樹(shù)的先根遍歷和后根遍歷過(guò)程

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

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

7. 圖

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

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

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

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

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

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

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

8. 查找

1) 了解查找表和平均查找長(zhǎng)度的定義

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

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

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

9. 內(nèi)部排序

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

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

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

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

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

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

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

三、試卷題型

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

四、參考書(shū)目

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

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

推薦閱讀

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