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

《數(shù)據(jù)結(jié)構(gòu)與算法》課程教學(xué)大綱一、課程簡介課程中文名數(shù)據(jù)結(jié)構(gòu)與算法課程英文名DataStructureandAlgorithm雙語授課□是√否課程代碼10112010課程學(xué)分5總學(xué)時數(shù)80（含實踐32）課程類別□通識教育課程□公共基礎(chǔ)課程√專業(yè)教育課程□綜合實踐課程□教師教育課程課程性質(zhì)√必修□選修□其他課程形態(tài)□線上√線下□線上線下混合式□社會實踐□虛擬仿真實驗教學(xué)考核方式√閉卷□開卷□課程論文□課程作品□匯報展示√報告√課堂表現(xiàn)□階段性測試□平時作業(yè)√其他（可多選）開課學(xué)院大數(shù)據(jù)與智能工程學(xué)院開課系(教研室)數(shù)據(jù)科學(xué)與大數(shù)據(jù)技術(shù)系面向?qū)I(yè)數(shù)據(jù)科學(xué)與大數(shù)據(jù)技術(shù)開課學(xué)期第2學(xué)期先修課程C語言程序設(shè)計后續(xù)課程Python程序設(shè)計選用教材耿國華.數(shù)據(jù)結(jié)構(gòu)-用C語言描述（第3版）[M].北京：高教出版社,2021.參考書目[1]嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)（C語言版）.清華大學(xué)出版社，2007.[2][美]馬克·艾倫·維斯（Mark，Allen，Weiss）著，馮舜璽譯.數(shù)據(jù)結(jié)構(gòu)與算法分析-語言描述（原書第2版）.機(jī)械工業(yè)出版社,2019.課程資源[1]中國大學(xué)MOOC—西北大學(xué)：/sCourse/course_4246.html[3]中國大學(xué)MOOC—北京大學(xué)：/course/PKU-1002534001課程簡介《數(shù)據(jù)結(jié)構(gòu)與算法》是數(shù)據(jù)科學(xué)與大數(shù)據(jù)技術(shù)專業(yè)必修的專業(yè)核心課程，教學(xué)內(nèi)容包括緒論、線性表、棧和隊列、串、樹和二叉樹、圖、查找、排序。通過理論與實踐相結(jié)合的系統(tǒng)學(xué)習(xí)，對工程問題中用計算機(jī)解決的非數(shù)值問題進(jìn)行分析、總結(jié)出計算機(jī)加工處理的數(shù)據(jù)對象的特性，用合適的抽象數(shù)據(jù)類型加以描述，以達(dá)到對問題的正確理解和描述；在對工程問題正確理解和描述的基礎(chǔ)上，選擇合適的存儲結(jié)構(gòu)，進(jìn)行算法設(shè)計、C語言程序編寫、運行調(diào)試及總結(jié)評價，從而實現(xiàn)問題求解。二、課程目標(biāo)表1課程目標(biāo)序號具體課程目標(biāo)課程目標(biāo)1通過數(shù)據(jù)結(jié)構(gòu)與算法理論與實踐相結(jié)合的系統(tǒng)學(xué)習(xí)，能夠識別并應(yīng)用合適的數(shù)學(xué)、自然科學(xué)和數(shù)據(jù)結(jié)構(gòu)與算法的知識，對工程問題中用計算機(jī)解決的非數(shù)值問題進(jìn)行分析、總結(jié)出計算機(jī)加工處理的數(shù)據(jù)對象的特性，用合適的抽象數(shù)據(jù)類型加以描述，以達(dá)到對問題的正確理解和描述，獲得關(guān)于問題的正確結(jié)論。課程目標(biāo)2能夠根據(jù)明確的需求，設(shè)計出針對計算機(jī)相關(guān)工程問題的解決方案并運用C語言實施，即在對工程問題正確理解和描述的基礎(chǔ)上，選擇合適的存儲結(jié)構(gòu)，進(jìn)行算法設(shè)計、程序編寫、運行調(diào)試及總結(jié)評價，從而實現(xiàn)問題求解。在此過程中能夠根據(jù)用戶需求確定計算機(jī)軟件或相關(guān)產(chǎn)品的設(shè)計目標(biāo)、設(shè)計和實施方案，在現(xiàn)實約束條件下，對設(shè)計方案進(jìn)行可行性研究和驗證；能夠在設(shè)計環(huán)節(jié)中體現(xiàn)創(chuàng)新意識，并考慮社會、安全、法律、文化以及產(chǎn)品使用環(huán)境等因素。課程目標(biāo)3能夠根據(jù)需求和軟件的使用環(huán)境對產(chǎn)品進(jìn)行驗證，包括設(shè)計實驗數(shù)據(jù)、綜合分析研究測試結(jié)果、對結(jié)果進(jìn)行評估，得到合理有效的結(jié)論。表2-1課程目標(biāo)與畢業(yè)要求對應(yīng)關(guān)系（數(shù)據(jù)科學(xué)與大數(shù)據(jù)技術(shù)專業(yè)）畢業(yè)要求指標(biāo)點課程目標(biāo)畢業(yè)要求2：問題分析：能夠應(yīng)用數(shù)學(xué)、自然科學(xué)、計算機(jī)科學(xué)和工程科學(xué)的基本原理，通過文獻(xiàn)研究、數(shù)學(xué)建模、工程經(jīng)驗提煉等方法，在大數(shù)據(jù)應(yīng)用的構(gòu)思與設(shè)計階段，識別、表達(dá)、分析大數(shù)據(jù)應(yīng)用領(lǐng)域復(fù)雜工程問題及其解決方法，以獲得有效結(jié)論?！綡】2.2能夠識別與表達(dá)計算系統(tǒng)中的關(guān)鍵問題，針對計算系統(tǒng)設(shè)計與實現(xiàn)的需求進(jìn)行系統(tǒng)分析和模擬。課程目標(biāo)1畢業(yè)要求3：設(shè)計/開發(fā)解決方案：能夠針對大數(shù)據(jù)應(yīng)用領(lǐng)域的復(fù)雜工程問題，綜合應(yīng)用數(shù)據(jù)科學(xué)與大數(shù)據(jù)技術(shù)基本原理和方法，設(shè)計、開發(fā)滿足特定應(yīng)用需求的系統(tǒng)方案，并能夠在設(shè)計環(huán)節(jié)中體現(xiàn)創(chuàng)新意識，考慮社會、健康、安全、法律、文化以及環(huán)境等多維度協(xié)同發(fā)展因素?！綥】3.2能夠識別計算機(jī)軟件系統(tǒng)設(shè)計與實現(xiàn)中的關(guān)鍵問題，并對方案進(jìn)行持續(xù)優(yōu)化，體現(xiàn)創(chuàng)新性。課程目標(biāo)2畢業(yè)要求4：研究：能夠基于數(shù)據(jù)科學(xué)與大數(shù)據(jù)技術(shù)的相應(yīng)原理，采用科學(xué)方法對大數(shù)據(jù)應(yīng)用領(lǐng)域中的復(fù)雜工程問題進(jìn)行研究，制定技術(shù)路線、設(shè)計實驗方案并開展實驗，通過實驗分析得到合理有效的結(jié)論?！綧】4.2能夠針對大數(shù)據(jù)應(yīng)用領(lǐng)域復(fù)雜工程問題，根據(jù)解決方案進(jìn)行方案設(shè)計與實施，能對設(shè)計或?qū)嵤┻^程的中間結(jié)果或數(shù)據(jù)進(jìn)行正確分析和反饋。課程目標(biāo)3三、課程學(xué)習(xí)內(nèi)容與方法（一）理論學(xué)習(xí)內(nèi)容及要求表3-1課程目標(biāo)、學(xué)習(xí)內(nèi)容和教學(xué)方法對應(yīng)關(guān)系序號課程模塊學(xué)習(xí)內(nèi)容學(xué)習(xí)任務(wù)課程目標(biāo)學(xué)習(xí)重點難點教學(xué)方法學(xué)時1緒論1.數(shù)據(jù)結(jié)構(gòu)與算法這門課程發(fā)展簡史；研究內(nèi)容及在計算機(jī)科學(xué)中的地位與作用1.拓展閱讀:數(shù)值計算與非數(shù)值計算2.練習(xí)：時間和空間復(fù)雜度課程目標(biāo)1重點：1.理解在非數(shù)值計算的程序設(shè)計中算機(jī)操作對象的數(shù)學(xué)模型特點明確課程的研究內(nèi)容2.數(shù)據(jù)結(jié)構(gòu)的基本概念及相關(guān)術(shù)語3.數(shù)據(jù)結(jié)構(gòu)的形式定義4.數(shù)據(jù)結(jié)構(gòu)的不同存儲結(jié)構(gòu)及其特點5.抽象數(shù)據(jù)類型ADT的描述方法6.抽象數(shù)據(jù)類型ADT的高級語言表示和實現(xiàn)方法7.算法的概念及特性難點：8.數(shù)據(jù)結(jié)構(gòu)的不同存儲結(jié)構(gòu)及其特點9.算法的評價方法1.課堂講授：針對第1、2、3節(jié)2.案例教學(xué)：針對第4節(jié)52.數(shù)據(jù)結(jié)構(gòu)的相關(guān)概念與術(shù)語，其中包括：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項、數(shù)據(jù)對象、數(shù)據(jù)結(jié)構(gòu)、邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)、數(shù)據(jù)類型、抽象數(shù)據(jù)類型ADT課程目標(biāo)13.抽象數(shù)據(jù)類型ADT的表示和實現(xiàn)方法課程目標(biāo)14.算法及算法的評價方法課程目標(biāo)32線性表1.線性表的有關(guān)概念及定義1.拓展閱讀：順序存儲和鏈?zhǔn)酱鎯Φ膽?yīng)用場景2.練習(xí)：線性表的插入和刪除課程目標(biāo)1重點：1.線性表的有關(guān)概念及邏輯結(jié)構(gòu)特點2.順序表上插入、刪除和定位運算的實現(xiàn)及效率分析3.線性表定位、插入、刪除運算在單鏈表上的實現(xiàn)4.循環(huán)鏈表、雙鏈表5.一元多項式的表示及相加難點：6.循環(huán)鏈表、雙鏈表7.一元多項式的表示及相加1.課堂講授：針對第1、2、3節(jié)2.案例教學(xué)：針對第4節(jié)72.線性表的順序表示及實現(xiàn)課程目標(biāo)23.線性表的鏈?zhǔn)奖硎炯皩崿F(xiàn)課程目標(biāo)24.線性表的應(yīng)用：多項式及其相加課程目標(biāo)33棧和隊列1.棧的定義、存儲表示及實現(xiàn)1.拓展閱讀：棧和隊列的應(yīng)用場景2.練習(xí)：棧的多種輸出序列、循環(huán)隊列課程目標(biāo)1重點：1.棧的定義及特點2.棧的順序存儲結(jié)構(gòu)及各種運算的實現(xiàn)3.棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)及各種運算的實現(xiàn)4.根據(jù)實際問題選擇應(yīng)用棧5.隊列的定義及特點；6.隊列的順序存儲結(jié)構(gòu)及其上的運算實現(xiàn)7.隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)及其上的運算實現(xiàn)8.根據(jù)實際問題選擇應(yīng)用隊列難點：9.隊列的順序存儲結(jié)構(gòu)及其上的運算實現(xiàn)1.課堂講授：針對第1、3節(jié)2.案例教學(xué)：針對第2、4節(jié)62.棧的應(yīng)用課程目標(biāo)23.隊列的定義、存儲表示及實現(xiàn)課程目標(biāo)14.隊列的應(yīng)用課程目標(biāo)24串1.串的數(shù)據(jù)類型定義1.拓展閱讀：串的匹配算法課程目標(biāo)1重點：1．串類型的特點2．串的各種基本操作的含義3.串的定長表示和實現(xiàn)4.串的堆分配表示和實現(xiàn)5.串的簡單模式匹配（布魯特-福斯）算法難點：6.串的定長表示和實現(xiàn)7.串的堆分配表示和實現(xiàn)1.課堂講授：針對第1、2節(jié)2.演示教學(xué)：針對第3節(jié)32.串的存儲表示和各種基本操作的實現(xiàn)課程目標(biāo)13.串的模式匹配算法課程目標(biāo)25樹和二叉樹1.樹的定義和基本術(shù)語1.拓展閱讀：平衡二叉樹2.練習(xí)：二叉樹的遍歷課程目標(biāo)1重點：1.理解樹的遞歸定義2.理解樹的有關(guān)基本概念和術(shù)語3.二叉樹的定義、性質(zhì)及性質(zhì)的推導(dǎo)過程、邏輯特點及五種基本形態(tài)、基本運算4.二叉樹的順序存儲結(jié)構(gòu)、鏈?zhǔn)酱鎯Y(jié)構(gòu)特點及其類型說明5.二叉樹的三種遍歷方法及其算法6.在遍歷基礎(chǔ)上實現(xiàn)二叉樹的建立7.二叉樹遍歷算法的應(yīng)用：二叉樹各類結(jié)點的輸出、數(shù)目統(tǒng)計、深度的計算等8.二叉樹的雙親表示法、孩子表示法、孩子兄弟表示法難點：9.樹的表示方法10.樹或森林與二叉樹的轉(zhuǎn)換11.哈夫曼樹和哈夫曼編碼1.課堂講授：針對第1、2節(jié)2.演示教學(xué)：針對第3、4節(jié)3.案例教學(xué)：針對第5節(jié)82.二叉樹的定義、性質(zhì)和存儲結(jié)構(gòu)課程目標(biāo)13.二叉樹的遍歷以及遍歷算法的各種描述形式課程目標(biāo)14.樹的存儲結(jié)構(gòu)、樹或森林與二叉樹的轉(zhuǎn)換、遍歷課程目標(biāo)25.哈夫曼樹和哈夫曼編碼課程目標(biāo)36圖1.圖的基本概念、存儲表示（鄰接矩陣、鄰接表、十字鏈表，鄰接多重表）1.拓展閱讀：最小生成樹的應(yīng)用場景2.練習(xí)：關(guān)鍵路徑課程目標(biāo)1重點：1.圖的基本概念2.圖的存儲表示3.圖的搜索遍歷4.圖的連同分量、最小生成樹算法5.有向圖的拓?fù)渑判蛩惴?.關(guān)鍵路徑7.最短路徑難點：8.圖的搜索遍歷9.拓?fù)渑判?0.關(guān)鍵路徑11.最短路徑1.課堂講授：針對第1節(jié)2.演示教學(xué)：針對第2、3節(jié)3.案例教學(xué)：針對第4、5節(jié)82.圖的遍歷與連通性：深度優(yōu)先搜索；廣度優(yōu)先搜索課程目標(biāo)23.圖的連通分量。最小生成樹：普里姆算法；克魯斯卡爾算法課程目標(biāo)24.拓?fù)渑判?、關(guān)鍵路徑課程目標(biāo)25.最短路徑課程目標(biāo)27查找1.查找的基本概念1.拓展閱讀：平衡二叉樹2.練習(xí)：哈希表的建立及查找課程目標(biāo)1重點：1.查找表的基本概念及查找原理。2.查找效率及平均查找長度的討論。3.順序表的順序查找。4.有序表的查找。5.索引順序表的查找。6.二叉排序樹7.哈希表難點：8.二叉排序樹的插入、刪除9.哈希表的建立及查找分析1.課堂講授：針對第1、2、3節(jié)2.案例教學(xué)：針對第4節(jié)62.靜態(tài)查找表課程目標(biāo)13.動態(tài)查找表課程目標(biāo)14.哈希表課程目標(biāo)38排序1.排序的基本概念1.拓展閱讀：內(nèi)部排序與外部排序2.練習(xí)：冒泡排序和快速排序課程目標(biāo)1重點：1.排序有關(guān)基本概念和術(shù)語。2.排序算法效率討論。3.插入類排序：簡單插入排序、折半插入排序、Shell排序4.交換類排序：冒泡排序、快速排序5.選擇類排序：簡單選擇排序、樹形選擇排序、堆排序6.二路歸并排序7.分配類排序：多關(guān)鍵字排序、基數(shù)排序。難點：8.Shell排序、快速排序、堆排序9.對于每種排序方法要正確理解排序的基本思想、算法策略并能進(jìn)行性能分析1.課堂講授：針對第1節(jié)2.演示教學(xué)：針對第2、3、4、5、6節(jié)52.插入類排序課程目標(biāo)33.交換類排序課程目標(biāo)34.選擇類排序課程目標(biāo)35.歸并排序課程目標(biāo)36.分配類排序課程目標(biāo)3實驗學(xué)習(xí)內(nèi)容及要求表3-2課程目標(biāo)、學(xué)習(xí)內(nèi)容和教學(xué)方法對應(yīng)關(guān)系序號項目名稱項目來源教學(xué)目標(biāo)（觀測點、重難點）學(xué)時數(shù)項目類型要求每組人數(shù)教學(xué)方法課程目標(biāo)1實驗1：C語言編程復(fù)習(xí)及訓(xùn)練實驗教材1．復(fù)習(xí)C語言的基礎(chǔ)知識與編程技能，熟悉開發(fā)環(huán)境、程序編輯、調(diào)試運行過程4設(shè)計性實驗必做1實驗指導(dǎo)課程目標(biāo)12.C語言數(shù)組的定義、操作及應(yīng)用（重點）3.C語言鏈表的定義、操作及應(yīng)用（重點）4.C語言函數(shù)知識的應(yīng)用（重點）2實驗2：線性表的基本操作實現(xiàn)及應(yīng)用實驗教材1.實現(xiàn)線性表的順序表示及各種操作（重點）4設(shè)計性實驗必做1實驗指導(dǎo)課程目標(biāo)22.實現(xiàn)線性表的鏈?zhǔn)奖硎炯案鞣N操作（重點）3.線性表的應(yīng)用（難點）3實驗3：棧與隊列的實現(xiàn)及應(yīng)用實驗教材1.完成棧的建立、各種操作的實現(xiàn)及在實際問題中應(yīng)用（重點）4設(shè)計性實驗必做1實驗指導(dǎo)課程目標(biāo)22.完成隊列的建立、各種操作的實現(xiàn)及在實際問題中應(yīng)用（重點）4實驗4：字符串處理實驗教材1.綜合應(yīng)用字符串的存儲表示，C語言提供的各種基本操作函數(shù)實現(xiàn)指定串的操作，完成指定的應(yīng)用串的編程任務(wù)2設(shè)計性實驗必做1實驗指導(dǎo)課程目標(biāo)15實驗5：二叉樹的表示與遍歷實驗教材1.完成二叉樹的二叉鏈表的建立（重點）4設(shè)計性實驗必做1實驗指導(dǎo)課程目標(biāo)12.完成二叉樹的遍歷：先序遍歷、中序遍歷、后序遍歷（重點）3.完成二叉樹遍歷操作的應(yīng)用（難點）6實驗6：圖的存儲表示及應(yīng)用實驗教材1.掌握圖的鄰接矩陣的建立、輸出及應(yīng)用（重點）4綜合性實驗必做1實驗指導(dǎo)課程目標(biāo)12.掌握圖的鄰接表的建立、輸出及應(yīng)用（重點）7實驗7：圖的搜索實驗教材1.用不同的存儲結(jié)構(gòu)表示圖，按照深度優(yōu)先的方法搜索輸出圖的各個頂點（難點）2綜合性實驗必做1實驗指導(dǎo)課程目標(biāo)22.用不同的存儲結(jié)構(gòu)表示圖，按照廣度優(yōu)先的方法搜索輸出圖的各個頂點（難點）8實驗8：圖的拓?fù)渑判驅(qū)嶒灲滩?.選擇一種存儲結(jié)構(gòu)表示圖2綜合性實驗必做1實驗指導(dǎo)課程目標(biāo)22.輸出圖的拓?fù)渑判蛐蛄校y點）9實驗9：基本查找、排序算法的實現(xiàn)及應(yīng)用實驗教材1.選用不同的存儲結(jié)構(gòu)表示查找表，并在此基礎(chǔ)上實現(xiàn)、應(yīng)用查找算法（重點）6設(shè)計性實驗必做1實驗指導(dǎo)課程目標(biāo)32.選用不同的存儲結(jié)構(gòu)表示記錄序列，并在此基礎(chǔ)上實現(xiàn)、并運用各種排序算法（重點）3.根據(jù)不同的數(shù)據(jù)特性選擇存儲結(jié)構(gòu)、查找和排序算法來解決實際問題。（難點）四、課程考核（一）考核內(nèi)容與考核方式表4-1課程目標(biāo)、考核內(nèi)容與考核方式對應(yīng)關(guān)系課程目標(biāo)考核內(nèi)容所屬學(xué)習(xí)模塊/項目考核占比考核方式課程目標(biāo)11.數(shù)據(jù)結(jié)構(gòu)與算法這門課程展簡史；研究內(nèi)容及在計算機(jī)科學(xué)中的地位與作用緒論40%課堂交互、閉卷考試、實驗報告2.數(shù)據(jù)結(jié)構(gòu)的相關(guān)概念與術(shù)語，其中包括：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項、數(shù)據(jù)對象、數(shù)據(jù)結(jié)構(gòu)、邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)、數(shù)據(jù)類型、抽象數(shù)據(jù)類型ADT緒論3.抽象數(shù)據(jù)類型ADT的表示和實現(xiàn)方法緒論4.線性表的有關(guān)概念及定義線性表5.棧的定義、存儲表示及實現(xiàn)棧和隊列6.隊列的定義、存儲表示及實現(xiàn)棧和隊列7.串的數(shù)據(jù)類型定義串8.串的存儲表示和各種基本操作的實現(xiàn)串9.樹的定義和基本術(shù)語樹和二叉樹10.二叉樹的定義、性質(zhì)和存儲結(jié)構(gòu)樹和二叉樹11.二叉樹的遍歷以及遍歷算法的各種描述形式樹和二叉樹12.圖的基本概念、存儲表示（鄰接矩陣、鄰接表、十字鏈表，鄰接多重表）圖13.查找的基本概念查找14.靜態(tài)查找表查找15.動態(tài)查找表查找16.排序的基本概念排序課程目標(biāo)21.線性表的順序表示及實現(xiàn)線性表40%課堂交互、閉卷考試、實驗報告2.線性表的鏈?zhǔn)奖硎炯皩崿F(xiàn)線性表3.棧的應(yīng)用棧和隊列4.隊列的應(yīng)用棧和隊列5.串的模式匹配算法串6.樹的存儲結(jié)構(gòu)、樹或森林與二叉樹的轉(zhuǎn)換、遍歷樹和二叉樹7.圖的遍歷與連通性：深度優(yōu)先搜索；廣度優(yōu)先搜索圖8.圖的連通分量。