基于分類隨機算法的試卷生成算法研究

摘 要：隨機算法是設計在線考試系統(tǒng)時常用的一種組卷算法，本文在簡單隨機算法的基礎上，提出了一種行之有效的分類隨機算法，同時給出了具體的實現(xiàn)方案，并對該算法的擴展性進行了研究。

關鍵詞：隨機算法；考試系統(tǒng)；試卷生成

中圖分類號：TP311.52

隨著信息技術與網(wǎng)絡的迅速發(fā)展，在線考試已成為組織考試的主要方式之一。與傳統(tǒng)考試方式相比，在線考試有著獨特的優(yōu)勢，它能將考試過程中的試卷組織、審定印制、傳送收集、登記分發(fā)、評判歸檔等各個環(huán)節(jié)縮短到一至兩個環(huán)節(jié)。因此，研究如何設計一個好用的在線考試系統(tǒng)具有重要的現(xiàn)實意義，而支撐考試系統(tǒng)的核心之一則是組卷算法，本文在常用的隨機算法的基礎上提出了一種優(yōu)化的分類隨機算法，并對該算法進行了擴展，使其滿足用戶更細致的要求。

1 分類隨機算法概述

在進行試卷生成算法設計時，首先要考慮到如何從試題庫中抽取出符合條件的試題，并且要做到隨機抽取、覆蓋所有設定的知識點且不重復。如果系統(tǒng)每次都從試題庫全集隨機對比約束條件進行抽取，勢必影響效率，所以，本文在簡單隨機算法的基礎上進行改進，首先利用若干個約束條件將試題庫全集劃分成若干個子集，并且把將要生成的試卷的試題總數(shù)按一定規(guī)則分解，每一個試題子集對應一個抽題數(shù)量，然后針對不同的試題子集隨機抽取出指定數(shù)量的試題，最后再將抽出的試題組成試卷。改進后的隨機算法可稱之為分類隨機算法，此法對每一次抽題而言，縮小了隨機抽題的范圍，提高了運算效率，而且，約束條件越多，劃分的試題子集就越多，對試題的抽取就更能精確地控制，因此，也就越能達到靈活配置試卷的目的。

分類隨機算法的重點之一在于如何根據(jù)約束劃分試題子集，首先要梳理約束需求，使得每個約束相互獨立而不是互相影響，只有這樣才能精確地劃分出試題子集。此外，約束并不是越多越好，因為有些試題庫的題目數(shù)有限，當約束越多，所劃分的試題子集就越多，每個子集中所含題目也就越少，很可能滿足不了抽出指定數(shù)量題目的要求。

2 分類隨機算法的實現(xiàn)

2.1 若干假定。為簡化研究，本文進行若干環(huán)境假定：

2.1.1 假定試題庫中試題類型只有判斷、單選、多選三種客觀題，生成的試卷也只有這三種題型。

2.1.2 假定試題庫中的每個試題的難易度以容易、中等、難三個等級區(qū)分，生成的試卷的整體難易度也以這三種等級區(qū)分。

2.1.3 假定試卷的整體難易度為容易時，試卷中的容易題比例：中等題比例：難題比例=70%：20%：10%；試卷的整體難易度為中等時，試卷中的容易題比例：中等題比例：難題比例=50%：30%：20%；試卷的整體難易度為難時，試卷中的容易題比例：中等題比例：難題比例=30%：40%：30%。

2.1.4 假定題庫中每道試題不定義固化的分值，管理員生成試卷時可隨意指定每類試題的分值。

2.2 數(shù)據(jù)庫表設計。探討組卷算法時，離不開數(shù)據(jù)庫的表結構設計，和組卷相關的表應有試題表（Question）、試卷配置表（Paper）等。

試題表的主要字段應包括所屬章ID（ChapterId）、所屬節(jié)ID（SectionId）、所屬知識點ID（PointId）、題目（Title）、題型（Type）、難度（LevelQuestion）等。

試卷配置表應能完整存儲考試管理員輸入的用來生成試卷的各種條件信息，故此表主要字段應包括試卷整體難易度（LevelPaper）、判斷題數(shù)量（SumType1）、判斷題分值（ScoreType1）、單選題數(shù)量（SumType2）、單選題分值（ScoreType2）、多選題數(shù)量（SumType3）、多選題分值（ScoreType3）。

2.3 算法設計。考試管理員在創(chuàng)建一份試卷時，應輸入一些必要的配置指令，這些指令應包括整套試卷的難度、每類題型的題量、每類題型的分值、抽題的章節(jié)范圍等。假設考試管理員準備創(chuàng)建一份試卷，他輸入的指令是：整套試卷難度為中等；判斷題10題，每題1分；單選題30題，每題2分；多選題10題，每題3分；抽題范圍指定為前三章。至此，系統(tǒng)已經(jīng)獲取足夠的信息來生成試卷了，其算法用偽代碼示例如下（以Java語言和Oracle數(shù)據(jù)庫為例）：

第一步：先根據(jù)題型和難度兩個維度構造一個二維整形數(shù)組ListTypeLevel，用來存儲分類抽取的題量。

//聲明QuestionNum數(shù)組，用來存儲按題型抽取的試題總量。

QuestionNum[]=10，30，10}；

//聲明Percent二維數(shù)組，用來存儲不同難度的抽題比例。

Percent[][]={70%，20%，10%}，{50%，30%，20%}，{30%，40%，30%}}；

//聲明ChapterId，用來存儲抽題范圍，本例假定范圍為前三章，則數(shù)組中假設存入id1、id2、id3依次代表前三章Id。

ChapterId[]={id1，id2，id3}；

//聲明ListTypeLevel，用來存儲分類抽取的題量。

ListTypeLevel[][]={0，0，0}，{0，0，0}，{0，0，0}}；

for（int type=0；type<3；type++）

{

for（int level=0；level<2；level++）

{

ListTypeLevel[type][level]=QuestionNum[type]*Percent[1][level]；

//遵循四舍五入法則

}

ListTypeLevel[type][2]=QuestionNum[type]-ListTypeLevel[type][0]

-ListTypeLevel[type][1]；

}

由上可以得出ListTypeLevel{{5，3，2}，{15，9，6}，{5，3，2}}。

第二步：根據(jù)得出的ListTypeLevel數(shù)組，分類抽取試題，并把抽取出來的試題的ID存入Record中。

for（int type=0；type<3；type++）

{

for（int level=0；level<3；level++）

{

Record=Record+select ID from Question

where Type=type and Level=level

and ChapterId in（ChapterId[0]、ChapterId[1]、ChapterId[2]）

and rownum<=ListTypeLevel[type][level]

order by dbms_random.random；

//在數(shù)據(jù)庫試題表中“題型”字段等于type并且“難度”字段等于level的所有記錄中，隨機抽取ListTypeLevel[type][level]個記錄。

}

}

經(jīng)過以上循環(huán)的累加，抽題集合Record就順利形成了。

3 分類隨機算法的擴展

以上是基本的分類隨機算法，可以滿足一般的在線考試系統(tǒng)的基本需求，就依上例所示，用戶如果提出手動指定前三章的抽題題量比重，則上面的基本算法還需做些擴展才行。假定用戶希望重點考一下第二章，希望整個試卷中三章試題的題量比例為25%，50%，25%，那么該怎樣擴展基本算法呢？其實只需要對上面已經(jīng)得到的ListTypeLevel{{5，3，2}，{15，9，6}，{5，3，2}}再加入一個“章”的維度，進行擴展即可，算法示意如下：

ChapterPercent[]={25%，50%，25%}；

for（int type=0；type<3；type++）

{

for（int level=0；level<3；level++）

{

for（int chapter=0；chapter<2；chapter++）

{

ex_ListTypeLevel[type][level][chapter]=ListTypeLevel[type][level]

*ChapterPercent[chapter]；

//遵循四舍五入法則

}

ex_ListTypeLevel[type][level][2]=ListTypeLevel[type][level]

-ex_ListTypeLevel[type][level][0]-ex_ListTypeLevel[type][level][1]；

}

}

由以上算法可得ex_ListTypeLevel數(shù)組的值為：

ex_ListTypeLevel{{{1，3，1}，{1，2，0}，{1，1，0}}，{{4，8，3}，{2，5，2}，{1，3，2}}，{{1，3，1}，{1，2，0}，{1，1，0}}}。

然后再根據(jù)ex_ListTypeLevel，分類抽取試題。

for（int type=0；type<3；type++）

{

for（int level=0；level<3；level++）

{

for（int chapter=0；chapter<3；chapter++）

{

Record=Record+select ID from Question

where Type=type and Level=level

and ChapterId=ChapterId[chapter]

and rownum<=ex_ListTypeLevel[type][level][chapter]

order by dbms_random.random；

}

}

}

至此，擴展后的組卷算法滿足了用戶對指定范圍內(nèi)不同部分靈活設置權重的需求。

4 結束語

通過以上敘述可以看出，分類隨機組卷算法將抽題的動作進行分解，根據(jù)管理員指定的試卷難度，試題類型及試題分值，劃分出若干小的分類范圍，逐一按要求抽取指定數(shù)量的試題，最后再組合成整個試卷。此種算法邏輯清晰，不可能出現(xiàn)重復抽題的現(xiàn)象，分值與難度分別界定，方便管理員靈活配置試卷總分及試卷難度，試卷的整體難度規(guī)則也可以通過管理端由管理員自定義。此外，算法本身具有較好的擴展性，方便研發(fā)人員根據(jù)用戶的需求增加必要的約束條件?？傊怂惴ㄔ趯嶋H應用中是一種行之有效的組卷算法，較好地滿足了在線考試系統(tǒng)的基本需求。

參考文獻：

[1]張亞輝.在線考試系統(tǒng)[D].吉林大學，2008.

[2]郭蘭英等.高校課程考試自動組卷算法的研究設計[J].現(xiàn)代電子技術，2009（16）：87.

作者簡介：呂東哲（1983.11-），男，科員，工程師，工學學士，研究方向：計算機軟件工程。

作者單位：公安部第一研究所 信息安全事業(yè)部，北京 100048