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

《數(shù)據(jù)結(jié)構(gòu)與算法》課程教學大綱課程代碼：適用專業(yè):計算機應用技術總學時數(shù): 68學時,其中：理論教學34學時,實踐教學3４學時。學分:４、5考核方式:機試一、制訂大綱得依據(jù)本大綱根據(jù)201３年軟件技術專業(yè)教學計劃制訂。二、課程簡介數(shù)據(jù)結(jié)構(gòu)就是介于數(shù)學、計算機硬件與計算機軟件之間得一門計算機科學與技術專業(yè)得核心課程,就是高級程序設計語言、編譯原理、操作系統(tǒng)、數(shù)據(jù)庫等課程得從數(shù)據(jù)表示與數(shù)據(jù)處理上瞧有五個基本組成“要素”分別就是邏輯結(jié)構(gòu),存儲結(jié)構(gòu)、基本運算、算法及不同數(shù)據(jù)結(jié)構(gòu)得比較與算法分析。三、課程性質(zhì)、教育目標(一)性質(zhì):本課程為計算機系軟件技術專業(yè)得專業(yè)課。(二）得程序,為學習操作系統(tǒng)、編譯原理與數(shù)據(jù)庫等課程奠定基礎。四、課程教學內(nèi)容與基本要求第一部分 緒(一)教學內(nèi)容數(shù)據(jù)結(jié)構(gòu)得基本概念與術語；抽象數(shù)據(jù)類型得表示;算法與算法分析。（二)重點、難點重點：數(shù)據(jù)結(jié)構(gòu)得基本概念及相關術語。難點：算法得時間復雜度分析。(三）教學基本要求知識要求:了解：抽象數(shù)據(jù)類型及面向?qū)ο蟾拍?理解:算法得定義及算法得特性；掌握:數(shù)據(jù)結(jié)構(gòu)得基本概念、算法得性能分析與度量方法第二部分 線性表(一)教學內(nèi)容線性表得定義及操作；線性表得順序存儲定義及操作實現(xiàn)；３.單鏈表得定義;單鏈表中得插入與刪除;帶表頭結(jié)點得單鏈表;靜態(tài)鏈表;４.循環(huán)鏈表得類定義及運算;雙向鏈表得類定義及運算;線性表得應用:多項式及其相加。（二)重點、難點重點：順序表得數(shù)組定義方式及實現(xiàn),單鏈表得定義及實現(xiàn)。難點:循環(huán)鏈表與雙向鏈表得定義及實現(xiàn)。(三)教學基本要求知識要求：了解:靜態(tài)鏈表。理解:線性表得定義及操作。掌握:順序表得數(shù)組定義方式及實現(xiàn),單鏈表、循環(huán)鏈表與雙向鏈表得定義及實現(xiàn)第三部分 棧與隊列(一)教學內(nèi)容示上得基本運算;棧得應用；及基本運算;(二)重點、難點重點:棧得定義及實現(xiàn);隊列得定義及實現(xiàn)。難點：棧得應用中得表達式求值;循環(huán)隊列(隊列得順序存儲)。(三)教學基本要求知識要求：了解:隊列得應用。理解:棧得應用中得遞歸算法。掌握:棧得定義及實現(xiàn)；隊列得定義及實現(xiàn)。棧得應用中得表達式求值;循環(huán)隊列(隊列得順序存儲)。第四部分 串、數(shù)組與廣義(一)教學內(nèi)容字符串得抽象數(shù)據(jù)類型;字符串操作得實現(xiàn);字符串得模式匹配數(shù)組得邏輯結(jié)構(gòu)定義與存儲方法;特殊矩陣與稀疏矩陣得壓縮存儲方法;廣義表得概念；廣義表得表示及操作;廣義表存儲結(jié)構(gòu)得實現(xiàn)；(二)重點、難點重點:串與數(shù)組得基本概念、存儲結(jié)構(gòu)。廣義表得概念與存儲結(jié)構(gòu)及其相關運算得實現(xiàn)。難點:串得模式匹配算法,特殊矩陣與稀疏矩陣得壓縮存儲。(三)教學基本要求知識要求:了解:串得一些基本處理操作、矩陣得相關運算。理解:廣義表得遞歸算法。掌握：串與數(shù)組得基本概念、存儲結(jié)構(gòu)。廣義表得概念與存儲結(jié)構(gòu)及其相關運算得實現(xiàn)。串得模式匹配算法，特殊矩陣與稀疏矩陣得壓縮存儲。第五部分 樹與二叉(一)教學內(nèi)容樹得基本概念;二叉樹得定義、性質(zhì)、存儲表示及相關運算;二叉樹得遍歷；線索二叉樹;森林與二叉樹得相互轉(zhuǎn)換；哈夫曼樹及哈夫曼編碼。（二)重點、難點重點:二叉樹得定義、性質(zhì)、存儲表示;二叉樹得遍歷;難點:二叉樹得相關運算。(三)教學基本要求知識要求:了解：線索二叉樹上得復雜運算實現(xiàn)。理解：二叉樹得相關運算。掌握：二叉樹得定義、性質(zhì)、存儲表示；二叉樹得遍歷;森林與二叉樹得相互轉(zhuǎn)換;哈夫曼樹及哈夫曼編碼。第六部分 (一)教學內(nèi)容1.圖得基本概念、存儲表示(鄰接矩陣、鄰接表、十字鏈表,鄰接多重表)；２.圖得遍歷與連通性:深度優(yōu)先搜索;廣度優(yōu)先搜索;連通分量;重連通分量;3.最小生成樹:克魯斯卡爾算法;普里姆算法;最短路徑;(二)重點、難點重點:圖得存儲表示;圖得遍歷;最小生成樹;最短路徑;難點:關鍵路徑得求解。(三)教學基本要求知識要求:了解:圖得存儲結(jié)構(gòu)中得鄰接多重表。理解:圖得遍歷算法。掌握：圖得存儲表示（鄰接矩陣、鄰接表)；圖得遍歷;最小生成樹;最短路徑;拓撲排序、關鍵路徑第七部分 查找（一)教學內(nèi)容１.靜態(tài)查找(順序查找、折半查找、分塊查找)；２．動態(tài)查找（二叉排序樹);3.哈希查找。(二)重點、難點重點：靜態(tài)查找；二叉排序樹得建立。難點:二叉排序樹得刪除;平衡二叉樹得調(diào)整。(三)教學基本要求知識要求:了解:查找得相關概念、作用。理解:哈希函數(shù)得構(gòu)造。掌握:靜態(tài)查找;二叉排序樹得相關知識;哈希查找法與解決沖突得方法第八部分 排序(一）教學內(nèi)容1.排序概念;２.插入排序、交換排序、選擇排序、歸并排序、基數(shù)排序;3.各種排序方法得比較。(二)重點、難點難點:堆排序。(三)教學基本要求知識要求:了解:各種排序方法得時間復雜度得分析方法。理解:排序方法“穩(wěn)定”或“不穩(wěn)定”得含義。掌握:各種方法得排序過程及其依據(jù)得原則。第九部分 文(一)教學內(nèi)容1.基本概念;2.文件組織；３.順序文件、隨機文件、索引文件、倒排文件。(二)重點、難點難點:文件得使用。4串、數(shù)組與廣義表4串、數(shù)組與廣義表34六、學習教學場地、設施要求(課程中得實踐部分）34１0０%序號項目(實驗)名稱學習教學場地、設施要求1線性表得應用2棧與隊列得應用實踐教學在機房進行，機器需要安裝有C言環(huán)境。素質(zhì)要求：具備良好得編程習慣與能力。五、學時（理論與實踐）分配表序號 教學內(nèi)容課時分配理論教學實踐教學考核權(quán)重１ 緒論 225%２ 線性表 442２%3 棧與隊列 55５%5樹與二叉樹5樹與二叉樹6圖7查找８排序９總文件計４４3%5６25%４42０%4410％4４８％2２2%33串得簡單操作4二叉樹得算法實現(xiàn)5圖得遍歷6分塊查找7冒泡排序說明:分實踐項目列出場地、設施要求,如每個實踐項目得場地與設施基本相同,也可以一次性描述。七、考核及評分辦法考核得原則:閉卷考試?？己朔绞?考試；期末考試;筆試(閉卷);各教學環(huán)節(jié)占總分得比例:實驗、作業(yè)占30%,