《數(shù)據(jù)結(jié)構(gòu)》教案

1、安慶師范學(xué)院教案（課時計劃）課程名稱：數(shù)據(jù)結(jié)構(gòu)授課班級：授課地點：主講教師：程玉勝2015-2016學(xué)年第2學(xué)期7001、數(shù)據(jù)結(jié)構(gòu)的概念及相關(guān)術(shù)語02、抽象數(shù)據(jù)類型的表示與實現(xiàn)、算法和算法分析03、線性表的類型左義、線性表的順序表示和實現(xiàn)04、線性表的鏈式表示和實現(xiàn)（線性鏈表）05、循環(huán)鏈表、雙向鏈表、一元多項式的表示及相加06、棧、棧應(yīng)用舉例（數(shù)制轉(zhuǎn)換、括號匹配、行編輯）07、迷宮求解、表達式求值、棧與遞歸的實現(xiàn)0&隊列09、機動10、習(xí)題課1K串類型的泄義、串的表示和實現(xiàn)12、串的模式匹配算法、串操作應(yīng)用舉例13、數(shù)組的泄義、順序表示和實現(xiàn)、矩陣的壓縮存儲14、稀疏矩陣的存儲結(jié)構(gòu)、

2、廣義表15、樹的左義和基本術(shù)語、二叉樹的左義16、二叉樹的性質(zhì)、二叉樹的存儲結(jié)構(gòu)17、遍歷二叉樹和線索二叉樹18、樹和森林19、赫夫曼樹及苴應(yīng)用20、習(xí)題課21、圖的定義和術(shù)語、圖的存儲結(jié)構(gòu)22、十字鏈表、鄰接多重表、圖的遍歷23、圖的連通性問題24、有向無環(huán)圖及苴應(yīng)用25、最短路徑26、靜態(tài)査找表27、二叉排序樹和平衡二叉樹28、B-樹和B+樹29、哈希表30、排序概述、插入排序31、快速排序、選擇排序32、歸并排序、基數(shù)排序33、外部排序、各種排序方法的比較34、文件編 號周 次1日93課時2期安排課 題數(shù)據(jù)結(jié)構(gòu)的概念及相關(guān)術(shù)語教 材的 重 點、 難點 分析重點：(1)數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)(

3、2)數(shù)據(jù)結(jié)構(gòu)的存儲結(jié)構(gòu)(3)抽象數(shù)據(jù)類型的槪念教孳目一掌握數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)對象的概念熟練掌握數(shù)據(jù)結(jié)構(gòu)的槪念及其邏輯結(jié)構(gòu)和物理結(jié)構(gòu)的分類掌握抽象數(shù)據(jù)類型的定義方法教SIS講授法多媒體教學(xué)內(nèi)容安排與板書設(shè)計：第一章緒論1. 1什么是數(shù)據(jù)結(jié)構(gòu)非數(shù)值計算問題舉例數(shù)據(jù)結(jié)構(gòu)產(chǎn)生的背景數(shù)據(jù)結(jié)構(gòu)在計算機科學(xué)中的地位和作用1. 2基本概念和術(shù)語數(shù)據(jù)數(shù)據(jù)元素數(shù)據(jù)對象數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的形式泄義Data-Structure =(D, S)數(shù)據(jù)的邏輯結(jié)構(gòu)及分類：集合、線性、樹形、圖形結(jié)構(gòu)學(xué)過程數(shù)據(jù)的物理結(jié)構(gòu)：順序存儲結(jié)構(gòu)與鏈式存儲結(jié)構(gòu)數(shù)據(jù)類型抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型的形式定義ADT= (D,S,P)抽象數(shù)據(jù)類型泄義

4、舉例-Triplet師生雙邊活動；提問：什么是數(shù)據(jù)類型？舉例：演示實驗：教具準備：課 后作 業(yè)1.2,1.19教 學(xué)后 記教材：嚴蔚敏吳偉民編著：數(shù)據(jù)結(jié)構(gòu)(C語言版)，淸華大學(xué)出版社.1997 年參考書目：lWirth N： Algorithms+Data Structures=Programs, Prentice-Hall Inc., 1976対S巴斯：計算機算法:設(shè)計和分析引論,復(fù)旦大學(xué)出版社,1985號2周 次1日96課時2期安排課 題抽象數(shù)據(jù)類型的表示與實現(xiàn)、算法和算法分析教 材的 重AA >難點 分析重點：(1)算法復(fù)雜度的分析方法難點：(1)算法復(fù)雜度的分析方法學(xué)(1)理解數(shù)

5、據(jù)抽象的意義(2)熟悉類C語言(3)掌握抽象數(shù)據(jù)類型的表示和實現(xiàn)方法目(4)掌握算法描述和算法分析的方法教醫(yī)豔教學(xué)內(nèi)容安與排板書設(shè)計：1. 3抽象數(shù)據(jù)類型的表示和實現(xiàn)數(shù)據(jù)抽象的意義類C語言抽象數(shù)據(jù)類型的表示和實現(xiàn)舉例教學(xué)過程1. 4算法和算法分析算法算法的定義算法的特性：有窮性、確定性、可行性、輸入、輸岀算法設(shè)計的要求正確性、可讀性、健壯性、效率與低存儲量需求算法效率的度量時間度量的方法分析時間復(fù)雜度T(n) = O(f(n)時間復(fù)雜度的計算算法的存儲空間需求S(n) = O(f(n)師生雙邊活動：提問：舉例：演示實驗：教具準備：課 后作 業(yè)1.4,1.20教 學(xué)后 記編 號3周 次2日910

6、課時2期安排課 題線性表的類型進義、線性表的順序表示和實現(xiàn)教 材的 重 點X 難點 分析重點：(1)順序表的基本運算(2)順序表上實現(xiàn)的各種算法的時間性能分析教學(xué)目標(biāo)(1)理解線性表的邏輯結(jié)構(gòu)特征(2)熟練掌握順序表的描述方法、特點及有關(guān)概念(3)熟練掌握順序表的基本運算教學(xué)內(nèi)容安排與板書設(shè)計：第二章線性表線性結(jié)構(gòu)的特點2. 1線性表的類型定義線性表的定義及其表示線性表的類型定義線性表操作舉例：用線性表表示集合、線性表的合并教學(xué) 過 程2. 2線性表的順序表示和實現(xiàn)線索性表的順序表示線性表的順序存儲結(jié)構(gòu)的定義及其特征順序表的基本運算順序表的初始化順序表的插入操作順序表的刪除操作順序表的合并順序

7、表基本操作的時間復(fù)雜度計算師生雙邊活動：提問：舉例：演示實驗：教具準備：課 后作 業(yè)2.12教 學(xué)后記編 號4周 次2日913課時2期安排課 題線性表的鏈式表示和實現(xiàn)(線性鏈表)教 材的重 點 難點 分析重點：(1)鏈表的基本運算(2)鏈表上實現(xiàn)的各種算法的時間性能分析教學(xué)目鮭(1)熟練掌握鏈表的描述方法、特點及有關(guān)概念(2)掌握鏈表的基本運算(3)掌握靜態(tài)鏈表的構(gòu)造方法教算鬻教學(xué)內(nèi)容安排與板書設(shè)計：2. 3線性表的鏈式表示和實現(xiàn)2. 3. 1線性鏈表單鏈表的定義單鏈表的存儲結(jié)構(gòu)特征單鏈表的基本操作：插入教學(xué) 過 :rn刪除有序鏈表的合并靜態(tài)鏈表靜態(tài)鏈表的定義靜態(tài)鏈表的操作舉例程師生雙邊活動：

8、提問：mallocf) free()舉例：演示實驗：教具準備：課 后作 業(yè)2.17,2.25教學(xué)后13編號5周 次2 時 課排 安179 日期3課題教 材的 重難點 分析教學(xué)目Vn方和學(xué)段 學(xué)法教手教學(xué)3.2.過 程循環(huán)鏈表的定義循環(huán)鏈表的操作教學(xué)過程2. 3. 3雙向鏈表雙向鏈表的定義雙向鏈表的操作特點線性鏈表的類型定義2. 4 一元多項式的表示及相加一元多項式的表示一元多項式的相加一元多項式的類型定義多項式的相加算法師生雙邊活動：提問：舉例：演示實驗：教具準備：課 后作 業(yè)2.32教 學(xué)后 記編 號6周 次3日920課時2期安排課 題棧、棧應(yīng)用舉例(數(shù)制轉(zhuǎn)換、括號匹配、行編輯)教 材的 重

9、 點、 難點 分析重點：(1)棧在兩種存儲結(jié)構(gòu)上實現(xiàn)的基本運算。難點：棧滿?？盏臈l件及它們的描述掌握棧這種數(shù)據(jù)結(jié)構(gòu)的特點(2)熟悉棧與線性表的關(guān)系學(xué)(3)重點掌握順序棧和鏈式棧的五種基本運算目(4)掌握棧的應(yīng)用方法教歳鬻教教學(xué)內(nèi)容安排與板書設(shè)計：學(xué)過程第三章棧與隊列3. 1棧3. 1. 1抽象數(shù)據(jù)類型棧的左義棧及其與線性表的關(guān)系棧的類型定義教學(xué)過程3. 1. 2棧的表示和實現(xiàn)順序棧的定義鏈棧的定義3. 2棧的應(yīng)用舉例3. 2. 1數(shù)制轉(zhuǎn)換3. 2. 2括號匹配的檢驗3. 2. 3行編輯程序師生雙邊活動：提問：舉例：演示實驗：教具準備：課3.15后作 業(yè)教 學(xué)后 記編 號7周 次4日9 24豊時

10、2期安排課 題迷宮求解、表達式求值、棧與遞歸的實現(xiàn)教 材的重 點、 難點 分析教 學(xué) 目 標(biāo)(1)能應(yīng)用棧解決一些實際問題(2)T解遞歸算法執(zhí)行過程中棧的變化過程教孝方和學(xué) 學(xué)法教手段教學(xué)內(nèi)容安排與板書設(shè)計：3. 2. 4迷宮求解過3. 2. 5表達式求值程3. 3棧與遞歸的實現(xiàn)教學(xué)過程師生雙邊活動：提問：舉例：演示實驗：教具準備：課 后作3.19,3.25業(yè)教 學(xué)后 記號S周 次4日9 27課時2期安排課 題隊列教 材的 重難點 分析重點：(1)隊列在兩種存儲結(jié)構(gòu)上實現(xiàn)的基本運算。難點：(1)循環(huán)隊列(注意隊滿隊空的條件及它們的描述)教(1)掌握隊列這種數(shù)據(jù)結(jié)構(gòu)的特點(2)熟悉隊列與線性表的

11、關(guān)系(3)掌握循環(huán)隊列和鏈式隊列的五種基本運算(4)能應(yīng)用隊列解決一些實際問題教 學(xué)方教學(xué)內(nèi)容安排與板書設(shè)計；3. 4隊列3. 4. 1抽象數(shù)據(jù)類型隊列的定義隊列的定義(FIFO)隊列的類型定義教學(xué)過程3. 4. 2鏈隊列一隊列的鏈式表示和實現(xiàn)單鏈隊列的定義單鏈隊列的操作3. 4. 3循環(huán)隊列一隊列的順序表示和實現(xiàn)隊列的順序存儲結(jié)構(gòu)循環(huán)隊列的基本操作師生雙邊活動：提問：舉例：演示實驗：教具準備：課 后作 業(yè)3.29教 學(xué)后 記號9周 次日課時5帕戸10.1宀霊2期安排課 題機動教 材的 重 點、 難點 分析教S鬍教學(xué)內(nèi)容安排與板書設(shè)計：教學(xué)過程師生雙邊活動：提問：舉例：演示實驗：教具準備：課

12、后作 業(yè)教 學(xué)后 記編 號10周 次5日10.4蠢時2期安排課 題習(xí)題課教 材的 重 點、 難點 分析學(xué)目教講授法S鬍教學(xué)內(nèi)容安排與板書設(shè)計：教學(xué)過程師生雙邊活動：提問：舉例：演示實驗：教具準備：課 后作 業(yè)教 學(xué)后 記編 號n周 次6日10.8蠢時2期安排課 題串類型的泄義、串的表示和實現(xiàn)材的 重 點、 難點 分析重點：(1)串的基本運算難點：(1)串的動態(tài)存儲結(jié)構(gòu)教學(xué)目標(biāo)(1)熟悉串的有關(guān)概念，串與線性表的關(guān)系(2)掌握串的靜態(tài)存儲結(jié)構(gòu)與動態(tài)存儲結(jié)構(gòu)和它們的優(yōu)缺點(3)熟練掌握串的基本運算教蠶鬻教學(xué)內(nèi)容安排與板書設(shè)計：第四章串4. 1串類型的定義串的槪念串類型的定義教學(xué) 過 程4. 2串的

13、表示和實現(xiàn)4. 2. 1楚長順序存儲表不串的定長順序存儲表示串聯(lián)接求子串4. 2. 2堆分配存儲表示串的堆分配存儲表不堆的基本操作4. 2. 3串的塊鏈存儲表示師生雙邊活動：提問：舉例：演示實驗：教具準備：課 后作業(yè)4.17,4.22.24教 學(xué)后 記編 號12周 次6曲日10.11需豊時2期安排課 題串的模式匹配算法、串操作應(yīng)用舉例教 材的重點 難點 分析教學(xué)目(1)理解串的模式匹配算法(2)7解串的應(yīng)用教齧?z 教學(xué)內(nèi)容安排與板書設(shè)計：4. 3串的模式匹配算法4. 3. 1求子串位苣的定位函數(shù)4. 3. 2模式匹配的一種改進算法KMP算法教 學(xué) 過 程4. 4串操作應(yīng)用舉例4. 4. 1文

14、本編輯師生雙邊活動：提問：舉例：演示實驗：教具準備：課 后作 業(yè)4.8教學(xué)后 記編 號13周次7日10 15課時2期安排課 題數(shù)組的定義、順序表示和實現(xiàn)、矩陣的壓縮存儲教 材的 重難點 分析重點：(1)多維數(shù)組的存儲方式(2)矩陣的壓縮存儲方式難點：(1)稀疏矩陣的壓縮存儲表示下實現(xiàn)的算法(2)熟悉數(shù)組的按行(列)優(yōu)先順序的存儲結(jié)構(gòu)中的地址計算方 法(2)熟悉特殊矩陣在壓縮存儲時的下標(biāo)變換(3)理解稀疏矩陣的三元組和十字鏈表兩種壓縮存儲表示孝方和學(xué)段 學(xué)法教手教學(xué)內(nèi)容安排與板書設(shè)計：第五章數(shù)組和廣義表5. 1數(shù)組的定義數(shù)組的類型定義二維數(shù)組教 學(xué) 過 程5. 2數(shù)組的順序表示和實現(xiàn)二維數(shù)組的存

15、儲方式數(shù)組的順序存儲表不和實現(xiàn)5. 3矩陣的壓縮存儲5. 3. 1特殊矩陣對稱矩陣對角矩陣5. 3. 2稀疏矩陣稀疏矩陣的類型定義1、三元組順序表師生雙邊活動：提問：舉例：演示實驗：教具準備：課 后作 業(yè)5.21教 學(xué)后 記編 號14周 次7日 期10.18課時 安排2課 題稀疏矩陣的存儲結(jié)構(gòu)、廣義表的定義和存儲結(jié)構(gòu)教 材的 重重點：(1)廣義表的定義及其運算教(1)掌握稀疏矩陣的存儲結(jié)構(gòu)學(xué)(2)熟悉廣義表的有關(guān)槪念和運算目 標(biāo)(3)掌握廣義表的兩種存儲結(jié)構(gòu)教S鬻教學(xué)內(nèi)容安排與板書設(shè)計：2、行邏輯鏈接的順序表3、十字鏈表5. 4廣義表的定義教學(xué) 過 1TI廣義表的類型定義廣義表舉例廣義表的特點

16、5. 5廣義表的存儲結(jié)構(gòu)討論：程M元多項式的表示廣義表的遞歸算法師生雙邊活動：提問：舉例：演示實驗：教具準備：課 后作 業(yè)5.26,5.12教學(xué)后 記編 號15周 次8日 期10.22課時 安排2課 題樹的定義和基本術(shù)語、二叉樹的定義教 材的重重點：(1)樹的基本術(shù)語(2)二叉樹的定義難點分析教(1)掌握樹的泄義和有關(guān)術(shù)語學(xué) 目 標(biāo)(2)熟悉二叉樹的遞歸定義，有關(guān)術(shù)語及基本概念教學(xué)內(nèi)容安排與板書設(shè)計：第六章樹和二叉樹6. 1樹的定義和基本術(shù)語樹的類型定義基本術(shù)語教學(xué)過程6. 2二叉樹6. 2. 1二叉樹的定義二叉樹的類型定義二叉樹的基本形態(tài)師生雙邊活動：提問：舉例：演示實驗：教具準備：課 后作

17、 業(yè)6.2教 學(xué)后 記編 號16周 次8日10.25倖豊時2期安排課 題二叉樹的性質(zhì)和和存儲結(jié)構(gòu)教 材的 重 點、 難點 分析重點：（1）二叉樹的存儲結(jié)構(gòu)難點：（1）二叉樹的性質(zhì)教（1）熟練掌握二叉樹的性質(zhì)及證明方法學(xué) 冃 標(biāo)(2)熟練掌握二叉樹的順序和鏈式存儲結(jié)構(gòu)及特點講授法教學(xué)內(nèi)容安排與板書設(shè)計：6. 2. 2二叉樹的性質(zhì)性質(zhì)1性質(zhì)2性質(zhì)3性質(zhì)4性質(zhì)5教學(xué) 過 程6. 2. 3二叉樹的存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)鏈式存儲結(jié)構(gòu)師生雙邊活動：提問：舉例：演示實驗：教具準備：課 后作 業(yè)6.6,6.11教 學(xué)后 記編 號17周 次9日10.29蠢時2期安排課 題遍歷二叉樹和線索二叉樹教 材的 重 點X

18、難點 分析重點：（1）二叉樹的遍歷算法及其相關(guān)應(yīng)用難點：（1）二叉樹的非遞歸遍歷算法教學(xué)目鮭r教芻鬻教學(xué)過程6.3.教學(xué)過程6.師生雙邊活動：提問：舉例：演示實驗：教具準備：課 后作 業(yè)6.43647656教 學(xué)后 記編 號18周 次9曲日11.1需時2期安排課 題樹和森林教 材的 重 點、重點：（1）樹的存儲結(jié)構(gòu)難點 分析教學(xué)目壇r教瞽?x教學(xué)過6.4-程教學(xué)過程6.46.師生雙邊活動：提問：舉例：演示實驗：教具準備：課 后作 業(yè)6.60,6.66教學(xué)后 記編 號19周 次1日115課時20期安排課 題赫夫曼樹及其應(yīng)用教材的 重 點、重點：（1）赫夫曼編碼難點 分析教學(xué)目壇r教瞽?x法 授

19、講教學(xué)過6.-程6.6.教學(xué)過程師生雙邊活動：提問：舉例：演示實驗：教具準備：課 后作 業(yè)6.26教學(xué)后 記編 號20周 次1日118課時2o期1,8安排課 題習(xí)題課教材的 重 點、難點 分析教學(xué)目一i教瞽?x講授法教學(xué)內(nèi)容安排與板書設(shè)計：教學(xué)過程師生雙邊活動：提問：舉例：演示實驗：教具準備：課 后作 業(yè)教學(xué)后 記編 號21周 次11日 期11.12課時 安排2課 題圖的定義和術(shù)語、圖的存儲結(jié)構(gòu)重點：（1）圖的存儲材的重總教蠶寫程章七7教學(xué)過72.72.7程圖的鄰接表存儲表示鄰接表和逆鄰接表師生雙邊活動：提問：舉例：演示實驗：教具準備：課 后作 業(yè)7.14J.15教學(xué)后 記編 號22周 次11

20、日 期11.15課時 安排2課題十字鏈表、鄰接多重表、圖的遍歷教 材的 重 點、 難點 分析重點：(1)圖的遍歷難點：(1)圖的遍歷非遞歸算法教學(xué)目M(1)熟練掌握圖的四種存儲結(jié)構(gòu)和建立算法(2)熟練掌握圖的深度優(yōu)先遍歷和廣度優(yōu)先適歷教學(xué)內(nèi)容安排與板書設(shè)計：7. 2. 3十字鏈表有向圖的十字鏈表存儲表示構(gòu)造有向圖7. 2. 4鄰接多重表無向圖的鄰接多重表教學(xué)7. 3圖的遍歷7. 3. 1深度優(yōu)先搜索7. 3. 2廣度優(yōu)先搜索過程師生雙邊活動：提問：舉例：演示實驗：教具準備：課 后作 業(yè)7.22,7.28教 學(xué)后 記編 號23周1日11.19課時2次2期安排課 題圖的連通性問題教 材的 重難點

21、分析重點：（1）最小生成樹的構(gòu)造教 學(xué) 目 標(biāo)掌握最小生成樹的兩種構(gòu)造方法教學(xué)內(nèi)容安排與板書設(shè)計：7. 4圖的連通性問題7. 4. 1無向圖的連通分量和生成樹7. 4. 2有向圖的強連通分量教7. 4. 3最小生成樹Prim算法學(xué)過程Kruskal 算法7. 4. 3關(guān)節(jié)點和重連通分疑師生雙邊活動：提問：舉例：演示實驗：教具準備：課 后作 業(yè)7.32教 學(xué)后記周 次12日 期11.22課時 安排2課 題有向無環(huán)圖及其應(yīng)用Tli伽重點：拓撲排序(2)求關(guān)鍵路徑難點：(1)求關(guān)鍵路徑掌握拓撲排序的方法(2)掌握關(guān)鍵路徑的求法教學(xué)內(nèi)容安排與板書設(shè)計；7. 5有向無環(huán)圖及其應(yīng)用DAG7. 5. 1拓撲

22、排序7. 5. 2關(guān)鍵路徑AOE網(wǎng)關(guān)鍵路徑教學(xué)過程師生雙邊活動：提問：舉例：演示實驗：教具準備：課 后作 業(yè)7.36教學(xué)后記編 號25周 次13日 期11.26課時 安排2課 題最短路徑T乩驀重點：（1）求最短路徑難點：（1）求每一對頂點之間的最短路徑教孳目一熟練掌握從某個源點到英余各頂點的最短路徑的求法掌握求每一對頂點之間的最短路徑的求法教S蠶教學(xué)內(nèi)容安排與板書設(shè)計：7. 6最短路徑7. 6. 1從某個源點到其余各頂點的最短路徑Dijkstra 算法7. 6. 2每一對頂點之間的最短路徑教學(xué)過程師生雙邊活動；提問：舉例：演示實驗：教具準備：課 后作 業(yè)7.42教 學(xué)后 記號26周 次13日

23、期11.29課時 安排2課 題靜態(tài)查找表教 材的重點、 難點 分析重點：(1)順序查找折半查找教學(xué)目鮭(1)熟練掌握靜態(tài)査找的各種方法教蠶鬻教學(xué)內(nèi)容安排與板書設(shè)計：第八章查找査找表與靜態(tài)查找表和動態(tài)査找表關(guān)鍵字與主關(guān)鍵字和次關(guān)鍵字查找與成功和不成功教學(xué)過程& 1靜態(tài)査找表靜態(tài)査找表的類型定義& 1. 1順序表的查找順序査找平均査找長度& 1. 2有序表的查找折半查找折半查找的性能分析& 1. 3靜態(tài)樹表的査找& 1. 4索引順序表的査找表其索引表分塊查找?guī)熒p邊活動：提問：舉例：演示實驗：教具準備：課 后作業(yè)9.29教 學(xué)后 記編 號27周 次14日 期

24、12.3課時 安排2課 題二叉排序樹和平衡二叉樹教 材的 重 點X 難點 分析重點：(1)動態(tài)查找表及查找算法(2)二叉排序樹難點：二叉排序樹教 學(xué) 目 標(biāo)(1)熟練掌握二叉排序樹的構(gòu)造方法及查找過程(2)掌握AVL樹的構(gòu)造教學(xué)內(nèi)容安排與板書設(shè)計：& 2動態(tài)查找表動態(tài)查找表的類型定義& 2. 1二叉排序樹和平衡二叉樹1、二叉排序樹及其査找過程二叉排序樹教學(xué) 過 程2、二叉排序樹的插入和刪除二叉排序樹的構(gòu)造二叉排序樹的刪除3、二叉排序樹的査找分析4、平衡二叉樹平衡二叉樹與不平衡的二叉樹平衡樹的生成過程二叉排序樹的平衡旋轉(zhuǎn)二叉排序樹的類型定義5、平衡樹查找的分析師生雙邊活動：提問：

25、舉例：演示實驗：教具準備：課 后作 業(yè)9.33教 學(xué)后記編 號28周 次14日 期12.6課時 安排2課 題B樹和B+樹教 材的重 點 難點 分析教學(xué)目鮭掌握B-樹和B+樹的構(gòu)造和查找(2)7解鍵樹的構(gòu)造方法教算鬻教教學(xué)內(nèi)容安排與板書設(shè)計：8. 2. 2B樹和B+樹1、B-樹及其查找2、B-樹査找分析教學(xué) 過 :rn3、B-樹的插入和刪除4、B+樹& 2. 3鍵樹程師生雙邊活動：提問：舉例：演示實驗：教具準備：課 后作 業(yè)教學(xué)后13編 號29周 次15日 期12.10課時 安排2課 題哈希表教 材的 重Av» %難點 分析難點：(1)哈希表及查找算法教學(xué)目V(1)熟練掌握哈希

26、表的建表方法、沖突的處理及查找過程(2)理解哈希表與其它存儲結(jié)構(gòu)的表的本質(zhì)區(qū)別(3)熟練掌握哈希表的平均查找長度的計算(等概率)蠶?1教學(xué)教學(xué)內(nèi)容安排與板書設(shè)計：& 3哈希表過 程& 3. 1什么是哈希表哈希函數(shù)沖突散列教& 3. 2哈希函數(shù)的構(gòu)造方法1、直接定址法2、數(shù)字分析法3、平方取中法4、折疊法5、除留余數(shù)法6、隨機數(shù)法& 3. 3處理沖突的方法過程1、開放定址法2、再哈希法3、鏈地址法4、建立一個公共溢岀區(qū)& 3. 4哈希表的查找及其分析師生雙邊活動：提問：舉例：演示實驗：教具準備：課 后作 業(yè)9.46教 學(xué)后 記編 號30周 次15日 期12

27、.13課時 安排2課 題排序概述、插入排序教 材的 重難點 分析重點：(1)希爾排序(1)深刻理解插入排序的基本思想及其特點(2)熟練掌握插入排序方法的排序過程(3)掌握插入排序算法時間復(fù)雜度的分析方法并熟記苴分析結(jié) 論目 標(biāo)教S鬻教學(xué)內(nèi)容安排與板書設(shè)計：第九章排序9. 1排序概述排序排序方法的穩(wěn)定性內(nèi)部排序與外部排序教學(xué)過9. 2插入排序9. 2. 1直接插入排序9. 2. 2其他插入排序1、折半插入排序2、2-路插入排序3、表插入排序9. 2. 3希爾排序43E師生雙邊活動：提問：舉例：演示實驗：教具準備：課 后作 業(yè)10.25教 學(xué)后 記編 號31周 次16日 期12.17課時安排2課 題快速排序、選擇排序教 材的重 點、 難點 分析重點：(1)快速排序(2)堆排序難點：快速排序(2)堆排序教學(xué)目Z(1)深刻理解快速排序的基本思想及其特點(2)熟練掌握快速排序方法的排序過程(3)掌握快速排序算法時間復(fù)雜度的分析方法并熟記苴分析結(jié) 論(4)深刻理解選擇排序的基本思想及其特點(5)