數(shù)據(jù)結(jié)構(gòu)考試大綱

一、

本課程的地位、作用和任務(wù)

數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)專(zhuān)業(yè)（包括軟件、應(yīng)用和科學(xué)教育等專(zhuān)業(yè)）的主干課、專(zhuān)業(yè)基礎(chǔ)課，主要介紹用計(jì)算機(jī)解決一系列問(wèn)題特別是非數(shù)值信息處理問(wèn)題時(shí)所用的各種組織數(shù)據(jù)的方法、存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)的方法以及在各種結(jié)構(gòu)上執(zhí)行操作的算法。通過(guò)教學(xué)要求學(xué)生掌握各種數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)、存儲(chǔ)表示、運(yùn)算方法以及在計(jì)算機(jī)科學(xué)中最基本的應(yīng)用，培養(yǎng)、訓(xùn)練學(xué)生選用合適的數(shù)據(jù)結(jié)構(gòu)和編寫(xiě)質(zhì)量高、風(fēng)格好的應(yīng)用程序的能力，并為后續(xù)課程的學(xué)習(xí)打下良好的理論基礎(chǔ)和實(shí)踐基礎(chǔ)。

二、

課程內(nèi)容及學(xué)時(shí)分配

第一章

緒論

(1)數(shù)據(jù)、數(shù)據(jù)對(duì)象、數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)類(lèi)型

(2)算法及算法描述

(3)算法的時(shí)間復(fù)雜度和空間復(fù)雜度

本章學(xué)時(shí)數(shù)：2，本章習(xí)題數(shù)：4

第二章

線(xiàn)性表

2.1

線(xiàn)性表的邏輯結(jié)構(gòu)

線(xiàn)性表的形式定義及基本操作

2.2線(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu)

(1)線(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu)描述

(2)在順序存儲(chǔ)結(jié)構(gòu)表示方式下線(xiàn)性表基本操作的實(shí)現(xiàn)

2.3

線(xiàn)性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

(1)線(xiàn)性表的單鏈表表示及其實(shí)現(xiàn)方法

(2)循環(huán)鏈表

(a)表示

(b)運(yùn)算

(3)雙向鏈表

(a)類(lèi)型描述

(b)運(yùn)算實(shí)現(xiàn)

2.4一元多項(xiàng)式的表示及相加

(1)

一元多項(xiàng)式的線(xiàn)性表表示

(2)一元多項(xiàng)式基本操作的實(shí)現(xiàn)

本章學(xué)時(shí)數(shù)：6，本章習(xí)題數(shù)：10

第三章

棧和隊(duì)列

3.1

棧

(1)

抽象數(shù)據(jù)類(lèi)型棧的定義

(2)

棧的順序存儲(chǔ)和鏈接存儲(chǔ)

(3)

?；静僮鞯膶?shí)現(xiàn)

3.2

表達(dá)式求值

棧的應(yīng)用--表達(dá)式求值

(a)算法描述

(b)操作過(guò)程

3.3

棧與遞歸過(guò)程

(1)遞歸算法執(zhí)行過(guò)程中棧的狀態(tài)變化過(guò)程

(2)遞歸過(guò)程轉(zhuǎn)化成非遞歸過(guò)程的變換方法

3.4

隊(duì)列

(1)抽象數(shù)據(jù)類(lèi)型隊(duì)列的定義

(2)隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

(3)隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)

本章學(xué)時(shí)數(shù)：6，本章習(xí)題數(shù)：10

第四章

串

4.1

串及其操作

(1)串的概念

(2)串的基本操作

4.2

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

(1)

串的靜態(tài)存儲(chǔ)結(jié)構(gòu)

(a)非緊縮格式

(b)緊縮格式

(2)串的動(dòng)態(tài)存儲(chǔ)結(jié)構(gòu)

(a)串的鏈表存儲(chǔ)方式

(b)存儲(chǔ)密度

4.3串基本操作的實(shí)現(xiàn)

(1)

靜態(tài)結(jié)構(gòu)存儲(chǔ)串時(shí)的操作

(a)聯(lián)接函數(shù)

(b)求子串函數(shù)

(c)定位函數(shù)

(2)

模式匹配的改進(jìn)算法

(3)堆結(jié)構(gòu)存儲(chǔ)串時(shí)的操作

(a)賦值操作

(b)聯(lián)接運(yùn)算

(c)求子串操作

4.4

串操作應(yīng)用舉例(自學(xué))

串的應(yīng)用及實(shí)現(xiàn)

本章學(xué)時(shí)數(shù)；4，本章習(xí)題數(shù)：6

第五章

數(shù)組和廣義表

5.1

數(shù)組的定義和運(yùn)算

(1)

二維數(shù)組、n維數(shù)組的邏輯結(jié)構(gòu)

(2)

數(shù)組的基本操作

5.2

數(shù)組的順序存儲(chǔ)結(jié)構(gòu)

(1)

以行序?yàn)橹餍虻拇鎯?chǔ)結(jié)構(gòu)

(2)

以列序?yàn)橹餍虻拇鎯?chǔ)結(jié)構(gòu)

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

(1)特殊矩陣和稀疏矩陣

(a)下（上）三角矩陣

(b)對(duì)角矩陣

(c)稀疏矩陣

(2)三元組表

(a)形式描述

(b)轉(zhuǎn)置運(yùn)算

(c)相乘運(yùn)算

(3)十字鏈表

(a)形式描述

(b)加法運(yùn)算

5.4

廣義表的定義

廣義表的定義和特點(diǎn)

5.5

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

廣義表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)表示

5.6

m元多項(xiàng)式的表示(自學(xué))

三元多項(xiàng)式的廣義表表示

本章學(xué)時(shí)數(shù)：4，本章習(xí)題數(shù)：8

第六章

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

6.1

樹(shù)的結(jié)構(gòu)的定義和基本操作

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

(2)樹(shù)的基本操作

6.2

二叉樹(shù)

(1)二叉樹(shù)的定義和操作

(2)二叉樹(shù)的性質(zhì)

(3)

二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)

（a）順序存儲(chǔ)結(jié)構(gòu)

(2)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

6.3

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

(1)遍歷二叉樹(shù)的操作定義與算法描述

(a)先序遍歷

(b)中序遍歷

(c)后序遍歷

(2)線(xiàn)索二叉樹(shù)定義及存儲(chǔ)結(jié)構(gòu)

(a)線(xiàn)索鏈表

(b)二叉樹(shù)的線(xiàn)索化

(3)線(xiàn)索二叉樹(shù)的基本操作

6.4

樹(shù)和森林

(1)樹(shù)的存儲(chǔ)結(jié)構(gòu)

(a)雙親表示法

(b)孩子表示法

(c)孩子兄弟表示法

(2)森林與二叉樹(shù)的轉(zhuǎn)換

(a)森林轉(zhuǎn)換成二叉樹(shù)

(b)二叉樹(shù)轉(zhuǎn)換成森林

(3)樹(shù)的遍歷

(a)先序遍歷

(b)中序遍歷

(c)后序遍歷

6.5

樹(shù)與等價(jià)問(wèn)題

(1)等價(jià)問(wèn)題描述及其抽象數(shù)據(jù)類(lèi)型

(2)基本操作實(shí)現(xiàn)

6.6

哈夫曼樹(shù)及應(yīng)用

(1)哈夫曼樹(shù)定義及哈夫曼算法描述

(2)哈夫曼編碼

(a)前綴編碼概念

(b)求哈夫曼編碼的算法

本章學(xué)時(shí)數(shù)：12，本章習(xí)題數(shù)：15

第七章

圖

7.1

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

(1)圖的基本概念

(2)圖的基本操作

7.2

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

(1)數(shù)組表示法

(a)形式描述

(b)鄰接矩陣

(2)鄰接表

(a)鄰接表

(b)逆鄰接表

(3)十字鏈表

(a)存儲(chǔ)結(jié)構(gòu)

(b)十字鏈表建立算法

(4)鄰接多重表

7.3

圖的遍歷

(1)深度優(yōu)先搜索及其算法

(2)廣度優(yōu)先搜索及其算法

7.4

圖的連通性問(wèn)題

(1)無(wú)向圖的連通分量和生成樹(shù)

(2)有向圖的強(qiáng)連通分量

(3)最小生成樹(shù)定義及算法

(a)最小生成樹(shù)概念

(b)Prim算法

(c)Kruskal算法

7.5

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

(1)拓?fù)渑判?/p>

(2)AOV-網(wǎng)及關(guān)鍵路徑

7.6

最短路徑

(1)單源最短路徑與Dijkstra算法

(2)每對(duì)頂點(diǎn)之間的最短路徑與Floyd算法

本章學(xué)時(shí)數(shù)：10，本章習(xí)題數(shù)：10

第八章

動(dòng)態(tài)存儲(chǔ)管理

8.1

概述

動(dòng)態(tài)存儲(chǔ)問(wèn)題概述

8.2

可利用空間表及分配方法

(1)可利用空間表結(jié)構(gòu)形式

(2)三種分配策略

（a）首次擬合法

(b)最佳擬合法

(c)最差擬合法

8.3

邊界標(biāo)識(shí)法

(1)可利用空間表的結(jié)構(gòu)

(2)分配算法

(3)回收算法

8.4

伙伴系統(tǒng)

(1)可利用空間表的結(jié)構(gòu)

(2)分配算法

(3)回收算法

8.5

無(wú)用單元收集

(1)無(wú)用單元收集基本步驟

(2)三種標(biāo)志算法

8.6

存儲(chǔ)緊縮

存儲(chǔ)緊縮基本步驟

本章學(xué)時(shí)數(shù)：4，本章習(xí)題數(shù)：5

第九章

查找

9.1

靜態(tài)查找表

(1)順序表的查找

(2)有序表的查找

(3)靜態(tài)樹(shù)表的查找

(4)索引順序表的查找

9.2

動(dòng)態(tài)查找表

(1)二叉排序樹(shù)和平衡二叉樹(shù)

(a)二叉排序樹(shù)查找算法

(b)

二叉排序樹(shù)插入和刪除算法

(c)

二叉排序樹(shù)查找分析

(d)平衡二叉樹(shù)

(2)B-樹(shù)和B+樹(shù)

(a)

B-樹(shù)的查找、插入和刪除算法

(b)B+樹(shù)的查找、插入和刪除算法

(3)鍵樹(shù)

(a)雙鏈樹(shù)

(b)Trie樹(shù)

9.3

哈希表

(1)哈希表定義及哈希函數(shù)的構(gòu)造方法

(2)處理沖突方法

(a)開(kāi)放定址法

(b)再哈希法

(c)鏈地址法

(d)建公共溢出區(qū)法

(3)哈希表的查找及其分析

本章學(xué)時(shí)數(shù)：8，本章習(xí)題數(shù)：10

第十章

內(nèi)部排序

10.1

概述

排序基本概念

10.2

插入排序

(1)

直接插入排序

(2)

折半插入排序、2-路插入排序和表插入排序

(3)希爾排序

10.3

快速排序

(1)快速排序算法

(2)快速排序算法性能

10.4

選擇排序

(1)簡(jiǎn)單選擇排序

(2)樹(shù)形選擇排序

(3)堆排序

(a)堆定義

（b）篩選算法

(c)堆排序算法

(d)時(shí)間復(fù)雜度分析

10.5

歸并排序

歸并排序算法及性能

10.6

基數(shù)排序

(1)多關(guān)鍵字排序

(a)MSD法

(b)LSD法

(2)鏈?zhǔn)交鶖?shù)排序

10.7

各種內(nèi)部排序方法的比較討論(課堂討論)

本章學(xué)時(shí)數(shù)：10，本章習(xí)題數(shù)：12

第十一章

外部排序

11.1

外存信息的存取(簡(jiǎn)講)

(1)磁帶信息的存取

(2)磁盤(pán)信息的存取

11.2

外部排序的方法

(1)外部排序的歸并過(guò)程

(2)外部排序所需時(shí)間

11.3

多路平衡歸并的實(shí)現(xiàn)

(1)敗者樹(shù)概念

(2)k-路歸并算法描述

11.4

置換-選擇排序

(1)置換-選擇排序排序過(guò)程

(2)置換-選擇排序算法描述

11.5

緩沖區(qū)的并行操作處理（簡(jiǎn)講）

11.6

最佳歸并樹(shù)

(1)最佳歸并樹(shù)概念

(2)附加虛段數(shù)目的判定

11.7

磁帶歸并排序

（1）平衡歸并

（2）多步歸并

本章學(xué)時(shí)數(shù)：4，本章習(xí)題數(shù)：4

第十二章

文件

12.1

有關(guān)文件的基本概念

(1)文件及其類(lèi)別

(2)記錄的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)

(3)文件的操作

(4)文件的物理結(jié)構(gòu)

12.2

順序文件

(1)順序文件概念及特點(diǎn)

(2)批處理算法

12.3

索引文件概念

(1)靜態(tài)索引

(2)動(dòng)態(tài)索引

12.4

ISAM文件和VSAM文件

(1)ISAM文件

(2)VSAM文件

12.5

直接存取文件（散列文件）

直接存取文件組織方法

12.6

多關(guān)鍵字文件

(1)多重表文件

(2)倒排文件

本章學(xué)時(shí)數(shù)：2，本章習(xí)題數(shù)：3

三、

先修課程

離散數(shù)學(xué)，PASCAL語(yǔ)言(或C語(yǔ)言)

四、

教材及主要參考書(shū)

1、

嚴(yán)蔚敏等，數(shù)據(jù)結(jié)構(gòu)（第二版），清華大學(xué)出版社

2、

管紀(jì)文等，數(shù)據(jù)結(jié)構(gòu)，高等教育出版社

3、

朱望規(guī)，數(shù)據(jù)結(jié)構(gòu)，西安交大出版社

4、

E.Horowitz

and

Sahni，F(xiàn)oudamentals

of

Data

Structures,

by

Pitmen

Publishing

Limited.

5、

D.E.Knuth，The

Art

of

Computer

Programming，by

Addison-Wesley

Publishing

Company,Inc.

五、

實(shí)驗(yàn)