大數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)實(shí)訓(xùn)教案設(shè)計(jì)

1、數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)實(shí)訓(xùn)教案授課教師職稱開課單位課程名稱數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)實(shí)訓(xùn)課程代 碼課程性質(zhì)必修2公共 基礎(chǔ)課學(xué)科基礎(chǔ)課專業(yè)課實(shí)踐性環(huán)節(jié)2其它選修口選修口課程學(xué)時(shí)3232課程學(xué) 分2 2學(xué)時(shí)分配理論學(xué)時(shí)（0 0）實(shí)踐學(xué)時(shí)（3232 ）優(yōu)選專業(yè)軟件工程教學(xué)班學(xué)年學(xué)期20152015 學(xué)年第 2 2 學(xué)期授課方式多媒體+ +實(shí)驗(yàn)考核方 式考試2考查口教材名稱數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)作者劉燕君 等 出版社及 出版時(shí)間機(jī)械工業(yè)出版社，20142014扌曰疋參考書數(shù)據(jù)結(jié)構(gòu)（C+C+版）作者王紅梅 等出版社及 出版時(shí)間清華大學(xué)出版社，20112011數(shù)據(jù)結(jié)構(gòu)項(xiàng)目實(shí)訓(xùn)戴文華 等人民郵電出 版社，20122012教

2、案編寫時(shí)間20152015 年 3 3 月1早節(jié) 名稱第一早數(shù)據(jù)結(jié)構(gòu)概論教學(xué) 時(shí)數(shù)1 1授課 方式課堂講授教學(xué) 目的 及要求1.理解數(shù)據(jù)結(jié)構(gòu)的定義，并掌握數(shù)據(jù)結(jié)構(gòu)研究的內(nèi)容2.理解數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)使用的4 種基本存儲(chǔ)方法3.掌握時(shí)間復(fù)雜度的計(jì)算方法教學(xué) 重點(diǎn) 與難點(diǎn)正確理解算法的有窮性和可行性的含義，掌握空間復(fù)雜度的計(jì)算方法討論練習(xí)作業(yè)1.求解百錢買百雞問題P3，實(shí)驗(yàn)題目 1.4.1教學(xué) 手段多媒體+課后練習(xí)參考 資料1. 劉燕君，等.數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)（C+語言描述）M.機(jī)械工業(yè)出版社，2014.2. 王紅梅，等.數(shù)據(jù)結(jié)構(gòu)（C+版） M.清華大學(xué)出版社，2011.3. 戴文華，等.數(shù)據(jù)結(jié)構(gòu)項(xiàng)目實(shí)

3、訓(xùn)M.人民郵電出版社，2012.具體 內(nèi)容1.學(xué)習(xí)目的10mi ns2.數(shù)據(jù)結(jié)構(gòu)定義及研究?jī)?nèi)容15mi ns3.數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)方式10mi ns4.空間復(fù)雜度的計(jì)算10mi ns2早節(jié)名稱第一早類和類模板編程教學(xué) 時(shí)數(shù)1 1授課 方式課堂講授+實(shí)訓(xùn)教學(xué) 目的 及要求1.熟悉類模板的設(shè)計(jì)2.熟悉動(dòng)態(tài)分配內(nèi)存的方法3.掌握多文件編程和基本調(diào)試方法教學(xué) 重點(diǎn) 與難點(diǎn)1.熟悉模板2.熟悉動(dòng)態(tài)分配內(nèi)存的使用方法討論練習(xí)作業(yè)1.約瑟夫環(huán)游戲程序P10,實(shí)驗(yàn)題目 2.2.1 ,2. 折線程序 P14，實(shí)驗(yàn)題目 2.3.1教學(xué) 手段多媒體+課堂練習(xí)+課后練習(xí)參考 資料1. 劉燕君，等.數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)（C+語言

4、描述）M.機(jī)械工業(yè)出版社，2014.2. 王紅梅，等.數(shù)據(jù)結(jié)構(gòu)（C+版） M.清華大學(xué)出版社，2011.3. 戴文華，等.數(shù)據(jù)結(jié)構(gòu)項(xiàng)目實(shí)訓(xùn)M.人民郵電出版社，2012.具體 內(nèi)容1.模板函數(shù)專門化和模板重載10mi ns2.類模板5mi ns3.在類中使用動(dòng)態(tài)分配內(nèi)存5mi ns4.課堂練習(xí)，難點(diǎn)提示25mi ns3早節(jié)名稱第三早線性表訓(xùn)練教學(xué) 時(shí)數(shù)4 4授課 方式課堂講授+實(shí)訓(xùn)教學(xué) 目的 及要求1.理解線性表的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的異冋2.掌握順序表上實(shí)現(xiàn)的各種基本運(yùn)算的算法3.掌握單鏈表上實(shí)現(xiàn)的各種基本運(yùn)算的算法教學(xué) 重點(diǎn) 與難點(diǎn)1.理解線性表的順序存儲(chǔ)結(jié)構(gòu)優(yōu)缺點(diǎn)2.理解線性表的鏈?zhǔn)?/p>

5、存儲(chǔ)結(jié)構(gòu)優(yōu)缺點(diǎn)3.掌握線性表的基本運(yùn)算的算法4.難點(diǎn)是循環(huán)鏈表討論練習(xí)作業(yè)1.一元多項(xiàng)式的加法運(yùn)算P28，實(shí)驗(yàn)題目 3.3.1 ,2.改進(jìn)的約瑟夫環(huán)游戲?qū)崿F(xiàn)P34，實(shí)驗(yàn)題目 3.4.1教學(xué) 手段多媒體+課堂練習(xí)+課后練習(xí)參考 資料1. 劉燕君，等.數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)（C+語言描述）M.機(jī)械工業(yè)出版社，2014.2. 王紅梅，等.數(shù)據(jù)結(jié)構(gòu)（C+版） M.清華大學(xué)出版社，2011.3. 戴文華，等.數(shù)據(jù)結(jié)構(gòu)項(xiàng)目實(shí)訓(xùn)M.人民郵電出版社，2012.具體 內(nèi)容1.復(fù)習(xí)線性表順序存儲(chǔ)結(jié)構(gòu)特性及基本運(yùn)算10mi ns2.復(fù)習(xí)線性表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)特性及基本運(yùn)算15mi ns3.通過學(xué)生信息表建立的例子，講解鏈表的

6、建立過程20mi ns4.課堂練習(xí)，難點(diǎn)提示135mi ns4早節(jié)名稱第四早棧和隊(duì)列訓(xùn)練教學(xué) 時(shí)數(shù)4 4授課 方式課堂講授+實(shí)訓(xùn)教學(xué) 目的 及要求1.熟悉順序棧、鏈棧、循環(huán)隊(duì)列、鏈隊(duì)列的存儲(chǔ)結(jié)構(gòu)2.熟練掌握順序棧、鏈棧、循環(huán)隊(duì)列、鏈隊(duì)列的基本運(yùn)算3.掌握通過棧或隊(duì)列解決實(shí)際應(yīng)用問題的方法教學(xué) 重點(diǎn) 與難點(diǎn)1.理解棧和隊(duì)列的特性2.熟練掌握棧和隊(duì)列的基本運(yùn)算，在解決實(shí)際應(yīng)用問題中靈活使用棧和隊(duì)列討論練習(xí)作業(yè)1.八皇后問題完整的算法實(shí)現(xiàn)P49，實(shí)驗(yàn)題目 4412.模擬后綴表達(dá)式的計(jì)算過程實(shí)現(xiàn)P 54 ,實(shí)驗(yàn)題目 4.5.1教學(xué) 手段多媒體+課堂練習(xí)+課后練習(xí)參考 資料1. 劉燕君，等.數(shù)據(jù)結(jié)構(gòu)課程

7、設(shè)計(jì)（C+語言描述）M.機(jī)械工業(yè)出版社，2014.2. 王紅梅，等.數(shù)據(jù)結(jié)構(gòu)（C+版） M.清華大學(xué)出版社，2011.3. 戴文華，等.數(shù)據(jù)結(jié)構(gòu)項(xiàng)目實(shí)訓(xùn)M.人民郵電出版社，2012.具體 內(nèi)容1.棧的特性和基本操作10mins2.通過類模板 Stack 的例子說明類模板專門化和使用方法20mins3.隊(duì)列的特性和基本操作10mins4.課堂練習(xí)，難點(diǎn)提示140mins5早節(jié)名稱第五早樹和二叉樹訓(xùn)練教學(xué) 時(shí)數(shù)4 4授課 方式課堂講授+實(shí)訓(xùn)教學(xué) 目的 及要求1.熟悉二叉樹的定義、性質(zhì)2.熟練掌握二叉樹的存儲(chǔ)結(jié)構(gòu)3.熟練掌握二叉樹的遍歷4.了解最優(yōu)二叉樹的特性5.掌握建立最優(yōu)二叉樹和哈夫曼編碼的方法

8、教學(xué) 重點(diǎn) 與難點(diǎn)1.編寫實(shí)現(xiàn)二叉樹的各種運(yùn)算的算法2.解決與樹或二叉樹相關(guān)的應(yīng)用問題3.理解線索化二叉樹討論練習(xí)作業(yè)1.查找結(jié)點(diǎn)并顯示該結(jié)點(diǎn)的層次和路徑P116，實(shí)驗(yàn)題目 7.2.12.哈夫曼編碼算法設(shè)計(jì)及實(shí)現(xiàn)P125，實(shí)驗(yàn)題目 7.4.1教學(xué) 手段多媒體+課堂練習(xí)+課后練習(xí)參考 資料1. 劉燕君，等.數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)（C+語言描述）M.機(jī)械工業(yè)出版社，2014.2. 王紅梅，等.數(shù)據(jù)結(jié)構(gòu)（C+版） M.清華大學(xué)出版社，2011.3. 戴文華，等.數(shù)據(jù)結(jié)構(gòu)項(xiàng)目實(shí)訓(xùn)M.人民郵電出版社，2012.具體 內(nèi)容1.復(fù)習(xí)樹和二叉樹的定義和性質(zhì)10mi ns2.復(fù)習(xí)二叉樹的存儲(chǔ)結(jié)構(gòu)和遍歷20mi ns3

9、.復(fù)習(xí)哈夫曼編碼過程10mi ns4.課堂練習(xí)，難點(diǎn)提示140mi ns6早節(jié)名稱第六早圖結(jié)構(gòu)訓(xùn)練教學(xué) 時(shí)數(shù)4 4授課 方式課堂講授+實(shí)訓(xùn)教學(xué) 目的 及要求1.掌握?qǐng)D的鄰接矩陣和鄰接表兩種基本的存儲(chǔ)方式2.掌握?qǐng)D在兩種存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)的兩種遍歷算法3.掌握求最小生成樹算法思想4.掌握求最短路徑算法思想5.掌握拓?fù)渑判蛩惴ㄋ枷虢虒W(xué) 重點(diǎn) 與難點(diǎn)1.掌握?qǐng)D的鄰接矩陣和鄰接表兩種存儲(chǔ)方式及對(duì)應(yīng)的遍歷算法2.掌握求最小生成樹、求最短路徑以及拓?fù)渑判蛩惴ǖ幕舅枷爰皶r(shí)間性能討論練習(xí)作業(yè)1.無向網(wǎng)絡(luò)的最小生成樹的普利姆算法實(shí)現(xiàn)P135，實(shí)驗(yàn)題目 8.2.12.交通咨詢系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)P138，實(shí)驗(yàn)題目 8.3

10、.1教學(xué) 手段多媒體+課堂練習(xí)+課后練習(xí)參考 資料1. 劉燕君，等.數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)（C+語言描述）M.機(jī)械工業(yè)出版社，2014.2. 王紅梅，等.數(shù)據(jù)結(jié)構(gòu)（C+版） M.清華大學(xué)出版社，2011.3. 戴文華，等.數(shù)據(jù)結(jié)構(gòu)項(xiàng)目實(shí)訓(xùn)M.人民郵電出版社，2012.具體 內(nèi)容1.復(fù)習(xí)圖的基本術(shù)語5mi ns2.復(fù)習(xí)圖的存儲(chǔ)表示方式5mi ns3.復(fù)習(xí)圖的基本運(yùn)算，包括深度優(yōu)先搜索法、廣度優(yōu)先搜索法、生成最小生成樹法和產(chǎn)生最短路徑法30mi ns4.課堂練習(xí)，難點(diǎn)提示140mi ns7早節(jié)名稱第七早排序算法訓(xùn)練教學(xué) 時(shí)數(shù)4 4授課 方式課堂講授+實(shí)訓(xùn)教學(xué) 目的 及要求1.掌握有關(guān)內(nèi)部排序的一些常用方

11、法，包括插入排序、交換排序、選擇排序和歸并排序2.熟悉內(nèi)部排序的基本思想、排序過程、算法實(shí)現(xiàn)、時(shí)間和空間性能分析3.熟悉不同排序算法的差異教學(xué) 重點(diǎn) 與難點(diǎn)1.掌握希爾排序算法2.掌握快速排序算法3.熟練掌握堆排序算法討論練習(xí)作業(yè)1.堆排序算法設(shè)計(jì)及實(shí)現(xiàn)P159，實(shí)驗(yàn)題目 9.3.12.學(xué)生成績(jī)處理系統(tǒng)P161 ,實(shí)驗(yàn)題目 9.4.1教學(xué) 手段多媒體+課堂練習(xí)+課后練習(xí)參考 資料1. 劉燕君，等.數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)（C+語言描述）M.機(jī)械工業(yè)出版社，2014.2. 王紅梅，等.數(shù)據(jù)結(jié)構(gòu)（C+版） M.清華大學(xué)出版社，2011.3. 戴文華，等.數(shù)據(jù)結(jié)構(gòu)項(xiàng)目實(shí)訓(xùn)M.人民郵電出版社，2012.具體

12、內(nèi)容1.復(fù)習(xí)排序的基本概念5mi ns2.復(fù)習(xí)經(jīng)典的排序算法30mi ns3.比較幾種排序算法的時(shí)間復(fù)雜度、穩(wěn)定性、輔助空間、對(duì)記錄存儲(chǔ)方式的要求和排序方法的選取10mi ns4.課堂練習(xí)，難點(diǎn)提示135mi ns8早節(jié)名稱第八早查找算法訓(xùn)練教學(xué) 時(shí)數(shù)2 2授課 方式課堂講授+實(shí)訓(xùn)教學(xué) 目的 及要求1.熟悉各種查找算法，并能熟練應(yīng)用2.掌握順序查找、二分查找、二叉查找樹上的查找，以及散列表上的查找的基本思想和 算法實(shí)現(xiàn)3.熟悉查找算法的評(píng)價(jià)方法教學(xué) 重點(diǎn) 與難點(diǎn)1.掌握線性表和二叉排序樹的查找方法2.難點(diǎn)是解決散列表沖突的方法3.掌握查找方法所需的存儲(chǔ)結(jié)構(gòu)討論練習(xí)作業(yè)1.航班信息的查詢與檢索

13、P177，實(shí)驗(yàn)題目 10.3.1教學(xué) 手段多媒體+課堂練習(xí)+課后練習(xí)參考 資料1. 劉燕君，等.數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)（C+語言描述）M.機(jī)械工業(yè)出版社，2014.2. 王紅梅，等.數(shù)據(jù)結(jié)構(gòu)（C+版） M.清華大學(xué)出版社，2011.3. 戴文華，等.數(shù)據(jù)結(jié)構(gòu)項(xiàng)目實(shí)訓(xùn)M.人民郵電出版社，2012.具體 內(nèi)容1.復(fù)習(xí)順序表查找算法10mins2.復(fù)習(xí)二叉排序樹上的查找算法15mi ns3.復(fù)習(xí)散列表查找算法15mins4.課堂練習(xí)，難點(diǎn)提示50mins9早節(jié)名稱第九早分治算法訓(xùn)練教學(xué) 時(shí)數(shù)4 4授課 方式課堂講授+實(shí)訓(xùn)教學(xué) 目的 及要求1.掌握分治算法的基本原理2.利用分治策略編程解決輸油管道、循環(huán)賽日

14、程表、郵局選址和集合劃分問題教學(xué) 重點(diǎn) 與難點(diǎn)掌握分治算法的設(shè)計(jì)思想，通過實(shí)際問題來應(yīng)用分治設(shè)計(jì)算法討論練習(xí)作業(yè)1.輸油管道問題2.循環(huán)賽日程表3.郵局選址4.集合劃分教學(xué) 手段多媒體+課堂練習(xí)+課后練習(xí)參考 資料1. （美）克林伯格，等算法設(shè)計(jì)M.清華大學(xué)出版社，2007.2. Thomas H.Cormen，等.算法導(dǎo)論M.機(jī)械工業(yè)出版社出版（第二版），2006.具體 內(nèi)容1.復(fù)習(xí)分治算法框架10mi ns2.分析典型二分法30mi ns3.課堂練習(xí)，難點(diǎn)提示140mi ns10早節(jié)名稱第十早回溯算法訓(xùn)練教學(xué) 時(shí)數(shù)4 4授課 方式課堂講授+實(shí)訓(xùn)教學(xué) 目的 及要求1.掌握回溯算法的基本原理2.利用回溯策略編程解決橋本分?jǐn)?shù)式、馬的遍歷、素?cái)?shù)環(huán)和排列樹的回溯搜索問題教學(xué) 重點(diǎn) 與難點(diǎn)掌握回溯算法的設(shè)計(jì)思想，通過實(shí)際問題來應(yīng)用回