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

一、

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

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

二、

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

第一章

緒論

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

(2)算法及算法描述

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

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

第二章

線性表

2.1

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

線性表的形式定義及基本操作

2.2線性表的順序存儲結(jié)構(gòu)

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

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

2.3

線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)

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

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

(a)表示

(b)運(yùn)算

(3)雙向鏈表

(a)類型描述

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

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

(1)

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

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

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

第三章

棧和隊(duì)列

3.1

棧

(1)

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

(2)

棧的順序存儲和鏈接存儲

(3)

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

3.2

表達(dá)式求值

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

(a)算法描述

(b)操作過程

3.3

棧與遞歸過程

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

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

3.4

隊(duì)列

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

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

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

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

第四章

串

4.1

串及其操作

(1)串的概念

(2)串的基本操作

4.2

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

(1)

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

(a)非緊縮格式

(b)緊縮格式

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

(a)串的鏈表存儲方式

(b)存儲密度

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

(1)

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

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

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

(c)定位函數(shù)

(2)

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

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

(a)賦值操作

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

(c)求子串操作

4.4

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

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

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

第五章

數(shù)組和廣義表

5.1

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

(1)

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

(2)

數(shù)組的基本操作

5.2

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

(1)

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

(2)

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

5.3矩陣的壓縮存儲

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

(a)下（上）三角矩陣

(b)對角矩陣

(c)稀疏矩陣

(2)三元組表

(a)形式描述

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

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

(3)十字鏈表

(a)形式描述

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

5.4

廣義表的定義

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

5.5

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

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

5.6

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

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

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

第六章

樹和二叉樹

6.1

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

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

(2)樹的基本操作

6.2

二叉樹

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

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

(3)

二叉樹的存儲結(jié)構(gòu)

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

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

6.3

遍歷二叉樹和線索二叉樹

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

(a)先序遍歷

(b)中序遍歷

(c)后序遍歷

(2)線索二叉樹定義及存儲結(jié)構(gòu)

(a)線索鏈表

(b)二叉樹的線索化

(3)線索二叉樹的基本操作

6.4

樹和森林

(1)樹的存儲結(jié)構(gòu)

(a)雙親表示法

(b)孩子表示法

(c)孩子兄弟表示法

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

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

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

(3)樹的遍歷

(a)先序遍歷

(b)中序遍歷

(c)后序遍歷

6.5

樹與等價問題

(1)等價問題描述及其抽象數(shù)據(jù)類型

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

6.6

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

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

(2)哈夫曼編碼

(a)前綴編碼概念

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

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

第七章

圖

7.1

圖的定義和術(shù)語

(1)圖的基本概念

(2)圖的基本操作

7.2

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

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

(a)形式描述

(b)鄰接矩陣

(2)鄰接表

(a)鄰接表

(b)逆鄰接表

(3)十字鏈表

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

(b)十字鏈表建立算法

(4)鄰接多重表

7.3

圖的遍歷

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

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

7.4

圖的連通性問題

(1)無向圖的連通分量和生成樹

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

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

(a)最小生成樹概念

(b)Prim算法

(c)Kruskal算法

7.5

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

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

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

7.6

最短路徑

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

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

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

第八章

動態(tài)存儲管理

8.1

概述

動態(tài)存儲問題概述

8.2

可利用空間表及分配方法

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

(2)三種分配策略

（a）首次擬合法

(b)最佳擬合法

(c)最差擬合法

8.3

邊界標(biāo)識法

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

(2)分配算法

(3)回收算法

8.4

伙伴系統(tǒng)

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

(2)分配算法

(3)回收算法

8.5

無用單元收集

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

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

8.6

存儲緊縮

存儲緊縮基本步驟

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

第九章

查找

9.1

靜態(tài)查找表

(1)順序表的查找

(2)有序表的查找

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

(4)索引順序表的查找

9.2

動態(tài)查找表

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

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

(b)

二叉排序樹插入和刪除算法

(c)

二叉排序樹查找分析

(d)平衡二叉樹

(2)B-樹和B+樹

(a)

B-樹的查找、插入和刪除算法

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

(3)鍵樹

(a)雙鏈樹

(b)Trie樹

9.3

哈希表

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

(2)處理沖突方法

(a)開放定址法

(b)再哈希法

(c)鏈地址法

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

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

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

第十章

內(nèi)部排序

10.1

概述

排序基本概念

10.2

插入排序

(1)

直接插入排序

(2)

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

(3)希爾排序

10.3

快速排序

(1)快速排序算法

(2)快速排序算法性能

10.4

選擇排序

(1)簡單選擇排序

(2)樹形選擇排序

(3)堆排序

(a)堆定義

（b）篩選算法

(c)堆排序算法

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

10.5

歸并排序

歸并排序算法及性能

10.6

基數(shù)排序

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

(a)MSD法

(b)LSD法

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

10.7

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

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

第十一章

外部排序

11.1

外存信息的存取(簡講)

(1)磁帶信息的存取

(2)磁盤信息的存取

11.2

外部排序的方法

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

(2)外部排序所需時間

11.3

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

(1)敗者樹概念

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

11.4

置換-選擇排序

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

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

11.5

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

11.6

最佳歸并樹

(1)最佳歸并樹概念

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

11.7

磁帶歸并排序

（1）平衡歸并

（2）多步歸并

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

第十二章

文件

12.1

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

(1)文件及其類別

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

(3)文件的操作

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

12.2

順序文件

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

(2)批處理算法

12.3

索引文件概念

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

(2)動態(tài)索引

12.4

ISAM文件和VSAM文件

(1)ISAM文件

(2)VSAM文件

12.5

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

直接存取文件組織方法

12.6

多關(guān)鍵字文件

(1)多重表文件

(2)倒排文件

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

三、

先修課程

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

四、

教材及主要參考書

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)