基于ACM—ICPC训练模式数据结构实践教学探索.doc

基于ACM—ICPC训练模式数据结构实践教学探索 　　摘要：针对目前数据结构课程实践教学上的不足，提出基于ACM-ICPC训练模式的数据结构课程系统化的实践教学方案。 关键词：ACM-ICPC；数据结构；实践教学 数据结构是计算机专业的一门重要的专业基础课。该课程要求学生掌握程序设计所用到的各种数据结构的逻辑结构、存储结构及算法。数据结构是编译程序、操作系统、数据库系统以及其他系统软件和应用软件的基础。鉴于该课程在计算机专业课程中的重要地位，很多高校对该课程的教学模式和方法展开了深入的研究。文献[1]结合教学实践，提出在教学内容、教学方法、教学手段、教材建设等方面进行全方位改革的思路；文献[2]对研究性教学理论与方法进行研究，提出数据结构教学中的协同教学和多元教学等方法；文献[3]分析了目前在课程教学中存在的不足之处，为加强数据结构实践教学，给出实践教学的9个案例；文献[4]研究了数据结构课程实践教学的特征，并给出一些实践教学改革的具体实施方法；文献[5]提出一种实践性教学模式，并给出课堂理论教学、实验设计及实施、课程课外实践活动、形成性考核等教学实践中的4个环节的实施方法。 数据结构是一门实践性很强的课程，它不但要求学生掌握各种常用数据结构的定义、特点以及基于这些数据结构的基本算法，更重要的是要求学生不断提高自身算法设计的能力。学生只有经过系统化的训练，才能真正地理解和掌握课程的内容，才能在实际问题求解中灵活地选择合适的数据结构，找到更好的求解方法。目前，国内外针对该课程的教学方法和教学模式的研究，虽然认识到实践教学的重要性，但并未给出系统化的训练方案。笔者在总结多年教学经验的基础上，提出了系统化实践教学的方案，并基于ACM-ICPC训练模式，对该方案进行了实施，收到了很好的效果。 1 ACM-ICPC模式 1.1 ACM-ICPC模式的优势 ACM国际大学生程序设计竞赛（简称ACM-ICPC）是由国际计算机界历史最悠久、最具权威性的计算机组织ACM学会（Association for Computer Machinery）主办，是世界上公认的规模最大、水平最高、最为公平的国际大学生程序设计竞赛，其目的在于让大学生运用计算机来充分展示自己在压力情况下，分析问题、解决问题的能力。该项竞赛从1970年开始举办，荟萃了世界各大洲的精英，受到国际知名公司的关注。 将ACM-ICPC训练模式引入数据结构的教学中，可以鼓励学生多动手、多动脑、多实践，相对于传统的实践教学具有以下几方面的优势： 1）实践教学在网络上进行，不受时间和空间的限制。 教师可以通过在线评测系统布置实训内容，学生可以根据自己的情况选择合适的时间完成训练题目。学生完成编程后提交程序代码就可以立刻得到评测结果，激发了学生的学习热情。教师也可以分析学生提交的程序，以便在课堂上补充讲解。 2）有利于创造学生之间良好的学术交流氛围。 ACM-ICPC训练模式让学生在课余时间自主进行算法和程序的交流，通过网上发帖的方式，实现学生与教师、学生与学生之间的交流和互动，有助于创造良好的学习交流氛围。 3）减轻教师的指导负担。 为让学生更好地掌握数据结构课程的内容，教师会在课程的教学中，布置大量算法设计方面的作业。传统的手工批改作业的任务非常繁重，学生的作业量以及作业反馈时间都会受到限制，在一定程度上打击了学生的积极性。而ACM-ICPC训练模式的在线评测系统可以对学生的作业进行评测，从而减轻教师的指导负担。 1.2 在线评测技术 我们将ACM-ICPC在线评测技术引入数据结构的教学中，开发了数据结构实训系统。该系统可对学生提交的程序源代码进行编译和执行，并通过预先设计的测试数据检验程序的正确性。这大大减轻了教师的工作负担，缩短了作业的反馈时间，激发了学生实践训练的激情。 在线评测系统流程如图1所示。学生提交程序源码后，系统首先将源码保存到数据库，插入待评测队列。如果系统评测内核run.exe正常运行，则将源码传递到评测内核进行编译。如果源码编译错误直接输出结果提示用户程序编译错误。源码在编译通过之后，若运行超时则直接输出超时错误，否则评测程序将该程序运行的结果与预置的结果文件内容进行比较，如果完全一致，系统将输出程序正确，反之输出程序错误。无论哪一种情况，系统都会将评测结果保存到数据库。 2 ACM-ICPC训练模式的数据结构实践教学方案的设计 数据结构实践教学以培养学生算法设计能力为目的，要求学生学会选择合理的数据结构，设计出相应问题的求解算法，学会如何把理论知识用于解决实际问题，提高自身分析问题、解决问题的能力，从而具备计算机软件工作所需要的基本能力。但传统的数据结构实验大