基于ACM竞赛的数据结构实验课程教学研究

张少仲 白英 王小妹 陈媛嫄

摘  要： 分析了目前数据结构实验课程教学的现状和存在的问题，提出将ACM竞赛理念与数据结构实验教学相结合。根据数据结构实验课程特点，重新优化实验内容，构建基于ACM竞赛的实验题集。针对不同层次的学生，给出基于ACM竞赛的不同级别的实验题目，从而有益于各层次学生的编程能力、分析与解决问题能力以及沟通能力的提高。

关键词： 数据结构实验; ACM竞赛; 实验教学; 实验题集

中图分类号：G642.0          文献标识码：A      文章编号：1006-8228（2020）10-73-03

Abstract： This paper analyzes the current situation and existing problems of the teaching of data structure experiment course， and proposes to combine the concept of ACMICPC （Association for Computing Machinery， International Collegiate Programming Contest） with the teaching of data structure experiment course. According to the characteristics of data structure experiment course， the experiment content is re-optimized to construct the experiment question set based on ACMICPC. According to the students of different levels， experiment questions of different levels based on ACMICPC are given， which is beneficial to the improvement of the abilities of programming， analysis and problem-solving as well as the communication ability of students in different levels.

Key words： data structure experiment; ACMICPC; experiment teaching; experiment question set

0 引言

数据结构课程是计算机相关专业的基础课程，在专业课程体系中起着承上启下的作用。课程对培养学生的数据模型抽象能力、算法设计能力和复杂的程序设计能力具有重要的作用。课程知识内容和算法技术，无论对于后续学习其他专业课程，或是将来从事软件开发相关工作，都是必须掌握的基础内容[1]。

“程序设计基础”这门课是对数据结构课程影响最大的先修课程，这门课学完后，学生的编程能力差异很明显，有部分学生已经掌握了一定的编程技巧，但有更多的学生甚至不怎么会编程[2]。在基础不牢的情况下来学习数据结构知识，理论和实验难以兼顾。

为了改善数据结构课程教学质量，课题组以实验教学为突破口，进行了积极有益的探索，实现了各个层次的学生都有收获的实验教学。以尊重学生个体差异性为前提，力求使学生发挥各自的潜能，取得更好的学习效果，达到提升整体教学水平的目的。

ACM 国际大学生程序设计竞赛（简称 ACMICPC）是由国际计算机界历史最悠久、最具权威性的计算机组织ACM学会（Association for Computer Machinery）主办，是世界上公认的规模最大、水平最高的国际大学生程序设计竞赛，其目的在于让大学生运用计算机来充分展示自己在压力情况下，分析问题、解决问题的能力。该项竞赛从1970年开始举办，荟萃了世界各大洲的精英，受到国际知名公司的关注[3]。ACM竞赛具有较长的历史，方法成熟，将ACM竞赛模式应用于数据结构课程实验教学过程中，对于改变和完善具体实验训练项目，推动大学生科技创新教育，提升高校人才培养质量具有重要的现实意义[4]。

1 传统实验教学中存在的问题

传统的实验教学模式下，教师在课堂上提前将实验内容布置给学生，所有的学生做同样的实验题目，提交的时间和实验结果参差不齐。这导致实验教学面临如下问题。

⑴ 由于学生的编程能力差距大，对不同层次的学生起不到因材施教的效果。数据结构实验课程是用程序设计语言对理论课程中的算法编程实现，因此，学生必须具有一定的编程能力以解决实际问题。现在的数据结构教材的实验部分大多是基于C语言编写的，课程中涉及了大量C语言中的重点和难点。很多学生对这部分知识点掌握不牢固，用起来生疏，导致了对算法的思路是清晰的，但却难以用C语言将算法实现出来[4]。学生的程序设计语言基础和编程能力差距大，相同的实验题目会让不同层次的学生获得的实验效果不同。编程基础好的同學完成得快，质量很高;多数学生编程不够熟练，阻碍了学生对算法思想的验证和对综合设计性问题的解决;个别同学还有抄袭情况发生。

⑵ 相同的实验题目难以科学地量化和评价教学效果。传统的数据结构实验课程的考核方式多为：平时实验态度+编程能力+实验结果+实验报告。但是相同的实验题目导致实验结果和实验报告内容也基本相同。对于实验态度良好的学生，基本只能靠编程能力的评判来区分学习成绩了。而对编程能力的评判基本是看代码提交时间、运行时间、占用内存、以及代码编写规范程度。而这部分内容只占总分的一部分，结果就是学生的考核分数相对集中，难以对课程教学效果给出科学评价。

⑶ 对每一届学生都用相同的实验内容，影响学生学习的积极性。编程基础好的同学完成得快，课堂时间就能顺利完成;而大多数同学还需要课余时间来完成。这样不能激起学生的学习兴趣，对不同层次的学生起不到因材施教的效果。加上原有的实验考核方式缺乏精准性，对同学间的抄袭、互联网上的抄袭甄别困难，不仅影响学生学习的积极性，也达不到教学目标。

⑷ 实验内容的设置难以达到培养学生的工程实践能力的能力目标。传统的数据结构实验题目基本上是针对某一章的课堂讲授内容设计的，学生只需应用该部分的知识即可完成实验题目，不需要思考是否还有其他的解决方案，更谈不上选择最优的方案来解决问题，无法培养学生的工程实践能力，难以达到课程设置的能力目标[5]。

总之，实验题目的单一化、统一化是导致上述实验教学问题的主要根源。鉴于此，将不同层次的实验题目汇聚在一起，由浅入深，构建一个用于数据结构实验教学的实验题集，是解决问题的一个方法。课题组针对ACM竞赛的题目，有选择性地汇聚成一个实验题集，用于数据结构的实验教学中，从而改革了传统的实验教学模式，激发了学生的积极性，使不同层次的学生都能有所收获，也达到了因材施教的效果。

2 基于ACM竞赛的数据结构实验课程改革

ACM竞赛的题目有如下特点：有实际背景，趣味性和实用性较强;考查的知识范围较全面;层次性较好，分不同水平的题目;灵活、新颖，绝大部分题没有定解，留有广阔的思维空间。ACM竞赛的题目以解决问题为目标，而解题方法不受限制，可以让学生有更多的创新思维空间。将ACM竞赛的题目汇聚成一个实验题集，引入到数据结构的实践教学中，可激发学生的学习热情和潜力，提高学生自主学习能力、创新能力，也有利于团队精神的培养。在具体运用中采取了以下几条措施。

2.1 实验内容分级，实验题目灵活化，多样化

首先我们将实验内容分级，分成初级（单一算法的练习）、中级（需要用算法解决实际问题）和高级（结合若干算法来解决一个较大规模的问题）题目。学生可以根据自身情况选择不同级别的题型和题目数量来完成。这样可以满足学生学习过程中不同层次的需求，充分调动他们学习的主动性和积极性。除此之外，很多实际问题是有多解的，这样的实验题目充分激发了学生的学习主动性和积极性，将被动学习化为主动学习，更好地达到实验教学目的。

2.2 将传统的ACM竞赛题目改编为实验题目

根据ACM竞赛题目的特点，我们从中精心挑选相关题目，或将原有数据结构实验题目改造为ACM竞赛题目形式，形成了与数据结构实验要求相对应的初、中、高级实验题集，将其作为实验题目。将传统的以算法为主线的实验教学体系改为以问题为主线的实验教学体系，通过具体问题描述给出题目，让学生自主选择合理的数据结构和算法进行求解，加深学生对基础知识和算法的深入理解，以“学以致用”的方式来牢固掌握所学知识。

2.3 考核方式灵活，综合评定学生

学生对分数非常敏感，恰当的实验成绩评分标准有利于激发学生的学习动力，反之有可能会挫伤其学习积极性。将学生提交的程序由ACM在线测评系统进行评测，不仅考察其正确性，还对代码的运行时间、占用内存、输入输出格式加以限制等，可以综合考察学生对算法的灵活运用。

我校的数据结构实验课已经与理论课拆分，成为一门独立课程，而且比原来增加了4学时。共计12次课，24学时，满分100分。实验评分标准的制订，需考虑对学生具有激励作用，经过新的教学模式的探索，課题组决定采用以完成实验题目为主的评分方式。

⑴ 对实验题目的完成占总分的90%，实验态度和实验报告占10%。

⑵ 完成初、中、高级题目的分数占比是1：2：4;即完成一个高级题相当于完成两个中级题，完成一个中级题相当于完成两个初级题。

⑶ 完成两个高级题即可获得60分，以后每完成一个高级题加10分。加到80分以后，每完成一个高级题加5分。加到90分后为止。

该评分标准为学生设立较低的及格目标，使学生更容易进入完成实验题目的状态;其次完成6个高级实验题目就能拿满分，更能激发学生挑战更高级别实验任务的动力。同时即使12次实验课中完成12个初级实验题目，成绩也只能是及格多一点，要想取得好成绩还远远不够。从而确保了该评分标准在总体上不降低实验教学的要求。这样，不仅在成绩评定上做到了客观、公正，还更好地发掘了学生的创新能力，提高他们对知识点的掌握程度。

2.4 加强师生之间、学生之间的有益互动，培养良好的团队合作精神

传统的手工批改作业的任务非常繁重，学生的作业量以及作业反馈时间都会受到限制，在一定程度上打击了教师和学生的积极性。而ACM竞赛模式的在线评测系统可以对学生的作业进行自动评测，从而减轻教师的指导负担。学生在自主完成实验任务的过程中，遇到困难可以寻求教师个别指导，为学生提供解决问题的有关线索;同时，鼓励学生之间、师生之间的讨论和交流，用来丰富、矫正和加深对当前实验问题的解决方案，培养了良好的团队合作精神和沟通能力。

3 结束语

将ACM竞赛的题目选编成一个实验题集，引入到数据结构的实验教学中，一改传统实验授课全员实验题目统一模式为独立选择实验题目模式，不同层次的学生采用不同的实验题目，使不同层次的学生都能得到提高。实验题目选择个性化，将全体授课与个别指导相结合，可激发学生的学习热情和潜力，提高学生自主学习能力、创新能力，也有利于团队精神的培养。实验课引入相对自动化的实验考核方式，减轻了教师负担，使教师把更多精力投入到辅导学生方面。这种基于ACM竞赛的数据结构实验教学方式也有助于培养学生的工程实践能力、团队合作精神和协同能力。今后，我们还将继续将教学改革深入下去，以期培养高水平、高素质的优秀创新人才。

参考文献（References）：

[1] 张安勤，田秀霞等.数据驱动的数据结构课程案例设计研究与实践[J].软件工程，2020.23（4）：54-56

[2] 刘忠民，李广瑞.数据结构课程实验分层教学的探索和实践[J].计算机教育，2018.6：128-130

[3] 韩建民，钟发荣等.基于ACM-ICPC训练模式的数据结构实践教学探索[J].计算机教育，2013.5：103-107

[4] 李涵，吴秋新.基于ACM模式的数据结构实践教学改革的探索与思考[J].山东青年，2012.9：39-40，42

[5] 杨彬，王青正.工程教育专业认证背景下的数据结构教学改革[J].计算机时代，2020.4：61-63，67