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

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

中圖分類號(hào)：TP311.52

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

1 分類隨機(jī)算法概述

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

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

2 分類隨機(jī)算法的實(shí)現(xiàn)

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

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

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

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

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

2.2 數(shù)據(jù)庫表設(shè)計(jì)。探討組卷算法時(shí)，離不開數(shù)據(jù)庫的表結(jié)構(gòu)設(shè)計(jì)，和組卷相關(guān)的表應(yīng)有試題表（Question）、試卷配置表（Paper）等。

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

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

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

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

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

QuestionNum[]=10，30，10}；

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

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

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

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

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

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的所有記錄中，隨機(jī)抽取ListTypeLevel[type][level]個(gè)記錄。

}

}

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

3 分類隨機(jī)算法的擴(kuò)展

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

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；

}

}

}

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

4 結(jié)束語

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

參考文獻(xiàn)：

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

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

作者簡(jiǎn)介：呂東哲（1983.11-），男，科員，工程師，工學(xué)學(xué)士，研究方向：計(jì)算機(jī)軟件工程。

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