《數據結構與算法》教學大綱

數據結構與算法課程教學大綱課程基本信息二、課程簡介及教學基本要求《數據結構與算法》是計算機程序設計的重要理論基礎，是計算機相關專業(yè)的核心專業(yè)基礎課程，針對我校計算機學院大學二年級學生開設，它前承高級語言程序設計和高等數學，后接操作系統(tǒng)、編譯原理、數據庫原理、人工智能等專業(yè)課程。程序設計就像搭積木，數據結構是零件，而算法則是設計圖紙。高效運行且節(jié)約存儲空間的程序，取決于數據結構和算法的設計。課程的學習效果不僅關系到后續(xù)課程的學習，而且直接關系到軟件設計水平的提高和專業(yè)素質的培養(yǎng)，在計算機學科教育中有非常重要的作用。本課程將按照“線性結構，樹型結構，圖形結構，集合結構”四大模塊循序漸進展開，重點學習線性表、字符串、棧和隊列、樹和二叉樹、圖以及集合在計算機上的存儲和處理。課程采用“線下+線上”“課程+思政”“理論+實踐”六位一體，“課前導學→理論精講→小組實驗→闖關訓練→實踐擴展→答疑反饋”六階遞進的混合教學模式。理論課要求：講解數據結構與算法的基礎理論、基本操作、手工模擬和算法實現，通過理論講解、實操演示、動畫模擬、翻轉課堂等方法組織教學，每周提供一次線上輔導答疑。實驗課要求：使用學校在線教育綜合平臺（網址：），每位學生根據提供的素材完成數據結構與算法實驗作業(yè)，并將實驗報告上傳到課程平臺。課前和課后要求：基于“學堂在線”（網址：/）和學校在線教育綜合平臺（網址：）精品在線課程學習平臺，拓展延伸學生知識面，引導學生自主學習，積極完成課前導學、闖關訓練、習題微課等內容，提高學生針對現實問題的分析、設計和編碼能力。三、課程教學目標通過本課程的學習，使學生掌握數據結構的基本理論與知識，算法設計與分析的基本方法與技巧，培養(yǎng)學生分析和解決實際問題的能力，并為其開展計算機學科應用奠定數據結構與算法方面的基礎。通過解決工程問題，踐行學術道德教育，增強學生軟件崗位職業(yè)道德和團隊合作意識，理論聯(lián)系實際、精益求精的工作態(tài)度以及勇于開拓的創(chuàng)新精神。具體目標如下：目標1.理解數據結構和算法的基本概念。掌握常用基本數據結構的邏輯特征、存儲表示和基本運算。掌握常用查找和排序算法，并能夠分析不同算法的適用場景。目標2.具備初步的算法分析能力，會計算算法的時間、空間復雜度。目標3.提升分析解決問題的能力，學會分析數據對象的特性，選擇（應用）有效的數據結構，設計合適的算法，并編寫和調試程序。目標4.培養(yǎng)軟件崗位職業(yè)道德和團隊合作意識，理論聯(lián)系實際、精益求精的工作態(tài)度以及勇于開拓的創(chuàng)新精神。畢業(yè)要求畢業(yè)要求分解指標點課程教學目標課程貢獻度1.工程知識1.1掌握數學、自然科學、工程基礎和計算機專業(yè)的基本概念和基本理論知識，并能夠將其用于計算機領域復雜工程問題的表述。（知識掌握）目標1H2.問題分析2.1具備應用數學、自然科學和工程科學的基本原理，識別和判斷復雜工程問題的關鍵環(huán)節(jié)和參數的能力。（識別）目標2H3.工程設計3.2理解和分析計算機應用的特定需求，對復雜工程問題進行分解，對子系統(tǒng)模塊和業(yè)務流程進行設計與開發(fā)。（功能設計）目標3H4.調查研究4.1基于計算機專業(yè)技術原理，通過文獻研究、信息分析等相關方法，研究和分析計算機領域復雜工程問題的解決方案。（研究分析）4.2針對相關領域關鍵問題，研究對象特征，運用計算機科學相關原理和專業(yè)知識選擇研究路線，設計實驗方案。（設計方案）目標3H8.溝通表達和團隊合作8.1具有團隊精神，能夠勝任團隊成員角色，具有一定獨立解決工程問題的能力，同時又能配合團隊合作完成任務，能組織團隊成員開展工作，并具有合理協(xié)調和決策的能力。（組織與協(xié)作）目標4L注：課程貢獻度用標志表示（“H”表示“高”，“M”表示“中”，“L”表示“低”）四、教學內容與教學方法第一章緒論【課程內容】數據結構與算法課程主要研究非數值計算的現實問題中的數據在計算機中表示、存取和處理。本章內容包括：1.什么是數據結構2.數據結構的基本概念和術語3.算法和算法分析4．抽象數據類型知識點：數據的三層次，數據結構的三要素，四種邏輯結構，四種存儲結構，算法的概念和特點，算法的時間和空間復雜度。【教學方法】講授法結合討論法、翻轉課堂、案例教學、項目教學等多種教學方法?！局握n程目標】目標1，目標2。【重/難點】重點：數據結構的概念和術語、算法時間復雜性分析方法。難點：數據邏輯結構和存儲結構的定義以及區(qū)別，算法時間復雜性分析方法以及復雜性函數的漸進表示。【學時分配】線下理論教學2學時，線下實驗0學時，線上單元導學0.5學時，線上習題解析0.5學時，線上答疑輔導1學時課程總學時64，其中：理論學時4課程總學時64，其中：理論學時48，實驗學時16。線上學習內容未計入總學時計算。下同，不再贅述?！驹u價方式】在線學習數據的形成性評價+闖關訓練和實驗作業(yè)的結果性評價。第二章線性表【課程內容】線性結構是最簡單、最常用的數據結構，其特點是數據元素之間的邏輯關系是線性關系。線性結構是數據元素間約束力最強的一種數據結構：在非空線性結構的有限集合中，存在唯一一個被稱為“第一個”的數據元素；存在唯一一個被稱為“最后一個”的數據元素；除“第一個”數據元素無前驅外，集合中的每個數據元素均有且只有一個“直接”前驅；除“最后一個”元素無后繼外，集合中的每個數據元素均有且只有一個“直接”后繼。本章內容包括：1．線性表的類型定義2．線性表的順序表示和基本運算3．線性表的鏈式表示和基本運算4．雙鏈表的概念和基本運算5．循環(huán)鏈表的概念和基本運算6．線性表實現方法的比較7．算法設計舉例知識點：順序表、單鏈表的定義、特點及基本操作，雙向鏈表、循環(huán)鏈表的特點、定義及基本操作。【教學方法】講授法結合討論法、翻轉課堂、案例教學、項目教學等多種教學方法?！局握n程目標】目標1，目標2，目標3?！局?難點】重點：順序表、單鏈表、雙向鏈表、循環(huán)鏈表的插入、刪除操作。難點：順序表和單鏈表操作的實現?！緦W時分配】線下理論教學6學時，線下實驗4學時，線上單元導學1.5學時，線上習題解析1.5學時，線上答疑輔導3學時?！驹u價方式】在線學習數據的形成性評價+闖關訓練和實驗作業(yè)的結果性評價。第三章棧和隊列【課程內容】棧和隊列仍屬于線性結構，它們的邏輯結構和線性表相同，具有線性結構的共同特征。學習本章時，既要注意棧和隊列所具有的線性結構的共性，更要掌握其個性。棧和隊列的基本操作是線性表操作的子集，限定插入和刪除元素的操作只能在線性表的一端進行。棧按“后進先出”的規(guī)則進行操作，隊列按“先進先出”的規(guī)則進行操作。本章內容包括：1.棧的概念、特點、邏輯結構、存儲結構和基本運算2.棧的應用舉、棧與遞歸3.隊列的概念、特點、邏輯結構、存儲結構和基本運算4.算法設計舉例知識點：棧的特點及基本操作，順序棧和鏈棧的實現，棧與遞歸，隊列的特點和基本操作，循環(huán)隊列的實現，棧與隊列的綜合應用【教學方法】講授法結合討論法、翻轉課堂、案例教學、項目教學等多種教學方法。【支撐課程目標】目標1，目標2，目標3。【重/難點】重點：棧的壓棧和彈棧操作、隊列的入隊和出隊操作、中綴表達式求值難點：棧的應用：中綴表達式求值、中綴表達式轉后綴表達式、后綴表達式求值【學時分配】線下理論教學6學時，線下實驗2學時，線上單元導學1.5學時，線上習題解析1.5學時，線上答疑輔導3學時?！驹u價方式】在線學習數據的形成性評價+闖關訓練和實驗作業(yè)的結果性評價。第四章字符串【課程內容】從數據結構角度講，串屬于線性結構，是一種數據元素（簡稱元素）為字符的特殊的線性表。串的邏輯結構和線性表相似。學習本章時，要注意串所具有的線性結構的共性，更要掌握其個性。串的特殊性主要表現在以下兩個方面：①串中的一個元素是一個字符；②操作的對象一般不再是單個元素，而是一組元素。串的基本操作和線性表的基本操作有很大差別。在線性表的基本操作中，大多以單個元素作為操作對象，而在串的基本操作中，通常以“串的整體”作為操作對象，例如，在主串中查找子串的位置，在主串中截取一個子串。本章內容包括：1.串的基本概念2.串的表示和實現3.串的模式匹配算法知識點：字符串的概念、存儲和基本操作，模式匹配方法?！窘虒W方法】講授法結合討論法、翻轉課堂、案例教學、項目教學等多種教學方法?！局握n程目標】目標1，目標2，目標3?！局?難點】重點：串的基本概念和操作的實現，KMP算法的手工模擬。難點：KMP算法的實現?！緦W時分配】線下理論教學2學時，線下實驗0學時，線上單元導學0.5學時，線上習題解析0.5學時，線上答疑輔導1學時?！驹u價方式】在線學習數據的形成性評價+闖關訓練和實驗作業(yè)的結果性評價。第六章樹和二叉樹【課程內容】在前幾章主要介紹了線性結構，線性結構主要反映了數據元素之間的線性關系。從本章開始介紹非線性結構，其中樹結構就是一種重要的非線性結構，它可以用來描述數據元素間的層次關系。這種層次關系的特點是，任意一個結點的直接前驅（結點）如果存在，則一定是唯一的；直接后繼（結點）如果存在，則可以有多個，這也被稱為一對多的關系。本章內容包括：1.樹的概念2.二叉樹的概念和性質3.二叉樹的表示和實現4.樹和森林的遍歷運算5.樹與二叉樹的轉換6.算法設計舉例知識點：樹的定義和術語、二叉樹的定義、術語和主要性質、二叉樹的遍歷算法、二叉樹的擴展算法、二叉樹結構的性質、樹的鏈接存儲結構、樹與二叉樹的轉換、樹和森林的遍歷?！窘虒W方法】講授法結合討論法、翻轉課堂、案例教學、項目教學等多種教學方法?！局握n程目標】目標1，目標2，目標3?！局?難點】重點：二叉樹的性質、二叉樹的二叉鏈式存儲結構、二叉樹的遍歷、二叉樹結構的性質、樹與二叉樹的轉換、樹和森林的遍歷。難點：二叉樹的性質、二叉樹的遍歷及擴展算法、二叉樹結構的性質、樹和森林的遍歷、樹與二叉樹的轉換【學時分配】線下理論教學6學時，線下實驗2學時，線上單元導學1.5學時，線上習題解析1.5學時，線上答疑輔導3學時?！驹u價方式】在線學習數據的形成性評價+闖關訓練和實驗作業(yè)的結果性評價。第七章樹和二叉樹的應用【課程內容】第6章已經介紹了樹和二叉樹的相關概念、性質、存儲結構和基本運算，二叉樹具有廣泛的應用，常被用作表達式樹、哈夫曼樹、堆、二叉搜索（排序）樹、平衡二叉樹、判定樹等。本章內容包括：1.表達式樹2.哈夫曼樹和哈夫曼編碼3.堆和優(yōu)先級隊列4.算法設計舉例知識點：哈夫曼樹的概念；哈夫曼樹的創(chuàng)建和哈夫曼編碼，二叉堆的概念和特點、優(yōu)先級隊列的概念及其二叉堆實現?！窘虒W方法】講授法結合討論法、翻轉課堂、案例教學、項目教學等多種教學方法。【支撐課程目標】目標1，目標2，目標3?！局?難點】重點：1．哈夫曼樹的創(chuàng)建和哈夫曼編碼的過程。2．基于二叉堆的優(yōu)先級隊列的創(chuàng)建、入隊、出隊運算。難點：優(yōu)先級隊列的入隊、出隊、創(chuàng)建算法。【學時分配】線下理論教學4學時，線下實驗2學時，線上單元導學1學時，線上習題解析1學時，線上答疑輔導2學時?！驹u價方式】在線學習數據的形成性評價+闖關訓練和實驗作業(yè)的結果性評價。第八章圖【課程內容】圖是一種復雜的非線性結構，線性結構和樹結構也可以看成簡單的圖結構。在圖結構中，結點之間的關系是任意的，是一種“多對多”的關系，即每個結點可以有零個或多個直接前驅和直接后繼。本章內容包括：1.圖的概念和術語2.圖的存儲結構3.圖的遍歷知識點：圖的基本概念和術語、存儲結構、圖的遍歷算法、圖的生成樹【教學方法】講授法結合討論法、翻轉課堂、案例教學、項目教學等多種教學方法。【支撐課程目標】目標1，目標2，目標3?！局?難點】重點：基本概念（特別是完全圖、連通分量、生成樹和鄰接點）、圖的鄰接矩陣和鄰接表存儲表示的特點、圖的深度優(yōu)先和廣度優(yōu)先遍歷算法難點：圖的深度優(yōu)先和廣度優(yōu)先遍歷算法【學時分配】線下理論教學4學時，線下實驗4學時，線上單元導學1學時，線上習題解析1學時，線上答疑輔導2學時?！驹u價方式】在線學習數據的形成性評價+闖關訓練和實驗作業(yè)的結果性評價。第九章圖的應用【課程內容】第8章已經介紹了圖的基本概念和性質，重點討論了圖的存儲結構和遍歷運算。本章重點介紹最小生成樹、最短路徑、拓撲排序等內容，簡單介紹關鍵路徑算法，這些內容都屬于圖的應用，內容包括：1.最小生成樹2.有向無環(huán)圖及其應用3.最短路徑知識點：MST性質、最小生成樹（Prim和Kruscal）、拓撲排序算法、求每對頂點之間最短路徑的Dijkstra算法、求所有頂點間最短路徑的Floyd算法?！窘虒W方法】講授法結合討論法、翻轉課堂、案例教學、項目教學等多種教學方法?！局握n程目標】目標1，目標2，目標3?！局?難點】重點：求最小生成樹的Prim算法和Kruscal算法、拓撲排序算法、求最短路徑的Dijkstra和Floyd算法難點：最小生成樹Prim算法、最短路徑Dijkstra和Floyd算法【學時分配】線下理論教學4學時，線下實驗0學時，線上單元導學1學時，線上習題解析1學時，線上答疑輔導2學時?！驹u價方式】在線學習數據的形成性評價+闖關訓練和實驗作業(yè)的結果性評價。第十章集合與查找【課程內容】集合是基本的數據結構之一。集合中的數據元素除屬于同一個集合之外，沒有任何邏輯關系。集合上的運算主要有：查找某個元素是否存在，將集合中的元素按照它的某個唯一標識排序。集合有多種組織形式，例如，集合可以用線性表、搜索樹和散列表表示。本章首先介紹集合與查找的基本概念，然后討論與集合相關的查找方法和簡單的性能分析方法，包適用于靜態(tài)查找表的順序查找和折半查找，以及適用于動態(tài)查找表的二叉查找樹、AVL樹等，內容包括：1.集合與查找的基本概念2.靜態(tài)查找表上的查找3.動態(tài)查找表上的查找4.算法設計舉例知識點：集合與查找的基本概念、靜態(tài)查找表（順序查找算法，折半查找算法）；動態(tài)查找表（二叉查找樹基本概念、性質和操作）。【教學方法】講授法結合討論法、翻轉課堂、案例教學、項目教學等多種教學方法?！局握n程目標】目標1，目標2，目標3?！局?難點】重點：有序表的折半查找，二叉查找樹的查找、插入和刪除算法，平均查找長度的計算難點：二叉查找樹的查找、插入和刪除算法【學時分配】線下理論教學4學時，線下實驗0學時，線上單元導學1學時，線上習題解析1學時，線上答疑輔導2學時?！驹u價方式】在線學習數據的形成性評價+闖關訓練和實驗作業(yè)的結果性評價。第十一章散列表【課程內容】本章介紹的散列法是專用于集合的數據存儲和檢索方式，它不是利用比較的辦法，而是用一個散列函數將數據和它的存儲位置關聯(lián)起來，這樣就可以通過這個散列函數快速存儲和檢索數據。本章內容包括：1.散列表的概念2.構造散列函數的方法3.解決沖突的方法4.散列表的查找性能分析知識點：散列的基本概念和術語、散列函數，解決沖突方法?！窘虒W方法】講授法結合討論法、翻轉課堂、案例教學、項目教學等多種教學方法?！局握n程目標】目標1，目標2，目標3?！局?難點】重點：構造散列函數的除留余數法，解決沖突的線性探查法和鏈地址法，平均查找長度的計算難點：解決沖突方法：線性探查法和鏈地址法【學時分配】線下理論教學2學時，線下實驗0學時，線上單元導學0.5學時，線上習題解析0.5學時，線上答疑輔導1學時?！驹u價方式】在線學習數據的形成性評價+闖關訓練和實驗作業(yè)的結果性評價。第十二章排序【課程內容】排序是數據處理中經常用到的一種重要操作，通過排序可以將一組無序的數據元素按其關鍵字的非遞減（或非遞增）次序排列成有序序列，排序的目的之一就是方便數據的查找。本章將介紹幾種常用的排序方法及各種內部排序方法的比較，內容包括：1.排序的基本概念2.插入排序：直接插入排序、折半插入排序、希爾排序3.交換排序：起泡排序、快速排序4.選擇排序：直接選擇排序、堆排序5.歸并排序：2路歸并排序6.各種內部排序方法的比較知識點：直接插入排序，冒泡排序，快速排序，直接選擇排序，堆排序，合并排序，基于關鍵詞比較的排序算法下界分析?！窘虒W方法】講授法結合討論法、翻轉課堂、案例教學、項目教學等多種教學方法?！局握n程目標】目標1，目標2，目標3?！局?難點】重點：直接插入排序，Shell排序，冒泡排序，快速排序，直接選擇排序，堆排序，歸并排序，基于關鍵詞比較的排序算法分析。難點：Shell排序，快速排序，堆排序，歸并排序?！緦W時分配】線下理論教學8學時，線下實驗2學時，線上單元導學2學時，線上習題解析2學時，線上答疑輔導2學時?！驹u價方式】在線學習數據的形成性評價+闖關訓練和實驗作業(yè)的結果性評價。五、課內實驗（實踐）序號實驗項目名稱實驗內容及要求學時支撐課程目標類型必做/選做1順序表順序表的類型定義及基本操作2目標3目標4設計性必做2單鏈表單鏈表的類型定義及基本操作2目標3目標4設計性必做3棧與隊列（1）棧的類型定義及基本操作（2）隊列的類型定義及基本操作2目標3目標4設計性必做4二叉樹二叉樹的類型定義和基本操作2目標3目標4設計性必做5Huffman樹建立Huffman樹并進行Huffman編碼2目標3目標4設計性必做6圖的鄰接矩陣表示法圖的鄰接矩陣表示法義及基本操作2目標3目標4設計性必做7圖的鄰接表表示法圖的鄰接表表示法義及基本操作2目標3目標4設計性必做8排序實現常用排序算法：直接插入排序、希爾排序、冒泡排序、快速排序、簡單選擇排序、堆排序、2路歸并排序，能夠測試上述算法性能。2目標3目標4驗證性必做注：類型包括驗證性、綜合性、設計性、演示性等。六、課程考核與評價課程考核包括過程性考核和期末考核，過程性考核包括平時考核和實驗/實踐考核，其中平時考核含考勤和課堂表現、微課學習情況、章節(jié)測驗或作業(yè)等。課程總評成績=平時成績（30%）+實驗/實踐成績（20%）+期末成績（50%）過程性考核成績占總成績的比例為50%，其中考勤和課堂表現占總成績的10%。成績組成考核/評價環(huán)節(jié)權重考核/評價細則平時成績考勤和課堂表現10%統(tǒng)計雨課堂上的出勤率和課堂表現，給予相應分值微課學習情況10%統(tǒng)計優(yōu)慕課（或學堂在線）由各專業(yè)授課教師選擇適合的在線教學平臺上的視頻觀看率和在線時長，給予相應分值由各專業(yè)授課教師選擇適合的在線教學平臺章節(jié)測試或作業(yè)10%統(tǒng)計優(yōu)慕課（或學堂在線）由各專業(yè)授課教師選擇適合的在線教學平臺上的章節(jié)測試或作業(yè)成績由各專業(yè)授課教師選擇適合的在線教學平臺實驗/實踐成績實驗報告20%以實驗報告為主要評價依據，以展演視頻（選做）作為參考期末成績在線考試50%依托“百科園”平臺開展在線考試七、教學資源（一）教材《算法與數據結構（C++語言版）》，主編:馮廣慧，出版社：電子工業(yè)出版社，出版時間：2018.12。（二）參考資料1.《算法與數據結構考研試題精析》，主編:陳守孔，出版社：機械工業(yè)出版社，出版時間：2020.62.《數據結構：思想與實現,高等教育出版社》，主編:翁惠、玉俞勇，出版社：高等教育出版社，出版時間：20183.《數據結構（C語言版）》，主編:嚴蔚敏，出版社：清華大學出版社，出版時間：1997.44.《TheArtofComputerProgramming,Volume1/FundamentalsAlgorithms:Volume3/SortingandSearching》，主編:D.E.Kunth,出版社：MA:Addison-Wesley，出版時間：19735.本課程在珠?？萍紝W院在線教育綜合平臺網址：/meol/jpk/course/layout/newpage/index.jsp?courseId=227346.本課程在“學堂在線”慕課平臺網址：/course/jluzh61021002425/12425244附錄1、課程思政知識點參考本課程通過提煉中國好故事，展示中國好成果，植入中國好素材，傳遞中國好聲音，把愛國基因融入學生血脈，培養(yǎng)以愛國主義為核心的精神品格。本課程思政點設計如下表所示。內容或章節(jié)思政教學案例融入實例思政元素挖掘第一章概論1.1什么是數據結構在介紹《數據結構與算法》課程的發(fā)展歷程、研究內容和重要性時，通過數據的對比分析，讓學生感受到軟件行業(yè)的快速發(fā)展。使學生在了解數據結構課程的同時，了解到中國軟件和信息技術服務業(yè)取得了長足的進步，目前正處于高速發(fā)展的成長期，激發(fā)學生職業(yè)價值認同感。第一章概論1.2基本概念和術語在集合結構的教學設計中，通過在幻燈片中播放新冠疫情期間全國志愿者馳援武漢的相關圖片，引入眾志成城的志愿者集體來類比集合結構，替換只注重知識傳授的傳統(tǒng)案例。引導學生在理解集合結構的概念和特點的同時，感受中華民族萬眾一心、同舟共濟、顧全大局、逆行而上的集體主義精神，以及個人命運與國家民族命運的血脈相連。第1章概論1.3算法和算法分析(1)在討論算法的重要性時，介紹圖靈獎獲得者DonaldE.Knuth教授的經典公式“算法+數據結構=程序”，這說明優(yōu)秀的算法能夠讓程序運行的更高效，比如金山WPS、釘釘、華為鴻蒙等（國產）軟件的更新，就是在更新算法。(2)更新算法設計例題，引入中國古代約5—6世紀成書的《張邱健算經》中的“百錢買百雞”問題，組織學生以小組為單位討論多種求解方法，并開展翻轉課堂活動，請3名學生登臺演示，分析不同求解方法的差別，最后引入李開復的話闡述算法的重要性。(1)強調中國的軟件產業(yè)肩負著通過國產化替代工程來增強關鍵領域信息安全的歷史使命，為將來可能成為行業(yè)中堅力量的學生們敲響信息安全預警，厚植愛國主義教育，強化信息安全意識。(2)使學生認識到算法設計的重要性，并了解到中國古代源遠流長的文化底蘊，增強文化自信。第2章線性表在介紹線性結構時，結合線性結構元素間1：1的特點，在幻燈片中播放十年間我國的GDP數據表。其中，GDP表的每行可以看作一條記錄（也稱