基于ACM竞赛模式的数据结构实践教学探讨

范建中，王秀友

(阜阳师范学院计算机与信息工程学院，安徽阜阳236037)

数据结构课程是计算机及相关专业的一门综合性专业基础课[1]，该课程的教学由理论教学和实践教学两部分构成。实践教学主要为验证理论教学中所学的算法为主，在理论教学时，大部分学生能理解课程中的一些基本概念和一些基本的算法设计，但实践教学时，相当一部分学生不能正确实现课程中的算法，更不要说将课程中所学的数据结构及相关算法用于分析解决实际问题了。通过多年的教学及与学生的沟通、同行的交流，发现传统数据结构实践教学中存在不少问题。首先，数据结构课程实践教学课时较少，但实践内容较多；其次，程序设计基础薄弱，计算思维能力不足；最后，实践教学模式落后，达不到预期的教学效果。

1 数据结构实践教学改革的必要性

ACM竞赛的目的在于培养大学生的创新思维和团队协作精神，在强压力下利用程序设计现场作答来展示自己分析问题和解决问题的能力。目前国内许多知名的IT企业采用在线评测（机试）的方式来招聘职员，或者通过各种在线比赛和比赛平台搜寻各类程序设计人才，如百度公司主办的Astar百度之星程序设计大赛、美团点评主办的CodeM编程竞赛等等。计算机类专业研究生入学考试初试时数据结构部分一般侧重算法分析和设计能力，在面试时大都采用在线评测的方式来测试学生的编程水平。各类与程序设计相关的学科竞赛的考查内容，也与数据结构课程的内容密切相关。因此在数据结构实践教学中引入ACM竞赛模式非常必要，它将有助于学生巩固所学的理论知识并加以应用，从而提高算法设计能力、就业竞争力，也有助于学生熟悉程序设计类竞赛模式，掌握竞赛中程序的设计策略，在竞赛中获得佳绩。

2 数据结构实践教学改革措施探讨

为解决传统数据结构实践教学模式中存在的主要问题，我们在实践教学中引入ACM竞赛模式。ACM竞赛通常有两种判题模式，第一种模式是采用基于C/S架构的PC^2软件来判题，常用于ACM竞赛正式比赛，试题需单独发放，不方便进行实践教学；第二种模式采用的是基于B/S架构的在线评测模式，多用于ACM竞赛练习或网络赛，该模式非常适合数据结构课程的实践教学。随着学科竞赛的蓬勃发展，各大高校、教育机构都建立了许多开放的在线评测系统来训练自己的ACM选手，像浙江大学的“ZOJ”、杭州电子科技大学的“HDUOJ”等，这些系统里有非常丰富的题库，能很好地锻炼学生的程序设计能力，但不适合直接用于数据结构的实践教学。因为系统题库是为培训ACM选手而设，对于大部分学生而言难度太大，容易挫伤学生的学习积极性和信心。要改善实践教学效果，提高学生的分析、解决问题及算法设计能力，就需要搭建自己的课程实践教学平台，设计合适的实践教学内容。

2.1 搭建数据结构实践教学平台

采用开源的OJ(Online Judge)系统搭建平台，由华中科技大学前ACM队员Sempr等同学开发的HUSTOJ，它是一个出色的免费开源系统，目前由zhblue维护，还在不断更新。通过对HUSTOJ进行配置和少量的开发就可以达到满足数据结构实践教学和举行校内程序设计竞赛的要求。

基于HUSTOJ构建的数据结构实践教学平台，教师可以创建题库、安排数据结构实验、进行数据结构考试、程序设计竞赛、代码抄袭检测、成绩统计、在线答疑等。学生通过浏览器查看要做的实验题目及课后作业，在规定的时间内完成实验及课后作业。学生提交后的程序代码由系统进行在线评判，系统及时返回评判结果，如果返回AC状态，则表明实验或作业被系统认可，返回其他状态，则意味着要重新修改代码再次提交。如果代码相似，系统也会标记和哪个学生是相似的。学生如有疑问可以发贴在讨论版讨论，也可以发即时消息给老师请求帮助。通过排行榜学生可看到自己的排名，教师可以看到整个实验情况，对于编程能力较差的同学，老师可以即时查看他的代码，并进行相应的指导。

2.2 以学生为本，合理设计实践教学内容

数据结构课程的教学目的是要求学生学会从问题出发，分析其内在的数据特性，根据问题需求设计数据的逻辑结构、存储结构及相应的操作算法，并初步掌握时间和空间分析技术。通过复杂程序设计的训练，使学生养成良好的代码编写习惯，具有分析问题，解决问题的能力。数据结构实践教学平台是通过在线评判问题正确与否的，传统的实验内容不合适直接放在实验平台上，需要根据学生的基本情况，分类、分层次合理设计实验内容[2-3]。

根据数据结构实践教学要求及学生程序设计能力不同，实验内容分为必做和选做两大类，必做类的实验内容主要考查学生对数据结构课程基本内容的掌握情况，选做类的内容主要针对学有余力的同学，一般为综合应用型或程序竞赛有关的一些问题。例如线性表的必做实验是顺序表和单链表的基本操作的实现，选做类的实验则为利用顺序表进行高精度的计算和利用单链表实现一元多项式的除法等。

必做类实验中数据结构实验题目分两个层次：基础型、算法设计型。基础型的实验设计成填空的形式，例如在顺序表的实验中，实验内容为验证顺序表的基本操作，可在实验平台上提供问题的相应要求，测试用例样例，给定主程序框架（完整的main()程序），在里面有相应的顺序表的基本操作调用，学生要做的是根据题目要求，自己定义顺序表的数据结构，及相应的基本操作的实现。学生只须提交顺序表数据结构的定义及基本操作实现的程序代码，不用提交包含main()的程序。实验平台利用已经设置好的后台测试用例来测试提交的代码，并返回相应的信息。这个层次的实验适用于全体学生，可用于检测学生对数据结构理论知识的掌握情况。算法设计型实验是要求学生利用所学的数据结构设计一个算法来解决一些简单的实际问题，例如在线性表的实验中，可设置一个集合的交、并实现的问题。这类问题要求学生做到会对问题进行简单的分析，找出数据的特性及逻辑关系，并定义出相应的数据结构及相关的操作实现。学生在实验过程中只需定义所需的数据结构，及相关操作的实现提交到系统上测试和判定。这个层次的试题可用于区分不同水平层次的学生，拉开实验成绩的档次，方便于挑选算法设计能力较好的同学进行培训以参加程序设计竞赛。

2.3 学生强弱组合，分组实验

ACM程序设计大赛由3名队员组成一队，使用同一台计算机协作共同解决竞赛的问题，有助于培养学生的创造力和团队合作精神。在数据结构实践教学中，仿照程序设计竞赛的模式，两人一组进行实验，组队时，先对班级学生进行摸底测试，然后根据成绩并结合自愿的原则进行强弱搭配，为了让不同层次的学生都有问题可做，并且都有兴趣去做，将每章的实验按难易程度编排3至5个题目，在这3至5个实验题目中至少有一个以上是基本的，基础弱的同学是能完成的，基础好的同学一般能解决所有问题，但在两节课的时间不一定能做完所有的题，这样就要求组内同学相互配合，才能完成所有问题。通过分组，每个班级分成多个小组，组内的同学是相互合作关系，组与组之间是竞赛关系，这样可以促进组内同学团队合作、组与组之间相互竞争，容易激发学生的学习兴趣[4-5]。

2.4 定期进行数据结构实验测试

分组实验虽能促进小组的同学相互合作、相互学习，但也可能存在一些问题，实验只是其中一个同学完成，这样的分组实验就失去了本义，定期进行数据结构实验测试就非常有必要。定期的数据结构实验测试分两种形式，一种是类似于平常实验方式，对平时的实验题进行稍作变化，要求学生在规定的时间内完成，用于检查平时分组实验时学生是否认真参与实验，以保证平时实验成绩的客观公正；另一种类似于期末考试，只不过采用机考形式来完成，考试的题型有选择题、判断题、填空题，这个过程在前述实践教学平台上无法实现，需借助浙江大学陈越老师的pintia（拼题A）系统来完成，该系统的基本功能是免费给教师使用，即教师可免费利用该系统组织考试。每次实验课，通过10分钟的课间机考，能巩固学生的理论基础知识，方便教师了解学生的理论知识掌握情况，并根据学生的学习情况及时改进教学方式，也方便教师统计平时考核成绩。采用定期的数据结构实验测试模式，学生须注重平时的实践训练、及时复习理论知识，才能顺利通过考核，从而有助于培养学生的自律自觉性，及程序设计实践能力，避免实验考核结果不客观，也就保证了实验考核不但有效有用，而且公平公正。

3 结束语

将ACM竞赛模式引入到数据结构实践教学中，借助数据结构实践教学平台的全天候开放，学生可以随时随地进行练习，提交程序代码，有效地解决了实践课的时间少、任务重的问题。利用数据结构实践教学平台进行分组形式参与实验，可以形成组与组之间的竞争和组内交流的良好学习氛围，充分使学生体会到团队合作的重要性。通过在数据结构实践教学平台上的实践训练，可使学生的分析实际问题、解决实际问题能力得以提高，利用系统进行实践考核，对学生的成绩评定也更加公平公正。