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

《數(shù)據(jù)結(jié)構(gòu)與算法》教學(xué)大綱一、課程基本信息課程名稱數(shù)據(jù)結(jié)構(gòu)與算法DataStructureandAlgorithm課程編碼CST310311030開課院部計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院課程團(tuán)隊(duì)數(shù)據(jù)結(jié)構(gòu)與算法教學(xué)團(tuán)隊(duì)學(xué)分3.0課內(nèi)學(xué)時(shí)52講授40實(shí)驗(yàn)0上機(jī)12實(shí)踐0課外學(xué)時(shí)52適用專業(yè)軟件工程授課語言中文先修課程計(jì)算概論、程序設(shè)計(jì)（C/C++）、離散數(shù)學(xué)課程簡介（必修）《數(shù)據(jù)結(jié)構(gòu)與算法》課程是面向軟件工程、計(jì)算機(jī)科學(xué)與技術(shù)、物聯(lián)網(wǎng)工程、智能科學(xué)與技術(shù)等IT類專業(yè)本科生開設(shè)的核心、必修專業(yè)基礎(chǔ)課。利用計(jì)算機(jī)求解問題就是要解決問題的數(shù)據(jù)在計(jì)算機(jī)中的表示和處理的問題，數(shù)據(jù)結(jié)構(gòu)是問題求解的基礎(chǔ)要素，算法是問題求解的關(guān)鍵要素。課程的主要內(nèi)容包括：數(shù)據(jù)、數(shù)據(jù)結(jié)構(gòu)和抽象數(shù)據(jù)類型等基本概念；從抽象數(shù)據(jù)類型的角度，分別討論線性表、樹和二叉樹以及圖等基本類型的數(shù)據(jù)結(jié)構(gòu)及其應(yīng)用；討論查找和排序算法的設(shè)計(jì)與實(shí)現(xiàn)并著重從時(shí)間上進(jìn)行定性或定量的分析和比較。課程的目標(biāo)是在學(xué)習(xí)高級(jí)語言程序設(shè)計(jì)等課程的基礎(chǔ)上，掌握利用計(jì)算機(jī)解決問題的一般性方法（抽象數(shù)據(jù)類型定義、表示和實(shí)現(xiàn)）和常用算法，能培養(yǎng)學(xué)生的計(jì)算機(jī)思維（邏輯思維和抽象思維）能力以及形式化思維方法，進(jìn)一步訓(xùn)練和強(qiáng)化學(xué)生的編程能力，逐步提升程序規(guī)模和運(yùn)行效率，培養(yǎng)和提升學(xué)生抽象和建立問題的計(jì)算機(jī)求解模型、設(shè)計(jì)合理的實(shí)現(xiàn)方案的能力，從而為軟件工程、數(shù)據(jù)庫原理、操作系統(tǒng)等課程的學(xué)習(xí)奠定堅(jiān)實(shí)的基礎(chǔ)，并建立正確的人生觀和價(jià)值觀。Thecourseofdatastructureandalgorithmisacoreandcompulsorybasiccourseforitmajorssuchassoftwareengineering,computerscienceandtechnology,Internetofthingsengineering,intelligentscienceandtechnology.Usingcomputertosolvetheproblemistosolvetheproblemofdatarepresentationandprocessinginthecomputer.Datastructureisthebasicelementofproblemsolving,andalgorithmisthekeyelement.Themaincontentsofthecourseinclude:basicconceptssuchasdata,datastructureandabstractdatatype,andsoon;discussingthedatastructureandapplicationoflineartable,tree,binarytreeandgraphfromtheperspectiveofabstractdatatype;thealgorithmdesignandimplementationonsearchandsorting,andtheanalysisandcomparisonintimeefficiencyqualitativeorquantitative.Thegoalofthecourseistomasterthegeneralmethods(definition,representationandimplementationofabstractdatatypes)andcommonalgorithmsofusingcomputerstosolveproblemsonthebasisoflearningadvancedlanguageprogrammingandothercourses,tocultivatestudents'computerthinking(logicalthinkingandabstractthinking)abilityandformalthinkingmethods,furthertrainandstrengthenstudents'programmingability,andgraduallyimprovetheprogramscaleandefficiency,cultivateandenhancetheabilityofstudentstoabstractandestablishthecomputersolutionmodelofproblems,anddesignareasonableimplementationscheme,soastolayasolidfoundationforthestudyofsoftwareengineering,databaseprinciples,operatingsystemsandothercourses，andestablishacorrectoutlookonlifeandvalues.負(fù)責(zé)人大綱執(zhí)筆人審核人二、課程目標(biāo)序號(hào)代號(hào)課程目標(biāo)OBE畢業(yè)要求指標(biāo)點(diǎn)任務(wù)自選1M1目標(biāo)1：掌握數(shù)據(jù)結(jié)構(gòu)的基本概念，理解數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)及抽象數(shù)據(jù)類型之間的關(guān)系，掌握常用算法的設(shè)計(jì)思想及實(shí)現(xiàn)方法，能夠運(yùn)用相關(guān)知識(shí)對(duì)比分析不同數(shù)據(jù)結(jié)構(gòu)和算法的特點(diǎn)和應(yīng)用場景從而用來解決具體的工程問題。能夠結(jié)合國家最新政策法規(guī)，理解正確社會(huì)主義核心價(jià)值觀對(duì)于本專業(yè)的重要指導(dǎo)意義。是1.22M2目標(biāo)2：能夠運(yùn)用數(shù)據(jù)結(jié)構(gòu)的基本原理，建立計(jì)算應(yīng)用領(lǐng)域問題中的抽象數(shù)據(jù)類型，選擇適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)模型并在此基礎(chǔ)上進(jìn)行算法設(shè)計(jì)，并證明算法的有效性。是3.22.43M3目標(biāo)3：能夠針對(duì)計(jì)算系統(tǒng)的功能模塊，以數(shù)據(jù)結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)為基礎(chǔ)進(jìn)行算法設(shè)計(jì)，并應(yīng)用軟硬件開發(fā)技術(shù)完成詳細(xì)設(shè)計(jì)與實(shí)現(xiàn)。是3.2三、課程內(nèi)容序號(hào)章節(jié)號(hào)標(biāo)題課程內(nèi)容/重難點(diǎn)支撐課程目標(biāo)課內(nèi)學(xué)時(shí)教學(xué)方式課外學(xué)時(shí)課外環(huán)節(jié)1第1章第一章緒論本章重點(diǎn)難點(diǎn)：算法的時(shí)間復(fù)雜度、抽象數(shù)據(jù)類型。////21.11.1數(shù)據(jù)結(jié)構(gòu)的概念數(shù)據(jù)結(jié)構(gòu)舉例、數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)、邏輯結(jié)構(gòu)、物理結(jié)構(gòu)、數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容。M10.5講授1自學(xué)資料31.21.2數(shù)據(jù)結(jié)構(gòu)的抽象形式數(shù)據(jù)類型、抽象數(shù)據(jù)類型。M10.5講授1課后作業(yè)41.31.3算法性能分析算法的性能分析、算法的時(shí)間復(fù)雜度。M21講授2自學(xué)作業(yè)5第2章第二章線性表本章重點(diǎn)難點(diǎn)：線性表在順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ)下的實(shí)現(xiàn)。////62.12.1線性表線性表的概念。M10.5講授1自學(xué)作業(yè)72.22.2順序表順序表的概念、類定義。M21.5講授1.5課后作業(yè)82.32.3單鏈表單鏈表的概念、類定義。M12講授2自學(xué)作業(yè)92.42.4線性鏈表的其他變形循環(huán)鏈表、雙向鏈表。M20.5講授1課后作業(yè)102.52.5單鏈表的應(yīng)用多項(xiàng)式及其運(yùn)算。M31講授1自學(xué)作業(yè)112.6上機(jī)1多項(xiàng)式的存儲(chǔ)及基本操作（順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ)）M1,M2,M32上機(jī)2上機(jī)12第3章第三章棧和隊(duì)列本章重點(diǎn)難點(diǎn)：棧的特點(diǎn)、存儲(chǔ)、及其應(yīng)用，隊(duì)列的特點(diǎn)及其存儲(chǔ)。/////133.13.1棧棧的概念、順序棧、鏈?zhǔn)綏！⒗ㄌ?hào)匹配、表達(dá)式的計(jì)算。M22講授0.5課后作業(yè)143.23.2隊(duì)列隊(duì)列的概念、循環(huán)隊(duì)列、鏈?zhǔn)疥?duì)列、優(yōu)先級(jí)隊(duì)列、雙端隊(duì)列。M31.5講授1自學(xué)作業(yè)153.3上機(jī)2表達(dá)式問題求值M1,M2,M32上機(jī)2上機(jī)16第4章第四章字符串和數(shù)組本章重點(diǎn)難點(diǎn)：字符串模式匹配，特殊矩陣、稀疏矩陣的存儲(chǔ)及操作。/////174.14.1多維數(shù)組的概念與存儲(chǔ)數(shù)組的數(shù)據(jù)結(jié)構(gòu)定義、數(shù)組基于順序存儲(chǔ)的實(shí)現(xiàn)。M20.5講授0.5課后作業(yè)184.24.2特殊矩陣對(duì)稱矩陣、三對(duì)角矩陣。M31講授1自學(xué)作業(yè)194.34.3稀疏矩陣稀疏矩陣的類定義、稀疏矩陣的轉(zhuǎn)置。M22講授1課后作業(yè)204.44.4字符串字符串線性結(jié)構(gòu)的特點(diǎn)，模式匹配算法。M31講授1自學(xué)作業(yè)21第5章第五章樹與森林本章重點(diǎn)難點(diǎn)：二叉樹的性質(zhì)、存儲(chǔ)及操作，線索二叉樹，Huffman樹。/////225.15.1數(shù)和森林的概念樹的定義、樹的抽象數(shù)據(jù)類型M20.5講授1課后作業(yè)235.25.2二叉樹二叉樹的定義、二叉樹的性質(zhì)、二叉樹的抽象數(shù)據(jù)類型。M31講授0.5自學(xué)作業(yè)245.35.3二叉樹的存儲(chǔ)二叉樹的順序存儲(chǔ)、二叉樹的鏈?zhǔn)酱鎯?chǔ)。M22講授1課后作業(yè)255.45.4二叉樹的遍歷中序遍歷、前序遍歷、后序遍歷、非遞歸遍歷。M31.5講授2課后作業(yè)265.55.5線索二叉樹線索、線索化二叉樹。M21.5講授1.5自學(xué)作業(yè)275.65.6樹與森林樹的存儲(chǔ)、森林與二叉樹的轉(zhuǎn)換、樹的遍歷、森林的遍歷。M31講授1.5課后作業(yè)285.75.7二叉樹的計(jì)數(shù)M20.5講授1自學(xué)作業(yè)295.85.8哈夫曼樹路徑長度、哈夫曼樹、哈夫曼編碼。M31.5講授0.5自學(xué)作業(yè)305.9上機(jī)3二叉樹的存儲(chǔ)、遍歷及計(jì)數(shù)M1,M2,M32上機(jī)2上機(jī)31第6章第六章圖本章重點(diǎn)難點(diǎn)：圖的存儲(chǔ)、遍歷、最小生成樹，最短路徑、關(guān)鍵路徑。/////326.16.1圖的基本概念圖的基本概念、圖的抽象數(shù)據(jù)類型。M21講授1.5課后作業(yè)336.26.2圖的存儲(chǔ)鄰接矩陣、鄰接表。M32講授1自學(xué)作業(yè)346.36.3圖的遍歷與連通性深度優(yōu)先遍歷、廣度優(yōu)先遍歷、連通分量。M22.5講授2.5課后作業(yè)356.46.4最小生成樹克魯斯卡爾算法、普里姆算法。M31講授1自學(xué)作業(yè)366.56.5最短路徑單源最短路徑問題、所有頂點(diǎn)之間的最短路徑。M21.5講授1.5課后作業(yè)376.66.6活動(dòng)網(wǎng)絡(luò)用頂點(diǎn)表示活動(dòng)的網(wǎng)絡(luò)、用邊表示活動(dòng)的網(wǎng)絡(luò)、拓?fù)渑判?、關(guān)鍵路徑。M32講授2自學(xué)作業(yè)386.5上機(jī)4圖的存儲(chǔ)及基本操作M1,M2,M32上機(jī)2上機(jī)39第7章第七章查找本章重點(diǎn)難點(diǎn)：順序查找、折半查找、平衡二叉樹、B樹、HASH查找。/////407.17.1靜態(tài)表查找順序查找、折半查找。M21講授1自學(xué)作業(yè)417.27.2動(dòng)態(tài)查找表查找二叉搜索樹、平衡二叉樹、B樹。M21講授1自學(xué)作業(yè)427.37.3HASH查找HASH函數(shù)、解決沖突的方法。M30.5講授1自學(xué)作業(yè)437.4上機(jī)5查找算法及應(yīng)用M1,M2,M32上機(jī)2上機(jī)44第8章第八章排序本章重點(diǎn)難點(diǎn)：SHELL排序、冒泡排序、快速排序、堆排序、歸并排序。/////458.18.1基于插入排序直接插入排序、折半插入排序、SHELL排序。M20.5講授1自學(xué)作業(yè)468.28.2基于交換的排序冒泡排序、快速排序。M31講授1自學(xué)作業(yè)478.38.3基于選擇的排序簡單選擇排序、堆排序。M20.5講授1自學(xué)作業(yè)488.48.4基于歸并的排序2-路歸并排序。M30.5講授1自學(xué)作業(yè)498.5上機(jī)6排序算法及應(yīng)用M1,M2,M32上機(jī)2上機(jī)四、考核方式序號(hào)考核環(huán)節(jié)操作細(xì)節(jié)總評(píng)占比1平時(shí)作業(yè)1.每章節(jié)布置4~5道編程練習(xí)題目。2.成績采用百分制，根據(jù)作業(yè)完成準(zhǔn)確性、是否按時(shí)上交、是否獨(dú)立完成評(píng)分。3.考核學(xué)生對(duì)基本知識(shí)的掌握能力，學(xué)生綜合運(yùn)用所學(xué)知識(shí)分析問題、解決問題的能力，題型主要為編程實(shí)踐。15%2實(shí)驗(yàn)1.本課程12個(gè)學(xué)時(shí)實(shí)驗(yàn)，共6次實(shí)驗(yàn)，采用限時(shí)完成的形式。2.成績采用百分制，根據(jù)實(shí)驗(yàn)完成情況評(píng)分。3.考核學(xué)生對(duì)數(shù)據(jù)結(jié)構(gòu)與算法知識(shí)的應(yīng)用能力，針對(duì)各章節(jié)重點(diǎn)問題，能夠根據(jù)需求確定設(shè)計(jì)目標(biāo)，從編程技術(shù)角度優(yōu)選解決方案獲得有效結(jié)論。25%3考勤+課堂表現(xiàn)隨機(jī)點(diǎn)名、刷卡點(diǎn)名等；隨機(jī)檢查學(xué)生上課精神狀態(tài)、回答問題情況；10%4期末考試1.閉卷考試，成績采用百分制，卷面成績總分100分。2.主要考核學(xué)生對(duì)電力拖動(dòng)自動(dòng)控制系統(tǒng)基本知識(shí)的掌握能力，學(xué)生綜合運(yùn)用所學(xué)知識(shí)分析問題、解決問題的能力，題型主要有簡答題、選擇題、分析題、程序設(shè)計(jì)題等。50%五、評(píng)分細(xì)則序號(hào)課程目標(biāo)考核環(huán)節(jié)大致占比評(píng)分等級(jí)1M1平時(shí)作業(yè)15%A-獨(dú)立思考、按時(shí)完成，解題思路比較清晰、步驟比較完整、格式比較合理、答案準(zhǔn)確B-獨(dú)立思考、按時(shí)完成，解題思路清晰、步驟完整、格式合理、答案準(zhǔn)確2M1實(shí)驗(yàn)25%A-實(shí)驗(yàn)過程中不能完成實(shí)驗(yàn)要求，不能得到正確的實(shí)驗(yàn)結(jié)果，不能從技術(shù)角度優(yōu)選解決方案獲得有效的結(jié)論B-實(shí)驗(yàn)過程中認(rèn)真完成實(shí)驗(yàn)要求，不能得到正確的實(shí)驗(yàn)結(jié)果，步驟敘述清楚，結(jié)果不完全正確，但是結(jié)合理論分析可以從技術(shù)角度優(yōu)選解決方案獲得有效的結(jié)論C-實(shí)驗(yàn)過程中認(rèn)真完成實(shí)驗(yàn)要求，得到正確的實(shí)驗(yàn)結(jié)果，步驟敘述比較清楚，程序運(yùn)行正確，從技術(shù)角度優(yōu)選解決方案獲得比較有效的結(jié)論D-實(shí)驗(yàn)過程中認(rèn)真完成實(shí)驗(yàn)要求，得到正確的實(shí)驗(yàn)結(jié)果，步驟敘述清楚，運(yùn)行結(jié)果完全正確，代碼格式規(guī)范，從技術(shù)角度優(yōu)選解決方案獲得有效結(jié)論3M1考勤+課堂表現(xiàn)10%A-全勤；精神狀態(tài)飽滿，回答問題準(zhǔn)確B-缺勤2次以內(nèi)。C-缺勤3次及以上且很少參加課堂討論。4M1期末考試50%（見試卷評(píng)分標(biāo)準(zhǔn)）5M2平時(shí)作業(yè)15%A-獨(dú)立思考、按時(shí)完成，解題思路比較清晰、步驟比較完整、格式比較合理、答案準(zhǔn)確B-獨(dú)立思考、按時(shí)完成，解題思路清晰、步驟完整、格式合理、答案準(zhǔn)確6M2實(shí)驗(yàn)25%A-實(shí)驗(yàn)過程中不能完成實(shí)驗(yàn)要求，不能得到正確的實(shí)驗(yàn)結(jié)果，不能從技術(shù)角度優(yōu)選解決方案獲得有效的結(jié)論B-實(shí)驗(yàn)過程中認(rèn)真完成實(shí)驗(yàn)要求，不能得到正確的實(shí)驗(yàn)結(jié)果，步驟敘述清楚，結(jié)果不完全正確，但是結(jié)合理論分析可以從技術(shù)角度優(yōu)選解決方案獲得有效的結(jié)論C-實(shí)驗(yàn)過程中認(rèn)真完成實(shí)驗(yàn)要求，得到正確的實(shí)驗(yàn)結(jié)果，步驟敘述比較清楚，程序運(yùn)行正確，從技術(shù)角度優(yōu)選解決方案獲得比較有效的結(jié)論D-實(shí)驗(yàn)過程中認(rèn)真完成實(shí)驗(yàn)要求，得到正確的實(shí)驗(yàn)結(jié)果，步驟敘述清楚，運(yùn)行結(jié)果完全正確，代碼格式規(guī)范，從技術(shù)角度優(yōu)選解決方案獲得有效結(jié)論7M2考勤+課堂表現(xiàn)10%A-全勤；精神狀態(tài)飽滿，回答問題準(zhǔn)確B-缺勤2次以內(nèi)。C-缺勤3次及以上且很少參加課堂討論。8M2期末考試50%（見試卷評(píng)分標(biāo)準(zhǔn)）9M3平時(shí)作業(yè)15%A-獨(dú)立思考、按時(shí)完成，解題思路比較清晰、步驟比較完整、格式比較合理、答案準(zhǔn)確B-獨(dú)立思考、按