新版數(shù)據(jù)結(jié)構(gòu)授課計(jì)劃安排

個(gè)人資料整理 僅限學(xué)習(xí)使用中山職業(yè)技術(shù)學(xué)院授課計(jì)劃所屬系部: 計(jì)算機(jī)工程系課程名稱: 數(shù)據(jù)結(jié)構(gòu)任課教師: 張玉霞授課班級:10 軟件2班授課學(xué)期: 10-11第2學(xué)期教案大綱《數(shù)據(jù)結(jié)構(gòu)》課程標(biāo)準(zhǔn)，自編<課程標(biāo)準(zhǔn)）個(gè)人資料整理 僅限學(xué)習(xí)使用教材名稱《數(shù)據(jù)結(jié)構(gòu)》<C++版），王紅梅、胡明，王濤，清華大學(xué)出版社，2009(主編/書號>《數(shù)據(jù)結(jié)構(gòu)》<C++版）學(xué)習(xí)輔導(dǎo)與實(shí)驗(yàn)指導(dǎo)，王紅梅、胡明，王濤，清華大學(xué)主要教參出版社，2009《數(shù)據(jù)結(jié)構(gòu)》<C++版）教師用書，王紅梅、胡明，王濤，清華大學(xué)出版社，(主編/書號>2009《數(shù)據(jù)結(jié)構(gòu)》，嚴(yán)蔚敏，清華大學(xué)出版社總學(xué)時(shí)數(shù)64理論學(xué)時(shí)數(shù)32實(shí)踐學(xué)時(shí)數(shù)32課程整體教案設(shè)計(jì)1）課程在本專業(yè)中的地位和作用。數(shù)據(jù)結(jié)構(gòu)是軟件技術(shù)專業(yè)重要的專業(yè)基礎(chǔ)課，在整個(gè)課程體系中處于承上啟下的核心地位，它一方面擴(kuò)展和深化在離散數(shù)學(xué)、程序設(shè)計(jì)語言等課程學(xué)到的基本技術(shù)和方法，一方面為進(jìn)一步學(xué)習(xí)操作系統(tǒng)、編譯原理、數(shù)據(jù)庫等專業(yè)課奠定堅(jiān)實(shí)的理論與實(shí)踐基礎(chǔ)。本課程在教給學(xué)生數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)和算法設(shè)計(jì)的同時(shí)，培養(yǎng)學(xué)生的抽象思維能力、邏輯推理能力和形式化思維方法，增強(qiáng)分析問題、解決問題和總結(jié)問題的能力，更重要的是培養(yǎng)專業(yè)興趣樹立創(chuàng)新意識。2）課程教案目標(biāo)用數(shù)字計(jì)算機(jī)解決實(shí)際問題都離不開數(shù)據(jù)表示和數(shù)據(jù)處理，而數(shù)據(jù)表示和處理的核心問題致意是數(shù)據(jù)結(jié)構(gòu)及實(shí)現(xiàn)——這正是數(shù)據(jù)結(jié)構(gòu)課程的基本內(nèi)容。從這個(gè)意義上說，數(shù)據(jù)結(jié)構(gòu)課程在知識學(xué)習(xí)和技能培養(yǎng)兩個(gè)方面都處于關(guān)鍵性地位。通過本課程的學(xué)習(xí)，應(yīng)達(dá)到知識和技能兩方面的目標(biāo)：知識方面：從數(shù)據(jù)結(jié)構(gòu)及其實(shí)現(xiàn)的角度系統(tǒng)地學(xué)習(xí)和掌握常用基本數(shù)據(jù)結(jié)構(gòu)及其不同的實(shí)現(xiàn)方法，了解并掌握分析、比較和選擇不同數(shù)據(jù)結(jié)構(gòu)及不同存儲結(jié)構(gòu)、不同算法實(shí)現(xiàn)的原則和方法，為后繼課程的學(xué)習(xí)打下良好的基礎(chǔ)。技能方面：通過對本課程的知識傳遞、算法設(shè)計(jì)和上機(jī)實(shí)踐的訓(xùn)練，培養(yǎng)學(xué)生的數(shù)據(jù)抽象能力、邏輯思維能力和程序設(shè)計(jì)的能力，提高分析問題和解決問題的能力。3）課程主要教案內(nèi)容及組織1.緒論<4學(xué)時(shí)）教案內(nèi)容：介紹數(shù)據(jù)結(jié)構(gòu)中常用的基本概念和術(shù)語及學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的意義。教案要求：熟練掌握數(shù)據(jù)結(jié)構(gòu)的一些基本術(shù)語和概念，了解抽象數(shù)據(jù)類型定義和使用，了解算法的基本概念和術(shù)語，了解算法的描述方法，掌握算法的時(shí)間復(fù)雜性分析。重點(diǎn)：了解數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及數(shù)據(jù)的運(yùn)算三方面的概念及相互關(guān)系，算法的概念和特性。難點(diǎn)：算法時(shí)間復(fù)雜性分析方法。2.線性表<8學(xué)時(shí)）教案內(nèi)容：介紹線性表的邏輯結(jié)構(gòu)和存儲表示方法，以及定義在邏輯結(jié)構(gòu)上的各種基本運(yùn)算及其在個(gè)人資料整理 僅限學(xué)習(xí)使用存儲結(jié)構(gòu)上如何實(shí)現(xiàn)這些基本運(yùn)算。教案要求：熟練掌握線性表的基本概念和類型定義；熟練掌握對順序表和單鏈表的常用操作方法及其程序?qū)崿F(xiàn)；了解循環(huán)鏈表和雙向鏈表的定義和它的插入、刪除等操作方法。重點(diǎn)：熟練掌握順序表和單鏈表上實(shí)現(xiàn)的各種基本算法及相關(guān)的時(shí)間性能分析。難點(diǎn)：使用本章所學(xué)到的基本知識設(shè)計(jì)有效算法解決與線性表相關(guān)的應(yīng)用問題。特殊線性表——棧、隊(duì)列和串<8學(xué)時(shí)）教案內(nèi)容：介紹棧和隊(duì)列的邏輯結(jié)構(gòu)定義以及在存儲結(jié)構(gòu)上如何實(shí)現(xiàn)棧和隊(duì)列的基本運(yùn)算，介紹串的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及其串上的基本運(yùn)算。教案要求：熟練掌握棧和隊(duì)列的定義，掌握順序和鏈?zhǔn)酱鎯Φ臈：完?duì)列的各種運(yùn)算的方法及程序?qū)崿F(xiàn)，掌握表達(dá)式求值等經(jīng)典問題求解方法并了解其算法，掌握串的有關(guān)概念及基本運(yùn)算，掌握串的存儲結(jié)構(gòu)，理解串的BF算法，了解KMP算法。重點(diǎn)：熟練掌握棧和隊(duì)列的特點(diǎn)；掌握棧和隊(duì)列在兩種存儲結(jié)構(gòu)上實(shí)現(xiàn)的基本運(yùn)算。難點(diǎn)：兩棧共享空間；循環(huán)隊(duì)列邊界條件的處理；隊(duì)滿隊(duì)空的判定條件，串的模式匹配算法。4．廣義線性表 ——數(shù)組和廣義表 <4學(xué)時(shí)）教案內(nèi)容：介紹數(shù)據(jù)的邏輯結(jié)構(gòu)特征及其存儲方式，特殊矩陣和稀疏矩陣的壓縮存儲方法及廣義表的概念。教案要求：掌握數(shù)組的邏輯結(jié)構(gòu)特征及其存儲方式，了解特殊矩陣和稀疏矩陣的壓縮存儲方法及廣義表的概念，了解廣義表的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)。重點(diǎn)：掌握數(shù)組的存儲方式。難點(diǎn)：稀疏矩陣壓縮存儲表示下實(shí)現(xiàn)的算法。5．樹和二叉樹 <10學(xué)時(shí)）教案內(nèi)容：介紹樹、二叉樹等的有關(guān)概念、存儲結(jié)構(gòu)等方面。教案要求：掌握樹的定義、性質(zhì)、存儲結(jié)構(gòu)，熟練掌握二叉樹的定義、性質(zhì)、存儲結(jié)構(gòu)及各種遍歷算法與實(shí)現(xiàn)，掌握樹與二叉樹的轉(zhuǎn)換，了解線索二叉樹，了解樹的遍歷，了解哈夫曼樹的定義，一般了解其應(yīng)用，了解森林與二叉樹轉(zhuǎn)換等。重點(diǎn)：掌握二叉樹的性質(zhì)及遍歷算法及其有關(guān)應(yīng)用。難點(diǎn)：二叉樹的非遞歸算法，使用本章所學(xué)到的有關(guān)知識設(shè)計(jì)出應(yīng)用問題的有效算法。6．圖<10學(xué)時(shí)）教案內(nèi)容：介紹圖的概念、兩種常用的存儲結(jié)構(gòu)、兩種遍歷算法以及圖的應(yīng)用算法。個(gè)人資料整理僅限學(xué)習(xí)使用教案要求：掌握圖的定義和術(shù)語；掌握鄰接矩陣和鄰接表表示法；熟練掌握圖兩種遍歷的基本思想和算法；了解求圖的最小生成樹的prim和kruskal算法；了解最短路徑問題和拓?fù)渑判?。重點(diǎn)：掌握在圖的兩種存儲結(jié)構(gòu)上實(shí)現(xiàn)的遍歷算法。難點(diǎn)：求最小生成樹，求最短路徑以及拓?fù)渑判颉?．檢索技術(shù)<6學(xué)時(shí)）教案內(nèi)容：介紹關(guān)于線性表、樹和哈希表的查找方法、算法實(shí)現(xiàn)以及各種查找方法的時(shí)間性能<平均查找長度）分析。教案要求：理解查找的基本概念，掌握線性表的順序查找的思想和算法；理解二叉查找樹的概念以及二叉查找樹上查找的基本思想和算法；理解平衡二叉樹的調(diào)整方法；理解哈希表、哈希表構(gòu)造的基本方法以及處理沖突的方法；以及各種查找方法的時(shí)間性能分析。重點(diǎn)：掌握順序查找、折半查找，二叉查找樹上查找的基本思想和算法實(shí)現(xiàn)。難點(diǎn)：二叉查找樹的刪除算法。8．排序技術(shù)<8學(xué)時(shí)）教案內(nèi)容：介紹內(nèi)部排序方法的基本思想、排序過程、算法實(shí)現(xiàn)、時(shí)間和空間性能的分析以及各種排序方法的比較和選擇。教案要求：排序是計(jì)算機(jī)程序設(shè)計(jì)的重要運(yùn)算，是數(shù)據(jù)處理的一項(xiàng)基本活動。掌握內(nèi)部排序方法的指導(dǎo)思想和特點(diǎn)，熟悉各種內(nèi)部排序算法并理解其基本思想；了解各種內(nèi)排序算法的優(yōu)缺點(diǎn)、時(shí)間和空間的性能比較以及使用場合。重點(diǎn)：各種內(nèi)排序的基本思想及內(nèi)排序方法的執(zhí)行過程。難點(diǎn)：各種內(nèi)排序方法的實(shí)現(xiàn)。9．索引技術(shù)<2學(xué)時(shí)）教案內(nèi)容：各種索引結(jié)構(gòu)的構(gòu)造方法，各種索引結(jié)構(gòu)基本操作<查找、插入、刪除）的執(zhí)行過程，各種索引結(jié)構(gòu)的適用情況。教案要求：掌握索引的基本概念，掌握稠密索引和分塊索引及其查找過程，理解多重表和倒排表的基本思想，掌握 2－3樹的定義及其特性，理解 2－3樹的插入、刪除和查找方法，掌握 B－和B＋樹的定義以及二者的區(qū)別，理解 B－樹的插入、刪除和查找方法。重點(diǎn)：稠密索引和分塊索引及其查找過程，多重表和倒排表的基本思想， 2－3樹的定義及其特性。難點(diǎn)：B－樹的插入、刪除和查找方法。4）課程教案方法選擇制作多媒體課件，該課件除了把握知識的內(nèi)涵，注意知識表達(dá)的完整性和準(zhǔn)確性之外，還將一些教案意圖融入多媒體課件，將教案內(nèi)容中抽象的、微觀的概念和不可見的過程，通過動畫個(gè)人資料整理 僅限學(xué)習(xí)使用形象地動態(tài)演示出來。2. 實(shí)驗(yàn)指導(dǎo)，通過“驗(yàn)證實(shí)驗(yàn)→設(shè)計(jì)實(shí)驗(yàn)→綜合實(shí)驗(yàn)” 三個(gè)層次組織各章的實(shí)驗(yàn)環(huán)節(jié)，循序漸進(jìn)提高實(shí)踐技能。4．通過實(shí)訓(xùn)的形式給出一些具有一定深度的綜合問題，引導(dǎo)并提高學(xué)生利用所學(xué)知識解決綜合問題的能力。教師可根據(jù)學(xué)生的學(xué)習(xí)情況和上機(jī)條件在總學(xué)時(shí)內(nèi)對講授和上機(jī)實(shí)習(xí)數(shù)的比例作適當(dāng)調(diào)整。5）課程教案情境設(shè)計(jì)學(xué)習(xí)情景一：線性表及其應(yīng)用：線性表的插入和刪除 <順序表、鏈表）。學(xué)習(xí)情景二：棧和隊(duì)列及其應(yīng)用：運(yùn)用棧來模擬程序的遞歸過程，實(shí)現(xiàn) n階Hanoi塔問題。學(xué)習(xí)情景三：樹及其應(yīng)用：建立一棵二叉樹、遍歷二叉樹各結(jié)點(diǎn) <按層次、前序、中序、后序）。學(xué)習(xí)情景四：圖及其應(yīng)用：建立圖的鄰接矩陣和鄰接表、給定任意兩個(gè)城市，求這兩個(gè)城市間的最短路徑。學(xué)習(xí)情景五：查找、排序算法的比較：給出一組關(guān)鍵字序列，用各種查找方法對給定關(guān)鍵碼進(jìn)行查找，采用各種排序方法對其進(jìn)行排序并輸出中間過程和結(jié)果。6）課程考試/考核方法總評成績=課堂表現(xiàn)及出勤<10%）+作業(yè)情況<10%）+實(shí)訓(xùn)工程<20%）+上機(jī)練習(xí)及上機(jī)作業(yè)<20%）+期末考試成績<40%）周次 授課內(nèi)容 課時(shí)數(shù) 備注介紹數(shù)據(jù)結(jié)構(gòu)中常用的基本概念和術(shù)語及學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的理論講解與上機(jī)1意義。4練習(xí)相結(jié)合。邊講邊練介紹線性表的邏輯結(jié)構(gòu)和存儲表示方法，以及定義在邏輯理論講解與上機(jī)結(jié)構(gòu)上的各種基本運(yùn)算及其在存儲結(jié)構(gòu)上如何實(shí)現(xiàn)這些基8練習(xí)相結(jié)合。邊2-3本運(yùn)算。講邊練個(gè)人資料整理 僅限學(xué)習(xí)使用介紹棧和隊(duì)列的邏輯結(jié)構(gòu)定義以及在存儲結(jié)構(gòu)上如何實(shí)現(xiàn)4-5棧和隊(duì)列的基本運(yùn)算，介紹串的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及其串上的基本運(yùn)算。介紹數(shù)據(jù)的邏輯結(jié)構(gòu)特征及其存儲方式，特殊矩陣和稀疏6矩陣的壓縮存儲方法及廣義表的概念。7-9介紹樹、二叉樹等的有關(guān)概念、存儲結(jié)構(gòu)等方面介紹圖的概念、兩種常用的存儲結(jié)構(gòu)、兩種遍歷算法以及9-11圖的應(yīng)用算法。介紹關(guān)于線性表、樹和哈希表的查找方法、算法實(shí)現(xiàn)以及12-13各種查找方法的時(shí)間性能