分类分段回溯试探算法在计算机基础在线考试系统中的应用

高欢欢

摘要：组卷算法有很多，回溯试探法结合分类分段算法，有效缩小回溯搜索范围，能解决试题重复率高、知识点覆盖面小的问题，提高了组卷效率。采用分类法，按照不同题型把题库分为5类，缩小了搜索范围，解决了知识点覆盖面问题。将试题按照章节、难度系数分段，将具有相同属性的试题分配到一个集合中，再从每段中随机抽取满足约束条件的一定数量试题组卷，解决试题重复率问题。将这种算法应用到在线考试系统中，生成满足需求的试卷。

关键词：在线考试系统；回溯试探算法；组卷

DOIDOI：10.11907/rjdk.1511643

中图分类号：TP319

文献标识码：A 文章编号：1672-7800（2016）005-0157-03

0 引言

计算机基础课程是大学的必修课程，计算机基础考试逐渐由传统笔试向机试转变，这种转变既能考查学生基础知识的掌握程度，又能考查学生的实际操作能力，减轻了教师负担，保证考试的公平、公正。组卷技术是在线考试系统实现的核心，目前组卷算法很多，常见的类型主要有简单随机抽取算法、回溯试探算法、遗传算法。

（1）简单随机抽取算法是从题库中随机抽取一定数量的满足预先设定条件的试题组成试卷。这种方法实现简单、容易理解、组卷速度较快，但是抽取的试题重复率高，尤其是题库小的系统[1]。

（2）回溯试探法是随机抽取算法的改进，它采用随机抽取算法从题库中抽取试题，如果满足条件就将试题标记放入预先建立的栈中，如果抽取的试题不满足条件，就返回到上一个成功状态，继续随机搜索。它有效地解决了简单随机算法的试题重复抽取问题，实现简单，但只适用于小型题库系统。对于大型题库来说，需要占用很大的内存空间，且组卷时间长、效率低。

（3）遗传算法是模仿生物界中遗传、变异、交叉等过程，依照基因组合原理对染色体进行编码，按照优胜劣汰的原则得到最优解。这种算法具有全局寻优、智能搜索和收敛速度快等优点，但是实现困难[2]。

柳浪涛、谷林[3]提出了一种“卷内分块、组块分层”的组卷机制，按照题目类型分为若干块，按块分别抽题。按照题型分块，即为题库分类；块内分组，即为不同类型试题分组。分类算法是指按照题型设计将题库分类，解决知识点覆盖面的问题，而分段算法是将各类题型试题按照“知识点”、“难度系数”字段分组，从每组试题中按照试题数量比例抽取相应的试题，以解决试题重复抽取问题。题量越大，抽取效果越好。

综合考虑算法难易、组卷速度、知识点覆盖率、试题重复率等问题，本文采用分类分段回溯试探算法。分类分段算法结合回溯试探算法，综合利用了两者的优点，弥补了两者的不足。首先将题库按照不同题型分类，然后再对不同类别的试题按照知识点、难度系数字段分段，最后对每类题库根据预先设定条件随机抽取试题。回溯试探算法是对简单随机算法的改进，随机抽取一道题加入试卷，系统将记录下这道题的知识点、试题序号放入预先建立的栈中，再根据约束条件随机抽取下一道题，将这道题的知识点、试题编号与上一道题记录下的知识点、试题序号相比较，如果不同，则将试题加入试卷并释放上一个记录，并写入这道题的属性，如果相同则重新抽取试题，以此类推。回溯试探法结合分类分段抽取法，有效缩小了回溯搜索的范围，提高了组卷速度，解决了试题知识点覆盖面、试题重复抽取以及知识点覆盖面问题。

1 数据库设计

题库设计质量的好坏对组卷成败至关重要。本文采用分类分段回溯试探算法，在试题库中按 “难度系数”排序，再按 “知识点”排序。排序后，同一个知识点的同一难度系数试题放在一起，组卷就是从同一知识点同一难度系数的题目中随机抽取指定数量的题目[4]。

计算机基础在线考试一般分为选择题、填空题、Excel操作题、Word操作题、Windows操作题几类。为了提高组卷效率，需要预先确定试卷为百分制，然后确定题型题量、小题分值、知识点分布等属性，这些设置好的试卷属性字段都统一存放在PaperSet数据表中。按照试卷属性设置表中数据，每种题型分别从相应的题库中抽取。题库表分为选择题及操作题。

选择题题库表结构如表1所示，操作题题库表结构如表2所示。其中“questType”字段表示为题型设置编号，“1”代表选择题，“2”代表填空题，“3”代表Excel操作题，“4”代表Word操作题，“5”代表Windows操作题。表2中的“OperateType”字段指每种操作题的操作类型，用数字代表不同的操作类型，例如Word操作题中“1”、“2”、“3”数字分别代表“表格操作”、“文本替换”、“段落缩进”操作类型，Excel题型主要设计有“单元格样式”、“行列样式”、“工作表操作”、“生成图表”等操作类型， Windows操作题主要设计有“文件夹删除”、“文件夹创建”、“文件夹重命名”、“文件复制”等操作类型。此外，题库中的“Chapter”字段，用数字代表不同的知识点分布，用“Degree”难度系数划分 “简单”、“中等”、“较难”、“困难”，分别用数字“1”、“2”、“3”、“4”来存储。

2 组卷

将在线考试系统设计的5种题型分为5个模块，在页面设置5个事件按钮，考生点击一个按钮将随机从相应题库抽取确定数量的试题，如图1所示。按照题型不同将题库分为5类，在这5大题库中又采用章节、难度系数的设定对每种题型进一步分组。题库中的每道题至少有如下4个属性，定义如下：

（1）分值：每道试题的分值，小题设置的分值与该题型的题量乘积即是该大题总分。设计试卷满分为100分，根据题型设置，单选题30分，15题，每题2分；填空题20分，10题，每题2分；Word题20分，5题，每题4分；Excel题20分，5题，每题4分，Window题10分，4题，每题2.5分。

（2）题型：试题的类型一般分为选择题、填空题、Excel操作题、Word操作题、Windows操作题等。给出试题类型，自动组卷将在给定的数据库表中搜索，缩小了搜索范围，加快了组卷速度。

（3）知识点：又称为考核点，它涉及具体考核内容，知识点按章节从前往后划分。每种题型预先设计一定数量的知识点，每道试题考查内容对应不同的知识点，每个考查的知识点录入一定数量的试题。

（4）难度系数：指测试试题的难易程度。它的定义是qi=1-Ri/n，qi表示第i题的难度系数，Ri表示此题平均得分值，n是该题的满分值[5]。试卷难度控制将容易、中等、困难试题所占比例进行设置。一般试卷的难度系数在中等才能使考试成绩成正态分布。题目区分度与它的难度相关，通常过高或过低题目的区分度都较小，中等难度的区分度最优[6]。

根据分类分段算法，按照题型设置，每种题型设置相应题库，分5次随机抽题。对于每类题库，再按照知识点、难度系数字段属性分配集合。根据回溯试探算法执行抽题，每种题型抽题的组卷事件触发按钮点击后，按照设定的难度系数、题型、题量等约束条件分别从相应的题库中随机抽取一道试题加入试卷中，将此试题的知识点、试题序号记录下来，再抽取下一道题，将这道题的知识点与上一题相比较，如果相同就放弃加入试卷并继续抽题，如果不一样即释放上一条记录，更新为当前记录。以此类推，直到完成组卷，算法描述如下：

3 实验结果

分类分段回溯试探组卷算法相较于随机抽取算法而言，解决了试题重复率高、知识点覆盖率小的问题，相较于回溯试探法而言解决了搜索速度慢、组卷效率低等问题。本文算法综合利用了分类分段随机算法以及回溯试探算法的优点，摒弃了它们的不足，代码实现较为简单，能够生成需要的试卷。

4 结语

本文采用的分类分段回溯试探算法，结合了简单随机抽取算法和回溯试探算法的优点，实现简单，大大缩小了搜索范围，组卷速度快且避免了试题重复率问题。在线考试组卷系统兼顾了题型、题量、分值、知识点分布、难度系数等试卷参数，能快速得到一份满意的计算机基础在线考试试卷。

参考文献：

[1]王琦.智能组卷算法研究比较[J].科技信息，2008（29）：403-418.

[2]高兴媛，古辉.在线考试系统自动组卷技术的研究与实现[J].计算机与现代化，2011（3）：155-157.

[3]柳浪涛，谷林.自动组卷系统试题难度和知识点覆盖控制算法[J].西安工程大学学报，2015，29（3）：321-324.

[4]雷勇.分类分段算法在组卷中的应用研究[J].实践与经验，2014（19）：41-44.

[5]桂阳，王修信，农京辉，等.大学物理试题库智能组卷随机抽取法的改进[J].广西物理，2008，29（2）：23-25.

[6]严思静，常红春.蚁群算法在组卷中的应用[J].职大学报，2014（6）：83- 87.

（责任编辑：杜能钢）