OnlineJudge在数据结构教学中的应用

文/向程冠 熊伟程 熊世桓

1 引言

目前，在大数据、计算机科学与与技术、人工智能、物联网等专业中，计算机程序设计类课程一直处于“饭碗”课程的地位，在所有的程序设计类课程中，数据结构与算法课程是必不可少的，是专业核心课程，学生打下扎实的计算机程序编写能力基础是学生学好专业方向课程的重要保障。2018年9月，教育部在《淘汰“水课”打造“金课”教育部要求提升本科教育教学质量》的通知中明确要求“各高校要认真查找课堂建设和管理中存在的突出问题和薄弱环节，严管、严抓教学秩序，制定整改措施，明确时间节点，落实责任到人，把从严管理的规矩立起来、把课堂教学建设强起来、把课堂教学质量提起来。同时，要全面梳理各门课程的教学内容，淘汰‘水课’、打造‘金课’，合理提升学业挑战度、增加课程难度、拓展课程深度，切实提高课程教学质量”，更关注以学生为中心的教学改革刻不容缓，把数据结构与算法这门课程打造成“金课”也是各高校积极研究的课题。

数据结构是一门实践性很强的课程，从事教学的教师们一直乐此不疲地进行教学改革，力求寻找一种事半功倍的教学方法来提高学生的程序设计能力，可令人遗憾的是大多数教师仅关注了“教法”的改革，忽略了“学法”改革的重要性。课堂上，主要还是以理论讲授为主，不重视学生的代码实现能力的训练，虽然在期末的考试中，大多数学生可以顺利过关，在优秀以上等级的学生也不在少数，可实践动手能力较差，大多数学生根本不会算法实现，导致学生成为所谓的计算机“理论”人才。原因在于过分强调老师在教学的的主导地位，忽略了学生的中心地位，把宝贵的课堂变成了学生观看教师工作和表演的场地，把学生当成了过客，直接导致学生的程序和算法设计能力太差，学生动手能力没有得到训练，最终失去了对专业的认同感。这种以教师为中心的传统教学方法，实验课形同虚设，教师完全没有展示算法的实现过程，实验课的监管不严。作业以纸质为主，教师的批阅工作量巨大，期末测评方式以笔试为主，无法评出学生对课程的掌握情况，教师阅卷时也只能看看程序设计题目的大体情况，没有机器的验证，也没有数据集的测试。因此，教学改革需关注学生动力能力的训练，教师少讲，学生多练，变笔试为机试，通过测评系统完成练习、小测、考试。本文根据我校近几年的教学实际情况，利用OnlineJudge 平台，要求学生在平台上至少完成800 道程序题，至少提交1 万行代码，程序设计类课程在练习、测试均使用OnlineJudge完成，通过从2014年开始引入OnlineJudge 系统进行教学以来，我校学生的程序设计能力大幅上升，取得显著的教学效率。

表1：Onlinejudge 测试结果

2 OnlineJudge概述

OnlineJudge 系统（简称OJ）主要应用于程序算法设计类的编程比赛中，选手通过浏览器和客户端向测试服务器提交代码，由测评机调用预先设置好的数据集作为输入对选手提交的程序代码进行测评，以考查代码的正确性、时间复杂度、空间复杂度，如ACM/ICPC（国际大学生程序设计竞赛），使用对运行代码进行测评。一般情况下，Onlinejudge 系统采用两种计分模式：ACM/ICPC 模式与测试点得分模式。前者必须满足所有测试点均通过正确性、时间度和空间复杂度的验证才算正确，成绩记录只有正确和不正确两种结果；后者按通过的正确性、时间复杂度和空间复杂度验证的测试点分别给分，并以累加分数作为最终得分，测试数据的设置可选择不同数据规模，也可选择设置不同的得分点，以考查选手的程序设计能力。目前，国内比较受欢迎的Onlinejudge系统有北京大学的POJ（PKU JudgeOnline，http://poj.org）、浙江大学的ZOJ（http://acm.zju.edu.cn）、杭州电子科技大学HDUOJ（http://acm.hdu.edu.cn）、贵州师范学院的码学堂（https://www.maxuetang.cn）等。国外的有TopCoder、Codeforces、AtCoder、SPOJ、USACO 等。

通常Onlinejudge 会在提交程序源码后，反馈执行结果，大多数的Onlinejudge 提供的反馈结果如表1所示。

3 在数据结构课程中使用OnlineJudge

3.1 用线上可以免费使用的OnlineJudge系统完成学生的平时程序编写练习

在数据结构课程的日常教学中，如果所有的程序练习题与测试数据集都由任课老师来准备，这将是一个非常庞大的工作量，并且刚参加工作的教师不一定具备出题的能力。因此，在教学中可采用在线的可免费使用的OnlineJudge 系统完成平时训练，如CCF（中国计算机学会）提供的程序设计在线评测系统（http://oj.noi.cn/oj/），系统中的题目含基本的程序设计算法类题目，教学中可先对题目作出筛选，设计好学生需要完成的题目，要求学生注册账号后按时完成老师要求的题目，但由于教师无法通过系统监控到学生的完成情况，教师可在线下检查学生的完成情况。为了达到良好的训练效果，线下监督是关键，不然学生没完成或直接复制别人的代码。要求学生至少完成其中的200 道题目，当学生有一定基础后，可适当增加难度。待学生有一定基础后，再选择如POJ、ZOJ 之类的Onlinejudge 系统，教师根据教学大纲与教学计划，先作好题目的规划，再组织学生完成有一定难度的题目。

3.2 自搭OnlineJudge系统完成测试与末考

在数据结构的教学中，如果任课教师需要自己开发一套OnlineJudge 系统，其难度还是比较大的。任课教师可以在网上寻找开源的OnlineJudge 系统进行安装后使用，比如哈工大的Onlinejudge，Hustoj 等，教师可根据操作手册下载并完成安装，通常需要在校园网内搭建即可，一般情况下用几台普通的计算机便可实现搭建适用于教学的Onlinejudge 系统。Onlinejudge 系统中最核心的是题库建设，任课教师可逐步完成自己的题库，在开始时，可在网上下载已经出好的数据集，熟悉后再进一步自己出题，还可在网上购买别人的试题。建立题库后及时对学生进行测试，在课堂上利用课前十分钟完成一道学生练习过的程序题，旨在检查学生是否在课下完成老师布置的任务，小测完成后无需讲解。

在期末考试中变笔试为机考，一方面大大减轻了老师的阅卷工作量，另一位方面更能检测出学生的程序设计水平，Onlinejudge 系统可当场出分，学生可当场知道自己的分数，能公平客观地反映出学生的学习情况。

4 结束语

将Onlinejudge 引入数据结构课程的课堂教学中，变传统的笔试为机试，体现了以学生为中心，加强学生动手能力的训练，从而提高学生的程序设计能力。经过近几年的教学实践，学生的程序设计能力大幅提升，教学效果明显。