融入在线评测系统的“算法与数据结构”课程实验设计

【前言】融入在线评测系统的“算法与数据结构”课程实验设计由文秘帮小编整理而成，但愿对你的学习工作带来帮助。学生通过本课程的学习，能够掌握各种常用的数据逻辑结构、存储结构、基本操作以及算法设计，同时能够根据具体问题选择适合的逻辑结构、存储结构及相应的处理算法。培养学生数据抽象能力和复杂程序设计能力，为今后软件开发打下坚实基础。因此，本课程是计算机专业本科...

摘 要：“算法与数据结构”课程是计算机学科的专业核心基础课程，具有承上启下的重要作用。本课程的教学质量将影响学生后续课程的学习。本文针对“算法与数据结构”课程师生比过低，实验课教师查验程序正确性所费时间过多的问题，提出了将在线评测系统融入“算法与数据结构”课程的实验设计之中。从而，可有效减轻教师查验程序的负担，保证教师有更多时间用于辅导学生，提高实验教学质量。

关键词：在线评测系统 算法与数据结构 实验设计

【中图分类号】G【文献标识码】B【文章编号】1008-1216（2015）08C-0078-02

一、引言

“算法与数据结构”课程是计算机学科的专业核心基础课程，具有承上启下的重要作用。本课程上承“程序设计”（包括C语言程序设计、C++面向对象程序设计），下启“操作系统”“数据库概论”“计算机图形学”等专业课程。

学生通过本课程的学习，能够掌握各种常用的数据逻辑结构、存储结构、基本操作以及算法设计，同时能够根据具体问题选择适合的逻辑结构、存储结构及相应的处理算法。培养学生数据抽象能力和复杂程序设计能力，为今后软件开发打下坚实基础。因此，本课程是计算机专业本科教学的重中之重。

然而，目前内蒙古大学计算机学院“算法与数据结构”课程的师生比大体为1：60。在上机实验的过程中，教师查验程序所花费的时间占实验总学时的80%左右，导致教师辅导学生解决实验中遇到各类问题的时间非常有限，使得实验教学效果大打折扣。因此，为了提高实验教学质量，保证教师有更多的时间用于辅导学生，有必要改进实验教学查验程序的方式。

二、在线评测系统概述

ACM/ICPC是由美国计算机协会（Association of Computing Machinery，ACM）主办的世界范围内规模最大、水平最高的国际大学生程序设计大赛（International Collegiate Programming Contest，ICPC）。

在线评测（Online Judgment，OJ）系统源于ACM/ICPC。在国际大学生程序设计大赛过程中，参赛选手按问题提交代码，在线评测系统能够自动评判代码的正确性，并将评判结果返回参赛选手。在线评测系统评判代码的流程如图1所示。

在线评测系统的评判结果包括以下几种：

（1）正确（Accepted，AC）：程序正确。

（2）编译错误（Compile Error，CE）：代码编译错误。

（3）超时错误（Time Limit Exceeded，LTE）：程序运行时间超过限制。

（4）超空间错误（Memory Limit Exceeded，MLE）：程序运行所需内存超过限制。

（5）结果错误（Wrong Answer，WA）：程序运行结果不正确。

图1 在线评测系统评判代码流程图

（6）格式错误（Presentation Error，PE）：程序运行结果与结果文件不完全一致，主要是间隔符存在问题，如空格、逗号、分号等。

当在线评测系统返回的结果不为AC时，学生可根据在线评测系统反馈的错误提示，对源代码进行修改和完善，直至反馈结果为AC为止。

在线评测系统具有如下优势和特点：

1）实验教学在网络上进行，不受时间和空间的限制。

任课教师通过在线评测系统实验题目和要求，学生可全天候提交代码，因此学生可根据自身情况合理安排时间，在截止日期之前完成题目即可。

2）减轻教师查验程序的负担。

由于在线评测系统能够自动评测学生提交代码的正确性，因此能够有效减少教师查验程序的时间。教师可将更多时间用于辅导学生解决实验中遇到的各种问题和困难，提高实验教学效果。

3）有利于营造“你追我赶”的学习氛围。

学生通过在线评测系统能够查看每道题目的提交情况以及何人、何时解决了该题目。这样，可在学生之间营造“你追我赶”的学习氛围，提高学生的积极性和主动性。

因此，如何按照在线评测系统的具体要求，设计“算法与数据结构”课程的相关实验，是本文所关注的主要问题。

三、基于在线评测系统的实验设计

在线评测系统的每道题目均需设定测试数据文件和结果文件，其中测试数据文件为程序提供输入数据，结果文件用于与程序运行结果的一致性比较。此外，在题目描述中还需指明测试数据的上、下限，以及输出结果的格式等内容，以便让学生在程序中定义符合要求的变量，控制程序运行结果的输出格式等。

为了能够让学生更好地掌握和巩固“算法与数据结构”课程所学知识，本课程分别为“线性表”、“栈与队列”、“二叉查找树”、“最小生成树”、“内排序算法”等核心内容配套相关实验。下面将以“栈与队列”的配套实验为例，介绍如何将该实验设计成满足在线评测系统要求的题目。

【题目描述】：设停车场是一个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在停车场的最北端），若停车场内已停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入停车场;当停车场内某辆车要离开时，在它之后进入的车辆必须先退出车场为它让路，待该辆车开出大门外，其他车辆再按原次序进入车场;每辆停放在车场的车在它离开停车场时，必须按它停留的时间长短交纳费用。试为停车场编制按上述要求进行管理的模拟程序。

【程序输入】：输入数据的第一行包含两个正整数n和m（n， m<=10）分别表示停车场的容量和每小时停车费用。从第二行开始，每行表示一组输入数据，由三项内容构成：

（1）一个大写英文字母，表示汽车“到达”或“离开”信息，输入'A'时，表示汽车达到，输入'D'时，表示汽车离开，输入'E'时，表示程序结束;

（2）一个正整数X，表示汽车牌号;

（3）一个正整数T，表示汽车到达或离开的时刻。这三项内容之间以一个空格间隔。

【程序输出】：对每一组输入数据进行操作后的输出信息为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置;若是车辆离开，则输出汽车在停车场内停留的时间（单位是小时）和应交纳的费用（在便道上停留的时间不收费），假设停车费为每小时m元。具体分为如下几种情况：

（1）如果汽车X到达，且停车场未满，则输出如下信息：“汽车X停靠在停车场Y号位置”（其中：X为汽车牌号，Y为停车场车位序号，1≤Y≤n）;

（2）如果汽车X到达，但停车场已满，则输出如下信息：“汽车X停靠在便道的Z号位置”（其中：X为汽车牌号，Z为便道的车位序号，1≤Z）;

（3）如果汽车X离开，且X在停车场内，则输出如下信息：“汽车X停车H小时，缴纳停车费M元”（其中：X为汽车牌号，H为停车时间，M为停车费用）;

（4）如果此时便道上的停车队列不为空，则将便道上的第一辆汽车停入停车场，并输出如下信息：“汽车X停靠在停车场Y号位置”（其中：X为汽车牌号，Y为停车场车位序号，1≤Y≤n）;

（5）如果汽车X离开，但停车场没有牌X的汽车，则输出如下信息：“汽车X不在停车场”（其中：X为汽车牌照号）。

四、结语

面对实验教学中繁重地查验工作，通过将在线评测系统融入“算法与数据结构”课程的实验设计中，充分利用在线评测系统的优势，有效减轻了教师的查验工作量，保证教师有更多地时间用于辅导学生，为学生解决实验中遇到的各种困难和问题，提高了实验教学质量。

在线评测系统也可以融入与“算法与数据结构”类似的其他课程的实验设计中，既能有效减轻教师查验程序的工作量，同时也能改善实验教学效果，提高教学质量。

项目信息：内蒙古大学“卓越教学团队”建设项目（2013-05），数据结构与程序设计系列课程教学团队。

参考文献：

[1] 张铭，赵海燕，王腾蛟，等. 北京大学“数据结构与算法”教学设计[J]. 计算机教育，2008，（20）.

[2] 赵玉兰，王俊义，周建涛，等. 数据结构与算法[M]. 北京：清华大学出版社，2008.

[3] 武建华. 基于ACM模式的数据结构实践教学改革与探索[J]. 计算机教育，2007，（12）.

[4] 卢玲，陈媛，苟光磊. 基于ACM竞赛的学习能力培养模式研究与实践[J]. 计算机教育，2013，（7）.

[5] 韩建民，钟发荣，赵相福，宋炯. 基于ACM-ICPC训练模式的数据结构实践教学探索[J]. 计算机教育，2013，（10）.