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

《數(shù)據(jù)結(jié)構(gòu)與演算法》課程教學(xué)大綱課程名稱：數(shù)據(jù)結(jié)構(gòu)與演算法課程類別（必修/選修）：必修課程英文名稱：DataStructureandAlgorithm總學(xué)時(shí)/周學(xué)時(shí)/學(xué)分：54/3/3其中實(shí)驗(yàn)學(xué)時(shí)：18先修課程：語(yǔ)言程序授課時(shí)間：周二5-7堂授課地點(diǎn)：實(shí)驗(yàn)616樓答疑時(shí)間、地點(diǎn)與方式：課程考核方式：開卷（）閉卷（）課程論文（v）其它（編程報(bào)告）使用教材：1.教材：[1]數(shù)據(jù)結(jié)構(gòu)與算法（第2版）汪沁、奚李峰、鄧芳、金冉、劉曉利、陳慧編著，《數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）》，清華大學(xué)出版，2018.62.參考書：[1]嚴(yán)蔚敏，吳偉民編著，《數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）》，清華大學(xué)出版，2012.5[2]嚴(yán)蔚敏，吳偉民編著，《數(shù)據(jù)結(jié)構(gòu)題集（C語(yǔ)言版）》，清華大學(xué)出版，2012.5/view/0e3e13cd32d4b14e852458fb770bf78a65293a87.html[3]許卓群，張乃孝，楊冬青，唐世渭，《數(shù)據(jù)結(jié)構(gòu)》，高等教育出版社，2004.[4]李云清，楊慶紅，揭安全編著，《數(shù)據(jù)結(jié)構(gòu)》（C語(yǔ)言版），人民郵電出版社，2007.[5]陳文博，朱青，《數(shù)據(jù)結(jié)構(gòu)與算法》，機(jī)械工業(yè)出版社，1996課程簡(jiǎn)介（一）緒論（1）介紹什么是數(shù)據(jù)結(jié)構(gòu)；（2）基本概念和術(shù)語(yǔ):數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)對(duì)象，以及數(shù)據(jù)結(jié)構(gòu)的定義、邏輯結(jié)構(gòu)、物理結(jié)構(gòu)（理解）數(shù)據(jù)類型、抽象數(shù)據(jù)類型；（3）抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)；（4）算法和算法分析:算法的概念、算法設(shè)計(jì)的要求以及算法效率的度量。（二）線性表（1）線性表的抽象數(shù)據(jù)類型定義和相關(guān)概念：數(shù)據(jù)項(xiàng)、記錄、文件等；（2）線性表順序存儲(chǔ)表示和基本操作的實(shí)現(xiàn)；（3）線性表的鏈?zhǔn)酱鎯?chǔ)表示和基本操作的實(shí)現(xiàn)；（4）稀疏多項(xiàng)式的抽象數(shù)據(jù)類型定義、表示和加法的實(shí)現(xiàn)。（三）棧和隊(duì)列（1）棧和隊(duì)列的結(jié)構(gòu)特性和抽象數(shù)據(jù)類型定義；（2）棧和隊(duì)列的順序存儲(chǔ)表示和實(shí)現(xiàn)；（3）棧和隊(duì)列的鏈?zhǔn)酱鎯?chǔ)表示和實(shí)現(xiàn)；（4）棧和隊(duì)列在程序設(shè)計(jì)中的應(yīng)用。（四）串（1）串的抽象數(shù)據(jù)類型定義；（2）串的表示和實(shí)現(xiàn):定長(zhǎng)順序存儲(chǔ)結(jié)構(gòu)和堆分配存儲(chǔ)結(jié)構(gòu)；（3）串的各種基本操作的實(shí)現(xiàn)及其應(yīng)用；（4）串的模式匹配操作。（五）數(shù)組和廣義表（1）數(shù)組的抽象數(shù)據(jù)類型定義及其順序表示和實(shí)現(xiàn)；（2）特殊矩陣和稀疏矩陣的壓縮存儲(chǔ)；（3）廣義表的抽象數(shù)據(jù)類型定義和存儲(chǔ)結(jié)構(gòu)。（六）樹和二叉樹（10學(xué)時(shí)）（1）樹的抽象數(shù)據(jù)類型定義和基本術(shù)語(yǔ)；（2）二叉樹的抽象數(shù)據(jù)類型定義、性質(zhì)和存儲(chǔ)結(jié)構(gòu)；（3）二叉樹的遍歷；（4）線索二叉樹的定義、遍歷及線索化二叉樹；（5）樹的存儲(chǔ)結(jié)構(gòu)、樹和森林的遍歷以及與二叉樹的轉(zhuǎn)換；（6）Huffman樹及其應(yīng)用。（七）圖（1）圖的定義和術(shù)語(yǔ)；（2）圖的四種存儲(chǔ)結(jié)構(gòu)：數(shù)組表示法（鄰接矩陣）、鄰接表、十字鏈表和鄰接多重表；（3）圖的兩種遍歷策略：深度優(yōu)先遍歷和廣度優(yōu)先遍歷；（4）圖的連通性和最小生成樹；（5）有向無(wú)環(huán)圖及其應(yīng)用：拓?fù)渑判蚝完P(guān)鍵路徑；（6）最短路徑問題。（八）查找（1）查找的基本概念和相關(guān)術(shù)語(yǔ)；（2）靜態(tài)查找表：順序查找、折半查找和索引順序表查找；（3）動(dòng)態(tài)查找表：二叉排序樹的查找、插入和刪除；（4）哈希表。（九）內(nèi)部排序（1）排序的基本概念和相關(guān)術(shù)語(yǔ)；（2）插入排序：直接插入排序、折半插入排序和希爾排序；（3）交換排序：起泡排序和快速排序；（4）選擇排序：簡(jiǎn)單選擇排序和堆排序；（5）歸并排序：二路歸并排序；（6）基數(shù)排序：鏈?zhǔn)交鶖?shù)排序；（7）各種內(nèi)部排序方法的比較討論。課程教學(xué)目標(biāo)數(shù)據(jù)結(jié)構(gòu)課程是計(jì)算機(jī)相關(guān)專業(yè)的專業(yè)基礎(chǔ)課、必修課程，主要介紹用計(jì)算機(jī)解決一系列問題特別是非數(shù)值信息處理問題時(shí)所用的各種組織數(shù)據(jù)的方法、存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)的方法以及在各種結(jié)構(gòu)上執(zhí)行操作的算法。通過(guò)本課程的學(xué)習(xí)，要求學(xué)生掌握各種數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)、存儲(chǔ)表示、運(yùn)算方法以及在計(jì)算機(jī)科學(xué)中最基本的應(yīng)用，培養(yǎng)、訓(xùn)練學(xué)生選用合適的數(shù)據(jù)結(jié)構(gòu)和編寫質(zhì)量高、風(fēng)格好的應(yīng)用程序的能力，培養(yǎng)學(xué)生分析問題、解決問題的能力，并為后續(xù)課程的學(xué)習(xí)打下良好的理論基礎(chǔ)和實(shí)踐基礎(chǔ)。介紹儲(chǔ)存數(shù)據(jù)的各種結(jié)構(gòu)，以及解決問題的簡(jiǎn)易方法。訓(xùn)練學(xué)生設(shè)計(jì)良好的編程數(shù)據(jù)結(jié)構(gòu)。撰寫程序的能力更加精進(jìn)，與具效率的程序。本課程與學(xué)生核心能力培養(yǎng)之間的關(guān)聯(lián)(授課對(duì)象為理工科專業(yè)學(xué)生的課程填寫此欄）：□核心能力1.核心能力2.核心能力3.核心能力4.□核心能力5.核心能力6.□核心能力7．□核心能力8．理論教學(xué)進(jìn)程表周次教學(xué)主題教學(xué)時(shí)長(zhǎng)教學(xué)的重點(diǎn)與難點(diǎn)教學(xué)方式作業(yè)安排1緒論3（1）介紹什么是數(shù)據(jù)結(jié)構(gòu)；（2）基本概念和術(shù)語(yǔ):數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)對(duì)象，以及數(shù)據(jù)結(jié)構(gòu)的定義、邏輯結(jié)構(gòu)、物理結(jié)構(gòu)（理解）數(shù)據(jù)類型、抽象數(shù)據(jù)類型；課堂講授與實(shí)踐編程練習(xí)2緒論3（3）抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)；（4）算法和算法分析:算法的概念、算法設(shè)計(jì)的要求以及算法效率的度量。課堂講授與實(shí)踐編程練習(xí)3線性表3（1）棧和隊(duì)列的結(jié)構(gòu)特性和抽象數(shù)據(jù)類型定義；（2）棧和隊(duì)列的順序存儲(chǔ)表示和實(shí)現(xiàn)；課堂講授與實(shí)踐編程練習(xí)4線性表3（3）棧和隊(duì)列的鏈?zhǔn)酱鎯?chǔ)表示和實(shí)現(xiàn)；（4）棧和隊(duì)列在程序設(shè)計(jì)中的應(yīng)用。課堂講授與實(shí)踐編程練習(xí)5棧和隊(duì)列3（1）串的抽象數(shù)據(jù)類型定義；（2）串的表示和實(shí)現(xiàn):定長(zhǎng)順序存儲(chǔ)結(jié)構(gòu)和堆分配存儲(chǔ)結(jié)構(gòu)；課堂講授與實(shí)踐編程練習(xí)6棧和隊(duì)列3（3）串的各種基本操作的實(shí)現(xiàn)及其應(yīng)用；（4）串的模式匹配操作。課堂講授與實(shí)踐編程練習(xí)7串3（1）串的抽象數(shù)據(jù)類型定義；（2）串的表示和實(shí)現(xiàn):定長(zhǎng)順序存儲(chǔ)結(jié)構(gòu)和堆分配存儲(chǔ)結(jié)構(gòu)；課堂講授與實(shí)踐編程練習(xí)8串3（3）串的各種基本操作的實(shí)現(xiàn)及其應(yīng)用；（4）串的模式匹配操作。課堂講授與實(shí)踐編程練習(xí)9數(shù)組和廣義表3（1）數(shù)組的抽象數(shù)據(jù)類型定義及其順序表示和實(shí)現(xiàn)；（2）特殊矩陣和稀疏矩陣的壓縮存儲(chǔ)；（3）廣義表的抽象數(shù)據(jù)類型定義和存儲(chǔ)結(jié)構(gòu)。課堂講授與實(shí)踐編程練習(xí)10期中考3編程考試11樹和二叉樹3（1）樹的抽象數(shù)據(jù)類型定義和基本術(shù)語(yǔ)；（2）二叉樹的抽象數(shù)據(jù)類型定義、性質(zhì)和存儲(chǔ)結(jié)構(gòu)；（3）二叉樹的遍歷；課堂講授與實(shí)踐編程練習(xí)12樹和二叉樹3（4）線索二叉樹的定義、遍歷及線索化二叉樹；（5）樹的存儲(chǔ)結(jié)構(gòu)、樹和森林的遍歷以及與二叉樹的轉(zhuǎn)換；（6）Huffman樹及其應(yīng)用。課堂講授與實(shí)踐編程練習(xí)13圖3（1）圖的定義和術(shù)語(yǔ)；（2）圖的四種存儲(chǔ)結(jié)構(gòu)：數(shù)組表示法（鄰接矩陣）、鄰接表、十字鏈表和鄰接多重表；（3）圖的兩種遍歷策略：深度優(yōu)先遍歷和廣度優(yōu)先遍歷；課堂講授與實(shí)踐編程練習(xí)14圖3（4）圖的連通性和最小生成樹；（5）有向無(wú)環(huán)圖及其應(yīng)用：拓?fù)渑判蚝完P(guān)鍵路徑；（6）最短路徑問題。課堂講授與實(shí)踐編程練習(xí)15查找3（1）查找的基本概念和相關(guān)術(shù)語(yǔ)；（2）靜態(tài)查找表：順序查找、折半查找和索引順序表查找；課堂講授與實(shí)踐編程練習(xí)16查找3（3）動(dòng)態(tài)查找表：二叉排序樹的查找、插入和刪除；（4）哈希表。課堂講授與實(shí)踐編程練習(xí)17內(nèi)部排序3（1）排序的基本概念和相關(guān)術(shù)語(yǔ)；（2）插入排序：直接插入排序、折半插入排序和希爾排序；（3）交換排序：起泡排序和快速排序；課堂講授與實(shí)踐編程練習(xí)18內(nèi)部排序3（4）選擇排序：簡(jiǎn)單選擇排序和堆排序；（5）歸并排序：二路歸并排序；（6）基數(shù)排序：鏈?zhǔn)交鶖?shù)排序；（7）各種內(nèi)部排序方法的比較討論。課堂講授與實(shí)踐編程練習(xí)19期末考3編程考試20期末考3編程考試合計(jì)：54成績(jī)?cè)u(píng)定方法及標(biāo)準(zhǔn)考核形式評(píng)價(jià)標(biāo)準(zhǔn)權(quán)重每周編程作業(yè)作業(yè)報(bào)告完成度40%期中考核編程考核20%期末考核編程考核30%出勤出席率10%大綱編寫時(shí)間：2018/09/17系（部）審查意見：。系（部）主任簽名：日期：年月日注：1、課程教學(xué)目標(biāo)：請(qǐng)精煉概括3-5條目標(biāo)，并注明每條目標(biāo)所要