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

一、主要內(nèi)容

1. 數(shù)據(jù)結構概述

1) 數(shù)據(jù)結構的基本概念和術語

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

3) 算法和算法分析

2. 線性表

1) 線性表的類型定義

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

3) 線性表的鏈式表示和實現(xiàn)

3. 棧和隊列

1) 棧的基本概念

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

3) 棧的應用

4) 隊列的基本概念

5) 隊列的表示與實現(xiàn)

4. 串

1) 串類型的定義

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

3) 串的模式匹配算法

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

1) 數(shù)組的定義

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

3) 矩陣的壓縮存儲

4) 廣義表的定義

5) 廣義表的存儲結構

6. 樹和二叉樹

1) 樹的定義和基本術語

2) 二叉樹

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

4) 樹和森林

5) 赫夫曼樹及其應用

7. 圖

1) 圖的定義和術語

2) 圖的存儲結構

3) 圖的遍歷

4) 生成樹和最小生成樹

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

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ù)結構概述

1) 了解數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項、數(shù)據(jù)對象、數(shù)據(jù)結構和抽象數(shù)據(jù)類型的含義

2) 理解數(shù)據(jù)結構的四種基本結構

3) 掌握邏輯結構、物理(存儲)結構、順序映像和鏈式映像的含義

4) 了解算法的定義，掌握算法的5個重要特性和算法設計的4個要求

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

6) 掌握算法的時間復雜度和空間復雜度分析方法

2. 線性表

1) 了解線性結構的概念及線性表上的基本運算

2) 掌握順序表的存儲結構特點和順序表基本運算的實現(xiàn)

3) 理解單鏈表的概念，掌握單鏈表的存儲結構特點，單鏈表的查找、插入和刪除操作，

單鏈表的建表方法

4) 理解循環(huán)鏈表和雙向鏈表的概念，掌握雙向鏈表的存儲結構特點、雙向鏈表的插入

和刪除操作

3. 棧和隊列

1) 了解棧的定義及基本運算

2) 掌握順序棧的存儲結構特點和順序棧基本運算的實現(xiàn)

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

4) 了解隊列的定義和基本運算

5) 掌握循環(huán)隊列的存儲結構特點和循環(huán)隊列基本運算的實現(xiàn)

6) 掌握鏈隊列的存儲結構特點和鏈隊列基本運算的實現(xiàn)

4. 串

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

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

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

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

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

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

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

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

5) 了解廣義表的定義和存儲結構

6. 樹和二叉樹

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

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

3) 掌握二叉樹的順序存儲結構和鏈式存儲結構

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

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

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

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

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

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

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

7. 圖

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

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

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

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

5) 了解拓撲排序的概念和拓撲排序過程

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

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

8. 查找

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

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

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

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

9. 內(nèi)部排序

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

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

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

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

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

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

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

三、試卷題型

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

四、參考書目

1、《數(shù)據(jù)結構(C語言版）》（嚴蔚敏，吳偉民著），清華大學出版社，2018。

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

推薦閱讀

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