《數(shù)據(jù)結(jié)構(gòu)與算法實(shí)驗(yàn)》教學(xué)大綱一、課程基本信息課程名稱數(shù)據(jù)結(jié)構(gòu)與算法實(shí)驗(yàn)DataStructureandAlgorithmExperiment課程編碼CST310411015開(kāi)課院部計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院課程團(tuán)隊(duì)數(shù)據(jù)結(jié)構(gòu)與算法教學(xué)團(tuán)隊(duì)學(xué)分1.5課內(nèi)學(xué)時(shí)36講授0實(shí)驗(yàn)36上機(jī)0實(shí)踐0課外學(xué)時(shí)36適用專業(yè)軟件工程授課語(yǔ)言中文先修課程程序設(shè)計(jì)（C/C++）、數(shù)據(jù)結(jié)構(gòu)與算法課程簡(jiǎn)介（必修）《數(shù)據(jù)結(jié)構(gòu)與算法實(shí)驗(yàn)》是《數(shù)據(jù)結(jié)構(gòu)與算法》課程的后續(xù)課程，是軟件工程專業(yè)的必修專業(yè)基礎(chǔ)課。該課程的目標(biāo)是：在完成“數(shù)據(jù)結(jié)構(gòu)與算法”課程要求的基本編碼實(shí)習(xí)題目（基本為驗(yàn)證性實(shí)習(xí)題目）的基礎(chǔ)上，進(jìn)行數(shù)據(jù)結(jié)構(gòu)和算法的高級(jí)進(jìn)階實(shí)習(xí)，進(jìn)一步加深對(duì)數(shù)據(jù)結(jié)構(gòu)和算法重要性的認(rèn)識(shí)，訓(xùn)練數(shù)據(jù)結(jié)構(gòu)和算法的相關(guān)知識(shí)的應(yīng)用能力，進(jìn)而提升利用計(jì)算機(jī)求解復(fù)雜問(wèn)題的能力并建立正確的人生觀和價(jià)值觀。實(shí)驗(yàn)課要完成一定數(shù)量的、較復(fù)雜問(wèn)題的求解。實(shí)習(xí)在實(shí)習(xí)平臺(tái)上完成，共設(shè)置了一定數(shù)量的題目。這些題目的求解會(huì)用到數(shù)據(jù)結(jié)構(gòu)與算法課程要求掌握的知識(shí)點(diǎn)，如數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)、算法、效率優(yōu)化等。題目完成后在實(shí)習(xí)平臺(tái)提交，平臺(tái)根據(jù)程序（數(shù)據(jù)結(jié)構(gòu)+算法）通過(guò)測(cè)試用例情況評(píng)價(jià)對(duì)數(shù)據(jù)結(jié)構(gòu)和算法的掌握情況并計(jì)分?！癉atastructureandalgorithmexperiment”isafollow-upcourseofDataStructureandAlgorithms.Itisacompulsorybasiccourseforsoftwareengineering.Thegoalofthiscourseistocarryoutadvancedpracticeofdatastructureandalgorithmonthebasisofcompletingthebasiccodingpracticesubjectrequiredbythecourse"DataStructureandAlgorithms"(basicallytheconfirmatorypracticetopic),tofurtherdeepentheunderstandingoftheimportanceofdatastructureandalgorithm,totraintheapplicationabilityofrelevantknowledgeofdatastructureandalgorithm,andtofurtherenhancetheutilizationofcomputers.Abilitytosolvecomplexproblems.Acertainnumberofcomplexproblemsshouldbesolvedintheexperimentclass.Theexperimentwascompletedontheexperimentalplatformandsomesubjectsweresetup.ThesolutionoftheseproblemswillusetheknowledgepointsrequiredbythecourseofDataStructureandAlgorithms,suchasdatastoragestructure,algorithm,etc.Afterthecompletionofthetopic,itissubmittedtothepracticeplatform.Theplatformevaluatesthemasteryofthedatastructureandalgorithmthroughtestcasesaccordingtotheprogram(datastructure+algorithm)andscoresthem.負(fù)責(zé)人大綱執(zhí)筆人審核人二、課程目標(biāo)序號(hào)代號(hào)課程目標(biāo)OBE畢業(yè)要求指標(biāo)點(diǎn)任務(wù)自選1M1目標(biāo)1：針對(duì)軟件系統(tǒng)的功能模塊能夠提出合理的解決方案，以邏輯結(jié)構(gòu)為基礎(chǔ)獨(dú)立完成存儲(chǔ)結(jié)構(gòu)和算法設(shè)計(jì)，并運(yùn)用軟件開(kāi)發(fā)技術(shù)完成詳細(xì)設(shè)計(jì)與實(shí)現(xiàn)。是3.32M2目標(biāo)2：針對(duì)實(shí)習(xí)內(nèi)容，能夠基于軟件工程專業(yè)知識(shí)，在分析數(shù)據(jù)特征和算法要求的前提下，以邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)為基礎(chǔ)設(shè)計(jì)算法，選擇研究路線，設(shè)計(jì)實(shí)驗(yàn)方案。能夠結(jié)合國(guó)家最新政策法規(guī)、新聞熱點(diǎn)等實(shí)時(shí)信息，思考本課程對(duì)國(guó)家信息產(chǎn)業(yè)的意義，設(shè)計(jì)實(shí)驗(yàn)題目。是4.13M3目標(biāo)3：能夠根據(jù)實(shí)驗(yàn)方案構(gòu)建實(shí)驗(yàn)系統(tǒng)，安全的開(kāi)展實(shí)驗(yàn)，正確地采集實(shí)驗(yàn)數(shù)據(jù)。是4.24M4目標(biāo)4：能對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行分析和解釋，并通過(guò)信息綜合得到合理有效的驗(yàn)證結(jié)論。是4.35M5目標(biāo)5：能夠針對(duì)具體的對(duì)象，開(kāi)發(fā)或選用滿足特定需求的現(xiàn)代軟件工具，模擬和預(yù)測(cè)專業(yè)問(wèn)題，并能夠分析結(jié)論的局限性。是5.3三、課程內(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題1.范圍查詢(Range)數(shù)軸上有n個(gè)點(diǎn)，對(duì)于任一閉區(qū)間[a,b]，試計(jì)算落在其內(nèi)的點(diǎn)數(shù)。/3實(shí)驗(yàn)//2第2題2.祖瑪(Zuma)祖瑪是一款曾經(jīng)風(fēng)靡全球的游戲，其玩法是：在一條軌道上初始排列著若干個(gè)彩色珠子，其中任意三個(gè)相鄰的珠子不會(huì)完全同色。此后，你可以發(fā)射珠子到軌道上并加入原有序列中。一旦有三個(gè)或更多同色的珠子變成相鄰，它們就會(huì)立即消失。這類消除現(xiàn)象可能會(huì)連鎖式發(fā)生，其間你將暫時(shí)不能發(fā)射珠子。/3實(shí)驗(yàn)//3第3題3.燈塔(LightHouse)海上有許多燈塔，為過(guò)路船只照明。對(duì)于任何一組給定的燈塔，請(qǐng)計(jì)算出其中有多少對(duì)燈塔能夠照亮彼此。/3實(shí)驗(yàn)//4第4題4.列車調(diào)度(Train)設(shè)某列車由編號(hào)依次為{1,2,...,n}的n節(jié)車廂組成。調(diào)度員希望知道，按照以上交通規(guī)則，這些車廂能否以{a1,a2,...,an}的次序，重新排列后從B端駛出。如果可行，應(yīng)該以怎樣的次序操作?/3實(shí)驗(yàn)//5第5題5.真二叉樹(shù)重構(gòu)(ProperRebuild)給定二叉樹(shù)的先序遍歷序列和后序遍歷序列，并不能確定唯一確定該二叉樹(shù)。/3實(shí)驗(yàn)//6第6題6.旅行商(TSP)Shrek是一個(gè)大山里的郵遞員，每天負(fù)責(zé)給所在地區(qū)的n個(gè)村莊派發(fā)信件。但杯具的是，由于道路狹窄，年久失修，村莊間的道路都只能單向通過(guò)，甚至有些村莊無(wú)法從任意一個(gè)村莊到達(dá)。這樣我們只能希望盡可能多的村莊可以收到投遞的信件。Shrek希望知道如何選定一個(gè)村莊A作為起點(diǎn)（我們將他空投到該村莊），依次經(jīng)過(guò)盡可能多的村莊，路途中的每個(gè)村莊都經(jīng)過(guò)僅一次，最終到達(dá)終點(diǎn)村莊B，完成整個(gè)送信過(guò)程。這個(gè)任務(wù)交給你來(lái)完成。/3實(shí)驗(yàn)//7第7題7.無(wú)線廣播(Broadcast)某廣播公司要在一個(gè)地區(qū)架設(shè)無(wú)線廣播發(fā)射裝置。該地區(qū)共有n個(gè)小鎮(zhèn)，每個(gè)小鎮(zhèn)都要安裝一臺(tái)發(fā)射機(jī)并播放各自的節(jié)目。/3實(shí)驗(yàn)//8第8題8.平均氣溫(Temperature)某氣象臺(tái)每天都要從遍布于各地的觀察站采集氣溫?cái)?shù)據(jù)，并通過(guò)互聯(lián)網(wǎng)為遠(yuǎn)程用戶提供統(tǒng)計(jì)查詢服務(wù)。/3實(shí)驗(yàn)//9第9題9.重名剔除(Deduplicate)Epicure先生正在編撰一本美食百科全書(shū)。為此，他已從眾多的同好者那里搜集到了一份冗長(zhǎng)的美食提名清單。既然源自多人之手，其中自然不乏重復(fù)的提名，故必須予以篩除。Epicure先生因此登門(mén)求助，并認(rèn)定此事對(duì)你而言不過(guò)是“一碟小菜”，相信你不會(huì)錯(cuò)過(guò)在美食界揚(yáng)名立萬(wàn)的這一良機(jī)/3實(shí)驗(yàn)//10第10題10.玩具(Toy)ZC神自小就是這方面的天才，他往往是一只手還沒(méi)揩干鼻涕，另一只手已經(jīng)迅速地將處于任意狀態(tài)的玩具復(fù)原至如圖(a)所示的初始狀態(tài)。物質(zhì)極其匱乏的當(dāng)年，ZC神只有一個(gè)這樣的玩具；物質(zhì)極大豐富的今天，你已擁有多個(gè)處于不同狀態(tài)的玩具?，F(xiàn)在，就請(qǐng)將它們?nèi)繌?fù)原吧。/3實(shí)驗(yàn)//11第11題11.任務(wù)調(diào)度(Schedule)根據(jù)初始優(yōu)先級(jí)設(shè)置，按照調(diào)度原則，預(yù)測(cè)一批計(jì)算任務(wù)的執(zhí)行序列。/3實(shí)驗(yàn)//12第12題12.循環(huán)移位(Cycle)所謂循環(huán)移位是指。一個(gè)字符串的首字母移到末尾,其他字符的次序保持不變。比如ABCD經(jīng)過(guò)一次循環(huán)移位后變成BCDA給定兩個(gè)字符串，判斷它們是不是可以通過(guò)若干次循環(huán)移位得到彼此/3實(shí)驗(yàn)//四、考核方式序號(hào)考核環(huán)節(jié)操作細(xì)節(jié)總評(píng)占比1實(shí)驗(yàn)1.本課程36個(gè)學(xué)時(shí)實(shí)驗(yàn)，共12次實(shí)驗(yàn)。2.成績(jī)采用百分制，根據(jù)實(shí)驗(yàn)完成情況評(píng)分。3.考核學(xué)生對(duì)數(shù)據(jù)結(jié)構(gòu)與算法知識(shí)的應(yīng)用能力，針對(duì)12個(gè)獨(dú)立的問(wèn)題，能夠根據(jù)題目功能和性能要求確定設(shè)計(jì)目標(biāo)，從技術(shù)角度優(yōu)選解決方案獲得有效結(jié)果。90%2考勤隨機(jī)點(diǎn)名、刷卡點(diǎn)名等5%3課堂表現(xiàn)隨機(jī)檢查學(xué)生上課精神狀態(tài)、回答問(wèn)題情況5%五、評(píng)分細(xì)則序號(hào)課程目標(biāo)考核環(huán)節(jié)大致占比評(píng)分等級(jí)1M1實(shí)驗(yàn)90%A-實(shí)驗(yàn)過(guò)程中認(rèn)真完成實(shí)驗(yàn)要求，得到正確的實(shí)驗(yàn)結(jié)果，實(shí)驗(yàn)報(bào)告格式正確，步驟敘述清楚，正確分析實(shí)驗(yàn)數(shù)據(jù)，從技術(shù)角度優(yōu)選解決方案獲得有效結(jié)論B-實(shí)驗(yàn)過(guò)程中認(rèn)真完成實(shí)驗(yàn)要求，得到正確的實(shí)驗(yàn)結(jié)果，實(shí)驗(yàn)報(bào)告格式正確，步驟敘述比較清楚，正確分析實(shí)驗(yàn)數(shù)據(jù)，從技術(shù)角度優(yōu)選解決方案獲得比較有效的結(jié)論C-實(shí)驗(yàn)過(guò)程中認(rèn)真完成實(shí)驗(yàn)要求，不能得到正確的實(shí)驗(yàn)結(jié)果，實(shí)驗(yàn)報(bào)告格式正確，步驟敘述清楚，沒(méi)有正確分析實(shí)驗(yàn)數(shù)據(jù)，但是結(jié)合理論分析可以從技術(shù)角度優(yōu)選解決方案獲得有效的結(jié)論D-實(shí)驗(yàn)過(guò)程中不能完成實(shí)驗(yàn)要求，不能得到正確的實(shí)驗(yàn)結(jié)果，不能從技術(shù)角度優(yōu)選解決方案獲得有效的結(jié)論2M1考勤5%A-全勤B-缺勤1次C-缺勤2-3次D-缺勤3次以上3M1課堂表現(xiàn)5%A-精神狀態(tài)飽滿，回答問(wèn)題準(zhǔn)確B-精神狀態(tài)一般，問(wèn)題回答一般4M2實(shí)驗(yàn)90%A-實(shí)驗(yàn)過(guò)程中認(rèn)真完成實(shí)驗(yàn)要求，得到正確的實(shí)驗(yàn)結(jié)果，實(shí)驗(yàn)報(bào)告格式正確，步驟敘述清楚，正確分析實(shí)驗(yàn)數(shù)據(jù)，從技術(shù)角度優(yōu)選解決方案獲得有效結(jié)論B-實(shí)驗(yàn)過(guò)程中認(rèn)真完成實(shí)驗(yàn)要求，得到正確的實(shí)驗(yàn)結(jié)果，實(shí)驗(yàn)報(bào)告格式正確，步驟敘述比較清楚，正確分析實(shí)驗(yàn)數(shù)據(jù)，從技術(shù)角度優(yōu)選解決方案獲得比較有效的結(jié)論C-實(shí)驗(yàn)過(guò)程中認(rèn)真完成實(shí)驗(yàn)要求，不能得到正確的實(shí)驗(yàn)結(jié)果，實(shí)驗(yàn)報(bào)告格式正確，步驟敘述清楚，沒(méi)有正確分析實(shí)驗(yàn)數(shù)據(jù)，但是結(jié)合理論分析可以從技術(shù)角度優(yōu)選解決方案獲得有效的結(jié)論D-實(shí)驗(yàn)過(guò)程中不能完成實(shí)驗(yàn)要求，不能得到正確的實(shí)驗(yàn)結(jié)果，不能從技術(shù)角度優(yōu)選解決方案獲得有效的結(jié)論5M2考勤5%A-全勤B-缺勤1次C-缺勤2-3次D-缺勤3次以上6M2課堂表現(xiàn)5%A-精神狀態(tài)飽滿，回答問(wèn)題準(zhǔn)確B-精神狀態(tài)一般，問(wèn)題回答一般7M3實(shí)驗(yàn)90%A-實(shí)驗(yàn)過(guò)程中認(rèn)真完成實(shí)驗(yàn)要求，得到正確的實(shí)驗(yàn)結(jié)果，實(shí)驗(yàn)報(bào)告格式正確，步驟敘述清楚，正確分析實(shí)驗(yàn)數(shù)據(jù)，從技術(shù)角度優(yōu)選解決方案獲得有效結(jié)論B-實(shí)驗(yàn)過(guò)程中認(rèn)真完成實(shí)驗(yàn)要求，得到正確的實(shí)驗(yàn)結(jié)果，實(shí)驗(yàn)報(bào)告格式正確，步驟敘述比較清楚，正確分析實(shí)驗(yàn)數(shù)據(jù)，從技術(shù)角度優(yōu)選解決方案獲得比較有效的結(jié)論C-實(shí)驗(yàn)過(guò)程中認(rèn)真完成實(shí)驗(yàn)要求，不能得到正確的實(shí)驗(yàn)結(jié)果，實(shí)驗(yàn)報(bào)告格式正確，步驟敘述清楚，沒(méi)有正確分析實(shí)驗(yàn)數(shù)據(jù)，但是結(jié)合理論分析可以從技術(shù)角度優(yōu)選解決方案獲得有效的結(jié)論D-實(shí)驗(yàn)過(guò)程中不能完成實(shí)驗(yàn)要求，不能得到正確的實(shí)驗(yàn)結(jié)果，不能從技術(shù)角度優(yōu)選解決方案獲得有效的結(jié)論8M3考勤5%A-全勤B-缺勤1次C-缺勤2-3次D-缺勤3次以上9M3課堂表現(xiàn)5%A-精神狀態(tài)飽滿，回答問(wèn)題準(zhǔn)確B-精神狀態(tài)一般，問(wèn)題回答一般10M4實(shí)驗(yàn)90%A-實(shí)驗(yàn)過(guò)程中認(rèn)真完成實(shí)驗(yàn)要求，得到正確的實(shí)驗(yàn)結(jié)果，實(shí)驗(yàn)報(bào)告格式正確，步驟敘述清楚，正確分析實(shí)驗(yàn)數(shù)據(jù)，從技術(shù)角度優(yōu)選解決方案獲得有效結(jié)論B-實(shí)驗(yàn)過(guò)程中認(rèn)真完成實(shí)驗(yàn)要求，得到正確的實(shí)驗(yàn)結(jié)果，實(shí)驗(yàn)報(bào)告格式正確，步驟敘述比較清楚，正確分析實(shí)驗(yàn)數(shù)據(jù)，從技術(shù)角度優(yōu)選解決方案獲得比較有效的結(jié)論C-實(shí)驗(yàn)過(guò)程中認(rèn)真完成實(shí)驗(yàn)要求，不能得到正確的實(shí)驗(yàn)結(jié)果，實(shí)驗(yàn)報(bào)告格式正確，步驟敘述清楚，沒(méi)有正確分析實(shí)驗(yàn)數(shù)據(jù)，但是結(jié)合理論分析可以從技術(shù)角度優(yōu)選解決方案獲得有效的結(jié)論D-實(shí)驗(yàn)過(guò)程中不能完成實(shí)驗(yàn)要求，不能得到正確的實(shí)驗(yàn)結(jié)果，不能從技術(shù)角度優(yōu)選解決方案獲得有效的結(jié)論11M4考勤5%A-全勤B-缺勤1次C-缺勤2-3次D-缺勤3次以上12M4課堂表現(xiàn)5%A-精神狀態(tài)飽滿，回答問(wèn)題準(zhǔn)確B-精神狀態(tài)一般，問(wèn)題回答一般13M5實(shí)驗(yàn)90%A-實(shí)驗(yàn)過(guò)程中認(rèn)真完成實(shí)驗(yàn)要求，得到正確的實(shí)驗(yàn)結(jié)果，實(shí)驗(yàn)報(bào)告格式正確，步驟敘述清楚，正確分析實(shí)驗(yàn)數(shù)據(jù)，從技術(shù)角度優(yōu)選解決方案獲得有效結(jié)論B-實(shí)驗(yàn)過(guò)程中認(rèn)真完成實(shí)驗(yàn)要求，得到正確的實(shí)驗(yàn)結(jié)果，實(shí)驗(yàn)報(bào)告格式正確，步驟敘述比較清楚，正確分析實(shí)驗(yàn)數(shù)據(jù)，從技術(shù)角度優(yōu)選解決方案獲得比較有效的結(jié)論C-實(shí)驗(yàn)過(guò)程中認(rèn)真完成實(shí)驗(yàn)要求，不能得到正確的實(shí)驗(yàn)結(jié)果，實(shí)驗(yàn)報(bào)告格式正確，步驟敘述清楚，沒(méi)有正確分析實(shí)驗(yàn)數(shù)據(jù)，但是結(jié)合理論分析可以從技術(shù)角度優(yōu)選解決方案獲得有效的結(jié)論D-實(shí)驗(yàn)過(guò)程中不能完成實(shí)驗(yàn)要求，不能得到正確的實(shí)驗(yàn)結(jié)果，不能從技術(shù)角度優(yōu)選解決方案獲得有效的結(jié)論14M5考勤5%A-全勤B-缺勤1次C-缺勤