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

《數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)》教學(xué)大綱一、課程基本信息課程名稱數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)BasicsofDataStructuresandAlgorithms課程編碼OSI322521020開課院部海洋與空間信息學(xué)院課程團(tuán)隊程序設(shè)計語言課程團(tuán)隊學(xué)分2.0課內(nèi)學(xué)時36講授24實驗0上機(jī)12實踐0課外學(xué)時36適用專業(yè)電子信息工程授課語言中文先修課程程序設(shè)計（C/C++）、程序設(shè)計（C/C++）實驗、高等數(shù)學(xué)（2-1）、線性代數(shù)課程簡介（限選）本課程為信號與信息處理方向?qū)I(yè)選修課，課程以C++為編程語言和實現(xiàn)工具，重點(diǎn)介紹線性表、棧和隊列、字符串和多維數(shù)組、樹和二叉樹等常用的數(shù)據(jù)結(jié)構(gòu)及其相關(guān)算法，重點(diǎn)探討與查找和排序相關(guān)的技術(shù)與算法。通過學(xué)習(xí)讓學(xué)生掌握利用計算機(jī)解決問題的一般性方法（抽象數(shù)據(jù)類型定義、表示和實現(xiàn)），培養(yǎng)學(xué)生的計算機(jī)思維（邏輯思維和抽象思維）能力以及形式化思維方法，進(jìn)一步訓(xùn)練和強(qiáng)化學(xué)生的編程能力，提高其終身學(xué)習(xí)素養(yǎng)和適應(yīng)發(fā)展能力，為后期專業(yè)相關(guān)的工程應(yīng)用軟件開發(fā)和數(shù)值算法軟件開發(fā)奠定堅實基礎(chǔ)。Thiscourseisanelectivecourseforsignalandinformationprocessingmajors.ThecourseusesCastheprogramminglanguageandimplementationtool,focusingonlineartables,stacksandqueues,stringsandmultidimensionalarrays,commondatastructuressuchastreesandbinarytreesandtheirrelatedalgorithms,focusingontechnologiesandalgorithmsrelatedtosearchandsorting.Throughlearning,studentscanmasterthegeneralmethodsofusingcomputerstosolveproblems(definition,representationandimplementationofabstractdatatypes)andcultivatestudents'computerthinking(logicalthinkingandabstractthinking)abilityandformalthinkingmethods,furthertrainingandstrengtheningstudents'programmingability,improvingtheirlifelonglearningliteracyandadaptivedevelopmentability,itlaysasolidfoundationforthedevelopmentofengineeringapplicationsoftwareandnumericalalgorithmsoftwarerelatedtothelaterspecialty.負(fù)責(zé)人大綱執(zhí)筆人審核人二、課程目標(biāo)序號代號課程目標(biāo)OBE畢業(yè)要求指標(biāo)點(diǎn)任務(wù)自選1M1目標(biāo)1：針對電子信息領(lǐng)域的實際編程任務(wù)選擇合適的數(shù)據(jù)結(jié)構(gòu)，設(shè)計和開發(fā)合理的算法程序求解問題。是3.23.22M2目標(biāo)2：了解程序設(shè)計、軟件開發(fā)相關(guān)的現(xiàn)代編程工具，理解并掌握基本的算法程序設(shè)計技能。是5.15.13M3目標(biāo)3：能夠使用C/C++編程工具設(shè)計、開發(fā)、調(diào)試、運(yùn)行電子信息領(lǐng)域的相關(guān)算法程序和軟件。是5.25.24M4目標(biāo)4：能夠結(jié)合實驗任務(wù)和課程作業(yè)，撰寫算法設(shè)計文稿、實驗總結(jié)報告及綜合設(shè)計文案。是10.110.1三、課程內(nèi)容序號章節(jié)號標(biāo)題課程內(nèi)容/重難點(diǎn)支撐課程目標(biāo)課內(nèi)學(xué)時教學(xué)方式課外學(xué)時課外環(huán)節(jié)1第1章第1章緒論本章重點(diǎn)難點(diǎn)：數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)類型和抽象數(shù)據(jù)類型【課程思政】介紹課程的地位與特點(diǎn)，強(qiáng)調(diào)課程的學(xué)習(xí)重點(diǎn)、難點(diǎn)及學(xué)習(xí)方法，引導(dǎo)學(xué)生意識到課程學(xué)習(xí)的重要性，明確學(xué)習(xí)紀(jì)律要求。/////21.11.1C++語言基礎(chǔ)知識數(shù)據(jù)類型，程序結(jié)構(gòu)，控制語句，輸入輸出，動態(tài)存儲分配，函數(shù)，數(shù)組，指針與引用，結(jié)構(gòu)體，類與對象，繼承與派生，多態(tài)性與虛函數(shù)M11.5講授、討論1作業(yè)、自學(xué)31.21.2數(shù)據(jù)結(jié)構(gòu)、算法及算法分析數(shù)據(jù)結(jié)構(gòu)的基本概念，數(shù)據(jù)結(jié)構(gòu)在程序設(shè)計中的作用，抽象數(shù)據(jù)類型，算法及其描述方法，算法性能分析與度量M11.5講授、討論0.5作業(yè)、自學(xué)4實驗1實驗1：C++編程工具的使用熟練使用VisualStudio或CodeBlocks等C++編程工具，熟練掌握C++基礎(chǔ)語法知識，熟練掌握C++程序的調(diào)試測試方法【課程思政】強(qiáng)調(diào)上機(jī)編程程序格式排版要求，引導(dǎo)學(xué)生認(rèn)識到軟件編程規(guī)范的重要性，要求學(xué)生在學(xué)習(xí)中努力發(fā)揚(yáng)規(guī)范精神和工匠精神。M2,M30實驗、上機(jī)2實驗、上機(jī)5第2章第2章線性表本章重點(diǎn)難點(diǎn)：存儲結(jié)構(gòu)與存取結(jié)構(gòu)、順序表模板類的設(shè)計與實現(xiàn)、單鏈表模板類的設(shè)計與實現(xiàn)【課程思政】告訴學(xué)生程序查錯沒有捷徑，只能是編程者靜下心來逐行逐塊測試調(diào)試自己的程序、切忌急躁，引導(dǎo)學(xué)生養(yǎng)成認(rèn)真仔細(xì)的做事習(xí)慣。/////62.12.1線性表的邏輯結(jié)構(gòu)線性表的定義，線性表的抽象數(shù)據(jù)類型定義M11講授、討論0.5作業(yè)、自學(xué)72.22.2線性表的順序存儲結(jié)構(gòu)及實現(xiàn)線性表的順序存儲結(jié)構(gòu)(順序表)，順序表的實現(xiàn)M11.5講授、討論1作業(yè)、自學(xué)82.32.3線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)線性表的鏈接存儲結(jié)構(gòu)(單鏈表)，單鏈表的實現(xiàn)M11.5講授、討論1作業(yè)、自學(xué)92.42.4順序表和鏈表的比較及應(yīng)用舉例順序表的應(yīng)用舉例(大整數(shù)求和)，單鏈表的應(yīng)用舉例(一元多項式求和)M11講授、討論1作業(yè)、自學(xué)10實驗2實驗2：線性表應(yīng)用實驗設(shè)計順序表模板類程序并測試運(yùn)行，應(yīng)用順序表實現(xiàn)大整數(shù)求和，設(shè)計單鏈表模板類程序并測試運(yùn)行，應(yīng)用單鏈表實現(xiàn)一元多項式求和M2,M3,M44實驗、上機(jī)4實驗、上機(jī)、撰寫報告11第3章第3章棧和隊列本章重點(diǎn)難點(diǎn)：棧和隊列的操作特性、棧和隊列模板類的設(shè)計與實現(xiàn)////123.13.1棧棧的邏輯結(jié)構(gòu)，棧的順序存儲結(jié)構(gòu)及實現(xiàn)，棧的鏈接存儲結(jié)構(gòu)及實現(xiàn)M11講授、討論1作業(yè)、自學(xué)133.23.2隊列隊列的邏輯結(jié)構(gòu)，隊列的順序存儲結(jié)構(gòu)及實現(xiàn)，隊列的鏈接存儲結(jié)構(gòu)及實現(xiàn)M11講授、討論1作業(yè)、自學(xué)143.33.3棧和隊列的比較/M11講授、討論1作業(yè)、自學(xué)15實驗3實驗3：棧和隊列應(yīng)用實驗設(shè)計順序棧模板類程序并測試運(yùn)行，設(shè)計鏈棧模板類程序并測試運(yùn)行，設(shè)計循環(huán)隊列模板類程序并測試運(yùn)行，設(shè)計鏈隊列模板類程序并測試運(yùn)行M2,M3,M42實驗、上機(jī)2實驗、上機(jī)、撰寫報告16第4章第4章字符串和多維數(shù)組本章重點(diǎn)難點(diǎn)：模式匹配算法、特殊矩陣壓縮存儲后存儲位置的計算////174.14.1字符串字符串的定義，字符串的存儲結(jié)構(gòu)，模式匹配M11講授、討論1作業(yè)、自學(xué)184.24.2多維數(shù)組數(shù)組的定義，數(shù)組的存儲結(jié)構(gòu)與尋址M11講授、討論1作業(yè)、自學(xué)194.34.3矩陣的壓縮存儲對稱矩陣的壓縮存儲，三角矩陣的壓縮存儲，對角矩陣的壓縮存儲，稀疏矩陣的壓縮存儲M11講授、討論1作業(yè)、自學(xué)204.44.4應(yīng)用舉例字符串的應(yīng)用舉例(凱撒密碼)，數(shù)組的應(yīng)用舉例(幻方)M11講授、討論1作業(yè)、自學(xué)21實驗4實驗4：字符串和多維數(shù)組應(yīng)用實驗編程實現(xiàn)BF算法程序、編程實現(xiàn)凱撒加密算法程序，掌握二維數(shù)組、三維數(shù)組的遍歷操作，設(shè)計對稱矩陣、三角矩陣、對角矩陣的壓縮存儲程序，設(shè)計稀疏矩陣的三元組順序表存儲程序，設(shè)計奇數(shù)階幻方算法程序M2,M3,M42實驗、上機(jī)2實驗、上機(jī)、撰寫報告22第5章第5章查找技術(shù)本章重點(diǎn)難點(diǎn)：折半查找、查找算法的性能分析////235.15.1概述查找的基本概念M10.5講授、討論0.5作業(yè)、自學(xué)245.25.2線性表的查找技術(shù)順序查找，折半查找M11.5講授、討論1.5作業(yè)、自學(xué)255.35.3常見查找算法的性能分析/M11講授、討論1作業(yè)、自學(xué)26實驗5實驗5：查找技術(shù)應(yīng)用實驗編程實現(xiàn)順序表的順序查找算法程序，編程實現(xiàn)折半查找非遞歸算法程序，編程實現(xiàn)折半查找遞歸算法程序M2,M3,M42實驗、上機(jī)2實驗、上機(jī)、撰寫報告27第6章第6章排序技術(shù)本章重點(diǎn)難點(diǎn)：排序算法的性能分析////286.16.1概述排序的基本概念M10.5講授、討論0.5作業(yè)、自學(xué)296.262交換排序與選擇排序冒泡排序，選擇排序M11.5講授、討論1.5作業(yè)、自學(xué)306.36.3常見排序算法的性能分析/M11講授、討論1作業(yè)、自學(xué)31實驗6實驗6：排序技術(shù)應(yīng)用實驗編程實現(xiàn)起泡排序算法程序，編程實現(xiàn)選擇排序算法程序M2,M3,M42實驗、上機(jī)2實驗、上機(jī)、撰寫報告32第7章第7章樹和二叉樹本章重點(diǎn)難點(diǎn)：二叉樹的邏輯結(jié)構(gòu)、二叉樹的構(gòu)造方法////337.17.1樹的邏輯結(jié)構(gòu)樹的定義和基本術(shù)語，樹的抽象數(shù)據(jù)類型定義，樹的遍歷操作M10.5講授、討論1作業(yè)、自學(xué)347.27.2樹的存儲結(jié)構(gòu)雙親表示法，孩子表示法，雙親孩子表示法，孩子兄弟表示法M10.5講授、討論1作業(yè)、自學(xué)357.37.3二叉樹的邏輯結(jié)構(gòu)二叉樹的定義，二叉樹的基本性質(zhì)，二叉樹的抽象數(shù)據(jù)類型定義，二叉樹的遍歷操作M11講授、討論1作業(yè)、自學(xué)367.47.4二叉樹的順序存儲結(jié)構(gòu)及實現(xiàn)/M11講授、討論1作業(yè)、自學(xué)四、考核方式序號考核環(huán)節(jié)操作細(xì)節(jié)總評占比1平時作業(yè)1.每周布置2-3道題目，平均每次課1道題以上。2.成績采用百分制，根據(jù)作業(yè)完成準(zhǔn)確性、是否按時上交、是否獨(dú)立完成評分。3.主要考核學(xué)生對數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)知識的掌握能力，學(xué)生綜合運(yùn)用所學(xué)知識分析問題、解決問題的能力；題型主要有問題分析、算法設(shè)計和程序編寫等。10%2實驗1.本課程設(shè)置有12學(xué)時的上機(jī)實驗，分6次進(jìn)行，每次2學(xué)時。2.成績采用百分制，根據(jù)實驗預(yù)習(xí)情況、實驗完成情況和實驗總結(jié)報告情況評分。3.主要考核學(xué)生對數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)知識的應(yīng)用能力，針對實際編程任務(wù)選擇合適的數(shù)據(jù)結(jié)構(gòu)，設(shè)計和開發(fā)合理的算法程序求解問題。30%3考勤隨機(jī)點(diǎn)名、刷卡點(diǎn)名等。5%4課堂表現(xiàn)隨機(jī)檢查學(xué)生上課精神狀態(tài)、回答問題情況。5%5期末考試1.閉卷考試，成績采用百分制，卷面成績總分100分。2.主要考核學(xué)生對數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)知識的掌握能力，學(xué)生綜合運(yùn)用所學(xué)知識分析問題、解決問題的能力，題型主要有填空題、簡答題、分析題、算法設(shè)計題、程序編寫題等。50%五、評分細(xì)則序號課程目標(biāo)考核環(huán)節(jié)大致占比評分等級1M1平時作業(yè)20%A-獨(dú)立思考、按時完成，書寫格式規(guī)范，步驟完整，答案正確。B-獨(dú)立思考、按時完成，書寫格式比較規(guī)范，步驟比較完整，答案正確。C-基本能獨(dú)立思考、按時完成，書寫格式基本規(guī)范，步驟基本完整，答案基本正確。D-作業(yè)抄襲，未能按時完成，書寫格式不規(guī)范，步驟不完整，答案不正確。2M1考勤10%M-缺勤2次以內(nèi)。N-缺勤3次及以上。3M1課堂表現(xiàn)10%M-精神面貌好，積極回答問題，積極參與課堂討論。N-精神面貌較差，回答問題不積極，很少參與課堂討論。4M1期末考試60%（見試卷評分標(biāo)準(zhǔn)）5M2實驗50%A-實驗預(yù)習(xí)工作到位，實驗完成的好，實驗總結(jié)報告內(nèi)容全面、認(rèn)識深刻。B-實驗預(yù)習(xí)工作較到位，實驗完成的較好，實驗報告內(nèi)容較全面、認(rèn)識到位。C-實驗預(yù)習(xí)工作一般，能夠完成實驗，實驗報告內(nèi)容一般、認(rèn)識一般。D-沒有做實驗預(yù)習(xí)，不能夠完成實驗，實驗報告無價值。6M2期末考試50%（見試卷評分標(biāo)準(zhǔn)）7M3實驗50%A-實驗預(yù)習(xí)工作到位，實驗完成的好，實驗總結(jié)報告內(nèi)容全面、認(rèn)識深刻。B-實驗預(yù)習(xí)工作較到位，實驗完成的較好，實驗報告內(nèi)容較全面、認(rèn)識到位。C-實驗預(yù)習(xí)工作一般，能夠完成實驗，實驗報告內(nèi)容一般、認(rèn)識一般。D-沒有做實驗預(yù)習(xí)，不能夠完成實驗，實驗報告無價值。8M3期末考試50%（見試卷評分標(biāo)準(zhǔn)）9M4實驗100%A-實驗預(yù)習(xí)工作到位，實驗完成的好，實驗總結(jié)報告內(nèi)容全面、認(rèn)識深刻。B-實驗預(yù)習(xí)工作較到位，實驗完成的較好，實驗報告內(nèi)容較全面、認(rèn)識到位。C-實驗預(yù)習(xí)工作一般，能夠完成實驗，實驗報告內(nèi)容一般、認(rèn)識一般。D-沒有做實驗預(yù)習(xí)，不能夠完成實驗，實驗報告無價值。評分等級說明：[A,B,C,D,E]=[90-100,80-89,70-79,60-69,0-59];[A,B,C,D]=[90-100,75-89,60-74,0-59];[A,B,C]=[90-100,75-89,60-74,0-59];[M,N]