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

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