谈基于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训练模式的数据结构实践教学相关论文由www.7ctime.com收集,如需论文.计竞赛（简称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训练模式的数据结构实践教学方案的设计
数据结构实践教学以培养学生算法设计能力为目的，要求学生学会选择合理的数据结构，设计出相应理由的求解算法，学会如何把理论知识用于解决实际理由，提高自身分析理由、解决理由的能力，从而具备计算机软件工作所需要的基本能力。但传统的数据结构实验大体上只有3-5个实验，学生仅受到部分知识的训练，在课后也很少有渠道获得练习的机会。
针对以上理由，我们设计了系统化的数据结构实践教学方案和数据结构实训系统。系统化的实践训练内容包括线性表、栈及队列、串、数组与广义表、树与二叉树、图、顺序折半查找、内部排序等。数据结构实验教学实训内容如图2所示，其中包含20个基础性实验题目。除了基础性实验外，方案增加了一些提高性训练题目和高级数据结构题目，比如并查集、线段树、树状数组、自动机等，供能力较强的学生学习训练。实验训练题目均是设计型，教师可根据学生的实际情况，组织实验课的教学内容。为了更好地实施实验教学，我们把这些题目均放在数据结构实训系统上，学生可随时提交程序，系统也会及时反馈所提交的算法是否正确。该系统的使用提高了学生的学习兴趣，减轻了教师的负担，而且方便教师了解学生的实践课题完成情况。
3 ACM-ICPC训练模式的数据结构实践教学方案的实施与效果
数据结构系统化实践教学方案的实施分以下几个步骤：1）数据结构实训系统的研发。
数据结构系统化实践教学方案实施的第一步是基于ACM-ICPC的在线评测技术，开发数据结构实训系统。该系统的论文导读：一页12
用户可分为3种角色：管理员、教师、学生。管理员的功能包括：学生批量注册、题目维护等；教师的功能包括：题目浏览、程序提交、代码查看、讨论版发帖等功能；学生的功能包括：题目浏览、程序提交、讨论版发帖等功能。
2）面向数据结构的ACM-ICPC训练题目的设计。
根据数据结构教学大纲的要求，我们设计了系统化的数据结构训练题目。这些题目均以ACM训练题目的形式添加到数据结构实训系统中。另外，我们也从ACM-ICPC竞赛题中挑选相关题目，将实验教学中传统的以算法为主线的体系结构改为以理由为主线的体系结构，使学生自主选择合理的数据结构和算法进行计算机解题，加深学生对基本概念和基础知识的理解，通过学以致用牢固掌握所学知识。数据结构实训系统部分题目如表1所示。
3）以ACM-ICPC训练模式进行数据结构实验教学。
实验前，程序设计评测系统中给出实验题目，并要求学生在有限的时间内完成实验题目。学生设计好程序后提交给自动判题系统来判断，系统会实时返回判断结果。如评判没有通过，学生可修改程序并再次提交。对多次提交不成功的学生，实验教师可给予及时辅导。实验结束时，学生可通过系统清楚地知道自己的排名。这样的实验环境迫使学生在课基于ACM—ICPC训练模式的数据结构实践教学相关范文由写论文的好帮手www.7ctime.com提供,转载请保留.前认真做好准备，课后强化与数据结构内容相关的试题，而且充分调动学生的学习兴趣，从而达到熟练掌握所学内容解决理由的实践教学目的。
基于ACM-ICPC训练模式的系统化实践教学方案从2010年开始实施，分别应用于浙江师范大学2010级和201计算机科学与技术专业、软件工程专业和网络工程专业的数据结构课程的教学中。方案实施前后学生完成数据结构实验题目情况的比较如表2所示。由表2可以看出，该方案的实施，大大地提高了学生对数据结构理论的掌握程度，提高了学生的实践能力。浙江师范大学201部分学生在数据结构实训系统上完成题目的情况如表3所示。
4 结语
基于ACM-ICPC训练模式的数据结构实践教学将理论学习和实验有机结合，注重算法设计能力的提高和解题思维能力的训练，同时引入竞争机制，为学生提供了因材施教的途径，激发了学生自主研究的兴趣。通过两年的实施，收到了很好的教学效果。
参考文献：
[1]李冬梅，孟伟。数据结构课程的教学改革与教材建设[J].计算机教育，2012（14）：38-41.
[2]徐薇，王志海。数据结构课程研究性教学理论及策略探索[J].计算机教育，2012（1）：35-38.
[3]王淮亭.数据结构实践教学探讨与实践[J].计算机教育，2009（12）：13

3.134，145.

[4]陈瑛.从数据结构课程特征本质谈实践教学改革[J].计算机教育，2012（6）：33-35，40.
[5]中华，肖莹莹.数据结构课程的实践性教学模式[J].计算机教育，2012f4）：103.105.