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

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