基于双向循环链表的分段随机组卷算法

张立忠 赵家宇 姜楠

摘要：针对计算机组卷中试题被重复抽取造成的执行效率低问题，提出了一种分段随机组卷算法。采用双向循环链表结构表示随机数的生成区间，通过已生成的随机数和随机步长值确定下一个随机数的独立生成区间。初始生成区间利用保存试题编号的数组下标集合获得。实验结果表明了本算法的可行性。与传统随机组卷算法相比，该算法随机选题时不需要频繁访问题库，并具有较高的执行效率。

关键词：分段随机； 双向循环链表；随机数；组卷；生成区间

中图分类号：TP391 文献标识码：A 文章编号：1009-3044（2012）33-8021-05

在课程自动化考核过程中，计算机自动组卷是其中的一个重要功能。自动组卷的实现多采用随机选取法并结合回溯试探的方法。随机选取法就是根据命题人提供的组卷指标由计算机程序从题库中随机选择一定数量的试题构成试卷。在这样的组卷过程中，由于试题的选取具有不确定性，通常利用回溯试探方法解决试题被重复抽取的问题。这种方法在题库中题量较多或组卷数量较大的情况下，耗费时间长，组卷成功率不高。

采用分段随机抽选法[1]和集合随机抽选法[2-3]将题库空间分段，通过缩小试题搜索的匹配范围可提高组卷效率和成功率，但这些组卷方法依赖试题数据库结构上的支持，尚未克服试题被重复抽取的缺陷。此外，基于遗传算法和模拟退火算法的组卷方法[4-5]对内存占用量大，运行时间长[6]。另有研究发现，虽然在题库中设置试题选中标识[7-8]可避免试题被重复抽取，但需长时间访问题库，增加了系统负担。

针对上述问题，该文提出一种新的随机组卷算法。采用双向循环链表结构表示随机数的生成区间。通过动态界定随机生成区间从根本上解决试题被重复抽取的难题。整个组卷过程不需要频繁访问数据库。实验测试结果表明了该算法是可行的。

1 算法描述

1.1 传统随机组卷算法[3]

传统随机组卷算法是利用随机函数在试题库中抽取符合要求的试题组成试卷，其过程是：生成一个不重复的随机数之后，以该随机数为试题编号到题库中选取试题，如果试题库中不存在以该随机数为试题编号的题目，则需要重新生成一个随机数继续选取试题。如果仍然找不到新随机数所对应的题目则必须再生成新的随机数，而且每次尝试都必须通过访问数据库来确定是否成功，反复调用随机函数的时间、进行比较的时间以及多次访问数据库的时间等累加起来，使得程序的效率大为降低。

1.2 分段随机组卷算法

为了解决传统随机组卷算法反复地回溯匹配的问题，需要考虑的是如何缩小搜寻匹配的范围以及随机数的非重复生成。任何组卷方法都是从试题库中按照一定的组卷指标和规则选取出指定数量的试题构成试卷。基于这个思想，将计算机自动组卷分成两步：第一步依据组卷指标筛选出候选试题，这个操作可借助于SQL语句完成；第二步从候选试题中随机抽取指定数量的试题，这一步是本算法的重点。

该文提出的分段随机组卷算法是在候选题库空间分段抽取试题，随机确定每一次抽题范围，且每次抽题范围相互独立；每段只随机选取一题，以便提高组卷效率。这里我们利用一个双向循环链表结构表示随机数的生成区间，并通过当前随机数和随机步长值随机确定下一个随机数的独立生成区间，使试题的重复抽取得以避免。

1.2.1 随机数的生成

候选题库的更新会影响试题编号的连续性，通过在试题库表中增加“随机数”字段可保证随机数产生区间的有效性[1-3]。这样做增加了数据库的存储及维护负担。该文用数组保存候选试题编号，并用数组下标集合作为随机数产生区间。随机数Rnd的生成公式：

在公式（1）中，Random为系统内部的随机函数，可产生0至1之间的随机小数。Start和Last分别表示数组下标的起止边界值。[…]为遵循四舍五入规则的取整运算。显然，[Rnd∈[Start，Last]]。

1.2.2 独立随机区间的生成

根据公式（1）可知，随机数的产生依赖于区间[[Start，Last]]。为了避免产生重复的随机数，根本的解决方法是为每个随机数提供独立的生成区间，即区间端点Start和Last的值在每个随机数生成之前应做相应的改变。这种改变与当前已生成的随机数Rnd相关，如公式（2）。

[Rnd<（Last-Start）/2] （2）

公式（2）成立表示Rnd代表的点位于当前区间的左半部分，则在[[Start，Last]]的左半区间为下一个随机数寻找一个随机生成区间，否则在[[Start，Last]]的右半区间寻找一个随机生成区间。这需要由公式（3）生成一个随机步长值p。

[p=Random×i，1i Rnum] （3）

公式（2）中的Rnum表示随机数的数目，即抽取试题的个数。[…]的含义同公式（1）。随机数的产生区间状态采用双向循环链表表示，其结点结构如图1所示。

在图1的结点结构中，num表示用于存储随机数的数据域，front和follow代表指针型数据域，分别指向当前结点的前驱和后继结点。独立随机区间的生成步骤如下：

1）生成区间首部Bm和尾部Lm两个初始边界结点，然后令Bm.num=Start-1，Lm.num=Last+1， Bm.front=Lm，Bm.follow=Lm，Lm.front=Bm，Lm.follow=Bm。

2）将Last =Lm.num-1，Start =Bm.num+1代入公式（1），把生成的随机数Rnd作为结点Store的数据域，同时将Store插入到Bm和Lm之间。

3）由公式（3）生成随机步长值p。根据公式（2）判断下一个随机数的产生范围。如果公式（2）成立，则不断移动Store指针指向其前驱结点；否则不断移动Store指针指向其后继结点。移动次数均为p次。

4）无效生成区间处理及新随机区间的生成：如果Store.numLast成立，不断移动Store指针指向其前驱结点，直到Store.numLast均不成立时为止。然后继续判断，如果Store.num-1>Store.front.num成立，修改随机区间的起止边界，即令起始结点指针Bm指向Store的前驱结点，终止结点指针Lm指向当前Store结点；如果Store.num+1

5）重复步骤（2）-（4），直到产生Rnum个随机区间为止。

1.2.3 算法实现

将已生成的随机数Rnd以Store结点的形式插入到一个双向循环链表中，并从当前Store结点出发，根据动态生成的随机步长值p为下一个随机数的产生界定一个独立随机区间，从而使得生成的每个随机数互不重复，直到生成Rnum个随机数为止。分段随机组卷算法过程rd的实现过程如下：

程序结束

2 实验结果与分析

硬件环境：Intel 双核1.73 GHz CPU和768M内存。仿真测试是在候选题库中有足够符合条件和数量试题的前提下进行。

测试了分段随机算法抽取不同数目试题的组卷时间。保存试题编号的数组下标Start=1，Last=10000。抽题数目Rnum分别取100，200，……，1000。图2的实验结果表明随着被抽取试题数量的增加，组卷时间呈现小幅度的线性增长趋势。这表明本算法具有较好的稳定性和实用性。

对传统随机算法与分段随机算法的组卷执行效率进行了测试。保存试题编号的数组下标Start=1，Last分别取1000，2000，……，9000。抽题数目Rnum=50。图3的实验结果表明，两种算法在计算机组卷中所需的时间随着题量的加大差距不大，但对同等规模的题库，分段随机算法的组卷时间稍小于传统随机算法。这是因为分段随机算法的时间消耗主要在独立随机区间的生成上，基于这些不断变化的随机区间即可生成互不重复的随机数，而传统随机算法的时间主要消耗在随机数的对比上，这个对比操作通常需要频繁访问数据库或者存储试题编号的整个数组空间。

从图3还可以发现，在抽取试题数目不变的情况下，分段随机算法的消耗时间并未随着试题数量的增加而显著增大。这是因为随机数及随机区间生成具有“随机性”，即不确定性。这种不确定性使得独立随机区间生成的时间消耗不会呈现出一定的规律性，从而体现出分段随机组卷算法的稳定性。

3 结束语

该文提出的分段随机组卷算法其核心思想是为每个随机数提供相互独立的生成区间，从根本上解决了组卷过程中试题被重复抽取的问题，提高了组卷效率和质量。实验结果表明本算法运行稳定，可靠性好。与传统随机组卷算法相比，分段随机组卷算法对试题数据库依赖性较弱，并具有较高的执行效率。

参考文献：

[1] 金汉均，郑世珏，吴明武.分段随机抽选法在智能组卷中的研究与应用[J].计算机应用研究，2003，20（9）：102-103，126.

[2] 王萌，金汉均，王晓荣.集合随机抽选法在智能组卷中的研究[J].计算机工程与设计，2006，27（19）：3583-3585.

[3] 丁庶炜，闫宏印，王世兵.基于集合随机抽选法的智能组卷的研究与应用[J].电脑开发与应用，2010，23（5）：10-11.

[4] 李霞婷，宋荣.改进型遗传算法在组卷系统中的研究与设计[J].电脑知识与技术，2011，7（20）：4947-4948.

[5] 陈瑛琦，赵蕾，邓林.基于模拟退火遗传算法的自动组卷系统的研究[J].电脑知识与技术，2010，6（11）：2719-2720.

[6] 胡楠，谢政权.基于混合求解算法的智能组卷研究[J].科学技术与工程，2009（13）：3642-3645，3651.

[7] 李目海.组卷中的随机抽取算法分析与实现[J].枣庄学院学报，2007，24（2）：39-41.

[8] 庄越，黄君羡.基于知识点和改进随机抽取算法的智能组卷方案研究[J].计算机与数字工程，2009，37（6）：16-18，56.