计算机考试系统随机生成算法的研究与应用

陈磊

（渤海船舶职业学院，辽宁兴城125105）

计算机考试系统随机生成算法的研究与应用

陈磊

（渤海船舶职业学院，辽宁兴城125105）

随着计算机应用技术的不断发展，开发计算机考试系统实现无纸化考试，成为近年来一个非常活跃的研究领域，而随机生成试题的功能是计算机考试系统的重要组成部分。基于Visual FoxPro程序设计语言的计算机考试系统中两种随机生成试题的算法，实现了随机生成题号和抽题功能的分离，简单实用且适合于多种计算机考试系统。

计算机考试系统；随机生成；算法；哈希函数法

在学校的教学过程中，考试环节是重要的组成部分。传统的考试方式在命题、组织考试、阅卷和统计分数的过程中，工作量大，要花费大量的时间和精力，而且工作效率比较低，也容易出现错误。

随着科学技术的不断发展，信息技术的不断进步，考试的载体和手段也发生了革命性的变化。如何运用计算机考试系统，客观、准确地评估应试者的知识和能力水平，已成为这个领域研究的重要内容。

1 随机生成试题的算法

作为一个完善的计算机考试系统，随机生成试题的功能必不可少。它是防止考生作弊、保证考试公平的一个重要手段。开发一个离散度高，效率也高的随机生成试题算法是随机生成试题功能的关键。

1.1 哈希函数法

在记录的存储位置和它的关键字key之间建立一个确定的对应关系即一个函数关系H(key)，使每个关键字key和结构中一个唯一的存储位置相对应，通常称这个函数H(key)为哈希函数。哈希函数是一个映像，即将关键字的集合映射到某个地址集合上，它的设置很灵活，只要这个地址集合的大小不超出允许范围即可。

由于哈希函数是一个压缩映像，因此在一般情况下很容易产生冲突。即key1≠key2，而H(key1)=H(key2)。因此，在设计哈希函数时，一方面要考虑选择一个好的哈希函数；另一方面要选择一种处理冲突的方法。所谓正确的哈希函数，指的是对于集合中的任意一个关键字，经哈希函数得到的哈希地址尽可能均匀地分布在线性表中的n个连续内存单元地址上，从而减少冲突，同时使计算过程尽可能简单以达到尽可能高的时间效率。

以笔者开发的计算机考试系统为例，原始题库是以二维表的形式存在的，以计算机基础题库为例，单选题60个，题号1至60。通过随机算法将60个单选题的原始顺序打乱生成一组新的排列顺序，然后按照这组新序列抽题、组题。哈希函数的构造方法采用随机数和除留余数综合的方法。1至60的数据集合作为关键字的集合，用i代表关键字，通过随机函数产生一个随机数rd作为因子乘以关键字i再除以一个等于或大于哈希表长度n的整数p后得到的余数作为此关键字的哈希地址，该地址保存到数组中。见以下表达式：

整数p选择了与n相邻的大于或等于n的质数，比如本例中单选题60个，p取值为质数61，因为质数是除了1和该数本身再也不能被其他数整除的数，所以连续的数据集合除以p取余数，产生冲突的可能性非常小，并且所得地址小于61，能够均匀地分布在1至60区间。经实验证明本例使用这种方法冲突率为0。

但是这种方法有一个弱点，它的理想状态是题目总数的下一个数恰好是质数，此时函数值的冲突率为0，且完全均匀地分布在指定区间。如果不是理想状态，就会出现两种情况，第一种情况，p值取题目总数的下一个数但不是一个质数，则函数值冲突率不为0；第二种情况，p值取大于或等于题目总数的相邻质数，但该质数不是题目总数的下一个数（比如共有55道题，大于等于55的相邻质数为59），则函数值不能完全均匀地分布在指定区间。

针对上述问题处理冲突的基本思想是：当发生冲突时，将待插入函数值存入另一个不产生冲突的地址中，从而解决冲突。本例采用的处理冲突的方法是开放地址法。所谓开放地址即未填入数据的空闲地址。开放地址法就是为产生冲突的记录求得一个地址序列：

增量di有三种取法：线性探测再散列、二次探测再散列（也称平方探测再散列）和随机探测再散列，本例采用线性探测再散列：di=i即di=1，2，3，…

增量di具有下面的特性：产生的Hi均不相同，且所产生的s(m-1)个Hi值能覆盖数组中所有的地址。

1.2 数组下标随机抽取法

首先将原始题号保存在数组ord（ns） 中，变量ns为题目总数，也是循环结构的终值，然后在循环中通过表达式int(rand()*(ns-i+1)+ 1)依次生成随机下标保存在变量idx中，在Visual FoxPro中随机函数rand()的函数值为大于等于0并且小于1的数，乘数 (ns-i+1)说明数组使用的长度不断缩小。通过表达式r(i)=ord (idx)，将随机下标对应的数组值保存到r(i)，将原始题号数组ord（ns） 中已抽取的数据ord (idx)依次与该数组后面的数据回溯交换，这样已用过的数组值被交换到后面去，未用过的数组值被交换到前面来，在从未使用的关键字中，获得新的关键字，直到循环结束。

在这种方法中，虽然下标idx可能是重复的即产生冲突，但是按此下标抽取的数组值却是全新的，避免了冲突并且完全均匀地分布在指定区间。同时这种方法不受题目数量的影响，调整方便。程序代码如下：

2 随机数的产生方法

随机生成一组不重复的题目，这个过程关键是由随机数来实现的，虽然在很多高级程序设计语言中提供了相当于rand（）这样产生随机数的函数，但是它产生的随机数并不能完全符合实际应用的要求，我们知道计算机不可能产生完全随机的数字，电脑中的随机数发生器都是通过设计的算法对事先预设的随机种子做相应的运算，最后得到的结果用来模拟完全随机数。这种随机数被称作伪随机数，伪随机数是以相同的概率从一组有限的数字中选取的，这会导致多名学生抽到相同的试卷，或同一个学生在不同的时间运行计算机考试系统会抽到相同的试卷。所以如何避免产生重复随机数就成了我们必须解决的问题。

解决的方法之一是采用计算机内部时钟的秒数当种子，因为电脑内部时间的秒数时刻都在变化，所以产生的随机数种子相同的可能性就很小，在Visual FoxPro中获取时钟的秒数的表达式如下：

该表达式中提取的秒数除以10取余数，可将随机种子的范围限定在0到9之间，秒数的取值范围为0到59，可根据实际需要对不同的数值进行除留余数的运算，以调整随机种子的范围。

3 SQL语句左连接操作抽取试题

随机生成的试题顺序有了，接下来要解决的就是如何把原始试题按随机顺序抽取出来，首先创建一个具有“题号”字段的数据表cf2，通过循环结构和replace命令将随机生成的试题顺序加入到表cf2的“题号”字段中，SQL语句的select-from-left join左连接操作，即结果中只出现左表中出现的记录，右表若无满足连接条件的记录，则相关字段的值取空值。连接过程中表cf2定义为左表，原始表定义为右表，通过左连接操作将原始表中的相关字段按照表cf2的题号顺序连接成一个新表，即可完成抽取试题的功能。然后关闭并删除表cf2，将新表的题号按照从小到大的顺序重新排列，程序代码如下：

replace record i题号with r(i)

next

select cf2.题号,cf.题型,cf.试题,cf.学生答案, cf.答案,cf.对错,cf.选项数;

from cf2 left join cf;

on cf2.题号=cf.题号into dbf cf3

*执行上面sql语句，不论cf2和cf是否打开，涉及到的三个表都会被打开，所以要关闭指定表

use in cf

use in cf2

drop table cf2&&用完删除cf2

for i=1 to an &&将题号重新按顺序排列

replace record i题号with i

next

4 分析与思考

上面介绍的两种随机生成试题的算法，都是用数组保存生成的随机数字。在生成随机数字的过程中没有同时抽取数据表中的记录，与一边生成随机数字一边访问数据库记录的算法相比，实现了随机生成题号和抽题功能的分离，便于后期的维护与完善，对于计算机考试系统的运行效率也有了很大提高。

[1]秦玉平,马靖善.《数据结构》(C语言版)(第二版)[M].北京:清华大学出版社,2012.

[2]周丽韫.基于ASP的在线考试系统随机生成不重复试题算法的研究[J].黑龙江科技信息,2011(9):92.

[3]段兴.Visual FoxPro实用程序100例[M].北京:人民邮电出版社,2002.

[4]熊发涯.Visual FoxPro程序设计[M].北京:中国铁道出版社,2005.?

［责任编辑：宋艳华］

Research and Application of Random Generating Algorithm in Computer Examination System

CHEN Lei
(Bohai Shipbuilding Vocational College,Xingcheng 125105,China)

With the continious development of computer application technology,it has become a very active research field in recent years to develop computer examination system to realize paperless examination.The function of randomly generated examination questions is an important part of computer examination system. Based on Visual FoxPro programming language computer test system,the two randomly generated test questions algorithm can achieve the separation of random qid and test extraction function,be simple and practical and suitable for a variety of computer test system.

computer examination system;random generation;algorithm;hash function method

TP312

A

2095-5928（2016）06-30-03

2016-09-15

辽宁省职业技术教育学会2015年立项课题（LZY15412）

陈磊（1982-），男，山东金乡人，讲师，学士，研究方向：计算机应用。

10.16850/j.cnki.21-1590/g4.2016.06.009