《數(shù)據(jù)結(jié)構(gòu)A》課程教學(xué)大綱（本科）

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

(DataStructuresA)

課程代碼：06410035

學(xué)分：4.0

學(xué)時：72（其中：課堂教學(xué)學(xué)時：56實(shí)驗(yàn)學(xué)時：0上機(jī)學(xué)時：16課程實(shí)踐學(xué)時：0）

先修課程：離散數(shù)學(xué)、程序設(shè)計基礎(chǔ)、面向?qū)ο蟪绦蛟O(shè)計

適用專業(yè)：網(wǎng)絡(luò)工程

教材：《數(shù)據(jù)結(jié)構(gòu)一C++實(shí)現(xiàn)（第二版）》，繆淮扣等，科學(xué)出版社，2014年第二版

一、課程性質(zhì)與課程目標(biāo)

（-）課程性質(zhì)

《數(shù)據(jù)結(jié)構(gòu)A》在計算機(jī)科學(xué)中是一門綜合性的專業(yè)基礎(chǔ)課，不僅是一般程序設(shè)計的基礎(chǔ)，而

且是設(shè)計和實(shí)現(xiàn)操作系統(tǒng)、數(shù)據(jù)庫系統(tǒng)、編譯程序及其它系統(tǒng)程序和大型應(yīng)用程序的重要基礎(chǔ)。本

課程討論各種數(shù)據(jù)組織中的數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)以及有關(guān)操作的算法。培養(yǎng)學(xué)生學(xué)會分析研

究計算機(jī)所要加工處理的數(shù)據(jù)的特征的能力，具備組織數(shù)據(jù)、存儲數(shù)據(jù)和處理數(shù)據(jù)的能力，通過在

實(shí)際應(yīng)用中選擇合適的數(shù)據(jù)結(jié)構(gòu)和設(shè)計相應(yīng)算法的訓(xùn)練，為今后從事系統(tǒng)軟件和應(yīng)用軟件的開發(fā)打

下一定的理論和實(shí)踐基礎(chǔ)。

（二）課程目標(biāo)

1.知識方面

1.1理解數(shù)據(jù)結(jié)構(gòu)的一些基本概念，掌握算法的描述方法，理解算法的時間復(fù)雜度和空間復(fù)雜

度的概念并掌握其分析方法。

1.2理解線性表的基本概念、邏輯特性和基本操作，掌握線性表的存儲表示方法，掌握線性表

的基本操作的算法設(shè)計與描述，掌握對算法性能進(jìn)行分析的方法并獲得有效結(jié)論，理解線性表的應(yīng)

用。

1.3理解棧和隊列的基本概念、邏輯特性和基本操作，掌握棧和隊列的存儲表示方法，掌握棧

和隊列的基本操作的算法設(shè)計與描述，掌握對算法性能進(jìn)行分析的方法并獲得有效結(jié)論，理解棧和

隊列的應(yīng)用。

1.4理解串的定義、存儲結(jié)構(gòu)和基本操作，掌握數(shù)組的定義以及順序存儲結(jié)構(gòu)表示，理解稀疏

矩陣的定義、存儲和操作，理解廣義表的定義以及相關(guān)概念。

1.5理解樹和二叉樹的基本概念、邏輯特性和基本操作，掌握樹和二叉樹的存儲表示方法，掌

握二叉樹的基本操作的算法設(shè)計與描述，掌握對算法性能進(jìn)行分析的方法并獲得有效結(jié)論，理解二

叉樹與樹、森林之間的關(guān)系，理解二叉樹的應(yīng)用。

1.6理解圖的基本概念、邏輯特性和基本操作，掌握圖的存儲表示方法，掌握圖的各種應(yīng)用操

作方法并了解其算法實(shí)現(xiàn)，掌握對算法性能進(jìn)行分析的方法并獲得有效結(jié)論。

1.7理解查找的基本概念，掌握各種查找方法及算法設(shè)計與描述，掌握對算法性能進(jìn)行分析的

方法并獲得有效結(jié)論。

1.8理解排序的基本概念，掌握各種排序方法及算法設(shè)計與描述，掌握對算法性能進(jìn)行分析的

方法并獲得有效結(jié)論。

2.能力與素質(zhì)方面

2.1具備依據(jù)工程實(shí)際問題的需求合理地組織數(shù)據(jù)，并在計算機(jī)中有效地存儲數(shù)據(jù)的能力。

2.2具備為解決工程實(shí)際問題進(jìn)行算法設(shè)計求解的能力

2.3具備對算法性能進(jìn)行分析的能力。

2.4具備把解決工程實(shí)際問題設(shè)計的算法通過具體的編程語言加以實(shí)現(xiàn)求解的能力。

（三）課程目標(biāo)與專業(yè)畢業(yè)要求指標(biāo)點(diǎn)的對應(yīng)關(guān)系

本課程支撐專業(yè)培養(yǎng)計劃中畢業(yè)要求指標(biāo)點(diǎn)1.3,2.3,3.1

指標(biāo)點(diǎn)L3：具備對復(fù)雜工程問題進(jìn)行計算機(jī)求解的工程基礎(chǔ)

指標(biāo)點(diǎn)2.3：具備對復(fù)雜工程問題進(jìn)行分析和求解的能力

指標(biāo)點(diǎn)3.1：具備對復(fù)雜網(wǎng)絡(luò)系統(tǒng)進(jìn)行需求分析的能力，能夠清晰地描述設(shè)計任務(wù)

要求指

示點(diǎn)指標(biāo)點(diǎn)1.3指標(biāo)點(diǎn)2.3指標(biāo)點(diǎn)3.1

課程目標(biāo)

課程目標(biāo)1.1V

課程目標(biāo)1.2VV

課程目標(biāo)1.3VV

課程目標(biāo)L4VV

課程目標(biāo)1.5VV

課程目標(biāo)1.6VV

課程目標(biāo)1.7VV

課程目標(biāo)L8VV

課程目標(biāo)2.1V

課程目標(biāo)2.2

課程目標(biāo)2.3V

課程目標(biāo)2.4V

二'課程內(nèi)容與教學(xué)要求

第一章緒論

本章支持課程目標(biāo)1」：理解數(shù)據(jù)結(jié)構(gòu)的一些基本概念，掌握算法的描述方法，理解算法的時間

復(fù)雜度和空間復(fù)雜度的概念并掌握其分析方法。2.3具備對算法性能進(jìn)行分析的能力。

（-）課程內(nèi)容

1.數(shù)據(jù)結(jié)構(gòu)的一些基本概念：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)邏輯結(jié)構(gòu)、數(shù)據(jù)存儲結(jié)構(gòu)、數(shù)據(jù)類

型、算法等。（講授）

2.算法時間復(fù)雜度和空間復(fù)雜度的分析。（講授）

3.算法描述方法。（講授）

（二）教學(xué)要求

1.了解本課程的性質(zhì)、任務(wù)和目的。

2.掌握數(shù)據(jù)結(jié)構(gòu)的一些基本概念。

3.具有對算法的時間復(fù)雜度和空間復(fù)雜度進(jìn)行分析的能力。

4.了解算法的描述方法。

（三）重點(diǎn)與難點(diǎn)

1.重點(diǎn)

數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項；邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)在概念上的聯(lián)系與區(qū)別；評價算

法優(yōu)劣的標(biāo)準(zhǔn)及方法。

2.難點(diǎn)

算法與程序的區(qū)別；邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)的聯(lián)系與區(qū)別；算法的時間復(fù)雜度分析

方法。

第二章線性表

本章支持課程目標(biāo)L2：理解線性表的基本概念、邏輯特性和基本操作，掌握線性表的存儲表

示方法，掌握線性表的基本操作的算法設(shè)計與描述，掌握對算法性能進(jìn)行分析的方法并獲得有效結(jié)

論，理解線性表的應(yīng)用；課程目標(biāo)2.1：具備依據(jù)工程實(shí)際問題的需求合理地組織數(shù)據(jù)，并在計算

機(jī)中有效地存儲數(shù)據(jù)的能力；2.2具備為解決工程實(shí)際問題進(jìn)行算法設(shè)計求解的能力；2.3具備對算

法性能進(jìn)行分析的能力；課程目標(biāo)2.4：具備把解決工程實(shí)際問題設(shè)計的算法通過具體的編程語言

加以實(shí)現(xiàn)求解的能力。

（-）課程內(nèi)容

1.線性表的基本概念和類型定義。（講授）

2.線性表的順序存儲表示及基本操作的實(shí)現(xiàn)。（講授+演示）

3.線性表的鏈?zhǔn)酱鎯Ρ硎炯盎静僮鞯膶?shí)現(xiàn)（單鏈表、循環(huán)鏈表、雙向鏈表、靜態(tài)鏈表）。

（講授+演示）

4.一元多項式的表示及相加。（講授+演示）

（二）教學(xué)要求

1.理解線性表的基本概念和類型定義。

2.掌握順序表和單鏈表上的基本操作方法并具備其算法實(shí)現(xiàn)能力。

3.理解循環(huán)鏈表和雙向鏈表的定義，掌握其插入、刪除等操作方法。

4.了解靜態(tài)鏈表的概念。

5.了解一元多項式的表示及相加運(yùn)算。

（三）重點(diǎn)與難點(diǎn)

1.重點(diǎn)

順序表和鏈?zhǔn)奖恚▎捂湵?、雙向鏈表）的基本操作。

2.難點(diǎn)

鏈?zhǔn)奖恚▎捂湵?、雙向鏈表）的基本操作以及一元多項式的相加運(yùn)算。

第三章棧和隊列

本章支持課程目標(biāo)L3：理解棧和隊列的基本概念、邏輯特性和基本操作，掌握棧和隊列的存

儲表示方法，掌握棧和隊列的基本操作的算法設(shè)計與描述，掌握對算法性能進(jìn)行分析的方法并獲得

有效結(jié)論，理解棧和隊列的應(yīng)用；課程目標(biāo)2.1：具備依據(jù)工程實(shí)際問題的需求合理地組織數(shù)據(jù),

并在計算機(jī)中有效地存儲數(shù)據(jù)的能力；2.2具備為解決工程實(shí)際問題進(jìn)行算法設(shè)計求解的能力；2.3

具備對算法性能進(jìn)行分析的能力；課程目標(biāo)2.4：具備把解決工程實(shí)際問題設(shè)計的算法通過具體的

編程語言加以實(shí)現(xiàn)求解的能力。

（-）課程內(nèi)容

1.棧的定義，棧的順序存儲表示、鏈?zhǔn)酱鎯Ρ硎炯盎静僮鞯膶?shí)現(xiàn)，棧的應(yīng)用（表達(dá)式

計算）。（講授+案例+演示）

2.隊列的定義，隊列的順序存儲表示（循環(huán)隊列）、鏈?zhǔn)酱鎯Ρ硎荆ㄦ滉犃校┘盎静僮?/p>

的實(shí)現(xiàn)。（講授+案例+演示）

3.遞歸。

（二）教學(xué)要求

1.理解棧和隊列的定義。

2.掌握順序存儲表示及鏈?zhǔn)酱鎯Ρ硎镜臈：完犃械幕静僮鞯姆椒ú⒕邆淦渌惴▽?shí)現(xiàn)能

力。

3.掌握表達(dá)式求值等方法，具有利用棧求解后綴表達(dá)式、將中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)

式的能力。

4.了解遞歸的概念。

（三）重點(diǎn)與難點(diǎn)

1.重點(diǎn)

棧和隊列的順序存儲表示、鏈?zhǔn)酱鎯Ρ硎炯盎静僮鞯膶?shí)現(xiàn)。

2.難點(diǎn)

順序棧的溢出判斷條件；循環(huán)隊列的隊空、隊滿判斷條件；遞歸。

第四章串、數(shù)組和廣義表

本章支持課程目標(biāo)L4：理解串的定義、存儲結(jié)構(gòu)和基本操作，掌握數(shù)組的定義以及順序存儲

結(jié)構(gòu)表示，理解稀疏矩陣的定義、存儲和操作，理解廣義表的定義以及相關(guān)概念；課程目標(biāo)2.1：具

備依據(jù)工程實(shí)際問題的需求合理地組織數(shù)據(jù)，并在計算機(jī)中有效地存儲數(shù)據(jù)的能力；2.2具備為解

決工程實(shí)際問題進(jìn)行算法設(shè)計求解的能力；2.3具備對算法性能進(jìn)行分析的能力。

（-）課程內(nèi)容

1.串的基本概念。（講授）

2.數(shù)組的定義以及順序存儲結(jié)構(gòu)。（講授）

3.稀疏矩陣的定義、存儲和操作。（講授+演示）

4.廣義表的定義。（講授）

（二）教學(xué)要求

1.了解串的基本概念。

2.掌握數(shù)組的定義以及順序存儲結(jié)構(gòu)，具有存儲地址換算的能力。

3.掌握稀疏矩陣的定義和壓縮存儲表示方法。

4.掌握稀疏矩陣的轉(zhuǎn)置方法并了解其算法。

5.掌握廣義表的定義。

（三）重點(diǎn)與難點(diǎn)

1.重點(diǎn)

數(shù)組的定義和數(shù)組的存儲結(jié)構(gòu)、稀疏矩陣的壓縮存儲、廣義表的定義。

2.難點(diǎn)

稀疏矩陣的壓縮存儲表示下的運(yùn)算的實(shí)現(xiàn)。

第五章樹和二叉樹

本章支持課程目標(biāo)L5：理解樹和二叉樹的基本概念、邏輯特性和基本操作，掌握樹和二叉樹

的存儲表示方法，掌握二叉樹的基本操作的算法設(shè)計與描述，掌握對算法性能進(jìn)行分析的方法并獲

得有效結(jié)論，理解二叉樹與樹、森林之間的關(guān)系，理解二叉樹的應(yīng)用；課程目標(biāo)2.1：具備依據(jù)工

程實(shí)際問題的需求合理地組織數(shù)據(jù)，并在計算機(jī)中有效地存儲數(shù)據(jù)的能力；2.2具備為解決工程實(shí)

際問題進(jìn)行算法設(shè)計求解的能力；2.3具備對算法性能進(jìn)行分析的能力；課程目標(biāo)2.4：具備把解

決工程實(shí)際問題設(shè)計的算法通過具體的編程語言加以實(shí)現(xiàn)求解的能力。

（-）課程內(nèi)容

1.樹的定義、術(shù)語、表示形式、基本操作。（講授+演示+案例）

2.二叉樹的定義、性質(zhì)、基本操作、存儲結(jié)構(gòu)表示。（講授）

3.二叉樹的各種遍歷方法及實(shí)現(xiàn)。（講授+演示+互動）

4.線索二叉樹。（講授+演示）

5.哈夫曼樹及其應(yīng)用。（講授+演示+案例）

6.樹的存儲結(jié)構(gòu)表示，樹、森林和二叉樹的轉(zhuǎn)換，樹和森林的遍歷。（講授+演示）

（二）教學(xué)要求

1.理解樹的定義、性質(zhì)。

2.掌握樹的存儲結(jié)構(gòu)以及樹和森林的遍歷方法。

3.掌握二叉樹的定義、性質(zhì)、存儲結(jié)構(gòu)。

4.掌握二叉樹的各種遍歷方法及算法實(shí)現(xiàn)，并具有對二叉樹進(jìn)行遍歷的能力。

5.掌握二叉樹的其他操作方法及算法實(shí)現(xiàn)。

6.掌握線索二叉樹的定義和算法實(shí)現(xiàn)，并具有將二叉樹進(jìn)行線索化的能力。

7.掌握樹、森林與二叉樹的轉(zhuǎn)換方法。

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

（三）重點(diǎn)與難點(diǎn)

1.重點(diǎn)

二叉樹的概念、遍歷及基本操作，二叉樹的線索化方法，樹的存儲結(jié)構(gòu)表示以及樹、

森林與二叉樹的轉(zhuǎn)換方法、樹和森林的遍歷方法，哈夫曼樹及其應(yīng)用.

2.難點(diǎn)

二叉樹上的復(fù)雜運(yùn)算；線索二叉樹的算法實(shí)現(xiàn)。

第六章圖

本章支持課程目標(biāo)1.6：理解圖的基本概念、邏輯特性和基本操作，掌握圖的存儲表示方法，

掌握圖的各種應(yīng)用操作方法并了解其算法實(shí)現(xiàn)，掌握對算法性能進(jìn)行分析的方法并獲得有效結(jié)論;

課程目標(biāo)2.1：具備依據(jù)工程實(shí)際問題的需求合理地組織數(shù)據(jù)，并在計算機(jī)中有效地存儲數(shù)據(jù)的能

力；2.2具備為解決工程實(shí)際問題進(jìn)行算法設(shè)計求解的能力；2.3具備對算法性能進(jìn)行分析的能力；

課程目標(biāo)2.4：具備把解決工程實(shí)際問題設(shè)計的算法通過具體的編程語言加以實(shí)現(xiàn)求解的能力。

（一）課程內(nèi)容

1.圖的定義、術(shù)語、基本操作。（講授）

2.圖的各種存儲結(jié)構(gòu)表示。（講授）

3.圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷以及圖的連通分量。（講授+演示）

4.圖的生成樹和最小生成樹。（講授+演示+案例）

5.最短路徑。（講授+演示+案例+自學(xué)）

6.活動網(wǎng)絡(luò)。（講授+演示+案例+自學(xué)）

（二）教學(xué)要求

1.理解圖的定義和術(shù)語。

2.掌握圖的存儲結(jié)構(gòu)表示方法。

3.掌握圖的深度和廣度優(yōu)先搜索方法及其實(shí)現(xiàn)，并具有利用深度和廣度優(yōu)先搜索方法對

圖進(jìn)行遍歷的能力。

4.掌握求圖的最小生成樹的普里姆法和克魯斯卡爾法并了解其實(shí)現(xiàn)算法，并具有利用普

里姆法和克魯斯卡爾法構(gòu)造圖的最小生成樹的能力。

5.掌握求解圖的最短路徑及其長度的方法并了解其實(shí)現(xiàn)算法，并具有構(gòu)造單源點(diǎn)最短路

徑及其長度的能力。

6.掌握拓?fù)渑判虻姆椒ú⒘私馄鋵?shí)現(xiàn)算法，并具有構(gòu)造拓?fù)溆行蛐蛄械哪芰Α?/p>

（三）重點(diǎn)與難點(diǎn)

1.重點(diǎn)

圖的存儲結(jié)構(gòu)、深度和廣度優(yōu)先搜索方法及其實(shí)現(xiàn)、圖的最小生成樹的構(gòu)造方法、圖

的最短路徑及其長度的求解方法、有向無環(huán)圖的拓?fù)溆行蛐蛄械臉?gòu)造方法。

2.難點(diǎn)

最小生成樹、最短路徑的算法思想及其算法實(shí)現(xiàn)、拓?fù)渑判虻乃惴▽?shí)現(xiàn)。

第七章查找

本章支持課程目標(biāo)L7：理解查找的基本概念，掌握各種查找方法及算法設(shè)計與描述，掌握對

算法性能進(jìn)行分析的方法并獲得有效結(jié)論；課程目標(biāo)2.1：具備依據(jù)工程實(shí)際問題的需求合理地組

織數(shù)據(jù)，并在計算機(jī)中有效地存儲數(shù)據(jù)的能力；2.2具備為解決工程實(shí)際問題進(jìn)行算法設(shè)計求解的

能力；2.3具備對算法性能進(jìn)行分析的能力；課程目標(biāo)2.4：具備把解決工程實(shí)際問題設(shè)計的算法

通過具體的編程語言加以實(shí)現(xiàn)求解的能力。

（一）課程內(nèi)容

1.查找的基本概念。（講授）

2.順序表的查找、有序表的折半查找以及索引順序表查找。（講授+演示+案例+對比）

3.二叉排序樹定義、查找、插入、刪除以及查找性能的分析。（講授+演示+對比）

4.平衡二叉樹的定義以及平衡旋轉(zhuǎn)。（講授+演示+對比+自學(xué)）

5.散列表的基本概念、散列函數(shù)、處理溢出的閉散列方法和開散列方法以及散列表查找

分析。（講授+演示）

（二）教學(xué)要求

1.理解查找的基本思想及查找成功和不成功的概念，掌握平均查找長度和最大查找長度

的定義和計算方法。

2.掌握在順序表、有序表上的查找方法及其算法實(shí)現(xiàn)，并具有對順序表、有序表、索引

順序表進(jìn)行查找分析的能力。

3.掌握二叉排序樹的插入、查找方法及其算法實(shí)現(xiàn)，并具有對二叉排序樹進(jìn)行查找分析

的能力，了解二叉排序樹的刪除操作及其算法實(shí)現(xiàn)。

4.了解平衡二叉樹的平衡旋轉(zhuǎn)和構(gòu)造過程。

5.掌握散列表的構(gòu)造方法，并具有對散列表進(jìn)行查找和分析的能力。

（三）重點(diǎn)與難點(diǎn)

1.重點(diǎn)

順序表的查找、二叉排序樹的查找和插入以及查找性能的分析、散列表的構(gòu)造方法以

及查找性能的分析。

2.難點(diǎn)

二叉排序樹刪除操作的算法實(shí)現(xiàn)、平衡二叉樹的平衡旋轉(zhuǎn)和構(gòu)造過程。

第八章排序

本章支持課程目標(biāo)L8：理解排序的基本概念，掌握各種排序方法及算法設(shè)計與描述，掌握對

算法性能進(jìn)行分析的方法并獲得有效結(jié)論；課程目標(biāo)2.1：具備依據(jù)工程實(shí)際問題的需求合理地組

織數(shù)據(jù)，并在計算機(jī)中有效地存儲數(shù)據(jù)的能力；2.2具備為解決工程實(shí)際問題進(jìn)行算法設(shè)計求解的

能力；2.3具備對算法性能進(jìn)行分析的能力；課程目標(biāo)2.4：具備把解決工程實(shí)際問題設(shè)計的算法

通過具體的編程語言加以實(shí)現(xiàn)求解的能力。

（-）課程內(nèi)容

1.基本概念。（講授）

2.插入排序。（講授+演示+對比）

3.交換排序。（講授+演示+對比）

4.選擇排序。（講授+演示+對比）

5.歸并排序。（講授+演示）

6.基數(shù)排序。（講授+演示+對比）

7.各種內(nèi)部排序方法的比較討論。（講授+對比）

(二)教學(xué)要求

1.理解排序的基本思想和基本概念，理解穩(wěn)定性的概念。

2.掌握各種排序方法的基本思想、步驟、算法，并具有時空效率分析的能力。

3.了解各種典型的內(nèi)部排序算法的特點(diǎn)和適用范圍。

(三)重點(diǎn)與難點(diǎn)

1.重點(diǎn)

各種排序方法及時空效率分析。

2.難點(diǎn)

快速排序、堆排序及其算法實(shí)現(xiàn)。

三、本課程開設(shè)的實(shí)驗(yàn)項目

編號實(shí)驗(yàn)項目名稱學(xué)時類型要求支撐的課程目標(biāo)

1.1線性表操作4設(shè)計性必做1.2,2.1,2.2,2.3,2.4

2.二叉樹操作4設(shè)計性必做1.5,2.1,2.2,2.3,2.4

3.2圖的操作4驗(yàn)證性必做1.6,2.1,2.2,2.3,2.4

4.查找操作2驗(yàn)證性必做1.7,2.1,2.2,2.3,2.4

5.內(nèi)部排序操作2驗(yàn)證性必做1.8,2.1,2.2,2.3,2.4

注：1.“類型”填驗(yàn)證性、綜合性、設(shè)計性等；

2.“要求”填必做、選做。

實(shí)驗(yàn)一線性表操作

1.實(shí)驗(yàn)內(nèi)容

單鏈表的創(chuàng)建、合并和輸出。

【擴(kuò)展內(nèi)容】以順序表為存儲結(jié)構(gòu)實(shí)現(xiàn)類似的功能要求。

2.實(shí)驗(yàn)?zāi)康?/p>

(1)熟悉用VisualC++進(jìn)行程序設(shè)計的方法。

(2)掌握單鏈表的創(chuàng)建、查找、插入和合并等運(yùn)算。

3.實(shí)驗(yàn)題目

本實(shí)驗(yàn)要求實(shí)現(xiàn)以下功能：

(1)從鍵盤輸入順序任意的5個整數(shù)，按有序插入的要求生成第一個有序單鏈表(不是通過

排序方法生成)，將該鏈表輸出顯示.

(2)再從鍵盤輸入順序任意的5個整數(shù)，按有序插入的要求生成第二個有序單鏈表(不是通

過排序方法生成)，將該鏈表輸出顯示。

(3)將這兩個有序單鏈表合并成一個有序單鏈表，可以使用兩個單鏈表的原有空間進(jìn)行合

并或者合并成新的有序單鏈表，將生成的有序單鏈表輸出顯示。

4.實(shí)驗(yàn)儀器設(shè)備

(1)學(xué)生每個一臺PC機(jī)。

(2)已安裝VS.net環(huán)境。

實(shí)驗(yàn)二二叉樹操作

1.實(shí)驗(yàn)內(nèi)容

二叉樹的建立和遍歷。

2.實(shí)驗(yàn)?zāi)康?/p>

(1)進(jìn)一步掌握指針變量的使用。

(2)掌握二叉樹的結(jié)構(gòu)特征以及各種存儲結(jié)構(gòu)的特點(diǎn)及使用范圍。

(3)掌握用指針類型描述、訪問和處理二叉樹的運(yùn)算。

(4)掌握?；蜿犃械氖褂?。

3.實(shí)驗(yàn)題目

本實(shí)驗(yàn)要求實(shí)現(xiàn)以下功能：

(1)按前序次序建立一棵二叉樹，以，#'表示空。

(2)中序、后序遍歷該二叉樹，輸出遍歷序列。

(3)求出該二叉樹的深度并輸出，或求出該二叉樹的葉子數(shù)目并輸出。

(4)試以棧為輔助存儲結(jié)構(gòu)實(shí)現(xiàn)二叉樹的前序非遞歸算法或以隊列為輔助存儲結(jié)構(gòu)實(shí)現(xiàn)二

叉樹的層次遍歷算法。

4.實(shí)驗(yàn)儀器設(shè)備

(1)學(xué)生每個一臺PC機(jī)。

(2)已安裝VS.net環(huán)境。

實(shí)驗(yàn)三圖的操作

1.實(shí)驗(yàn)內(nèi)容

圖的生成和圖的遍歷。

2.實(shí)驗(yàn)?zāi)康?/p>

(1)掌握圖的基本存儲方法——鄰接表和鄰接矩陣。

(2)熟練掌握圖的兩種遍歷方法。

3.實(shí)驗(yàn)題目

本實(shí)驗(yàn)要求實(shí)現(xiàn)以下功能：

(1)以鄰接矩陣或鄰接表作為存儲結(jié)構(gòu)建立一個無向圖。

(2)按深度優(yōu)先遍歷該無向圖，輸出遍歷序列。

(3)按廣度優(yōu)先遍歷該無向圖，輸出遍歷序列。

4.實(shí)驗(yàn)儀器設(shè)備

(1)學(xué)生每個一臺PC機(jī)。

(2)已安裝VS.net環(huán)境。

實(shí)驗(yàn)四查找操作

1.實(shí)驗(yàn)內(nèi)容

二叉排序樹的建立、二叉排序樹中結(jié)點(diǎn)的查找。

2.實(shí)驗(yàn)?zāi)康?/p>

(1)熟悉二叉排序樹的定義。

(2)理解二叉排序樹的建立過程。

(3)掌握二叉排序樹中查找結(jié)點(diǎn)的算法。

3.實(shí)驗(yàn)題目

本實(shí)驗(yàn)要求實(shí)現(xiàn)以下功能：

(1)對從鍵盤輸入的順序任意的若干個正整數(shù)建立一顆二叉排序樹，以-1作為結(jié)束。

(2)按先序、中序和后序遍歷該二叉排序樹，輸出每種遍歷的結(jié)果。

(3)從鍵盤輸入一個整數(shù)，在二叉排序樹中查找，給出是否查找成功的結(jié)果。

4.實(shí)驗(yàn)儀器設(shè)備

(1)學(xué)生每個一臺PC機(jī)。

(2)已安裝VS.net環(huán)境。

實(shí)驗(yàn)五內(nèi)部排序操作

1.實(shí)驗(yàn)內(nèi)容

快速排序。

2.實(shí)驗(yàn)?zāi)康?/p>

(1)熟悉各種內(nèi)部排序算法的思想。

(2)理解快速排序算法。

3.實(shí)驗(yàn)題目

本實(shí)驗(yàn)要求實(shí)現(xiàn)以下功能：對從鍵盤輸入的順序任意的8個正整數(shù)，通過快速排序使之成為

有序的序列。輸出每一趟排序的結(jié)果。

4.實(shí)驗(yàn)儀器設(shè)備

(1)學(xué)生每個一臺PC機(jī)。

(2)已安裝VS.net環(huán)境。

注：本課程為專業(yè)基礎(chǔ)課，授課對象為大二本科生，實(shí)驗(yàn)類型主要包括驗(yàn)證性實(shí)驗(yàn)和設(shè)計性實(shí)

驗(yàn)，實(shí)驗(yàn)報告主要包括題目、實(shí)驗(yàn)內(nèi)容、程序中使用的數(shù)據(jù)結(jié)構(gòu)及符號說明、程序的主要流程圖、

程序主要模塊的功能說明、程序運(yùn)行時的初值和運(yùn)行結(jié)果、收獲及體會、源程序。實(shí)驗(yàn)評價內(nèi)容與

評分比重以及評分細(xì)則參見附錄lo

四、學(xué)時分配及教學(xué)方法

章教學(xué)形式及學(xué)時分配

課堂實(shí)上課程主要教學(xué)方法支撐的課程目標(biāo)

小計

教學(xué)驗(yàn)機(jī)實(shí)踐

第一章緒論202講授1.1,2.3

1.2,2.1,2.2,

第二章線性表10414講授+演示

2.3,2.4

第三章棧、隊列講授+案例+演1.3,2.1,2.2,

404

和遞歸示2.3,2.4

第四章串、數(shù)組1.4,2.1,2.2,2.3

404講授+演示

和廣義表

第五章樹和二講授+演示+案1.5,2.1,2.2,

10414

叉樹例+互動2.3,2.4

講授+演示+案1.6,2.1,2.2,

第六章圖10414

例+自學(xué)2.3,2.4

講授+案例+演1.7,2.1,2.2,

第七章查找8210

示+對比+自學(xué)2.3,2.4

講授+演示+對1.8,2.1,2.2,

第八章排序8210

比2.3,2.4

合計561672

五、課程考核

(-)考核方式

考核形式考核要求考核權(quán)重對指標(biāo)點(diǎn)支持備注

主要考核學(xué)生對課堂講授的知識

點(diǎn)的復(fù)習(xí)、理解和掌握程度，考核

2.3(60%)

平時作業(yè)作業(yè)是否提交或按時提交、考核所10%

3.1(40%)

完成作業(yè)的質(zhì)量和正確程度?？偡?/p>

數(shù)平均計算(取5次作業(yè))

主要考核學(xué)生課堂聽講出勤情況。

課堂考勤5%

缺勤一次扣1分

完成5個實(shí)驗(yàn)，每次3分；主要考

2.3(40%)評分細(xì)則見附

實(shí)驗(yàn)查問題分析能力，編程實(shí)現(xiàn)能力和15%

3.1(60%)錄1

結(jié)果分析能力

1.3(20%)

期末考試閉卷70%

2.3(80%)

(-)本課程畢業(yè)要求達(dá)成度計算

畢業(yè)要求指標(biāo)點(diǎn)達(dá)成度=

n乙1￡對應(yīng)指標(biāo)點(diǎn)在總評中所占分?jǐn)?shù)

說明：課程指標(biāo)點(diǎn)達(dá)成度為對應(yīng)指標(biāo)點(diǎn)部分的所有得分除以對應(yīng)指標(biāo)點(diǎn)在總評成績的所占的總分?jǐn)?shù),

對應(yīng)指標(biāo)點(diǎn)的得分包括平時作業(yè)部分、實(shí)驗(yàn)部分、期末考試成績部分，其中n為總評成績合格的學(xué)

生數(shù)。

六'參考書目及學(xué)習(xí)資料（書名，主編，出版社，出版時間及版次）

1.《數(shù)據(jù)結(jié)構(gòu)（C語言版）》，嚴(yán)蔚敏，清華大學(xué)出版社，1997年第1版。

2.《數(shù)據(jù)結(jié)構(gòu)（用面向?qū)ο蠓椒ㄅcC++語言描述）》，殷人昆，清華大學(xué)出版社，2007年第2版。

3.《數(shù)據(jù)結(jié)構(gòu)、算法與應(yīng)用:C++語言描述數(shù)據(jù)結(jié)構(gòu)、算法與應(yīng)用：C++語言描述（Data

Structures,Algorithms.andApplicationinC++）》，［美］Sartaj,Sahni著，王立柱等譯，機(jī)械工業(yè)出版

社，2015年第2版。

七'大綱說明（內(nèi)容可包括課程基本要求、習(xí)題要求及其它一些必要的說明）

1.采用多媒體和黑板相結(jié)合的教學(xué)手段，配合例題的講解及適當(dāng)?shù)乃伎碱}，保證講課進(jìn)度的同

時，注意學(xué)生的掌握程度和課堂的氣氛。

2.根據(jù)各章節(jié)的具體情況，課后可布置適當(dāng)?shù)臅孀鳂I(yè)或思考題，以加深學(xué)生對所學(xué)內(nèi)容的理

解和掌握。

3.本課程有16個學(xué)時的實(shí)驗(yàn)，具體實(shí)驗(yàn)內(nèi)容任課教師亦可以根據(jù)實(shí)際教學(xué)情況適當(dāng)安排。

2017年9月15日

附錄1:實(shí)驗(yàn)評價內(nèi)容與評分比重以及評分細(xì)則

實(shí)驗(yàn)評價內(nèi)容與評分比重

評分項所占對畢業(yè)要求指

實(shí)驗(yàn)評價內(nèi)容要求

編號比重標(biāo)點(diǎn)支撐

要求理解實(shí)驗(yàn)要求、合理地組織數(shù)3.1

1問題分析與建模20%

據(jù)和存儲數(shù)據(jù)。

能夠編程實(shí)現(xiàn),給出正確的運(yùn)行結(jié)2.3

2編程實(shí)現(xiàn)能力與運(yùn)行結(jié)果40%

果。

能夠分析結(jié)果的有效性,并清晰表3.1

3結(jié)果分析與表述能力30%

述結(jié)論

4報告清晰，按時提交10%報告清晰，提交準(zhǔn)時3.1

注：具體評分細(xì)則見下表的實(shí)驗(yàn)評分細(xì)則。

實(shí)驗(yàn)評分細(xì)則（每次作業(yè)按100分計算）

不及格（59及

項目優(yōu)秀(100-90)良好（80-89）中等(70-79)及格(60-69)

以下）

問題分析能夠理解本次能夠理解本次