《數(shù)據(jù)結(jié)構(gòu)與算法》教學(xué)大綱(22+10)

《數(shù)據(jù)結(jié)構(gòu)與算法》課程教學(xué)大綱

課程英文名稱(chēng)：DataStructuresandAlgorithm

課程編號(hào)：0801330學(xué)分：2學(xué)時(shí)：22+10

-、課程教學(xué)對(duì)象

本教學(xué)大綱適用于非計(jì)算機(jī)專(zhuān)業(yè)理工科相關(guān)專(zhuān)業(yè)的普通本科學(xué)生數(shù)據(jù)結(jié)構(gòu)課程的理論教學(xué)和課

內(nèi)實(shí)驗(yàn)教學(xué)。

二、課程性質(zhì)及教學(xué)目的

數(shù)據(jù)結(jié)構(gòu)與算法是非計(jì)算機(jī)專(zhuān)業(yè)理工科相關(guān)專(zhuān)業(yè)的選修課程。本課程的教學(xué)活動(dòng)必須實(shí)現(xiàn)滿足學(xué)

生學(xué)習(xí)后繼專(zhuān)業(yè)課程的基本需要；為學(xué)生今后進(jìn)行各種軟件的開(kāi)發(fā)打下扎實(shí)的理論和實(shí)踐基礎(chǔ)的目的，

使學(xué)生在編程能力方面得到比較系統(tǒng)的訓(xùn)練。為此，本課程強(qiáng)調(diào)理論和實(shí)踐的統(tǒng)一，在對(duì)學(xué)生進(jìn)行基

本數(shù)據(jù)結(jié)構(gòu)的理論、技術(shù)和方法培養(yǎng)的同時(shí)，強(qiáng)調(diào)學(xué)生實(shí)踐能力的培養(yǎng)，突出學(xué)生針對(duì)實(shí)際問(wèn)題進(jìn)行

基本數(shù)據(jù)結(jié)構(gòu)分析和設(shè)計(jì)能力的培養(yǎng)。鼓勵(lì)學(xué)生學(xué)以致用，將學(xué)到的知識(shí)用以解決實(shí)際問(wèn)題。

三、對(duì)先修知識(shí)的要求

本課程的先修課程為高級(jí)程序設(shè)計(jì)語(yǔ)言、離散數(shù)學(xué)等。對(duì)先修課程的具體要求是掌握程序設(shè)計(jì)語(yǔ)

言的基本概念；掌握結(jié)構(gòu)化程序設(shè)計(jì)的基本原理以及初步的面向?qū)ο蟪绦蛟O(shè)計(jì)知識(shí)、具備良好的程序

設(shè)計(jì)習(xí)慣和較好的程序調(diào)試能力；掌握離散數(shù)學(xué)的基本理論；具有一定的邏輯思維和推理能力。

四、課程的主要內(nèi)容、基本要求和學(xué)時(shí)分配建議（總學(xué)時(shí)數(shù)：22）

知識(shí)模塊知識(shí)點(diǎn)要求學(xué)時(shí)學(xué)習(xí)方式課外學(xué)習(xí)要求

1.1數(shù)據(jù)結(jié)構(gòu)的研究對(duì)象C課堂講授

1.2數(shù)據(jù)結(jié)構(gòu)的基本概念A(yù)課堂講授

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

1.3抽象數(shù)據(jù)類(lèi)型的概念B2課堂講授

概念

1.4算法的基本概念B課堂講授

1.5算法復(fù)雜度的基本概念B課堂討論

2.1線性表的定義及其邏輯特征B課堂講授

2.2線性表的抽象數(shù)據(jù)類(lèi)型定義B課堂講授

2.3順序表的存儲(chǔ)結(jié)構(gòu)、基本操

2、線性表A2課堂討論

作算法及其時(shí)間性能

2.4各種鏈表結(jié)構(gòu)中實(shí)現(xiàn)線性表

A課堂講授

操作的基本方法

3、棧和隊(duì)列3.1棧的定義及其操作特性B2課堂講授

3.2順序棧的實(shí)現(xiàn)方法A課堂討論

3.3隊(duì)列的定義及其操作特性B課堂講授

3.4順序隊(duì)列的實(shí)現(xiàn)方法A課堂討論

4.1樹(shù)的定義及其基本術(shù)語(yǔ)C課堂講授

4.2樹(shù)和森林的遍歷方法B課堂講授

4.3二叉樹(shù)的定義及特點(diǎn)、二叉樹(shù)

B課堂講授

的基本性質(zhì)

4、樹(shù)和二叉4.4二叉樹(shù)的各種存儲(chǔ)結(jié)構(gòu)方法、

A4課堂講授

樹(shù)遍歷方法

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

B課堂討論

法

4.6哈夫曼樹(shù)的構(gòu)造方法和哈夫

A課堂講授

曼編碼方法

5.1圖的邏輯結(jié)構(gòu)及遍歷方法A課堂講授

5.2圖的存儲(chǔ)結(jié)構(gòu)及其實(shí)現(xiàn)A課堂講授

5、圖5.3最小生成樹(shù)B4課堂講授

5.4最短路徑B課堂講授

5.5AOV網(wǎng)與AOE網(wǎng)B課堂討論

6.1算法與程序A課堂講授

6、算法概述2

6.2算法復(fù)雜性分析B課堂講授

7.1遞歸的概念A(yù)課堂講授

7.2分治法的基本思想A課堂講授

7、遞歸與分

7.3二分搜索技術(shù)A4課堂講授

治策略

7.4大整數(shù)的乘法A課堂講授

7.5Strassen矩陣乘法A課堂講授

8.1動(dòng)態(tài)規(guī)劃算法的基本思想B課堂講授

8.2動(dòng)態(tài)規(guī)劃算法的基本要素A課堂講授

8、動(dòng)態(tài)規(guī)劃8.3矩陣連乘問(wèn)題A2課堂講授

8.4最長(zhǎng)公共子序列A課堂講授

8.5最大子段和問(wèn)題B課堂講授

注：知識(shí)點(diǎn)中粗體字部分為本課程的重點(diǎn)或難點(diǎn)

五、建議使用教材及參考書(shū)

[1J王紅梅，胡明，王濤.數(shù)據(jù)結(jié)構(gòu)（C++版）（第2版）[M].北京：清華大學(xué)出版社，2011

[2]王紅梅，胡明，王濤.數(shù)據(jù)結(jié)構(gòu)（C++版）學(xué)習(xí)輔導(dǎo)和實(shí)驗(yàn)指導(dǎo)[M].北京：清華大學(xué)出版社,

2006

[3J嚴(yán)蔚敏.數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）[M].北京：清華大學(xué)出版社，2002

[4]王曉東.計(jì)算機(jī)算法設(shè)計(jì)與分析[M].北京：電子工業(yè)出版社，2007

[5]余祥宣，崔國(guó)華，鄒海明.計(jì)算機(jī)算法基礎(chǔ)（第三版）[M].武漢：華中科技大學(xué)出版社，2006

[6]蘇德富，鐘誠(chéng).計(jì)算機(jī)算法設(shè)計(jì)與分析[M].北京：電子工業(yè)出版社，2001

[7]曹新譜.算法設(shè)計(jì)與分析[M].長(zhǎng)沙：湖南科學(xué)技術(shù)出版社，1984

[8]王曉東.算法設(shè)計(jì)與分析習(xí)題解答[M].北京：清華大學(xué)出版社，2006

[9]張永，李睿，年福忠.算法與數(shù)據(jù)結(jié)構(gòu)[MJ.北京：國(guó)防工業(yè)出版社，2008

六、課程考核方式

本課程采用筆試閉卷的考核方式，要求學(xué)生熟練掌握課程教學(xué)目標(biāo)要求的內(nèi)容，并能有效表達(dá)和

運(yùn)用，以達(dá)到該課程的能力培養(yǎng)目標(biāo)。

采用平時(shí)成績(jī)和期末考試成績(jī)相結(jié)合的方式：平時(shí)表現(xiàn)（考勤、隨堂提問(wèn)、作業(yè)、隨堂測(cè)驗(yàn)、實(shí)

驗(yàn)環(huán)節(jié)）：30%,期末考試：70%o

七、課內(nèi)實(shí)驗(yàn)（實(shí)訓(xùn)）環(huán)節(jié)及要求（總學(xué)時(shí)數(shù)：10）

根據(jù)實(shí)際教學(xué)情況和學(xué)生意愿，在以下實(shí)驗(yàn)中選擇5個(gè)實(shí)現(xiàn)項(xiàng)目（10學(xué)時(shí)），并通過(guò)課外編程進(jìn)行

學(xué)時(shí)補(bǔ)充。

序號(hào)實(shí)驗(yàn)（實(shí)訓(xùn)）項(xiàng)目實(shí)驗(yàn)（實(shí)訓(xùn)）內(nèi)容實(shí)驗(yàn)（實(shí)訓(xùn)）目的及要求學(xué)時(shí)

運(yùn)用高級(jí)語(yǔ)言（C++/Java）

理解線性表的順序存儲(chǔ)結(jié)構(gòu)

順序表處理程序的設(shè)編寫(xiě)一個(gè)至少包含四個(gè)基

1的實(shí)現(xiàn)方法及其各種操作的2

計(jì)本功能的順序表處理程

算法設(shè)計(jì)方法。

序，調(diào)試、給出正確結(jié)果。

運(yùn)用高級(jí)語(yǔ)言（C++/Java）

理解線性表的鏈接存儲(chǔ)結(jié)構(gòu)

鏈接表處理程序的設(shè)編寫(xiě)一個(gè)至少包含四個(gè)基

2的實(shí)現(xiàn)方法及其各種操作的2

計(jì)本功能的鏈接表處理程

算法設(shè)計(jì)方法。

序，調(diào)試、給出正確結(jié)果。

運(yùn)用高級(jí)語(yǔ)言（C++/Java）

編寫(xiě)一個(gè)包含入棧、出棧

3棧的基本操作理解棧的應(yīng)用2

基本操作的程序，調(diào)試、