综合训练项目任务书(数据结构).docVIP

软件学院综合训练项目任务书课程名称 数据结构 任课教师 孙宁 开课学期 2015年秋季学期 辽宁工程技术大学软件学院软件工程系一、 综合训练目的和任务数据结构是软件工程专业的主干核心课程之一，是计算机科学的算法理论基础和软件设计的技术基础。数据结构是实践性很强的课程。综合训练项目是加强学生实践能力的一个强有力手段。要求学生掌握数据结构的应用、算法的编写、类C语言的算法转换成C程序并上机调试的基本方法。综合训练项目要求学生在完成程序设计的同时能够写出比较规范的设计报告。严格实施综合训练项目这一环节，对于学生基本程序设计素养的培养和软件工作者工作作风的训练，将起到显著的促进作用。二、综合训练基本要求1通过综合训练项目，要求对数据结构的选择应用、算法的设计及其实现等方面加深对课程内容的理解与掌握。同时，在程序设计方法以及上机操作等基本技能方面受到比较系统的训练。2按照综合训练项目要求，以学生为主、指导教师指导为辅，认真、独立地完成综合训练项目的任务，有问题及时主动与指导教师沟通。3按照教学要求学生分组完成综合训练项目或独立完成，学生要发挥自主学习的能力，充分利用时间，按时完成设计内容。4每个项目结束后，通过答辩与点评的形式进行验收，根据点评意见，学生对项目进行整改后，提交项目报告与程序，教师给出该项目成绩。三、综合训练内容综合训练项目一1.目的 掌握线性结构的概念及工作原理，并能在相应的应用问题中正确选用它们，并实现算法以解决实际问题。2题目 单号组别完号题目1，双号组别完成题目2。题目1：运动会分数统计 (1)设计任务参加运动会有n个院系，编号为1n。比赛分成m个男子项目，和w个女子项目。项目编号为男子1m，女子m+1m+w。不同的项目取前五名或前三名积分；取前五名的积分分别为：7、5、3、2、1，前三名的积分分别为：5、3、2；哪些项目取前五名或前三名由学生自己设定。（m=20,n=20）(2)设计要求假设姓名长度不超过20个字符。每个项目结束时，将其编号、类型符（区分取前五名还是取前三名）输入，并按名次顺序输入运动员姓名、院系编号和成绩。产生各院系的成绩单，内容包括各院系取得的每项成绩的项目号、名次（成绩）、姓名和得分； 产生团体总分报表，内容包括院系编号、男子团体总分、女子团体总分和团体总分。 程序运行后有相应功能的选择菜单界面。题目2：停车场停车管理(1)设计任务设停车场是一个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北端），若车场内已停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后进入的车辆必须先退出车场为它让路，待该辆车开出大门外，其他车辆再按原次序进入停车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短缴纳费用。试为停车场编制按上述要求进行管理的模拟程序，程序运行要有相应功能选择菜单。(2)设计要求以栈模拟停车场，以队列模拟停车场外的便道，按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项：汽车“到达”或者“离开”信息、汽车牌照号码以及汽车到达或离开的时刻。对每一组输入数据进行操作后的输出信息为：a、若是车辆到达，则输出汽车在停车场内或便道上的停车位置；b、若是车辆离开，则输出汽车在停车场内停留的时间和应缴的费用（在便道上停留的时间不收费）。栈以顺序结构实现，队列以链表结构实现。需另设一个栈，临时停放为给要离开的汽车让路而从停车场退出来的汽车，也用顺序存储结构实现。输入数据按到达或离开的时刻有序。栈中每一个元素表示一辆汽车，包含2个数据项：汽车的牌照号码和进入停车场的时刻。程序运行有功能选择菜单。3时间安排:项目执行过程及时间安排阶段内容时间1任务布置。第7周周四2学生查阅资料,自行分析问题，提出解决方案,教师辅导答疑,初步完成训练项目。9周10周课后完成10周周日提交报告和源程序代码3学生互评成绩11周4学生演示,研讨及点评。第11周周四5改进原有系统,提交优化后的程序及项目报告第11周周五综合训练项目二1目的 掌握非线性结构的特点和应用，巩固所学的理论知识，培养综合运用所学知识解决实际问题的能力。2题目单号班级 单号组别完成题目1，双号组别完成题目2；双号班级 双号组别完成题目1，单号组别完成题目2。题目1：人类家谱管理系统 (1)设计任务 树形结构是一种非常重要的非线性结构，它用于描述数据元素之间的层次关系，人类家谱是树形结构的典型体现，通过此项训练让学生掌握树形结构的知识；使学生重点掌握树与二叉树的转换，二叉树的存储和遍历；此项训练要求构造一棵家谱树，并完成任意成员的查找； (2)设计要求 输入家族成员，创建家族族谱树。 插入新的家族成员。 对家族成员进行查找。 修改某一个家族成员信息。题目2：校园导航系统 (1)设计任务掌握图的结构特点及应用，运用所学知识解决现实问题。给出校园各主要建筑的名称信息及有线路联通的建筑之间的距离，利用校园导航系统计算出输入的起点到终点之间的最近距离及线路。 (2)设计要求输入各建筑信息及线路信息，构建图。本项目数据结构为有向网，采用邻接矩阵为存储结构。计算给定起点到终点之间最近距离的进行线路。参照迪杰斯特拉算法计算给定两点之间的最短路径。根据输入起点和终点，输出线路及总距离。3时间安排:项目执行过程及时间安排阶段内容时间1任务布置。第14周周二2学生查阅资料,自行分析问题，提出解决方案,教师辅导答疑,初步完成训练项目。14周15周课后完成15周周日提交报告和源程序代码3学生互评成绩16周4学生演示,研讨及点评。第16周周四5改进原有系统,提交优化后的程序及项目报告第16周周五综合训练项目三(选作)1目的 培养学生自我学习能力及创新能力。 2题目：撰写科技论文(1) 设计任务 要求学生根据所学某一算法（算法不限）或自学算法，查阅相关资料，对算法进行详细剖析、拓宽算法应用领域或改进算法。比如：模式匹配算法、最短路径算法，查找算法、排序算法等。(2) 设计要求 该题目为学生选作题目，不限定组别。要求完全按照科技论文书写格式撰写该论文。提交科技论文，每篇论文最多三个作者。3时间安排:项目执行过程及时间安排阶段内容时间1任务布置。第10周2学生查阅资料,自行提出问题，分析问题并给出解决解决方案，教师指导完成科技论文撰写并提交论文。1217周课后完成3提交论文及反馈意见。1217周4.成绩说明（1）该项目为选作项目，不占用综合训练项目总成绩。每篇论文成绩直接加入总成绩，综合训练项目总成绩满分45分。（2）每篇论文最多三个作者。对于合格论文，只有一个作者，每篇论文加5分；两个作者，第一作者3分，第二作者2；三个作者，第一作者3分，第二作者1分，第三作者1分。四、成果形式（1）本课程综合训练项目一、项目二按小组完成,每3人一组。每组需提交项目报告及程序源代码。（2）项目三为选作内容，提交科技论文一篇。五、评价方式1评价内容 (1)提交综合训练项目报告。 (2)提交完成的程序源代码。 (3)每教学单位内2个班级互相评分，根据评分标准每班成绩分为A+，A，B，C四档（对应95，90，80，75分），各档比例为15%，30%，40%，15%，教师审核最终评分。2评价标准 (1)综合训练项目报告 40%项目比例备注报告格式规范程度30%图表质量10%报告内容全面、清晰程度45%总结深刻程度10%参考文献5%(2)程序 60%项目比例备注程序运行情况20%功能实现情况40%算法清晰程度10%人机交互、界面及菜单10%独立完成情况20%三、成绩构成每组练项目总成绩为2个项目平均成绩乘以30%。五、综合训练项目报告模板 综合训练项目报告模板见附录。附录软 件 学 院 综合训练项目报告书课程名称 数据结构 项目名称 专业班级 组 别 成 员 任课教师 目 录说明： “目录”用小2号黑体字、居中；目录内容最少列出第一级标题（章）和第二级标题（节）；前者用4号黑体字，后者用4号宋体字，第三级标题用4号楷体字，居左顶格、单独占行，每一级标题后应标明起始页码。1 设计时间（一级标题，黑体，三号，1.5倍行距）2 设计任务(针对设计题目)3 设计内容 （一级标题，黑体，三号，1.5倍行距）（设计内容安排可以根据课程特点自行安排）3.1问题分析 （二级标题，黑体，小三，1.5倍行距） （如有 三级标题，黑体，四号，1.5倍行距） 格式要求：1. 上面各级标题均左顶格2. 正文：小四，中文宋体，西文Times New Roman3. 行间距1.5，首行缩进2字符4. 图表中文字：五号，宋体5. 有图名和表名，图名在图下面标注，表名在表上面标注,均5号宋体陈述说明设计的任务，强调的是程序要做什么？明确规定：1.程序所能达到的功能；（给出功能模块图）2.输入的形式和输入值的范围；3.输出的形式；4.测试数据：包括在正确的输入及输出结果和含有错误的输入及输出结果。3.3程序设计内容包括：1.本程序中用到的所有抽象数据类型的定义及实现，对每个操作只需要写出伪码算法；2. 主程序的流程3.函数说明及函数的调用关系图。4.主要函数伪码算法（伪码算法达到的详细程度建议为：按照伪码算法可以在计算机键盘直接输入高级程序设计语言程序）；3.3测试与分析3.3.1测试（三级标题，黑体，四号，1.5倍行距）给出测试数据，输出测试的结果，测试数据应该完整(覆盖算法各种情况)。3.3.2分析内容包括：1.调试过程中遇到的问题是如何解决的以及对设计与实现的回顾、讨论和分析；2.算法的时间复杂度和空间复杂度的分析，改进设想。3.4 代码源程序代码及必要注释。4 总结与展望包含以下内容: 该项目设计过程的收获、遇到问题、解决问题过程的思考、程序调试能力的思考、对数据结构这门课程的思考、在项目实施过程中对数据结构课程的认识等内容。 答辩结束后，根据其它组别完成情况及总结情况，对自己程序剖析，针对不足给出改进意见及策略。参考文献1 屈辉立,陈可明,石武信.JSP网站编程教程M.第1版, 北京:北京希望电子出版社,2005 2 白勇.用B/S模式构建在线考试系统J,重庆电力高等专科学校学报,2003,10(4): 100130. 3 Jiang Guo,Yuehong Liao,Behzad Parviz.A Survey of J2EE Application Performance Management SystemsJ,Proceedings of the IEEE Internation