《数据结构与算法实验》课程教学大纲

《数据结构与算法实验》教学大纲一、课程基本信息课程名称数据结构与算法实验DataStructureandAlgorithmExperiment课程编码CST310411015开课院部计算机科学与技术学院课程团队数据结构与算法教学团队学分1.5课内学时36讲授0实验36上机0实践0课外学时36适用专业软件工程授课语言中文先修课程程序设计（C/C++）、数据结构与算法课程简介（必修）《数据结构与算法实验》是《数据结构与算法》课程的后续课程，是软件工程专业的必修专业基础课。该课程的目标是：在完成“数据结构与算法”课程要求的基本编码实习题目（基本为验证性实习题目）的基础上，进行数据结构和算法的高级进阶实习，进一步加深对数据结构和算法重要性的认识，训练数据结构和算法的相关知识的应用能力，进而提升利用计算机求解复杂问题的能力并建立正确的人生观和价值观。实验课要完成一定数量的、较复杂问题的求解。实习在实习平台上完成，共设置了一定数量的题目。这些题目的求解会用到数据结构与算法课程要求掌握的知识点，如数据的存储结构、算法、效率优化等。题目完成后在实习平台提交，平台根据程序（数据结构+算法）通过测试用例情况评价对数据结构和算法的掌握情况并计分。“Datastructureandalgorithmexperiment”isafollow-upcourseofDataStructureandAlgorithms.Itisacompulsorybasiccourseforsoftwareengineering.Thegoalofthiscourseistocarryoutadvancedpracticeofdatastructureandalgorithmonthebasisofcompletingthebasiccodingpracticesubjectrequiredbythecourse"DataStructureandAlgorithms"(basicallytheconfirmatorypracticetopic),tofurtherdeepentheunderstandingoftheimportanceofdatastructureandalgorithm,totraintheapplicationabilityofrelevantknowledgeofdatastructureandalgorithm,andtofurtherenhancetheutilizationofcomputers.Abilitytosolvecomplexproblems.Acertainnumberofcomplexproblemsshouldbesolvedintheexperimentclass.Theexperimentwascompletedontheexperimentalplatformandsomesubjectsweresetup.ThesolutionoftheseproblemswillusetheknowledgepointsrequiredbythecourseofDataStructureandAlgorithms,suchasdatastoragestructure,algorithm,etc.Afterthecompletionofthetopic,itissubmittedtothepracticeplatform.Theplatformevaluatesthemasteryofthedatastructureandalgorithmthroughtestcasesaccordingtotheprogram(datastructure+algorithm)andscoresthem.负责人大纲执笔人审核人二、课程目标序号代号课程目标OBE毕业要求指标点任务自选1M1目标1：针对软件系统的功能模块能够提出合理的解决方案，以逻辑结构为基础独立完成存储结构和算法设计，并运用软件开发技术完成详细设计与实现。是3.32M2目标2：针对实习内容，能够基于软件工程专业知识，在分析数据特征和算法要求的前提下，以逻辑结构与存储结构为基础设计算法，选择研究路线，设计实验方案。能够结合国家最新政策法规、新闻热点等实时信息，思考本课程对国家信息产业的意义，设计实验题目。是4.13M3目标3：能够根据实验方案构建实验系统，安全的开展实验，正确地采集实验数据。是4.24M4目标4：能对实验结果进行分析和解释，并通过信息综合得到合理有效的验证结论。是4.35M5目标5：能够针对具体的对象，开发或选用满足特定需求的现代软件工具，模拟和预测专业问题，并能够分析结论的局限性。是5.3三、课程内容序号章节号标题课程内容/重难点支撑课程目标课内学时教学方式课外学时课外环节1第1题1.范围查询(Range)数轴上有n个点，对于任一闭区间[a,b]，试计算落在其内的点数。/3实验//2第2题2.祖玛(Zuma)祖玛是一款曾经风靡全球的游戏，其玩法是：在一条轨道上初始排列着若干个彩色珠子，其中任意三个相邻的珠子不会完全同色。此后，你可以发射珠子到轨道上并加入原有序列中。一旦有三个或更多同色的珠子变成相邻，它们就会立即消失。这类消除现象可能会连锁式发生，其间你将暂时不能发射珠子。/3实验//3第3题3.灯塔(LightHouse)海上有许多灯塔，为过路船只照明。对于任何一组给定的灯塔，请计算出其中有多少对灯塔能够照亮彼此。/3实验//4第4题4.列车调度(Train)设某列车由编号依次为{1,2,...,n}的n节车厢组成。调度员希望知道，按照以上交通规则，这些车厢能否以{a1,a2,...,an}的次序，重新排列后从B端驶出。如果可行，应该以怎样的次序操作?/3实验//5第5题5.真二叉树重构(ProperRebuild)给定二叉树的先序遍历序列和后序遍历序列，并不能确定唯一确定该二叉树。/3实验//6第6题6.旅行商(TSP)Shrek是一个大山里的邮递员，每天负责给所在地区的n个村庄派发信件。但杯具的是，由于道路狭窄，年久失修，村庄间的道路都只能单向通过，甚至有些村庄无法从任意一个村庄到达。这样我们只能希望尽可能多的村庄可以收到投递的信件。Shrek希望知道如何选定一个村庄A作为起点（我们将他空投到该村庄），依次经过尽可能多的村庄，路途中的每个村庄都经过仅一次，最终到达终点村庄B，完成整个送信过程。这个任务交给你来完成。/3实验//7第7题7.无线广播(Broadcast)某广播公司要在一个地区架设无线广播发射装置。该地区共有n个小镇，每个小镇都要安装一台发射机并播放各自的节目。/3实验//8第8题8.平均气温(Temperature)某气象台每天都要从遍布于各地的观察站采集气温数据，并通过互联网为远程用户提供统计查询服务。/3实验//9第9题9.重名剔除(Deduplicate)Epicure先生正在编撰一本美食百科全书。为此，他已从众多的同好者那里搜集到了一份冗长的美食提名清单。既然源自多人之手，其中自然不乏重复的提名，故必须予以筛除。Epicure先生因此登门求助，并认定此事对你而言不过是“一碟小菜”，相信你不会错过在美食界扬名立万的这一良机/3实验//10第10题10.玩具(Toy)ZC神自小就是这方面的天才，他往往是一只手还没揩干鼻涕，另一只手已经迅速地将处于任意状态的玩具复原至如图(a)所示的初始状态。物质极其匮乏的当年，ZC神只有一个这样的玩具；物质极大丰富的今天，你已拥有多个处于不同状态的玩具。现在，就请将它们全部复原吧。/3实验//11第11题11.任务调度(Schedule)根据初始优先级设置，按照调度原则，预测一批计算任务的执行序列。/3实验//12第12题12.循环移位(Cycle)所谓循环移位是指。一个字符串的首字母移到末尾,其他字符的次序保持不变。比如ABCD经过一次循环移位后变成BCDA给定两个字符串，判断它们是不是可以通过若干次循环移位得到彼此/3实验//四、考核方式序号考核环节操作细节总评占比1实验1.本课程36个学时实验，共12次实验。2.成绩采用百分制，根据实验完成情况评分。3.考核学生对数据结构与算法知识的应用能力，针对12个独立的问题，能够根据题目功能和性能要求确定设计目标，从技术角度优选解决方案获得有效结果。90%2考勤随机点名、刷卡点名等5%3课堂表现随机检查学生上课精神状态、回答问题情况5%五、评分细则序号课程目标考核环节大致占比评分等级1M1实验90%A-实验过程中认真完成实验要求，得到正确的实验结果，实验报告格式正确，步骤叙述清楚，正确分析实验数据，从技术角度优选解决方案获得有效结论B-实验过程中认真完成实验要求，得到正确的实验结果，实验报告格式正确，步骤叙述比较清楚，正确分析实验数据，从技术角度优选解决方案获得比较有效的结论C-实验过程中认真完成实验要求，不能得到正确的实验结果，实验报告格式正确，步骤叙述清楚，没有正确分析实验数据，但是结合理论分析可以从技术角度优选解决方案获得有效的结论D-实验过程中不能完成实验要求，不能得到正确的实验结果，不能从技术角度优选解决方案获得有效的结论2M1考勤5%A-全勤B-缺勤1次C-缺勤2-3次D-缺勤3次以上3M1课堂表现5%A-精神状态饱满，回答问题准确B-精神状态一般，问题回答一般4M2实验90%A-实验过程中认真完成实验要求，得到正确的实验结果，实验报告格式正确，步骤叙述清楚，正确分析实验数据，从技术角度优选解决方案获得有效结论B-实验过程中认真完成实验要求，得到正确的实验结果，实验报告格式正确，步骤叙述比较清楚，正确分析实验数据，从技术角度优选解决方案获得比较有效的结论C-实验过程中认真完成实验要求，不能得到正确的实验结果，实验报告格式正确，步骤叙述清楚，没有正确分析实验数据，但是结合理论分析可以从技术角度优选解决方案获得有效的结论D-实验过程中不能完成实验要求，不能得到正确的实验结果，不能从技术角度优选解决方案获得有效的结论5M2考勤5%A-全勤B-缺勤1次C-缺勤2-3次D-缺勤3次以上6M2课堂表现5%A-精神状态饱满，回答问题准确B-精神状态一般，问题回答一般7M3实验90%A-实验过程中认真完成实验要求，得到正确的实验结果，实验报告格式正确，步骤叙述清楚，正确分析实验数据，从技术角度优选解决方案获得有效结论B-实验过程中认真完成实验要求，得到正确的实验结果，实验报告格式正确，步骤叙述比较清楚，正确分析实验数据，从技术角度优选解决方案获得比较有效的结论C-实验过程中认真完成实验要求，不能得到正确的实验结果，实验报告格式正确，步骤叙述清楚，没有正确分析实验数据，但是结合理论分析可以从技术角度优选解决方案获得有效的结论D-实验过程中不能完成实验要求，不能得到正确的实验结果，不能从技术角度优选解决方案获得有效的结论8M3考勤5%A-全勤B-缺勤1次C-缺勤2-3次D-缺勤3次以上9M3课堂表现5%A-精神状态饱满，回答问题准确B-精神状态一般，问题回答一般10M4实验90%A-实验过程中认真完成实验要求，得到正确的实验结果，实验报告格式正确，步骤叙述清楚，正确分析实验数据，从技术角度优选解决方案获得有效结论B-实验过程中认真完成实验要求，得到正确的实验结果，实验报告格式正确，步骤叙述比较清楚，正确分析实验数据，从技术角度优选解决方案获得比较有效的结论C-实验过程中认真完成实验要求，不能得到正确的实验结果，实验报告格式正确，步骤叙述清楚，没有正确分析实验数据，但是结合理论分析可以从技术角度优选解决方案获得有效的结论D-实验过程中不能完成实验要求，不能得到正确的实验结果，不能从技术角度优选解决方案获得有效的结论11M4考勤5%A-全勤B-缺勤1次C-缺勤2-3次D-缺勤3次以上12M4课堂表现5%A-精神状态饱满，回答问题准确B-精神状态一般，问题回答一般13M5实验90%A-实验过程中认真完成实验要求，得到正确的实验结果，实验报告格式正确，步骤叙述清楚，正确分析实验数据，从技术角度优选解决方案获得有效结论B-实验过程中认真完成实验要求，得到正确的实验结果，实验报告格式正确，步骤叙述比较清楚，正确分析实验数据，从技术角度优选解决方案获得比较有效的结论C-实验过程中认真完成实验要求，不能得到正确的实验结果，实验报告格式正确，步骤叙述清楚，没有正确分析实验数据，但是结合理论分析可以从技术角度优选解决方案获得有效的结论D-实验过程中不能完成实验要求，不能得到正确的实验结果，不能从技术角度优选解决方案获得有效的结论14M5考勤5%A-全勤B-缺勤1次C-缺勤