PAGE1PAGE1--PAGE2-一、課程基本信息

《數(shù)據(jù)結構》教學大綱課程中文名稱數(shù)據(jù)結構課程英文名稱DataStructure培養(yǎng)方案版本2022版學分4總學時56開課學期2理論學時46上機學時10適用專業(yè)計算機科學與技術電子信息工程□網(wǎng)絡工程軟件工程課程類別通識課程平臺專業(yè)課程平臺修讀方式必修任選限選考核方式考試考查先修課程程序設計基礎二、課程簡介類別描述課程定位數(shù)據(jù)結構是計算機科學與技術、軟件工程等專業(yè)的專業(yè)基礎課程，在整個課程體系中處于承上啟下的核心地位，作為程序設計語言后續(xù)課程的數(shù)據(jù)結構課程是對程序設計語言的重要補充和發(fā)展，同時為進一步學習操作系統(tǒng)、編譯原理、數(shù)據(jù)庫等專業(yè)課奠定堅實的基礎。主要內(nèi)容線性表、棧和隊列、多維數(shù)組、樹和二叉樹、圖等數(shù)據(jù)模型的邏輯特征、存儲結構、基本操作、經(jīng)典應用，以及基本的查找技術和排序技術。學習成果分析和評價各種數(shù)據(jù)結構的存儲方法，針對實際工程問題抽象問題的數(shù)據(jù)模型，選擇或設計存儲結構，并在此基礎上應用程序設計語言實現(xiàn)基本操作。描述和復現(xiàn)各種基本操作和經(jīng)典算法的實現(xiàn)過程，分析算法的時間和空間性能。在解決問題的算法和程序設計訓練過程中，形成基本的計算思維能力、算法設計能力、程序設計語言的運用能力。三、課程目標本課程的主要教學環(huán)節(jié)有理論教學和實驗教學，課程的總體教學目標是：掌握數(shù)據(jù)結構的基本概念、基本原理和基本方法；掌握數(shù)據(jù)的邏輯結構、存儲結構及基本操作的實現(xiàn)，能夠?qū)λ惴ㄟM行基本的時間復雜度與空間復雜度的分析；能夠運用數(shù)據(jù)結構的基本原理和方法進行問題的分析與求解，具備采用C++語言設計與實現(xiàn)算法的能力。具體教學目標如下：1．描述基本數(shù)據(jù)模型的邏輯特征，分析和評價數(shù)據(jù)模型的不同存儲方法，進行存儲結構定義；針對計算機領域的工程問題，構建數(shù)據(jù)模型、設計存儲結構、描述存儲示意圖。2．描述數(shù)據(jù)結構的基本操作、經(jīng)典算法、經(jīng)典查找技術和排序技術的執(zhí)行過程，對重要的算法進行復現(xiàn)；針對計算機領域的工程問題，進行算法設計并運用大O記號進行算法性能分析。3．針對計算機領域具有時空性能約束的復雜工程問題，應用數(shù)據(jù)結構的基本原則和方法，通過比較、選擇、優(yōu)化等過程，設計合理的存儲結構和解決方案，進行數(shù)據(jù)表示、算法描述和程序?qū)崿F(xiàn)。四、課程支撐的畢業(yè)要求指標點及權重畢業(yè)要求畢業(yè)要求指標點課程目標權重畢業(yè)要求11.4比較與綜合：能夠利用計算思維和系統(tǒng)思維，對計算機領域復雜工程問題的解決方案進行比較與綜合，并體現(xiàn)出計算機科學領域先進的技術。課程目標20.3畢業(yè)要求22.2抽象和表達：能夠運用計算機科學的有關原理和數(shù)學模型方法，正確抽象和表達（形式化描述）計算機領域復雜工程問題。課程目標10.3畢業(yè)要求33.2功能模塊：能夠根據(jù)需求，設計滿足特定需求的功能模塊或設計相應的算法，并運用相應仿真工具或高級程序設計語言實現(xiàn)。課程目標30.4五、教學方法1.問題驅(qū)動的課堂講授法。課程的總體教學目標是培養(yǎng)學生的計算思維能力和應用計算機解決問題的算法與程序設計能力，因此，將教學主線確定為計算機進行問題求解的一般過程“問題→想法→算法→程序”，在這個一般過程中通過設疑、解疑，采用互動的方式進行知識傳遞。2.基于圖示的動畫演示法。在深刻揭示知識內(nèi)涵的基礎上，并將教學意圖融入多媒體課件，將教學內(nèi)容中抽象的概念和不可見的過程，通過動畫形象地動態(tài)演示出來。3.引導思維的啟發(fā)式教學。注意引導思維，通過講思路講過程講方法，展現(xiàn)問題的求解過程，通過設疑、問疑、解疑一步步啟發(fā)學生的思維，并將啟發(fā)式教學方法貫徹到每一個教學專題。4.（ACM），以小組方式進行討論，以抽簽方式進行展示，提高學生的主動學習意識。5.全程跟蹤的混合式教學。采用互動式教學工具，課前向?qū)W生發(fā)送預習任務，課前或課中設計相關測驗完成即時考核，提高課堂教學的學習效果，課后完成作業(yè)和學習檢查。六、教學環(huán)節(jié)與教學安排1.理論環(huán)節(jié)教學安排序號教學內(nèi)容學時分配基本要求（能力）課程目標1緒論課程概述；問題求解與程序設計；數(shù)據(jù)結構的基本概念；算法的基本概念；算法分析。重點是數(shù)據(jù)結構的基本概念；數(shù)據(jù)的邏輯結構、存儲結構以及二者之間的關系；算法及算法的特性；大Ｏ記號。難點是抽象數(shù)據(jù)類型；算法的時間復雜度分析。4明確本課程的重要性，界定課程目標及學習方法；說明數(shù)據(jù)結構和算法在程序設計中的作用；描述數(shù)據(jù)結構和算法的基本概念；對基本算法進行算法分析。目標12線性表線性表的邏輯結構；線性表順序存儲結構及實現(xiàn)；線性表鏈接存儲結構及實現(xiàn)；順序表和鏈表的比較。重點是順序存儲結構和鏈接存儲結構的基本思想；順序表和單鏈表的基本算法；順序表和單鏈表基本操作的時間性能；順序表和鏈表之間的比較。難點是線性表的抽象數(shù)據(jù)類型定義；基于單鏈表算法設計；雙鏈表算法設計。6針對線性表問題可抽象邏輯結構、設計順序存儲和鏈接存儲實現(xiàn)其算法；描述和評價其他線性表鏈接存儲結構及算法實現(xiàn)，比較順序表和鏈表各自特性。應用線性結構解決計算機領域的復雜工程問題。目標1目標2目標33棧的邏輯結構定義；棧的存儲結構及實現(xiàn)；隊列的邏輯結構定義；隊列的存儲結構及實現(xiàn)。重點是棧和隊列的操作特性；棧和隊列基本操作的實現(xiàn)。難點是循環(huán)隊列的存儲方法；循環(huán)隊列隊空和隊滿的判定條件4針對具體問題選擇正確的數(shù)據(jù)結構；設計順序棧和鏈棧存儲結構及實現(xiàn)；設計循環(huán)隊列和鏈隊列存儲結構及實現(xiàn)。應用棧和隊列解決計算機領域的復雜工程問題。目標1目標2目標34特殊矩陣和稀疏矩陣的壓縮存儲方法。重點是數(shù)組的尋址方法；特殊矩陣的壓縮存儲和尋址方法。難點是稀疏矩陣的壓縮存儲2解釋數(shù)組的邏輯結構和存儲結構，以及尋址方法；解釋特殊矩陣和稀疏矩陣的壓縮存儲方法，能夠給出尋址的計算方法。目標1目標25樹和二叉樹樹的邏輯結構；樹的存儲結構；二叉樹的邏輯結構；二叉樹的存儲結構及實現(xiàn)；樹、森林和二叉樹之間的轉(zhuǎn)換；哈夫曼樹及哈夫曼編碼。重點是二叉樹的性質(zhì)；二叉樹和樹的存儲表示；二叉樹的遍歷及算法實現(xiàn)；樹與二叉樹的轉(zhuǎn)換關系；哈夫曼樹。難點是二叉樹的層序遍歷算法；二叉樹的建立算法；哈夫曼算法8抽象樹的邏輯結構、設計存儲結構；應用樹和二叉樹的遍歷解決問題；描述二叉樹的定義和基本性質(zhì)；設計并實現(xiàn)二叉鏈表及其遍歷遞歸算法；描述二叉樹的其他存儲結構和非遞歸算法；應用二叉樹層序遍歷及建立算法解決實際問題；完成樹、森林和二叉樹之間的轉(zhuǎn)換；描述哈夫曼算法的執(zhí)行過程；應用樹結構解決計算機領域的復雜工程問題。目標1目標2目標36圖圖的邏輯結構；圖的存儲結構及實現(xiàn)；最小生成樹；最短路徑；有向無環(huán)圖。重點是圖的基本術語；圖的存儲表示；圖的遍歷；圖的經(jīng)典應用。難點是圖的遍歷算法；Prim算法；Kruskal算法；Dijkstra算法；Floyd算法；拓撲排序算法；關鍵路徑算法8識記圖的定義及基本術語；描述圖的鄰接矩陣和鄰接表存儲方法及實現(xiàn)算法；描述PrimDijkstraKruskalFloyd算AOVAOE義及性質(zhì)，描述拓撲排序算法和關鍵路徑算法的執(zhí)行過程；應用圖結構解決計算機領域目標1目標2目標37查找的基本概念及算法性能；線性表的查找技術；樹表的查找技術；散列表的查找技術；各種查找方法的比較。重點是折半查找算法及性能分析；二叉查找樹的構造及查找；平衡二叉樹的調(diào)整；散列表的構造和查找；B樹的定義；字符串模式匹配。難點是二叉查找樹的刪除操作；平衡二叉樹的調(diào)整；B樹的插入和刪除操作8描述順序查找、折半查找、二叉查找樹的查找過程和性能分析；完成二叉查找樹的刪除、平衡二叉樹的調(diào)整、B樹的查找等具體過程；解釋B樹的定義、插入和刪除操作原理；設計并構造散列表并進行散列查找的性能分析；針對具體問題實例描述BF算法和KMP算法的執(zhí)行過程；比較各種查找方法特性，在應用中選擇合適的查找方法。目標2目標38排序的基本概念及算法性能；插入排序；交換排序；選擇排序；歸并排序；各種排序算法的比較。重點是各種排序算法的基本思想；各種排序算法的執(zhí)行過程；各種排序算法及時間復雜度分析；各種排序算法之間的比較。難點是快速排序、堆排序、歸并排序等算法及時間復雜度分析6解釋排序的基本概念和排序算法性能分析方法；復現(xiàn)直接插入排序、起泡排序、快速排序的一次劃分、簡單選擇排序的執(zhí)行過程；復現(xiàn)快速排序、堆排序、二路歸并排序的非遞歸實現(xiàn)、二路歸并排序的遞歸實現(xiàn)；描述希爾排序、篩選法調(diào)整堆的原理和執(zhí)行過程；比較各種排序算法特性，在應用中選擇合適的排序方法。目標2目標32.實踐環(huán)節(jié)教學安排序號實驗內(nèi)容學時分配基本要求（能力）課程目標1線性表及其應用：實際問題中線性表的插入和刪除（順序表、鏈表），刪除重復數(shù)據(jù)、士兵隊列訓練等問題2針對線性表實際問題抽象數(shù)據(jù)模型、設計存儲結構、進行算法設計與程序?qū)崿F(xiàn)，進行實驗總結，撰寫實驗報告。目標32棧和隊列及其應用：運用棧來模擬程序的遞歸過程、漢諾塔問題、進制轉(zhuǎn)換等問題2針對棧、隊列實際問題抽象數(shù)據(jù)模型、設計存儲結構、進行算法設計與程序?qū)崿F(xiàn)，進行實驗總結，并撰寫實驗報告。目標33樹及其應用：建立一棵二叉樹、二叉樹的遍歷（層次、前序、中序、后序）、FindthemandCatchthem等問題2針對樹實際問題抽象數(shù)據(jù)模型、設計存儲結構、進行算法設計與程序?qū)崿F(xiàn)，進行實驗總結，并撰寫實驗報告。目標34圖及其應用：建立圖的鄰接矩陣和鄰接表，針對實際問題求最小生成樹、最短路徑2針對圖實際問題抽象數(shù)據(jù)模型、設計存儲結構、進行算法設計與程序?qū)崿F(xiàn)，進行實驗總結，并撰寫實驗報告。目標35查找、排序算法的比較：給出具有不同特性的數(shù)據(jù)，采用各種查找方法對給定關鍵碼進行查找，比較查找性能；采用各種排序方法對其進行排序，比較排序性能2針對查找、排序?qū)嶋H問題抽象數(shù)據(jù)模型、設計存儲結構、進行算法設計與程序?qū)崿F(xiàn)，進行實驗總結，并撰寫實驗報告。目標3七、教材、參考書目和教學資源教材：[1]C++實現(xiàn)（4）.北京：清華大學出版社，2025.[2]數(shù)據(jù)結構學習輔導和實驗指導——從概念到實現(xiàn).王紅梅等編著.清華大學出版社，2024.參考書目：[1]ThomasH.Corman等.殷建平等譯.算法導論（第3版）.機械工業(yè)出版社.2013.[2]MarkA.Weiss.數(shù)據(jù)結構與算法分析：C++語言描述（第4版）.機械工業(yè)出版社.2016.[3]Bentley.黃倩譯.編程珠璣（2）.人民郵電出版社.2015.[4](C2010.[5]數(shù)據(jù)結構(C++語言版)第3版.鄧俊輝編著.北京：清華大學出版社.2013.教學資源：MOOC課程耿國華西北工業(yè)大學：/course/NWU-298002陳越浙江大學：https:///course/zju0901-93001/八、考核方案1.課程目標達成途徑課程目標達成途徑考核內(nèi)容考核方式課程目標1課堂講授：驅(qū)動式課堂教學，以問題為驅(qū)動，引導學生從問題出發(fā)，進行邏輯模型構建；完成數(shù)據(jù)表示，根據(jù)操作約束進行存儲結構選擇或重組。課外作業(yè)：通過完成布置的習題，鞏固數(shù)據(jù)結構邏輯結構、存儲結構、基本操作的原理及運用，形成基本的數(shù)據(jù)結構和算法的應用能力。平時測驗：針對數(shù)據(jù)結構邏輯結構、存儲結構、基本操作等相關知識設計選擇題，以隨堂或課后發(fā)放的形式，檢查課堂掌握情況，并促進和進行應用訓練。期中考試：通過閉卷考試，階段性檢驗具體問題下邏輯模型構建、存儲結構選擇、基本操作實現(xiàn)應用能力。期末考試：通過閉卷考試，全面檢驗具體問題下邏輯模型構建、存儲結構選擇、基本操作實現(xiàn)應用能力。1.針對給出問題，進行表、樹、圖等數(shù)據(jù)結構邏輯模型的構建；2.針對給出問題，在問題條件約束下選擇與優(yōu)化存儲結構。平時測驗，課外作業(yè)，期中考試，期末考試。課程目標2課堂講授：驅(qū)動式課堂教學，以問題為驅(qū)動，引導學生從問題出發(fā)，形成“想法”，基于存儲結構完成由“想法”到“算法”的實踐過程，并進行算法復雜度分析。課外作業(yè)：通過完成布置的習題，鞏固數(shù)據(jù)結構經(jīng)典算法及常用的數(shù)據(jù)處理技術經(jīng)典算法，形成基本復現(xiàn)和應用能力。平時測驗：針對數(shù)據(jù)結構經(jīng)典算法及常用的數(shù)據(jù)處理技術經(jīng)針對給出問題，選擇并應用數(shù)據(jù)結構經(jīng)典算法及常用的數(shù)據(jù)處理針對給出問題，選擇滿足時間、空間性能約束的典算法，并對平時測驗，課外作業(yè)，期中考試，期末考試。典算法知識選取選擇題型，以隨堂或課后發(fā)放的形式，檢查課堂掌握情況，并促進和進行應用訓練。期中考試：通過閉卷考試，階段性檢驗時間性能約束、空間性能約束的復雜工程問題中，算法設計能力；檢驗進行時間、空間漸近分析能力。期末考試：通過閉卷考試，全面檢驗時間性能約束、空間性能約束的復雜工程問題中，選擇經(jīng)典算法的設計思想，進行算法復現(xiàn)及重組的能力；檢驗進行時間、空間漸近分析能力。求解過程進行時間、空間復雜度分析；課程目標3實驗教學：針對基本數(shù)據(jù)結構及數(shù)據(jù)處理技術的問題，采用“問題?想法?算法?程序”問題求解過程及一般方法，開展主題實驗，形成初步計算思維能力、運用程序設計語言解決實際問題的能力。期中考試：通過閉卷考試，階段性檢驗面對工程問題，采用“問題?想法?算法?程序”問題求解方法進行問題求解能力；考察算法設計及運用程序設計語言解決實際問題的能力。期末考試：通過閉卷考試，全面檢驗面對復雜工程問題，采用“問題?想法?算法?程序”問題求解方法進行問題求解能力；考察算法設計及運用程序設計語言解決實際問題的能力。針對工程實踐具體問題，應用“問題?想法?算法?程序”的問題求解過程及一般方法，進行邏輯模型設計、數(shù)據(jù)結構設計實現(xiàn)、算法設計與程序設計，完成問題求解。課外作業(yè)，實驗教學，期中考試，期末考試。2.考核環(huán)節(jié)與成績比例課程目標作業(yè)（10%）平時測驗（30%）實驗（10%）期末考試（60%）權重和課程目標10.150.250.51課程目標20.150.250.51課程目標30.10.70.21九、考核標準依據(jù)1.作業(yè)考核與評價標準課程目標評價標準100~90分89~80分79~70分69~60分59~20分19~0分針對給出問題可分析針對給出問題可分析得出正確邏輯模型；得出正確邏輯模型；針對給出問題可分析針對給出問題可分析目標1針對邏輯模型可對所針對邏輯模型可對所學存儲結構進行比得出正確邏輯模型；可針對邏輯模型選擇得出正確邏輯模型；可針對邏輯模型給出針對給出問題可分析得出基本邏輯模型。不能進行基本邏輯模型分析、構建。較、組合、優(yōu)化，設較，結合比較結果選合適的存儲結構。一種基本存儲結構。計出合適存儲結構擇合適的存儲結構針對給出問題可選擇針對給出問題可選擇合適的經(jīng)典算法或設計滿足時間性能、空間性能要求的算法進行“問題”解決；可對算法進行時間、空間性能分析。針對給出問題可選擇經(jīng)典算法或設計基本算法解決“問題”。針對給出問題可給出解決“問題”基本思路。針對給出問題不能給出解決“問題”基本思路。合適的經(jīng)典算法或設針對給出問題可選擇計時間性能、空間性合適的經(jīng)典算法或設目標2“問題”解決；可對計基本算法解決“問題”；可對算法進行算法進行時間、空間基本的時間、空間性性能分析，并據(jù)分析能分析。結果進行算法改進注：每次作業(yè)均以百分計，作業(yè)成績70分達到課程目標。2.平時測驗考核與評價標準課程目標評價標準100~90分89~80分79~70分69~60分59~20分19~0分針對考核問題，在時針對考核問題，在時針對考核問題，在時間限定內(nèi)，不能進行基本邏輯模型分析、構建。間限定內(nèi)，可分析得間限定內(nèi)，可分析得針對考核問題，在時針對考核問題，在時出正確邏輯模型；針出正確邏輯模型；針間限定內(nèi)，可分析得間限定內(nèi)，可分析得針對考核問題，在時目標1對邏輯模型可對所學對邏輯模型可對所學出正確邏輯模型；可出正確邏輯模型；可間限定內(nèi)，可分析得存儲結構進行比較、存儲結構進行比較，針對邏輯模型選擇合針對邏輯模型給出一出基本邏輯模型。組合、優(yōu)化，設計出結合比較結果選擇合適的存儲結構。種基本存儲結構。合適存儲結構適的存儲結構目標2針對考核問題，在時間限定內(nèi)，可選擇合適的經(jīng)典算法或設計時間性能、空間性能較優(yōu)的算法進行“問題”解決；可對算法進行時間、空間性能分析，并據(jù)分析結果進行算法改進針對考核問題，在時間限定內(nèi)，可選擇合適的經(jīng)典算法或設計滿足時間性能、空間性能要求的算法進行“問題”解決；可對算法進行時間、空間性能分析。針對考核問題，在時間限定內(nèi)，可選擇合適的經(jīng)典算法或設計基本算法解決“問題”；可對算法進行基本的時間、空間性能分析。針對考核問題，在時間限定內(nèi)，可選擇經(jīng)典算法或設計基本算法解決“問題”。針對考核問題，在時間限定內(nèi)，可給出解決“問題”基本思路。針對考核問題，在時間限定內(nèi)，不能給出解決“問題”基本思路。注：每次平時測驗均以百分計，小測成績70分達到課程目標3．實驗考核與評價標準課程目標評價標準100~90分89~80分79~70分69~60分59~0分能夠?qū)o定的實際問題能夠?qū)o定的實際問題能夠?qū)o定的實際問題能夠?qū)o定的實際問題部分完成實驗任務，實抽象正確的數(shù)據(jù)模型；抽象正確的數(shù)據(jù)模型；抽象數(shù)據(jù)模型；可實現(xiàn)驗報告撰寫一般。可以分析、選擇、設可以分析、選擇、設計析、選擇合適的存儲結一種存儲結構；算法設計、優(yōu)化存儲結構；針合適的存儲結構；可針構；算法設計合理，滿計基本合理，基本滿足對問題設計滿足時間、足題目約束條件；算法題目約束條件；算法實目標3間、空間約束條件的算空間約束條件的算法；實現(xiàn)正確，實驗報告撰現(xiàn)基本正確，實驗報告法基礎上可進行進一步算法實現(xiàn)正確，實驗報寫較規(guī)范；能夠?qū)嶒炞珜懟緷M足規(guī)范。算法優(yōu)化；算法實現(xiàn)正告撰寫規(guī)范；能夠?qū)嵔Y果進行一定的分析。驗結果進行分析并進行范；能夠?qū)嶒灲Y果進算法改進。行分析。注：實驗成績以百分計，成績70分達到課程目標。4．期末考試成績考核與評價標準課程目標評價標準100~90分89~80分79~70分69~60分59~20分19~0分目標1針對考試命題，在時間限定內(nèi)，可分析得出正確邏輯模型；針對邏輯模型可對所學存儲結構進行比較、組合、優(yōu)化，設計出合適存儲結構；步驟清晰、圖表規(guī)范。針對考試命題，在時間限定內(nèi)，可分析得出正確邏輯模型；針對邏輯模型可對所學存儲結構進行比較，結合比較結果選擇合適的存儲結構；步驟清晰、圖表較規(guī)范。針對考試命題，在時間限定內(nèi)，可分析得出正確邏輯模型；可針對邏輯模型選擇合適的存儲結構；具