基于PCOJ的数据结构实验教学探索

张仕 吴闻 郭躬德 严宣辉 严晓明

文章编号：1672-5913（2015）03-0030-03

中图分类号：G642

摘要：针对数据结构课程实践教学中的若干问题，在自主开发的程序设计竞赛在线测试平台上有针对性地提出平台改进、试题设计和教学改革的方法，阐述这些方法应用到实际教学工作中对数据结构课程教学的促进作用，最后说明取得的良好效果。

关键词：数据结构；实验教学；教学改革；程序设计竞赛在线测试平台

0 引 言

ACM国际大学生程序设计竞赛（ACM inter-national collegiate programming contest，简称ACM-ICPC或ICPC）是由美国计算机协会（ACM）主办的，一项旨在展示大学生创新能力、团队精神和在压力下编写程序、分析和解决问题能力的年度竞赛。福建师范大学从2003年开始组织学生参加ICPC，同时组织开发了程序设计竞赛在线测试（ programming contest online judge，PCOJ）平台，用于程序竞赛的训练工作。

实践教学是计算机专业教学过程中一个必不可少的环节。数据结构课程便是计算机科学与技术专业中理论和实践紧密结合的一门核心课程，其主要研究内容是数据的逻辑结构、存储结构及操作，教学目的在于培养学生的数据抽象能力，为解决实际问题时进行数据的组织和操作奠定基础。要学好数据结构这门课，不但需要从理论上理解和掌握相关知识，而且需要通过实验和实践环节提高实际动手能力和在实际问题中应用数据结构抽象、解决实际问题的能力。

1 研究现状

虽然多年的教学实验改革使计算机实践教学逐步受到重视，在实验室建设和教学实践中有了长足的发展，但是学生仍然存在理论学习与程序设计能力严重脱节的情况。通过对学生的访谈、日常教学中的观察，笔者总结出这种理论与实践脱节的问题主要有以下几方面。

（1）重理论学习，轻实践动手。教学过程中教师布置的多是书面作业，学生完成编程后不需要进行严格的程序检查和调试运行，只需理论可行，忽视实践动手的培养。

（2）程序问题不能及时解决。学生在编程练习遇到问题时没有通畅的沟通渠道，不能及时得到教师的指导，而教师在课上与学生的沟通有限。

（3）实践动手要求低。实验课的练习只有一些代表性案例，学生虽然完成了实验，但是实践工作量严重不足；另一方面，实验题目难度不大，这对于学有余力、对自己有更高要求的学生而言缺少了练习的强度。

（4）程序bug多。学生编写的程序只用少量数据进行简单的测试，不能全面测试到程序中的所有指令调用，这导致完成的实验代码可能存在大量的bug，但学生却不能及时发现并改正，程序的实用程度大大降低。

（5）考核不合理。当前对数据结构课程的考核大多是对书面作业、理论知识的考核，对实验环节的考核则主要是通过实验报告。教师很难了解学生对知识与技能的实际掌握情况，实验报告也很难客观真实地反映学生的实验情况。

（6）现有的把ICPC和教学结合的教学改革，更加侧重的是利用ICPC对现行的教学方法、教学体系进行改革，鼓励学生通过竞赛练习提高程序设计水平和解决问题的能力，鲜有把ICPC竞赛平台加以改进再结合到实验教学中的思路。

2 PCOJ平台的改进

福建师范大学计算机系组织开发了程序设计竞赛在线测试平台（ PCOJ），用于ICPC竞赛的日常训练工作。竞赛训练平台给学生提供大量的试题，让学生能够通过大量的训练，熟练利用综合知识分析并通过编程序解决实际问题。

和竞赛目的不同，数据结构实验教学的目标是要求学生能够解决特定的问题，更是要培养学生组织程序的能力、按照规定抽象数据类型定义要求实现特定数据结构的能力、按照预定义接口实现函数的能力、规范化程序书写的习惯。用一句话概括它们的区别：程序竞赛要求的是“学生具有特别突出的解决问题能力”，数据结构教学则是为学生“打好宽阔扎实的基础”。基于此，要把该平台应用到数据结构课程的教学中，需要根据具体的需求对该系统做以下两点改进。

（1）程序竞赛时所要求提交的是一个单一的文件，该文件包括解决特定问题的完整程序。文件提交到平台后，测试平台先编译该程序，生成可执行文件，平台会自动读出数据作为该可执行文件的输入，允许该可执行文件运行，产生结果和预先设定的结果对比。在数据结构的实验环节中，，教师需要让学生掌握程序设计的方法，还要求学生掌握程序组织方法、具体数据结构实现重用思想，这些要求不同于竞赛要求。为此，平台改进的第一个方面是要允许学生利用文件组织具体的应用，单独的文件反映的是某一个具体内容，要允许学生针对一个试题提交多个文件，所提交的文件可以包括完整可运行的程序，也可以是某个模块的实现。

（2）学生的组织方式，原有PCOJ平台没有对学生按照班级管理的功能，改进后的平台针对具体课程，教师可以注册账号、开设班级，学生也可以申请账号，加入某一个班级，实现以班级为单位的管理。这大大方便了教师了解学生的实验完成情况、练习和讨论参与情况等，为课程成绩的评定提供多维参考。

3 基+PCOJ的实验教学改革

3.1 分层次的实验教学体系

对于同一门课程，学生掌握的程度不同，针对不同层次的学生要指定不同难度的练习，因此我们把实验分为必做和提高两人类必做实验重点考核学生对基础知识的掌握情况；而提高类题目针对学有余力的学生，有的放矢，为他们提供一个更高的目标。

例如二叉树的遍历实验，我们设置的必做实验是利用递归思想完成先序、中主序和后序遍历提高类实验则要求在前面章节实现的线性表、栈和队列基础上，完成二叉树先序、中序和后序遍历操作的非递归实现。在排序和查找部分，提高类实验要求学生能够利用多线程提高算法的效率。

3.2 分类的试题设计

数据结构课程的教学目的除了要求学生掌握线性、树、图等结构组织和操作知识外，还要训练学生进行复杂程序设计的基本技能，培养良好的程序设计习惯（如面向接口的编程思想），加深对数据结构定义、算法、算法应用的理解，提高实践能力。基于此，我们把数据结构实验试题分为三大类：数据结构应用类、数据结构实现类、算法设计实现类，如图l所示

数据结构应用类试题指已经按ADT定义并实现了某个数据结构，再提出基于该数据结构的应用题目，要求利用该数据结构解决相应的问题并提交平台测试和判定。例如利用栈实现迷宫问题的求解，对该类试题，实验平台发布的试题说明中包括可以使用的具体数据结构的类型定义（.h文件）、所要实现的具体应用说明、测试数据例。学生根据实验题目要求，在所定义数据结构实现的基础上，应用该数据结构实现应用要求。学生可以提交多个程序文件，其中一个是包含main（）的程序，其他文件则是在主程序文件中引用到的定义和实现。实验平台将利用存在的数据结构和学生提交的文件进行编译、运行、测试，并根据最后测试结果返回相关信息。

数据结构实现类试题是指已经设定好了数据结构的应用程序，学生应按照要求的ADT实现特定的数据结构，以便应用程序得到支撑，如一个基于线性表的学生管理程序。对于该类试题，实验平台发布的试题说明中包括数据结构的抽象数据类型定义（ ADT）、数据结构应用需要的接口、数据结构应用简单例、测试数据例。其中，具体数据结构的抽象类型定义ADT清楚说明了所需要实现的数据结构各类操作。学生在实验过程中可以提交多个程序文件，其中对于数据结构应用需要的数据结构定义文件要按照要求进行命名：实验平台将利用系统中的数据结构应用程序和提交的相关文件进行编译，再利用平台中的数据集对应用进行测试并根据最后测试结果返回相关信息。

算法设计实现类试题是指已经有一个特定的应用，该应用基于某一数据结构，但是在这一数据结构实现中还缺少某一关键算法，要求学生根据算法的定义设计和实现该算法，以便应用完整的某一数据结构支撑应用程序的运行，如线性表的插入操作实现。对于该类试题，实验平台发布的试题说明中包括数据结构的抽象数据类型定义（ ADT）、数据结构的类型定义、特定算法的函数头定义和算法需要实现的功能。学生在实验过程中只需要将该算法的实现提交到系统上测试和判定，这类试题适用于平时的小作业以及以算法设计为侧重的数据结构和算法实验。

3.3 基于论坛的师生交流

在实验教学体系中，我们还提供论坛作为师生交流的平台。很多时候，教师不但会回答本班学生的提问，而且会回答其他班级学生的提问。教师通过论坛可以更好地了解学生对知识的掌握情况，发现不足，在课堂上加以弥补。论坛的设置缓解了学生碰到问题不能够及时交流的问题，增加了师生的交流和了解，促进教师实施更有针对性的课堂教学。

3.4 基于平台的实验测试

针对当前学生对实验程序测试不完全，导致程序中存在大量未被发现的bug的问题，我们利用实验平台的自动测试功能发现问题。学生所编写的程序可以提交到平台上进行自动编译、测试和运行，而运行所使用的数据集是针对特定问题特别设计的。由于在设计实验试题测试数据时可以综合考虑各方面特别是一些边界情况、规模问题，自动测试会帮助发现更多潜在bug并给出相应提示。对程序测试的高要求自然会在潜移默化中培养学生程序设计的严密性，促使其重视程序设计中的细节问题。

3.5 基于平台的实验考核

有了这个实验平台，教师布置的实验不再局限于每次实验的单个题目，还可以把平常的课堂作业也用实验试题（主要为算法设计实现类）的方式反映在实验平台上，这样学生完成的作业也就有更加客观的考核和评价，同时减轻了教师的负担，让教师有更多时间与学生就相关实验进行交流。对学生学习的评价，则可以充分利用学生使用实验平台过程中产生的行为记录，包括从该生平时所做练习、实验、提高实验和交流情况等进行综合考虑，从而提高评价的客观性。

4 结语

我们通过把PCOJ的软硬件平台和数据结构实验教学相结合并改进，形成一个完整的数据结构实验教学体系；加强该数据结构实验平台的建设和应用使数据结构的实践教学方法、平台应用、实验内容、考核方式等越来越系统化，能够服务于多层次、多角度的实验教学活动。数据结构实验教学改革不但能使学生对数据结构课程理论加深理解，也大大提高了学生的动手能力，形成了理论和实践相互促进的良好态势。实验平台的使用能够更好地训练学生进行复杂程序设计的基本技能，培养良好的程序设计习惯，为后续课程实验奠定更加坚实的基础。当然，在未来的教学过程中还不断会有新的问题和挑战出现，这些都会促进我们对实践教学方法、手段继续完善，使数据结构的实践教学水平不断提高。