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

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

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

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

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

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

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

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

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

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

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

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

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

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

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