數(shù)據(jù)結(jié)構(gòu)課程規(guī)范案例一至四

1、CERACU/T XXXXX XXXX附 錄 A（資料性附錄）數(shù)據(jù)結(jié)構(gòu)課程規(guī)范案例一A.1 數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)知識點對照表表 A.1-1基礎(chǔ)知識點對照表標識符名稱對照課程能力要求DS_O1緒論第 1章、第 2章掌握DS_O1_01數(shù)據(jù)結(jié)構(gòu)的基本概念第1.1 節(jié)理解DS_O1_02抽象數(shù)據(jù)類型第1.2 節(jié)掌握DS_01_03算法第 2章掌握DS_02線性表第 3章掌握 +應(yīng)用DS_02_01線性表的類型定義第3.1 節(jié)理解DS_02_02線性表的順序表示和實現(xiàn)第3.2 節(jié)掌握DS_02_03線性表的鏈式表示和實現(xiàn)第3.2 節(jié)掌握DS_02_04線性表應(yīng)用實例第3.3 節(jié)應(yīng)用DS_03棧和隊列第 4章掌

2、握 +應(yīng)用DS_03_01棧第4.1節(jié)掌握DS_03_01_01棧的基本概念第4.1節(jié)理解DS_03_01_02棧的實現(xiàn)第4.1節(jié)掌握DS_03_01_03棧的應(yīng)用第4.1節(jié)應(yīng)用DS_03_02隊列第4.2節(jié)掌握DS_03_02_01隊列的基本概念第4.2節(jié)理解DS_03_02_02循環(huán)隊列第4.2節(jié)掌握DS_03_02_03鏈隊列第4.2節(jié)掌握DS_03_02_04隊列的應(yīng)用第4.2節(jié)應(yīng)用DS_04數(shù)組第4.3節(jié)掌握DS_04_01數(shù)組的定義和順序存儲第4.3節(jié)掌握DS_04_02特殊矩陣的壓縮存儲第4.3節(jié)掌握DS_04_03稀疏矩陣的壓縮存儲第4.3節(jié)掌握DS_05樹與二叉樹第 5章掌握

3、 +應(yīng)用DS_05_01二叉樹第5.2 節(jié)掌握DS_05_01_01二叉樹的定義及其主要性質(zhì)第5.2 節(jié)理解DS_05_01_02二叉樹的存儲結(jié)構(gòu)第5.2 節(jié)掌握DS_05_01_03二叉樹的遍歷第5.2 節(jié)掌握DS_05_01_04線索二叉樹第5.4 節(jié)掌握學(xué)時要求12講授 4實踐 6講授 5實踐 6講授 2講授 8實踐 811CERACU/T XXXXX XXXXDS_05_02二叉樹的應(yīng)用第5.4 節(jié)應(yīng)用DS_05_02_01哈夫曼樹及應(yīng)用第5.4 節(jié)應(yīng)用DS_05_02_02堆及應(yīng)用第8.4 節(jié)掌握DS_05_03樹與森林第 5.1 節(jié)、第 5.3 節(jié)理解DS_05_03_01樹的存儲

4、結(jié)構(gòu)第5.1 節(jié)掌握DS_05_03_02樹、森林與二叉樹的轉(zhuǎn)換和遍歷第5.3 節(jié)掌握DS_05_03_03樹的應(yīng)用第5.4 節(jié)應(yīng)用DS_06圖第 6章掌握 +應(yīng)用DS_06_01圖的基本概念第6.1 節(jié)理解DS_06_02圖的存儲第6.1 節(jié)掌握DS_06_02_01鄰接矩陣第6.1 節(jié)掌握DS_06_02_02鄰接表第6.1 節(jié)掌握DS_06_02_03鄰接多重表第6.1 節(jié)掌握DS_06_02_04十字鏈表第6.1 節(jié)掌握DS_06_03圖的遍歷第6.2 節(jié)掌握DS_06_04圖的基本應(yīng)用第 6.3 節(jié)、第 6.4 節(jié)、應(yīng)用第6.5 節(jié)DS_06_04_01最小生成樹第6.3 節(jié)掌握DS

5、_06_04_02最短路徑第6.4 節(jié)應(yīng)用DS_06_04_03拓撲排序第6.5 節(jié)掌握DS_06_04_04關(guān)鍵路徑第6.5 節(jié)應(yīng)用DS_07查找第 7章掌握 +應(yīng)用DS_07_01查找的基本概念第7.1 節(jié)理解DS_07_02順序表的查找第7.2 節(jié)掌握DS_07_03有序表的查找第7.2 節(jié)掌握DS_07_04索引查找第7.2 節(jié)掌握DS_07_05串的模式匹配DS_07_06二叉搜索樹和平衡二叉樹第7.3 節(jié)掌握DS_07_06_01二叉搜索樹第7.3 節(jié)掌握DS_07_06_02平衡二叉樹第7.3 節(jié)掌握DS_07_07B樹和 B+樹第7.3 節(jié)應(yīng)用DS_07_08紅黑樹第7.3 節(jié)

6、掌握DS_07_09Tire 樹第7.3 節(jié)掌握DS_07_10哈希表第7.4 節(jié)應(yīng)用DS_07_10_01哈希函數(shù)構(gòu)造第7.4 節(jié)應(yīng)用DS_07_10_02處理沖突第7.4 節(jié)應(yīng)用DS_07_10_03哈希查找第7.4 節(jié)應(yīng)用DS_08內(nèi)部排序第 8章掌握 +應(yīng)用DS_08_01排序基本概念第8.1 節(jié)掌握DS_08_02插入排序第8.2 節(jié)掌握DS_08_03交換排序第8.3 節(jié)應(yīng)用講授 10實踐 8講授 8實踐 8講授 8實踐 612CERACU/T XXXXX XXXXDS_08_04選擇排序第8.4 節(jié)應(yīng)用DS_08_05二路歸并排序第8.5 節(jié)應(yīng)用DS_08_06基數(shù)排序第8.6

7、節(jié)應(yīng)用A.2數(shù)據(jù)結(jié)構(gòu)課程教學(xué)內(nèi)容教學(xué)學(xué)時理論教學(xué)48 學(xué)時，實踐教學(xué)42 學(xué)時課程教材數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計， Robert L.Kruse & Alexander J.Ryba，高等教育出版社；數(shù)據(jù)結(jié)構(gòu)、算法與應(yīng)用 C+語言描述（第二版） ，Sartaj Sahni 著，王立柱，劉志紅等譯 ，機械工業(yè)出版社序項目內(nèi)容號1基本信息課時1教學(xué)方式講授第1章緒論教學(xué)內(nèi)容第 1.1 節(jié) 數(shù)據(jù)結(jié)構(gòu)簡介第 1.2 節(jié) 有關(guān)的預(yù)備知識1. 了解本課程的教學(xué)目標、內(nèi)容及課程地位教學(xué)要求2. 熟悉數(shù)據(jù)結(jié)構(gòu)研究的內(nèi)容3. 掌握數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)對象、數(shù)據(jù)類型的基本概念數(shù)據(jù)結(jié)構(gòu)和算法之間的關(guān)系、算法設(shè)計的要

8、求以及如何設(shè)計一個好的算法。重點對于抽象數(shù)據(jù)結(jié)構(gòu)的說明及應(yīng)用介紹。難點2基本信息課時2教學(xué)方式講授第 2 章 算法的基本概念與算法分析第 2.1節(jié) 算法的基本概念教學(xué)內(nèi)容第 2.2節(jié) 算法的評估第 2.3節(jié) 算法的復(fù)雜性度量1.掌握算法性能分析的概念和方法2.熟練掌握算法空間復(fù)雜性的組成和分析方法教學(xué)要求3.熟練掌握算法時間復(fù)雜性的組成和分析方法4.熟練掌握漸進符號描述算法的復(fù)雜性13CERACU/T XXXXX XXXX如何使用分析和實驗的方法對算法的時間和空間復(fù)雜性進行分析；漸進符號的定重點義以及使用漸進符號描述算法的復(fù)雜性。難點實例特征的確定、基于實例特征對算法的時間、空間復(fù)雜度進行分或

9、測試；根據(jù)漸進符號的定義證明算法的漸進復(fù)雜性。3基本信息課時4教學(xué)方式講授第 3章 線性表第 3.1節(jié) 線性表的定義和基本運算教學(xué)內(nèi)容第 3.2節(jié) 線性表的實現(xiàn)第 3.3 節(jié) 線性表的應(yīng)用1. 熟悉線性表的定義2. 掌握線性表的公式化描述、鏈表描述和間接尋址描述教學(xué)要求3. 能夠選擇適當?shù)木€性表描述方式設(shè)計算法并解決實際問題線性表的公式化描述；鏈表描述的結(jié)構(gòu)及操作；循環(huán)鏈表、雙向鏈表的結(jié)構(gòu)、操重點作及應(yīng)用。難點線性表的不同描述方式的異同、復(fù)雜性分析以及特殊鏈表的應(yīng)用技巧。4基本信息課時7教學(xué)方式講授第 4 章 棧、隊列和數(shù)組第 4.1節(jié) 棧的定義、描述及應(yīng)用教學(xué)內(nèi)容第 4.2節(jié) 隊列的定義、描

10、述及應(yīng)用第 4.3節(jié) 數(shù)組、矩陣的抽象數(shù)據(jù)類型、存儲及應(yīng)用1.掌握棧、隊列的概念、性質(zhì)及應(yīng)用教學(xué)要求2.能夠針對不同的現(xiàn)實問題使用棧或隊列解決問題3.掌握數(shù)組、矩陣的抽象數(shù)據(jù)類型、操作及物理存儲方式棧的公式化描述和鏈表描述；隊列的公式描述和鏈表描述；循環(huán)隊列的性質(zhì)重點和應(yīng)用；數(shù)組和矩陣的存儲；特殊數(shù)組、矩陣及應(yīng)用。應(yīng)用棧進行遞歸與非遞歸的轉(zhuǎn)換；循環(huán)隊列的操作；特殊矩陣的壓縮。難點14CERACU/T XXXXX XXXX5基本信息課時8教學(xué)方式講授第 5章 樹型結(jié)構(gòu)第 5.1 節(jié) 樹的定義和基本概念教學(xué)內(nèi)容第 5.2 節(jié) 二叉樹的定義、性質(zhì)及遍歷第 5.3 節(jié) 樹、森林與二叉樹的關(guān)系第 5.4

11、 節(jié) 樹型結(jié)構(gòu)的應(yīng)用1. 熟練掌握樹、二叉樹的概念、性質(zhì)2. 熟練掌握樹、二叉樹和森林的遍歷方法及應(yīng)用教學(xué)要求3. 掌握樹、森林和二叉樹的關(guān)系4. 能夠應(yīng)用樹型結(jié)構(gòu)的特性解決實際問題二叉樹的性質(zhì)；二叉樹的操作；二叉樹遍歷及其應(yīng)用；樹、森林和二叉樹的相互重點轉(zhuǎn)換。難點應(yīng)用二叉樹的遍歷求解問題，二叉樹的非遞歸遍歷。6基本信息課時10教學(xué)方式講授第6章圖第 6.1節(jié) 圖的基本概念及存儲結(jié)構(gòu)教學(xué)內(nèi)容第 6.2節(jié) 圖的遍歷及求圖的連通分量第 6.3 節(jié) 生成樹和最?。ù鷥r）生成樹及應(yīng)用第 6.4 節(jié) 最短路徑及應(yīng)用第 6.5 節(jié) 有向無環(huán)圖及其應(yīng)用1. 熟練掌握圖的基本概念、性質(zhì)及存儲結(jié)構(gòu)2. 熟練掌握

12、圖的遍歷方法及其應(yīng)用教學(xué)要求3. 掌握最小生成樹、最短路徑的求解4. 掌握有向無環(huán)圖的應(yīng)用圖的概念、性質(zhì)及存儲；深度優(yōu)先遍歷和寬度優(yōu)先遍歷的方法及其應(yīng)用；最小生重點成樹、單源最短路徑的求解；有向無環(huán)圖的應(yīng)用。難點連通分量的求解、單源最短路徑的求解、圖中每一對頂點的最短路徑的求解、關(guān)鍵路徑的求解7基本信息課時8教學(xué)方式講授15CERACU/T XXXXX XXXX第7章查找第 7.1 節(jié) 查找的基本概念教學(xué)內(nèi)容第 7.2 節(jié) 順序表的查找第 7.3 節(jié) 樹表的查找第 7.4 節(jié) 哈希表及其查找1. 了解查找相關(guān)的術(shù)語和概念2. 熟練掌握不同查找算法的思想、方法教學(xué)要求3. 掌握不同算法的復(fù)雜性分

13、析順序查找、折半查找以及索引順序表的查找思想和方法；二叉排序樹、平衡二叉重點樹、 B- 樹的查找思想和方法；哈希表的查找思想及方法。平衡二叉樹平衡的調(diào)整；B 樹的插入和刪除；哈希表處理沖突的方法。難點8基本信息課時8教學(xué)方式講授第 8章 內(nèi)部排序第 8.1 節(jié) 排序的一般概念教學(xué)內(nèi)容第 8.2 節(jié) 插入排序第 8.3 節(jié) 交換排序第 8.4 節(jié) 選擇排序第 8.5 節(jié) 歸并排序第 8.6 節(jié) 分配排序和基數(shù)排序第 8.7 節(jié) 有關(guān)內(nèi)部排序算法的比較1. 了解內(nèi)部排序相關(guān)的術(shù)語和概念2. 熟練掌握不同內(nèi)部排序算法的思想、方法教學(xué)要求3. 掌握不同排序算法的穩(wěn)定性、復(fù)雜性分析不同排序算法的思想、方

14、法以及復(fù)雜性的分析；排序方法的異同、排序效率的比重點較；排序方法的和數(shù)據(jù)結(jié)構(gòu)的關(guān)聯(lián)。在熟練掌握各種內(nèi)部排序的基礎(chǔ)上，對其進行優(yōu)化以及針對特定問題的條件約束難點選擇排序算法解決問題。16CERACU/T XXXXX XXXX附錄 B（資料性附錄）數(shù)據(jù)結(jié)構(gòu)課程規(guī)范案例二(數(shù)據(jù)結(jié)構(gòu)課程教學(xué)大綱)B.1基本信息課程編碼： JS100481課程名稱：數(shù)據(jù)結(jié)構(gòu)英文名稱： Data Structure課程類型：必修課先修課程：面向過程程序設(shè)計、離散數(shù)學(xué)總 學(xué) 時： 80理論學(xué)時： 56實踐（上機）學(xué)時：24數(shù)據(jù)結(jié)構(gòu)是計算機的核心課程。它是操作系統(tǒng)、數(shù)據(jù)庫、編譯原理等軟件專業(yè)基礎(chǔ)課和專業(yè)課的重要基礎(chǔ)； 它還是

15、進行程序設(shè)計， 尤其是進行高水平的應(yīng)用程序和系統(tǒng)程序設(shè)計必不可少的基礎(chǔ)。通過本課程的學(xué)習(xí)，學(xué)生能深入、透徹地理解常用數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)的基本概念、特點，以及有關(guān)算法，掌握各種常用的數(shù)據(jù)結(jié)構(gòu)，提高數(shù)據(jù)抽象和程序設(shè)計能力，初步掌握算法的時間復(fù)雜性與空間復(fù)雜性的分析方法，能夠從問題出發(fā)設(shè)計面向數(shù)據(jù)結(jié)構(gòu)的求解算法，為后續(xù)課程如操作系統(tǒng)、編譯原理、數(shù)據(jù)庫系統(tǒng)等后續(xù)專業(yè)課程學(xué)習(xí)打下基礎(chǔ)。使得學(xué)生在后續(xù)的科研和工程項目中，面對大量數(shù)據(jù)的存儲、查詢的需求中，能夠選擇、組合、設(shè)計恰當?shù)臄?shù)據(jù)結(jié)構(gòu)和算法，在數(shù)據(jù)存儲密度、查詢效率、邏輯關(guān)系表達、可維護性及擴展性方面，較好地滿足所面對專業(yè)領(lǐng)域的需求，培養(yǎng)學(xué)生

16、對各類數(shù)據(jù)結(jié)構(gòu)和相關(guān)算法的分析和設(shè)計的能力，解決復(fù)雜工程問題的實踐能力。B.2本課程與其它課程的聯(lián)系數(shù)據(jù)結(jié)構(gòu)作為理論和實踐結(jié)合的課程，學(xué)習(xí)此課前應(yīng)具備面向過程程序設(shè)計、離散數(shù)學(xué)等方面的知識。面向過程程序設(shè)計為本課程提供實踐工具，離散數(shù)學(xué)為本課程提供理論基礎(chǔ)。本課程也是操作系統(tǒng)、數(shù)據(jù)庫、編譯原理等軟件專業(yè)基礎(chǔ)課和專業(yè)課的重要基礎(chǔ)；為這些后續(xù)課程分析問題時提供規(guī)范的思路，為解決問題提供好的結(jié)構(gòu)和算法。同時它還為進行程序設(shè)計，尤其是進行高水平的應(yīng)用程序和系統(tǒng)程序設(shè)計打下必不可少的堅實的基礎(chǔ)。B.3本課程與畢業(yè)要求的支撐關(guān)系本課程支撐的畢業(yè)要求指標點包括四點； 通過本課程的理論學(xué)習(xí)和實驗訓(xùn)練， 使學(xué)生

17、具備以下知識和能力分為四層。課程目標與畢業(yè)要求指標點的對應(yīng)關(guān)系如下：課程目標畢業(yè)要求指標點目標 1：掌握常用數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)、物指標點 2.1：能夠運用數(shù)學(xué)、 自然科學(xué)和工程科學(xué)的理結(jié)構(gòu)的策略和特點，能針對特定問題選基本原理，識別和判斷復(fù)雜軟件工程問題中的關(guān)鍵17CERACU/T XXXXX XXXX擇合適的數(shù)據(jù)結(jié)構(gòu)進行抽象定義和表達。環(huán)節(jié)和核心問題，并對問題進行正確定義和表述。目標 2：能夠?qū)μ囟☉?yīng)用問題進行數(shù)據(jù)抽象指標點 2.2：能針對復(fù)雜軟件工程問題中的關(guān)鍵環(huán)節(jié)建模和分析，形成合理的數(shù)據(jù)存儲組織方和核心問題，通過查閱、研究文獻資料，結(jié)合軟件案。工程專業(yè)及其他相關(guān)知識，形成備選的解決方案

18、。目標 3：針對數(shù)據(jù)存儲組織方案，能設(shè)計編指標點 4.1：能夠基于科學(xué)原理，通過文獻檢索或其寫出相應(yīng)算法，并對算法的時間復(fù)雜度和他相關(guān)方法，調(diào)研和分析復(fù)雜軟件工程問題的解決空間復(fù)雜度進行評價。方案，選擇合適的研究路線并設(shè)計出實驗方案。目標 4：能夠針對具體問題查閱資料、進行指標點 12.1：能認識到自主學(xué)習(xí)和終身學(xué)習(xí)的必要探索，并自主分析、設(shè)計和實現(xiàn)，能對算性，具有自主學(xué)習(xí)和終身學(xué)習(xí)的意識和基礎(chǔ)。法策略進行優(yōu)化。B.4課程教學(xué)內(nèi)容及要求第 1章引論（ 4學(xué)時）1. 教學(xué)內(nèi)容與 “計算機核心課程規(guī)范 ”知識點標識符對照關(guān)系：理論教學(xué)（ 4 學(xué)時）：（1）數(shù)據(jù)結(jié)構(gòu)的概念；DS_01_01（2）抽象

19、數(shù)據(jù)類型的定義與表示；DS_01_02（3）數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)等內(nèi)容；（4）算法的概念、評價標準、描述方法、性能分析。DS_01_032. 基本要求：（ 1）理解數(shù)據(jù)結(jié)構(gòu)、邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和抽象數(shù)據(jù)類型的基本概念；（ 2）理解數(shù)據(jù)結(jié)構(gòu)的發(fā)展和地位；（ 3）理解各種算法描述方法和算法設(shè)計的基本要求；（ 4）理解算法的評價標準和算法效率的度量方法，掌握算法時間復(fù)雜度和空間復(fù)雜度的評價方法。3. 重點及難點：重點： 邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)的區(qū)別，時間復(fù)雜度的分析和計算方法。難點： 時間復(fù)雜度的分析和計算方法。4. 教學(xué)模式： 授課、討論。5. 作業(yè)及課外學(xué)習(xí)要求（1）以數(shù)據(jù)結(jié)構(gòu)基本概念的知識

20、性作業(yè)和算法時間復(fù)雜度的分析性作業(yè)，對第1 章的內(nèi)容進行總結(jié)回顧，掌握基本概念和算法復(fù)雜度評價方法。（2）課前自主學(xué)習(xí)在線平臺上數(shù)據(jù)結(jié)構(gòu)基本概念和時間復(fù)雜度分析的相關(guān)視頻，課后完成在18CERACU/T XXXXX XXXX線平臺的本章練習(xí)和單元作業(yè)。第 2 章 線性表（ 10 學(xué)時）1. 教學(xué)內(nèi)容與 “計算機核心課程規(guī)范 ”知識點標識符對照關(guān)系：理論教學(xué)（ 8 學(xué)時）：（1）線性表的概念及運算；DS_02_01（2）線性表的順序存儲 順序表；DS_02_02（3）線性表的鏈式存儲 鏈表；DS_02_03（4）順序表和鏈表的比較。實驗教學(xué)（ 2 學(xué)時）：（1）單鏈表和順序表的簡單應(yīng)用 約瑟夫環(huán)

21、等；DS_02_03（2）單鏈表的應(yīng)用 一元稀疏多項式的存儲和加減運算等。DS_02_042. 基本要求：（ 1）理解線性表的概念、定義、邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)；（ 2）掌握線性表的順序存儲結(jié)構(gòu)及其各種基本運算，能根據(jù)實際問題運用順序表進行分析和設(shè)計，并分析算法性能；（ 3）掌握單鏈表、循環(huán)鏈表、雙向鏈表等鏈式存儲結(jié)構(gòu)及其各種基本運算；能根據(jù)特定問題選擇具體鏈式存儲結(jié)構(gòu)，并根據(jù)需求進行分析和設(shè)計；（ 4）理解約瑟夫環(huán)和稀疏多項式等問題的存儲結(jié)構(gòu)，編寫出相應(yīng)算法，并對其進行算法性能分析。3. 重點及難點：重點： 線性表的特征；順序表、單鏈表、循環(huán)鏈表、雙向鏈表的的存儲結(jié)構(gòu)及其各種基本運算。難點： 順

22、序表和鏈表這兩種存儲表示方法的綜合比較，靜態(tài)鏈表的存儲表示方法。4. 教學(xué)模式： 授課、討論、實驗5. 作業(yè)及課外學(xué)習(xí)要求（1）以順序表和鏈表特點和基本操作的知識性作業(yè)，對第2 章內(nèi)容進行總結(jié)回顧，能分析、設(shè)計線性表簡單應(yīng)用，并在編程環(huán)境中完成一元多項式等的實驗內(nèi)容，強化面向過程語言的編程能力，撰寫實驗報告；（ 2）課前自主學(xué)習(xí)在線平臺上線性表的相關(guān)視頻， 課后完成在線平臺的本章練習(xí)和單元作業(yè)。第 3 章 棧和隊列（ 10 學(xué)時）1. 教學(xué)內(nèi)容與“計算機核心課程規(guī)范”知識點標識符對照關(guān)系理論教學(xué)（ 6 學(xué)時）：（1）棧的概念及運算；DS_03_01_01（2）棧的順序存儲結(jié)構(gòu)及鏈式存儲結(jié)構(gòu)；D

23、S_03_01_0219CERACU/T XXXXX XXXX（3）棧的應(yīng)用；DS_03_01_03（4）隊列的概念及運算；DS_03_02_01（5）隊列的順序存儲結(jié)構(gòu)及鏈式存儲結(jié)構(gòu)；DS_03_02_02 、DS_03_02_03（6）隊列的應(yīng)用。DS_03_02_04實驗教學(xué)（ 4 學(xué)時）：（1）棧和隊列的簡單應(yīng)用；DS_03_01_03 、DS_03_02_04（2）棧的應(yīng)用 馬踏棋盤或迷宮問題等。DS_03_01_032. 基本要求：（ 1）掌握棧的定義、表示和基本操作，能夠針對具體問題查閱資料，并根據(jù)復(fù)雜軟件工程問題的需求，選擇合適的存儲類型，對該問題進行設(shè)計和實現(xiàn)；（ 2）掌握遞

24、歸的概念和遞歸的實現(xiàn)過程，能實現(xiàn)遞歸算法的非遞歸轉(zhuǎn)換；（ 3）掌握隊列的定義以及順序（循環(huán)隊列）和鏈式存儲結(jié)構(gòu)的實現(xiàn)，能根據(jù)實際問題分析，進行合理的數(shù)據(jù)存儲和算法描述。3. 重點及難點：重點： 棧和隊列的特點、存儲方式及基本操作；棧和隊列的應(yīng)用。難點： 采用棧和隊列數(shù)據(jù)結(jié)構(gòu)解決實際具體問題；遞歸的概念和遞歸的實現(xiàn)過程。4. 教學(xué)模式： 授課、討論、實驗5. 作業(yè)及課外學(xué)習(xí)要求（1）以棧和隊列基本概念、特點和的知識性作業(yè)，對第3 章內(nèi)容進行總結(jié)回顧，能分析和設(shè)計棧和隊列簡單應(yīng)用的解決方案，并且在編程環(huán)境中完成棧和隊列的實驗內(nèi)容，從實驗?zāi)康摹?內(nèi)容、方案設(shè)計、實驗結(jié)果等方面撰寫實驗報告；（ 2）成

25、立 3-5 人開發(fā)小組，選擇復(fù)雜工程問題，查閱資料，選擇合適存儲結(jié)構(gòu)，分析、設(shè)計和編寫算法，并對時間復(fù)雜度進行分析。（ 3）課前自主學(xué)習(xí)在線平臺上棧和隊列的相關(guān)視頻，課后完成在線平臺的本章練習(xí)和單元作業(yè)。第 4章串（4學(xué)時）1. 教學(xué)內(nèi)容與 “計算機核心課程規(guī)范 ”知識點標識符對照關(guān)系：理論教學(xué)（ 4 學(xué)時）：（1）串的基本概念及基本運算；（2）串的存儲結(jié)構(gòu)及實現(xiàn)；（3）串的模式匹配算法；DS_07_052. 基本要求：（ 1）理解串的基本概念及順序和鏈式存儲結(jié)構(gòu)；（ 2）掌握串的各種基本運算，能根據(jù)各種運算分析簡單文本編輯的設(shè)計思想；（ 3）掌握串的模式匹配算法， 能查閱資料并進行探索， 理

26、解 KMP 模式匹配算法思想， 并分析20CERACU/T XXXXX XXXX比較各類模式匹配算法的時間復(fù)雜度。3. 重點及難點：重點： 串的三種存儲方式，及基于存儲方式的查找、鏈接、求子串等操作；串的模式匹配算法。難點： 串的 KMP 模式匹配算法。4. 教學(xué)模式： 授課、討論5. 作業(yè)及課外學(xué)習(xí)要求（1）以串的概念、基本操作、存儲結(jié)構(gòu)的知識性作業(yè)對第4 章進行總結(jié)回顧，能分析和設(shè)計簡單模式匹配算法，并比較簡單模式匹配和KMP 模式匹配等算法的時間復(fù)雜度；（2）課前自主學(xué)習(xí)在線平臺上串的相關(guān)視頻，課后完成在線平臺的本章練習(xí)和單元作業(yè)。第 5 章 多維數(shù)組和廣義表（6 學(xué)時）1. 教學(xué)內(nèi)容與

27、 “計算機核心課程規(guī)范 ”知識點標識符對照關(guān)系：理論教學(xué)（ 4 學(xué)時）：（1）多維數(shù)組的順序存儲；DS_04_01（2）矩陣的壓縮存儲；DS_04_02、 DS_04_03（ 3）廣義表的概念、存儲及基本操作。實驗教學(xué)（ 2 學(xué)時）：（1）基于三元組壓縮存儲方式的矩陣簡單應(yīng)用 稀疏矩陣運算器加減法。DS_04_032. 基本要求：（ 1）掌握數(shù)組的順序存儲結(jié)構(gòu)；（ 2）理解稀疏數(shù)組的概念和壓縮存儲的方法；（ 3）理解稀疏矩陣的三元組存儲結(jié)構(gòu)和基本運算，能夠?qū)ο∈杈仃嚥扇∪M的存儲方式，設(shè)計和編寫加減操作等算法；（ 4）理解稀疏矩陣的十字鏈表存儲結(jié)構(gòu)；（ 5）理解廣義表的基本概念，掌握廣義表的

28、存儲結(jié)構(gòu)，能通過查閱資料，自主分析和設(shè)計廣義表的基本操作。3. 重點及難點：重點： 有規(guī)律矩陣的壓縮存儲地址映射關(guān)系；基于三元組表順序存儲結(jié)構(gòu)的轉(zhuǎn)置操作；廣義表的表頭、表尾計算方法。難點： 基于三元組存儲方式矩陣的“一次定位快速轉(zhuǎn)置”方法。4. 教學(xué)模式： 授課、討論、實驗5. 作業(yè)及課外學(xué)習(xí)要求（ 1）以數(shù)組的概念和順序存儲的知識性作業(yè)，特殊矩陣和稀疏矩陣的壓縮存儲分析方法，對第 5 章內(nèi)容進行總結(jié)回顧，能分析和設(shè)計稀疏矩陣的基本操作，并在編程環(huán)境中實現(xiàn)，撰寫實驗報告；（ 2）課前自主學(xué)習(xí)在線平臺上數(shù)組和廣義表的相關(guān)視頻，課后完成在線平臺的本章練習(xí)和單21CERACU/T XXXXX XXX

29、X元作業(yè)。第 6章 樹（ 16學(xué)時）1. 教學(xué)內(nèi)容與 “計算機核心課程規(guī)范 ”知識點標識符對照關(guān)系：理論教學(xué)（ 8 學(xué)時）：（1）樹的概念；（2）二叉樹的定義、性質(zhì)、存儲結(jié)構(gòu)；DS_05_01_01 、DS_05_01_02（3）二叉樹的遍歷及基于遍歷的應(yīng)用；DS_05_01_03（4）線索二叉樹的基本概念及基本操作；DS_05_01_04（5）樹和森林的概念和遍歷以及樹、森林、二叉樹之間的轉(zhuǎn)換；DS_05_03（6）哈夫曼樹及其應(yīng)用。DS_05_02_01實驗教學(xué)（ 8 學(xué)時）：（1）二叉樹、樹的遍歷及應(yīng)用；DS_05_01_03 、DS_05_03（2）哈夫曼樹的應(yīng)用 哈夫曼編譯碼器。DS

30、_05_02_012. 基本要求：（ 1）理解樹的基本概念及其存儲結(jié)構(gòu)；（ 2）掌握二叉樹的定義、性質(zhì)以及各種存儲結(jié)構(gòu)和遍歷算法，能根據(jù)實際需求對問題進行分析、設(shè)計、提出解決方案，并編寫相應(yīng)算法；（ 3）掌握線索二叉樹的概念、存儲結(jié)構(gòu)及線索化算法；（ 4）理解樹和森林與二叉樹間的轉(zhuǎn)換，掌握樹和森林的遍歷算法；（ 5）掌握哈夫曼樹的概念、存儲結(jié)構(gòu)，能設(shè)計和編寫編碼和譯碼算法，并查閱資料，理解文件壓縮和解壓縮的相關(guān)算法。3. 重點及難點：重點： 二叉樹的遍歷算法及基于遍歷的簡單應(yīng)用；樹和森林與二叉樹間的轉(zhuǎn)換，樹和森林的遍歷算法；哈夫曼樹的概念、存儲結(jié)構(gòu)和應(yīng)用哈夫曼樹構(gòu)造哈夫曼編碼。難點： 基于棧的

31、遞歸消除方法；應(yīng)用哈夫曼樹構(gòu)造編碼，解決數(shù)據(jù)壓縮問題。4. 教學(xué)模式： 授課、討論、實驗5. 作業(yè)及課外學(xué)習(xí)要求（1）以樹和二叉樹的概念、特點和存儲方式的知識性作業(yè)，對第6 章內(nèi)容進行總結(jié)回顧，能分析和設(shè)計二叉樹簡單應(yīng)用的解決方案；（ 2）掌握哈夫曼樹的創(chuàng)建、編碼和譯碼設(shè)計思想，在編程環(huán)境中完成數(shù)據(jù)統(tǒng)計、數(shù)據(jù)壓縮和解壓縮等實驗，從實驗?zāi)康?、?nèi)容、方案設(shè)計、實驗結(jié)果等方面撰寫實驗報告；（ 3）課前自主學(xué)習(xí)在線平臺上樹、二叉樹和哈夫曼樹的相關(guān)視頻，課后完成在線平臺的本章練習(xí)和單元作業(yè)。22CERACU/T XXXXX XXXX第 7章 圖（ 16學(xué)時）1. 教學(xué)內(nèi)容與 “計算機核心課程規(guī)范 ”知識

32、點標識符對照關(guān)系：理論教學(xué)（ 12 學(xué)時）：（1）圖的基本概念；DS_06_01（2）圖的存儲結(jié)構(gòu)；DS_06_02（3）圖的遍歷；DS_06_03（4）圖的最小生成樹、拓撲排序、關(guān)鍵路徑和最短路徑等應(yīng)用。DS_06_04實驗教學(xué)（ 4 學(xué)時）：（1）圖的遍歷；DS_06_03（2）圖的簡單應(yīng)用 最小生成樹、最短路徑或關(guān)鍵路徑。DS_06_04_01 、DS_06_04_02 、DS_06_04_042. 基本要求：（ 1）掌握圖的基本概念，掌握圖的鄰接矩陣和鄰接表的存儲結(jié)構(gòu)；（ 2）理解十字鏈表，鄰接多重表等存儲結(jié)構(gòu)；（ 3）掌握圖的深度優(yōu)先和廣度優(yōu)先遍歷算法，能上機編寫代碼實現(xiàn)圖的創(chuàng)建、遍

33、歷算法，并根據(jù)特定問題選擇合適的存儲結(jié)構(gòu)和遍歷策略，確定合理的解決方案；（ 4）理解圖的連通性、最小生成樹的概念，掌握求最小生成樹算法，能分析和設(shè)計道路網(wǎng)建設(shè)最經(jīng)濟的方案等復(fù)雜工程性問題；（ 5）理解有向無環(huán)圖的概念，掌握拓撲排序和關(guān)鍵路徑算法，能分析和設(shè)計工程建設(shè)時間的安排策略等復(fù)雜工程性問題；（ 6）理解帶權(quán)最短路徑的概念，掌握求最短路徑的算法，能根據(jù)實際問題選擇合適的最短路徑算法，確定合理的解決方案，通過查閱資料，自主分析和設(shè)計校園導(dǎo)游圖等復(fù)雜工程性問題。3. 重點及難點：重點： 圖的鄰接矩陣和鄰接表的存儲結(jié)構(gòu)；圖的深度優(yōu)先遍歷算法和廣度優(yōu)先遍歷算法；圖的最小生成樹算法、圖的拓撲排序和關(guān)

34、鍵路徑算法、圖的求最短路徑的 Dijkstra 算法、 Floyd 算法。難點： 理解圖的關(guān)鍵路徑算法、圖的求最短路徑算法；利用圖的重要算法解決實際具體問題。4. 教學(xué)模式： 授課、討論、實驗5. 作業(yè)及課外學(xué)習(xí)要求（1）以圖的概念、特點、存儲方式和簡單應(yīng)用等知識性作業(yè)，對第7 章的內(nèi)容進行總結(jié)回顧，在編程環(huán)境中完成圖的遍歷，撰寫實驗報告，根據(jù)道路網(wǎng)建設(shè)最經(jīng)濟方案、工程建設(shè)時間安排等復(fù)雜工程性問題選擇合適的解決方案；（ 2）課前自主學(xué)習(xí)在線平臺上圖的遍歷和應(yīng)用等相關(guān)視頻，課后完成在線平臺的本章練習(xí)和單元作業(yè)。第 8章查找（ 8學(xué)時）23CERACU/T XXXXX XXXX1. 教學(xué)內(nèi)容與 “

35、計算機核心課程規(guī)范 ”知識點標識符對照關(guān)系：理論教學(xué)（ 6 學(xué)時）：（ 1）查找的概念以及效率的評價方法；DS_07_01（2）基于線性表的查找 順序查找、折半查找、索引查找；DS_07_02 、DS_07_03、 DS_07_04（3）基于樹的查找 二叉排序樹、平衡二叉樹；DS_07_06_01 、DS_07_06_02（4）哈希查找法的概念和構(gòu)造方法。DS_07_09實驗教學(xué)（ 2 學(xué)時）：（1）簡單查找算法 二叉排序樹或哈希表查找等。DS_07_06_01 、DS_07_092. 基本要求：（ 1）理解查找的概念及其效率的評價方法；（ 2）理解靜態(tài)查找表的概念，熟練掌握順序、折半和分塊查

36、找算法，能根據(jù)復(fù)雜軟件工程問題的查找需求，選擇和設(shè)計合理的查找表；（3）理解動態(tài)查找表、二叉排序樹、平衡二叉樹的概念及平衡二叉樹的創(chuàng)建調(diào)整過程，能根據(jù)復(fù)雜軟件工程問題的查找需求，選擇合適的查找策略，并分析比較算法的平均查找長度；（4）理解哈希表的含義，掌握哈希函數(shù)的構(gòu)造和處理沖突的基本方法，能根據(jù)問題的查找要求，設(shè)計和實現(xiàn)查找策略；3. 重點及難點：重點： 順序、折半查找算法、二叉排序樹的插入、刪除和查找算法；哈希函數(shù)的構(gòu)造和處理沖突的基本方法；查找成功和不成功時的平均查找長度計算方法。難點： 理解折半查找的判定樹，分析折半查找的平均查找長度；二叉排序樹的插入、刪除算法；平衡二叉排序樹的創(chuàng)建調(diào)

37、整過程；哈希函數(shù)的查找成功和不成功的平均查找長度計算方法。4. 教學(xué)模式： 授課、討論、實驗5. 作業(yè)及課外學(xué)習(xí)要求（1）以查找的概念和基本方法的知識性作業(yè)和各類查找算法，對第8 章內(nèi)容進行總結(jié)回顧，能根據(jù)工程性問題選擇合理的查找算法，在編程環(huán)境中設(shè)計和實現(xiàn)，并對其進行平均查找長度分析，完成實驗報告撰寫；（ 2）課前自主學(xué)習(xí)在線平臺上查找的相關(guān)視頻，課后完成在線平臺的本章練習(xí)和單元作業(yè)。第 9章排序（ 6學(xué)時）1. 教學(xué)內(nèi)容與 “計算機核心課程規(guī)范”知識點標識符對照關(guān)系：理論教學(xué)（ 4 學(xué)時）：（ 1）排序的概念以及排序算法的性能評價；DS_08_01（2）插入類排序 直接插入排序、折半插入排

38、序、希爾排序；DS_08_02（3）交換類排序 冒泡排序、快速排序；DS_08_0324CERACU/T XXXXX XXXX（4）選擇類排序 簡單選擇排序、樹形選擇排序、堆排序；DS_08_04、 DS_05_02（5）歸并類排序 二路歸并排序、自然歸并排序；DS_08_05（6）分配類排序 基數(shù)排序；DS_08_06（7）外部排序方法介紹。DS_09_01實驗教學(xué)（ 2 學(xué)時）：（1）任選 2-3 種排序算法，實現(xiàn)一批數(shù)字從小到大的有序輸出。DS_082. 基本要求：（ 1）掌握插入類排序、交換類排序、選擇類排序的基本算法，能根據(jù)復(fù)雜軟件工程問題的排序需求和數(shù)據(jù)特性，分析比較排序方法時間復(fù)

39、雜度和空間復(fù)雜度，選擇并設(shè)計合理的排序算法；（2）理解歸并排序、基數(shù)排序的思想，查閱資料，了解外排序的概念，自主分析和設(shè)計簡單的外部排序算法；3. 重點及難點：重點： 理解快速排序、堆排序、歸并排序等排序算法的思想；掌握排序方法的平均時間復(fù)雜度、最壞時間復(fù)雜度和算法所需的輔助存儲空間。難點： 快速排序、堆排序、歸并排序、基數(shù)排序的排序思想；各種排序方法的綜合比較。4. 教學(xué)模式： 授課、討論5. 作業(yè)及課外學(xué)習(xí)要求（1）以排序的概念和基本方法的知識性作業(yè)和各類不同排序算法思想，對第9 章內(nèi)容進行總結(jié)回顧，能根據(jù)工程性問題選擇合理的排序算法，并對其進行時間復(fù)雜度、空間復(fù)雜度以及穩(wěn)定性分析；（2）

40、課前自主學(xué)習(xí)在線平臺上排序的相關(guān)視頻，課后完成在線平臺的本章練習(xí)和單元作業(yè)。B.5考核與評價方式及標準課程考核總評成績由平時成績、期中考試成績、期末考試成績?nèi)糠纸M成，每項成績滿分均是100 分。平時成績：主要考核對各個知識點的復(fù)習(xí)、理解和掌握程度；課堂討論情況、平時作業(yè)和每次實驗的完成情況。期中考試成績： 主要考核對課程前六章的知識點掌握程度以及運用理論知識解決實際問題的能力。期末考試成績： 主要考核對數(shù)據(jù)結(jié)構(gòu)與算法課程的知識點掌握程度以及運用理論知識解決實際問題的能力。備注：（ 1）平時成績占比不低于30%，不高于50%；25CERACU/T XXXXX XXXX（ 2） 期中考試占比不低

41、于 10%，不高于 20%（ 3） 期末考試占比不低于 30%，不高于 50%B.6建議教材及參考資料1 王曙燕 .數(shù)據(jù)結(jié)構(gòu)與算法（新形態(tài)教材） .北京：高等教育出版社 . 2019.2 王曙燕 .數(shù)據(jù)結(jié)構(gòu)與算法 .北京：人民郵電出版社 . 2013.3 王曙燕 .數(shù)據(jù)結(jié)構(gòu)與算法 .中國大學(xué) MOOC 在線平臺參考資料：1 耿國華 . 數(shù)據(jù)結(jié)構(gòu) C 語言描述 . 北京 : 高等教育出版社 . 2011.2 嚴蔚敏 . 數(shù)據(jù)結(jié)構(gòu) (第二版 ). 北京 :清華大學(xué)出版社 . 2012.26CERACU/T XXXXX XXXX附錄 C（資料性附錄）數(shù)據(jù)結(jié)構(gòu)課程規(guī)范案例三C.1 數(shù)據(jù)結(jié)構(gòu)與算法課程大

42、綱課程基本信息課程名稱數(shù)據(jù)結(jié)構(gòu)與算法英文名稱Data Structure and Algorithm課程編碼020224007課程類別專業(yè)教育課 /理論課 /必修學(xué)分數(shù)3.5開課學(xué)期3,4開課單位計算機系學(xué)時數(shù)總學(xué)時 (周 )講課實驗練習(xí)其它5648800適用專業(yè)計算機科學(xué)與技術(shù)、軟件工程、網(wǎng)絡(luò)工程、物聯(lián)網(wǎng)工程課程地位1 本課程在專業(yè)人才培養(yǎng)方案中的貢獻度數(shù)據(jù)結(jié)構(gòu)與算法是計算機類 /軟件類專業(yè)的技術(shù)基礎(chǔ)課，主要講述算法設(shè)計和數(shù)據(jù)結(jié)構(gòu)的基本原理和技術(shù)，是計算機科學(xué)的核心課程之一。通過本課程的學(xué)習(xí)，使學(xué)生較全面地掌握各種常用的基本數(shù)據(jù)結(jié)構(gòu)和算法設(shè)計的基礎(chǔ)知識和基礎(chǔ)理論，為學(xué)習(xí)后續(xù)課程提供必要的基礎(chǔ)

43、，提高學(xué)生的分析問題能力、邏輯思維能力與設(shè)計有效算法解決實際問題的能力，有助于培養(yǎng)學(xué)生具有嚴謹?shù)目茖W(xué)態(tài)度，增強創(chuàng)新能力，在專業(yè)人才培養(yǎng)中具有重要的作用。2.本課程與相關(guān)課程的關(guān)系本課程需要高等數(shù)學(xué)、離散數(shù)學(xué)、程序設(shè)計基礎(chǔ)等課程作為先修課，同時，是學(xué)習(xí)操作系統(tǒng)、數(shù)據(jù)庫原理、編譯原理和計算機網(wǎng)絡(luò)等后續(xù)課程的重要知識和能力基礎(chǔ)。3.本課程的特色數(shù)據(jù)結(jié)構(gòu)與算法屬于理論與實踐并重的重要專業(yè)基礎(chǔ)課程，是決定后續(xù)課程學(xué)習(xí)質(zhì)量與就業(yè)質(zhì)量的重要課程。通過本課程的學(xué)習(xí)，有利于學(xué)生科學(xué)素養(yǎng)與程序設(shè)計能力的培養(yǎng)，提高運用學(xué)科基本理論分析問題、解決問題的能力。課程以課堂教學(xué)傳授知識為主，充分借鑒現(xiàn)有開放式課程的教學(xué)模式

44、，將基于互聯(lián)網(wǎng)的在線學(xué)習(xí)資源、在線學(xué)習(xí)方法引入理論教學(xué)與實踐教學(xué)中，采用線上線下學(xué)習(xí)相結(jié)合，依托在線平臺引入過程化教學(xué)管理手段提高教學(xué)質(zhì)量。課程教學(xué)目標通過本課程的學(xué)習(xí)，使學(xué)生掌握為計算機加工處理的對象設(shè)計邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)，在此基礎(chǔ)上設(shè)計算法和進行算法分析，踐行“數(shù)據(jù)結(jié)構(gòu)+算法 =程序”這一理念。本課程的學(xué)習(xí)過程也是算法設(shè)計的技巧和能力的訓(xùn)練過程，使學(xué)生獲得編寫結(jié)構(gòu)正確、代碼易讀、符合軟件工程規(guī)范的程序的理論、技巧和能力，能夠選擇合適的數(shù)據(jù)結(jié)構(gòu)并設(shè)計算法進行問題求解。課程主要內(nèi)容27CERACU/T XXXXX XXXX（一）緒論（參考學(xué)時：3 學(xué)時）1、數(shù)據(jù)結(jié)構(gòu)基本概念和術(shù)語（ 1）理解數(shù)

45、據(jù)、數(shù)據(jù)元素和數(shù)據(jù)項的概念及其相互間的關(guān)系；（ 2）理解數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及其相互關(guān)系以及在數(shù)據(jù)結(jié)構(gòu)上施加的運算及其實現(xiàn)，理解抽象數(shù)據(jù)類型的概念。2、算法和算法分析掌握算法分析和算法設(shè)計的基本理論和技巧，培養(yǎng)科學(xué)嚴謹?shù)乃惴ㄔO(shè)計技巧和優(yōu)良的程序設(shè)計風(fēng)格。（二）線性結(jié)構(gòu)（參考學(xué)時：17 學(xué)時）1、線性表（參考學(xué)時：6 學(xué)時）（ 1）理解線性表的定義及其運算，理解順序表和鏈表的定義、組織形式、結(jié)構(gòu)特征和類型說明；（ 2）掌握在這兩種表上實現(xiàn)的插入、刪除和按值查找的算法；（ 3）掌握循環(huán)鏈表、雙 (循環(huán) ) 鏈表的結(jié)構(gòu)特點和在其上施加的插入、刪除等操作；（ 4）能夠應(yīng)用線性表解決實際問題。2、棧和隊列（參考學(xué)時：5 學(xué)時）（ 1）理解棧的定義、特征及在其上所定義的基本運算；（ 2）掌握在兩種存儲結(jié)構(gòu)上對棧所施加的基本運算的實現(xiàn)；（ 3）理解隊列的定義、特征及在其上所定義的基本運算；（ 4）掌握在兩種存儲結(jié)構(gòu)上對隊列所施加的基本運算的實現(xiàn)；（ 5）能夠應(yīng)用棧和隊列解決實際問題。3、串（參考學(xué)時：2 學(xué)時）（ 1）了解串的定義；（ 2）理解串的存儲方式；（ 3）掌握串的模式匹配 KMP 算法。4、數(shù)組和廣義表（參考學(xué)時：4 學(xué)時）（ 1）理解多維數(shù)組的結(jié)構(gòu)特點和在內(nèi)存中的兩種順序存儲方式；（ 2）理解并掌握矩陣和特