考试系统中随机算法的应用

摘要：在线考试系统可以充分的利用学校已有的计算机资源和网络资源，将教师的工作量大大减轻，而且还把老师从出试题、阅试卷等繁琐的工作中解脱出来，极大的提高教师的工作效率。考试系统中最重要的一部分内容就是组卷算法，随机算法是作为常用的一种组卷算法，该算法简单，易于实现，具有很好的操作性。该文主要探究的就是随机算法在在线考试系统中的应用。

关键词：在线考试系统；组卷算法；随机算法

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2013）28-6378-02

根据社会的进步和计算机技术和教育教学手段的不断创新与改革，考试形式已经发生了巨大的变化，如由纸质考试向网络考试发展，从传统的纸笔考试到计算机辅助考试，以及发展到最新的基于网络的无纸化考试。利用学校已有的计算机资源和网络资源，实施无纸化考试，是目前研究和应用十分广泛的领域。它是一种新兴的考试模式，把教师从出试卷、改试卷的繁忙工作中解脱出来，提高了教师的工作效率，同时也提高了考试效率。现在的社会，多种多样的职业资格证书考试、职称证书考试、学历考试等随处可见，这些考试的类型在不断增加，考试的要求也在不断的提高，而传统的出题方式和考试形式已不适应现代社会考试的需求和发展，在线考试系统也应运而生。与传统意义上的考试相比，基于网络的无纸化考试系统是一种新鲜的考试模式，是传统考试和考场的延伸，充分利用宽广的网络空间，考生通过该系统可以不受时间、不受地域限制完成科目作业和模拟考试，尤其是数据库技术在网络方面的运用，使考试过程更加简单化。但试题的组卷方式将是一个很值得探讨的问题。组卷算法的优劣直接决定着自动组卷系统的性能，一个好的组卷算法既要能够保证组卷的成功率，同时又要保证数据运算的时间效率。下面将详细的介绍随机算法在在线考试系统中的应用。

1 传统的随机组卷算法

随机算法在考试系统中的应用是非常广泛的，该算法通常情况下是采用选取法与回溯试探法相结合的方式，根据状态空间的控制指标，由计算机系统调用随机函数rand（n）产生一个从1到n之间的随机数，然后根据随机数去匹配数据库中试题库的编号把试题从试题库中抽取出来放入试卷库中，依此再重复该过程，在重复的过程中需要检验抽取的试题在试卷库中是否已经存在——出现重复、难度是否符合难度约束等一系列的要求，如果不匹配再调用随机函数rand（n）重新生成一个新的随机数，再抽取、检测，如此往复直到组完试卷为止，方法容易、易于理解与实现，十分简单，但是该方式效率低下，在大量题库系统中不宜采用。回溯试探法是记录随机选取产生的状态，搜索失败再释放上一次记录的状态类型，然后按照一定的变幻规律，用新的状态进行试探，通过不确定的回溯试探法直到生成满意的试题卷止。但在数据库很大且题量较多时，组卷时间就会很长，并不符合试题组卷的要求。还有一些基于自适应的组卷方法，把题目的属性约束存入一个矩阵，用遗传算法进行交叉运算和变异运算得到各指标权重最有的个体，从而得到满意的试卷，然而这个组卷方案对于题库的要求也非常高。分段随机抽选法事将试题库按照一定的规则分类，再从不同的类别随机抽选试题，来保证出题的分数合乎规则，这种算法应用对于题库的要求更高。

随机算法虽然理论上能够保证每道题被抽到的概率相同，但实际操作起来，经常会出现某道题被抽到的次数非常多，而某道题都没被抽到，这就与随机的等可能性相悖。下面以某班学生使用了在线考试系统进行某门科目考试为案例来进行分析。

该班共有38名同学进行了某门科目考试，每份试卷100题，题库中总共有1000道题目，学生考试后每道题目被抽到的次数如下表所示：

从上表中可以看出，题目被抽取到得次数差距较大，最少的是0次，最多的达到13次，所以理论上的等概率性实施起来并不是均等分配，当然其中主要原因是因为抽取试题次数不够多，如果随着抽题次数的不断增加，均等分配的可能性会越来越大。

2 改进算法

对于该系统中上述的算法缺陷，作者提出了一些方法以克服上述缺陷，具体如下：

每道题在数据库中存储时增加一个常量ave和一个变量count。

ave：每道题目抽取的次数不能超过该值；考生人数stu_sum，每份试卷的题目数exam，题库中题目总数ex_sum，ave=（stu_sum*exam*2/ex_sum）四舍五入；乘以2的目的是为了解决stu_sum*exam / ex_sum小于1时，ave的值限制了组卷的成功；同时乘以2后，放大了ave的值，增加了更多的随机性。

count：每道题目抽取的次数；

该算法中通过控制每道题目出现的次数count值不能大于ave的值。

除了以上的改进，还需添加一些约束，当然约束也不能太多，多了可能导致组卷时出现死循环，不能正常组卷，约束少了又很难获得成功的组卷，根据作者的研究，可以向其中添加如下的约束：如题量约束、选中状态约束、题型约束、知识点约束、难度约束和时间约束等约束，以保证试卷组卷的成功率。具体如下：

1） 约束试卷中题量

在一份试卷中，要对试卷的长度要加以控制，不能太长也不能太短，因此要对试卷的题量要有明确的约束，否则试卷的长度将难以控制。设每份试题的数量为m，每条题目的分值为bi，则存在如下约束ⅰ

2） 约束试卷中题型

根据考试科目的特性，不同的考试会有不同的考试题型，这就导致试题库中可能会存在多种题型，但并不是每次考试都需要用到所有题型，设置题型约束条件时明确考试的题型，每种题型的题量和每种题型的分值，设题型的数量为n，每种题型的题量为Ti（未选中题型的题量为0），每种题型的分值为Si（未选中题型的分值为0），则存在如下的如下约束ⅱ和约束ⅲ

3） 约束试卷中的知识点

众所周知，一份完整的试卷应该要包括知识体系的所有部分内容，只不过各个知识点的分值有所差距，每个知识点抽取试题的分值由根据知识点的重要性来决定，设知识点数量为j，每个知识点抽取的试题分值为Fi（如果某个知识点试题未被选中，则该分值为0），则存在如下约束ⅳ

4） 约束试卷的难度

在关系数据库中，存放试题的数据表有难度系数约束字段，在设置试卷难度系数时，可以根据学生的实际情况设置不同的试卷难度系数均值，设难度系数均值为N，选中的每道试题的难度系数为Ni，则存在如下的约束ⅴ

5） 约束考试时间

根据各个科目的特性，考生在考试时，系统应能够限制同学们的考试时间。设置学生考试时间为T，则考试最长时间不能超过设置的时间T。

3 结束语

组卷算法设计是在线考试系统设计的核心，该文通过对传统的随机算法进行改进，添加几个约束，形成了一个较好的随机算法，使得该算法在在线考试系统中克服了很多的缺陷，也为在线考试系统的实现提供了新思路。通过该思路，大大降低试题抽取的难度，而且可以一次抽取成功，进而很好地解决随机组卷中抽取试题效率低下和难以一次成功等问题。

参考文献：

[1] 于志敏，刘延华.选题组卷策略研究[J].电脑开发与应用，2001，14（3）：32-34.

[2] 刘博.智能教学系统中个性化题库的设计与实现[J].中国电化教育，2010（9）：110-114.

[3] 殷荣庆.题库系统的设计与研究[J].安徽教育学院学报，2004，22（6），36-40.