董晓璇， 叶建芳， 孙一萍

(东华大学 信息科学与技术学院， 上海 201620)

0 引言

作业训练与考试作为评测手段是教学过程中不可或缺的一环，而信息技术的快速发展使得基于Web在线作业与试卷生成系统成为计算机辅助教学中重要的组成部分[1]。该系统在一定程度上避免传统作业模式下普遍存在的作业抄袭现象；另一方面，克服任课老师命题的主观性。系统根据教学大纲要求，能够选择一个高效、科学、强壮的算法组卷是关键[2]。

目前常用的组卷算法有随机抽取法、回溯试探法与遗传算法。遗传算法具有全局寻优和收敛速度快的特点，但算法复杂、容易“早熟”[3]，而且当试题库比较大时，容易导致染色体编码过长，所花费的时间开销呈线性增长，同时对于小规模的试题库而言，有可能导致两次产生的试卷具有较高的试题重复率。

随机抽取法尽管结构简单，易于理解与实现，适合于小型的题库系统，在现有的大量考试系统中也有广泛应用，但是传统的随机抽取法是根据组卷状态空间的控制指标，随机抽取一道符合指标的试题，不断重复此过程。不难发现，该算法可能在证明已无法抽取合适试题的区域反复选题，进行大量无效操作，导致访问数据库过于频繁，从而增加组卷时间，甚至进入死循坏导致组卷失败[4]。在文献[5]中提出集合随机组卷算法，采用集合和题号预存的方法解决了反复回溯匹配问题，但是预存题号加大了空间的占用，对试题难度的控制较为粗略。……