《數(shù)據(jù)結構》教學大綱

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

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