福建2022年專升本數(shù)據(jù)結(jié)構(gòu)考試大綱

數(shù)據(jù)結(jié)構(gòu)( 100 分)

一、考試要求

1 、能分析數(shù)據(jù)的內(nèi)在邏輯關(guān)系。

2 、掌握常用數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示方法。

3 、理解數(shù)據(jù)表示和數(shù)據(jù)處理之間的關(guān)系，理解算法效率的分析方法。

4 、能利用常見的數(shù)據(jù)結(jié)構(gòu)，進(jìn)行算法設(shè)計(jì)。

二、考試內(nèi)容

第 1 章 引論

1 、了解數(shù)據(jù)結(jié)構(gòu)的基本概念。

2 、了解數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)、算法的概念。

3 、理解數(shù)據(jù)類型、抽象數(shù)據(jù)類型的概念。

4 、理解時(shí)間復(fù)雜度、空間復(fù)雜度的概念。

第 2 章 表

1 、理解 ADT 表的概念及基本運(yùn)算。

2 、掌握表的順序存儲(chǔ)結(jié)構(gòu)及其運(yùn)算的實(shí)現(xiàn)。

3 、掌握表的鏈接存儲(chǔ)結(jié)構(gòu)及其運(yùn)算的實(shí)現(xiàn)。

4 、理解單鏈表、循環(huán)鏈表、雙向鏈表的特點(diǎn)。

第 3 章 棧

1 、掌握棧的定義和基本運(yùn)算。

2 、掌握棧的順序?qū)崿F(xiàn)及其運(yùn)算的實(shí)現(xiàn)。

3 、掌握棧和隊(duì)列的鏈接實(shí)現(xiàn)及其運(yùn)算的實(shí)現(xiàn)。

4 、掌握棧的應(yīng)用。

第 4 章 隊(duì)列

1 、掌握隊(duì)列的定義和基本運(yùn)算。

2 、掌握隊(duì)列的順序?qū)崿F(xiàn)(循環(huán)隊(duì)列)及其運(yùn)算的實(shí)現(xiàn)。

3 、掌握隊(duì)列的鏈接實(shí)現(xiàn)及其運(yùn)算的實(shí)現(xiàn)。

4 、掌握隊(duì)列的應(yīng)用。

第 5 章 遞歸

? 理解遞歸的概念。

? 了解分治與遞歸的關(guān)系。

? 了解用棧模擬遞歸技術(shù)。

第 6 章 排序與選擇

? 理解排序的基本概念(關(guān)鍵字、內(nèi)外排序、穩(wěn)定性、時(shí)間效率、空間效率)

? 掌握選擇排序的方法(簡(jiǎn)單選擇排序、堆排序)

? 掌握插入排序的方法(直接插入排序)

? 掌握交換排序的方法(冒泡排序、快速排序)

? 了解合并排序的方法。

? 理解各種排序方法的優(yōu)缺點(diǎn)。

第 7 章 樹

1 、掌握樹的表示法，包括父親結(jié)點(diǎn)數(shù)組表示法、兒子鏈表表示法、左兒子右兄弟表示法。

2 、理解二叉樹的定義和術(shù)語、性質(zhì)。

3 、掌握二叉樹的存儲(chǔ)結(jié)構(gòu)，包括順序存儲(chǔ)實(shí)現(xiàn)和指針實(shí)現(xiàn)。

4 、掌握二叉樹的遍歷算法及其應(yīng)用。

5 、了解線索樹的概念。

第 8 章 集合

1 、了解以集合為基礎(chǔ)的抽象數(shù)據(jù)類型。

2 、了解集合上的基本運(yùn)算。

3 、了解集合的實(shí)現(xiàn)(位向量實(shí)現(xiàn)、鏈表實(shí)現(xiàn))。

第 9 章 符號(hào)表

? 理解抽象數(shù)據(jù)類型符號(hào)表的概念。

? 掌握符號(hào)表的數(shù)組實(shí)現(xiàn)。

? 掌握開散列表和閉散列表的實(shí)現(xiàn)。

? 理解散列函數(shù)構(gòu)造方法以及處理沖突的辦法。

? 掌握線性再散列技術(shù)。

第 10 章 字典

? 理解抽象數(shù)據(jù)類型字典及其運(yùn)算。

? 掌握二叉搜索樹及其實(shí)現(xiàn)。

第 11 章 優(yōu)先隊(duì)列

? 理解抽象數(shù)據(jù)類型優(yōu)先隊(duì)列及其基本運(yùn)算。

? 理解堆的概念及其實(shí)現(xiàn)。

? 掌握哈夫曼樹及其應(yīng)用。

第 12 章 圖

? 解圖的概念、術(shù)語。

2 、掌握?qǐng)D的存儲(chǔ)結(jié)構(gòu)(鄰接矩陣、鄰接表)

3 、掌握?qǐng)D的遍歷方法(深度優(yōu)先遍歷、廣度優(yōu)先遍歷)

4 、掌握?qǐng)D的最小生成樹的算法( prim 算法、 kruskal 算法)。

5 、掌握?qǐng)D的單源最短路徑的 dijkstra 算法。

? 了解所有頂點(diǎn)對(duì)之間的最短路徑 floyd 算法。

三、考題類型

? 選擇題(概念、存儲(chǔ)表示、算法描述)： 24 %

? 填空題(概念、存儲(chǔ)表示、算法描述)： 16 %

? 應(yīng)用題(綜合)： 40 %

? 算法設(shè)計(jì)題： 20 %

參考用書：

《數(shù)據(jù)結(jié)構(gòu)與算法》，王曉東編，高等教育出版社