浅谈如何通过在线判题考查基础数据结构

开篇：润墨网以专业的文秘视角，为您筛选了一篇浅谈如何通过在线判题考查基础数据结构范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

【摘要】要考察考生程序的健壮性时要考察程序能够很好地应对大输入量，老师就很难给予如此多的输入测试而计算机却可以。同时，通过在线判题也能够给考生提供实时的训练机会。在线判题还有一个特点就是系统、全面。在线判题汇聚了诸多类型的题目，并且具有系统性，能够将数据结构的各类知识汇聚在一起。

【关键词】考生，在线判题，数据结构

1、为什么使用在线判题

在线判题就是利用计算机自行判断考生提交的代码是否符合题目的要求，来减少老师的工作量，提高考生的代码编写能力。通过在线判题还能做到老师难以做到的事情。比如：要考察考生程序的健壮性时要考察程序能够很好地应对大输入量，老师就很难给予多次的输入测试而计算机却可以。

同时，通过在线判题也能够给考生提供实时的训练机会。无论何时何地，只要有计算机和网络，考生就能够练习数据结构。

在线判题还有一特点就是系统、全面。在线判题汇聚了诸多类型的题目，并系统的将数据结构的各类知识汇聚在一起。

在线判题系统又是如何提高考生的编程能力的呢？我们先列举出如图1.1的步骤。

2、题目类型分析

针对考察考生算法理解和运用阶段的不同，题目类型当然不同。由于数据结构还需要考虑算法的时间以及空间复杂度，因而有一些差别。接下来介绍几类运用于在线判题的题型。

2.1输出中间过程题

此类题目是考察考生是否了解算法步骤。如直接插入排序的考查就适合使用此类题型。

直接插入排序是将序列分为有序序列和无序序列，将无序序列中的第一个数插入到前面有序序列中，在有序序列中比刚才选出的数大的往后移动，直到选出的数能够放在合适的位置。如图2.1。排序的效果就是将某个序列有序化，对于函数库中已有的函数，用直接插入排序较为复杂，因此无法在算法复杂度上面考察直接插入排序。所以最好的做法就是通过输出中间过程来考察考生是否有效掌握了直接插入排序。于是就可以出下面的题目：

题目描述：直接插入排序的做法是将原始序列分为有序序列和无序序列两组。开始时有序序列中没有元素，而无序序列包含原始序列中的所有元素。每次从无序序列中将第一个元素取出插入有序序列中，有序序列中比取出的元素大的元素相应往后移动，如图2.1。

任务：将每行插入后的状态输出来。

输入：输入数据首先是一个整数N，代表有N组测试数据。每组测试数据有两行，第一行是一个整数m，代表这组序列有m个元素，第二行是这组序列中的m个元素。

输出：每组测试数据输出相应的m+1行，这m+1行中的第1行输出Case n：，n是输出的第几组序号。第i+1（0

2.2直接运用题

直接运用题考查的是考生直接运用某种算法的能力。这种题目对于考生来说并不困难，但对出题人来说较麻烦，若在线判题的题目使考生可运用其他算法解决，就无法达到出题目的。因此须切中考点，限定考生使用特定算法。例如可以出以下题目：

题目描述：金和欧比旺在纳步星（Naboo）受到敌人的攻击，逃亡途中他们得到了一份秘密文件。奇怪的是文件里只有数字、空格和加（+）、减（-）、乘（*）、除（/）四种符号。经过爱因斯坦的鉴定，得知这些数字和符号组成的原来是矮人国流传已久的后缀表达式。只要将这些后缀表达式解出就可避免一场腥风血雨。

输入：有多组输入数据，每组数据一行。每行就是一个后缀表达式。每个运算符都是双目运算符。数字之间、运算符之间以及数字与运算符之间用空格隔开。

输出：求解出这些后缀表达式，每行后缀表达式的结果输出到一行。

3、结论

由于在线判题就是利用计算机自行判断考生提交的代码是否符合题目的要求，减少了老师的工作量，提高了考生的代码编写能力，可以解决老师难以解决的问题。无论何时何地，只要有计算机和网络，考生就能够练习数据结构，有着非常广泛的实用性，并且具有可操作性，应用前景十分看好。

参考文献：

[1]徐孝凯，魏荣《数据结构》，机械工业出版社，1996年

[2]徐孝凯《数据结构简明教程》，清华大学出版社，1995年

[3]陈文博，朱青《数据结构与算法》，机械工业出版社，1996年

[4]许卓群，张乃孝，杨冬青，唐世渭《数据结构》，高等教育出版社，1988年

[5]李廉治，姜文清，郭福顺《数据结构》，大连理工大学出版社，1989年

作者简介：

冷雪琳（1989-）女，辽宁省营口市，现就读于浙江传媒学院新媒体学院信息管理与信息系统专业。