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

《數(shù)據(jù)結(jié)構(gòu)》教學(xué)大綱課程編號(hào)：13180503英文名稱：DataStructure學(xué)分：5學(xué)時(shí)：總學(xué)時(shí)96學(xué)時(shí)，其中理論64學(xué)時(shí)，實(shí)踐32學(xué)時(shí)先修課程：高級(jí)語(yǔ)言課程類別：專業(yè)基礎(chǔ)課授課對(duì)象：計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)學(xué)生教學(xué)單位：機(jī)械與電氣工程學(xué)院修讀學(xué)期：第2學(xué)期一、課程描述和目標(biāo)本課程是計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)的專業(yè)基礎(chǔ)課和核心課程，理論性和實(shí)踐性都很強(qiáng)，既要掌握理論知識(shí)，又要進(jìn)行算法設(shè)計(jì)與實(shí)現(xiàn)，還要上機(jī)調(diào)試運(yùn)行。通過本課程的學(xué)習(xí)，使學(xué)生具備較扎實(shí)的軟件技術(shù)知識(shí)和技能；使學(xué)生基本具備從現(xiàn)實(shí)問題抽象到信息范疇再到計(jì)算機(jī)中數(shù)據(jù)組織和處理的轉(zhuǎn)換，并編程實(shí)現(xiàn)解決問題的能力；培養(yǎng)學(xué)生分析和解決較復(fù)雜問題、算法設(shè)計(jì)和程序調(diào)試的能力，為學(xué)生的專業(yè)素質(zhì)和分析及解決問題的能力奠定基礎(chǔ)。通過學(xué)習(xí)本課程，達(dá)到以下課程目標(biāo)：課程目標(biāo)1：學(xué)習(xí)線性結(jié)構(gòu)、樹結(jié)構(gòu)和圖結(jié)構(gòu)等常用的數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)與基于這兩種結(jié)構(gòu)的算法，學(xué)習(xí)查找、排序等常用算法，培養(yǎng)算法設(shè)計(jì)和評(píng)價(jià)的初步能力。課程目標(biāo)2：能根據(jù)實(shí)際問題選擇合適的數(shù)據(jù)邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)，能運(yùn)用數(shù)據(jù)結(jié)構(gòu)相關(guān)知識(shí)編程求解實(shí)際問題，對(duì)復(fù)雜工程問題具有一定的算法設(shè)計(jì)能力和程序調(diào)試能力。二、課程目標(biāo)對(duì)畢業(yè)要求的支撐關(guān)系畢業(yè)要求指標(biāo)點(diǎn)課程目標(biāo)權(quán)重指標(biāo)點(diǎn)1-3：能夠?qū)⑺惴ㄔO(shè)計(jì)、面向?qū)ο蟪绦蛟O(shè)計(jì)思想等知識(shí)與方法，用于計(jì)算機(jī)相關(guān)領(lǐng)域的復(fù)雜工程問題的分析、設(shè)計(jì)與實(shí)現(xiàn)課程目標(biāo)1課程目標(biāo)2H指標(biāo)點(diǎn)2-2：能夠?qū)τ?jì)算機(jī)相關(guān)領(lǐng)域的復(fù)雜工程問題進(jìn)行有效的表達(dá)和建模、分析和評(píng)價(jià)，具備獲得有效結(jié)論的能力課程目標(biāo)1課程目標(biāo)2M指標(biāo)點(diǎn)4-1：能夠通過文獻(xiàn)閱讀和實(shí)驗(yàn)設(shè)計(jì)并采用計(jì)算機(jī)專業(yè)知識(shí)，就復(fù)雜工程應(yīng)用中涉及的局部性功能或性能問題進(jìn)行研究，并對(duì)結(jié)果或數(shù)據(jù)進(jìn)行分析與解釋課程目標(biāo)2H

三、教學(xué)內(nèi)容、基本要求與學(xué)時(shí)分配序號(hào)教學(xué)內(nèi)容基本要求及重、難點(diǎn)（含德育要求）學(xué)時(shí)教學(xué)方式對(duì)應(yīng)課程目標(biāo)1緒論：基本概念與術(shù)語(yǔ)；算法的概念及其分析方法。理解數(shù)據(jù)結(jié)構(gòu)、邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)、算法等基礎(chǔ)知識(shí)；能初步理解算法分析的方法。樹立學(xué)好專業(yè)知識(shí)、助力中國(guó)夢(mèng)的信念；獲取仰望星空、探索創(chuàng)新的精神動(dòng)力。4講授式討論式課程目標(biāo)12線性表：線性表的基礎(chǔ)知識(shí)；順序表；鏈表；STL之vector、list。理解線性表、順序表和鏈表的概念及結(jié)構(gòu)特征等知識(shí)；理解順序表和單鏈表的基本操作及其算法；能應(yīng)用線性表及vector、list求解實(shí)際問題。樹立攻堅(jiān)克難、勇于挑戰(zhàn)的信念；獲取腳踏實(shí)地、精誠(chéng)合作的精神動(dòng)力。8講授式啟發(fā)式探究式討論式練習(xí)式課程目標(biāo)1課程目標(biāo)23棧與隊(duì)列：順序棧；鏈棧；循環(huán)隊(duì)列；鏈?zhǔn)疥?duì)列；STL之stack、queue。理解棧/隊(duì)列的概念和結(jié)構(gòu)特點(diǎn)；理解棧/隊(duì)列的在順序/鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)下的基本操作方法及算法；能應(yīng)用棧/隊(duì)列結(jié)構(gòu)及stack、queue求解實(shí)際問題。獲取團(tuán)隊(duì)合作、探索創(chuàng)新的精神動(dòng)力；深刻理解社會(huì)主義核心價(jià)值觀。8講授式啟發(fā)式探究式討論式練習(xí)式課程目標(biāo)1課程目標(biāo)24其他線性結(jié)構(gòu)：串；STL之string；數(shù)組；廣義表。理解串、數(shù)組和廣義表的概念與術(shù)語(yǔ)；理解數(shù)組元素存儲(chǔ)地址的計(jì)算方法；理解求廣義表的表頭、表尾、長(zhǎng)度和深度的方法；能應(yīng)用string及串相關(guān)算法求解實(shí)際問題。養(yǎng)成腳踏實(shí)地、精益求真的習(xí)慣；獲取奮發(fā)向上、探索創(chuàng)新的精神動(dòng)力。2講授式討論式練習(xí)式課程目標(biāo)1課程目標(biāo)25樹結(jié)構(gòu)：樹的基本概念與術(shù)語(yǔ)；二叉樹的概念、性質(zhì)、存儲(chǔ)結(jié)構(gòu)、遍歷；哈夫曼樹和哈夫曼編碼；樹、森林與二叉樹的轉(zhuǎn)換。理解樹的基本概念與術(shù)語(yǔ)；理解二叉樹的概念及基礎(chǔ)知識(shí)；理解二叉樹的遍歷方法和算法；理解樹、森林與二叉樹的轉(zhuǎn)換方法；理解哈夫曼樹和哈夫曼編碼的構(gòu)造方法和算法；能應(yīng)用二叉樹的相關(guān)算法求解實(shí)際問題。樹立愛國(guó)情懷、文化自信；獲取奮發(fā)向上、探索創(chuàng)新的精神動(dòng)力。12講授式啟發(fā)式探究式討論式練習(xí)式課程目標(biāo)1課程目標(biāo)26圖結(jié)構(gòu)：圖的基本概念與術(shù)語(yǔ)；圖的存儲(chǔ)結(jié)構(gòu)；圖的遍歷；最小生成樹；最短路徑；拓?fù)渑判?。理解圖的基本概念與術(shù)語(yǔ)；理解圖的鄰接矩陣與鄰接表；理解最小生成樹、最短路徑和拓?fù)渑判虻姆椒ê退惴ǎ荒軕?yīng)用圖的遍歷算法、最小生成樹和最短路徑的算法求解實(shí)際問題。體會(huì)勤奮學(xué)習(xí)、洞察研究的價(jià)值；獲取奮發(fā)向上、探索創(chuàng)新的精神動(dòng)力。12講授式啟發(fā)式探究式討論式練習(xí)式課程目標(biāo)1課程目標(biāo)27查找：查找基礎(chǔ)知識(shí)；順序查找；二分查找；二叉排序樹；平衡二叉樹；哈希查找；STL之set、map。理解查找的有關(guān)概念及性能分析方法；理解各種查找的基礎(chǔ)知識(shí)和相關(guān)算法的方法；理解順序查找、二分查找、二叉排序樹和哈希查找的算法；能簡(jiǎn)單分析各種查找算法的時(shí)間復(fù)雜度；能應(yīng)用常用查找算法及set、map求解實(shí)際問題。堅(jiān)定家國(guó)情懷和助力中國(guó)夢(mèng)的信念；獲取奮發(fā)向上、探索創(chuàng)新的精神動(dòng)力。8講授式啟發(fā)式探究式討論式練習(xí)式課程目標(biāo)1課程目標(biāo)28排序：排序基礎(chǔ)知識(shí)；插入排序；冒泡排序；選擇排序；快速排序；堆排序；歸并排序；STL之sort、nth_element。理解排序的概念、分類、穩(wěn)定性等知識(shí)；理解插入排序、冒泡排序、選擇排序、快速排序、堆排序、歸并排序等排序的方法和算法；能簡(jiǎn)單分析各種排序方法的時(shí)間/空間復(fù)雜度；能應(yīng)用常用排序算法及sort、nth_element求解實(shí)際問題。樹立正確的世界觀、價(jià)值觀、人生觀；獲取奮發(fā)向上、探索創(chuàng)新的精神動(dòng)力。10講授式啟發(fā)式探究式討論式練習(xí)式課程目標(biāo)1課程目標(biāo)2合計(jì)64序號(hào)實(shí)驗(yàn)項(xiàng)目實(shí)驗(yàn)內(nèi)容與要求學(xué)時(shí)類型對(duì)應(yīng)課程目標(biāo)1大整數(shù)加法及其應(yīng)用實(shí)驗(yàn)內(nèi)容：（1）單鏈表的實(shí)現(xiàn)；（2）采用鏈表實(shí)現(xiàn)大整數(shù)加法；（3）在線相關(guān)題目求解。實(shí)驗(yàn)要求：必修。8設(shè)計(jì)課程目標(biāo)1課程目標(biāo)22棧序列匹配及其應(yīng)用實(shí)驗(yàn)內(nèi)容：（1）棧的實(shí)現(xiàn)；（2）棧序列匹配算法；（3）在線相關(guān)題目求解。實(shí)驗(yàn)要求：必修。8設(shè)計(jì)課程目標(biāo)1課程目標(biāo)23二叉排序樹及其應(yīng)用實(shí)驗(yàn)內(nèi)容：（1）建立二叉排序樹；（2）二叉排序樹的查找；（3）二叉排序樹的遍歷；（4）在線相關(guān)題目求解。實(shí)驗(yàn)要求：必修。8設(shè)計(jì)課程目標(biāo)1課程目標(biāo)24最小生成樹及其應(yīng)用實(shí)驗(yàn)內(nèi)容：（1）建立圖的存儲(chǔ)結(jié)構(gòu)；（2）最小生成樹算法；（3）在線相關(guān)題目求解。實(shí)驗(yàn)要求：必修。8設(shè)計(jì)課程目標(biāo)1課程目標(biāo)2合計(jì)32注：實(shí)驗(yàn)要求包括必修、選修；實(shí)驗(yàn)類型包括演示、驗(yàn)證、綜合、設(shè)計(jì)等，后兩類占比大于80%。四、課程教學(xué)方法線上教學(xué)與線下教學(xué)相結(jié)合；集中講授與探究式教學(xué)及翻轉(zhuǎn)課堂相結(jié)合；采用講授式、啟發(fā)式、探究式、討論式和練習(xí)式等教學(xué)方式。五、學(xué)業(yè)評(píng)價(jià)和課程考核（一）考核方式及具體要求序號(hào)考核方式課程目標(biāo)1（分值）課程目標(biāo)2（分值）合計(jì)1平時(shí)作業(yè)55102課程實(shí)驗(yàn)55103平時(shí)表現(xiàn)1010204期中考試73105期末考試351550課程目標(biāo)對(duì)應(yīng)分值6238100（二）考核與評(píng)價(jià)標(biāo)準(zhǔn)1.平時(shí)作業(yè)考核與評(píng)價(jià)標(biāo)準(zhǔn)觀測(cè)點(diǎn)分值90-100分70-89分60-69分0-59分平時(shí)作業(yè)按時(shí)完成，90%以上的作業(yè)內(nèi)容齊全，基本知識(shí)點(diǎn)理解、掌握到位。能夠利用理論知識(shí)編程求解具體問題。按時(shí)完成，70%以上的作業(yè)內(nèi)容齊全，基本知識(shí)點(diǎn)理解、掌握得較為到位。能夠較好地利用理論知識(shí)編程求解具體問題。延時(shí)完成，60%以上的作業(yè)內(nèi)容齊全，基本知識(shí)點(diǎn)理解、掌握得基本到位?；灸軌蚶美碚撝R(shí)編程求解具體問題。不交和補(bǔ)交，50%以下的作業(yè)內(nèi)容齊全，基本知識(shí)點(diǎn)理解、掌握有偏差。基本不能利用理論知識(shí)編程求解具體問題。2.課程實(shí)驗(yàn)考核與評(píng)價(jià)標(biāo)準(zhǔn)觀測(cè)點(diǎn)分值90-100分70-89分60-69分0-59分課程實(shí)驗(yàn)?zāi)芨鶕?jù)實(shí)驗(yàn)要求自主設(shè)計(jì)實(shí)驗(yàn)方案，有自己的設(shè)計(jì)理念，實(shí)驗(yàn)完成度高，效果好。實(shí)驗(yàn)報(bào)告內(nèi)容完整。能根據(jù)實(shí)驗(yàn)要求自主設(shè)計(jì)實(shí)驗(yàn)方案，有自己的設(shè)計(jì)理念，實(shí)驗(yàn)完成度較高，效果較好。實(shí)驗(yàn)報(bào)告比較完整。能根據(jù)實(shí)驗(yàn)要求自主設(shè)計(jì)實(shí)驗(yàn)方案，實(shí)驗(yàn)完成度一般，效果一般。實(shí)驗(yàn)報(bào)告基本完整?；灸芨鶕?jù)實(shí)驗(yàn)要求自主設(shè)計(jì)實(shí)驗(yàn)方案，實(shí)驗(yàn)完成度較差，效果較差。實(shí)驗(yàn)報(bào)告不完整。3.平時(shí)表現(xiàn)與評(píng)價(jià)標(biāo)準(zhǔn)根據(jù)回答問題、課堂表現(xiàn)、團(tuán)隊(duì)合作及課程網(wǎng)站的微課學(xué)習(xí)、測(cè)驗(yàn)、測(cè)試及討論等完成情況及評(píng)分標(biāo)準(zhǔn)評(píng)分（百分制）。4.期中考試與評(píng)價(jià)標(biāo)準(zhǔn)根據(jù)期中考試及評(píng)分標(biāo)準(zhǔn)評(píng)分（百分制）。5.期末考試與評(píng)價(jià)標(biāo)準(zhǔn)根據(jù)期末考試及評(píng)分標(biāo)準(zhǔn)評(píng)分（百分制）。六、教材與參考書（一）推薦教材《數(shù)據(jù)結(jié)構(gòu)與算法》，黃龍軍主編，上海交通大學(xué)出版社，2022年7月版。（二）參考資料1．《數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）（第2版）》，嚴(yán)蔚敏主編，人民郵電出版社，2015年2月版；2．《數(shù)據(jù)結(jié)構(gòu)（第2版）》，陳越主編，高等教育出版社，2016年6月版；3