一種高效的隨機組卷算法的設計

周文君

（湖南安全技術職業(yè)學院，湖南 長沙 410151）

一種高效的隨機組卷算法的設計

周文君

（湖南安全技術職業(yè)學院，湖南 長沙 410151）

為了實現(xiàn)更好的教育測量，各大院校都在積極地進行題庫系統(tǒng)的建設，組卷算法作為該類系統(tǒng)的核心，是研究的一大熱點。本文分析了傳統(tǒng)的隨機組卷算法存在的不足，提出一種改進的隨機組卷算法，實驗結果表明，本算法能較快速地實現(xiàn)按要求組卷。

題庫系統(tǒng)；隨機組卷；存儲過程

1 引言

隨著高校信息化建設的推進，傳統(tǒng)的人工制卷方式已無法滿足高校課程考試的需求，其弊端也日益突顯，許多高校都在積極地探索和研發(fā)題庫管理系統(tǒng)，以期提高工作效率、實現(xiàn)教考分離、加強教學質量的監(jiān)控，從而促進教學。題庫管理系統(tǒng)中的關鍵技術是組卷算法的設計，即根據(jù)用戶的組卷意愿（包括考試內容、章節(jié)、各類型試題數(shù)量、難度系數(shù)、時間等一系列的要求），自動從試題庫中抽選試題生成試卷的過程，設計并實現(xiàn)高效、適合題庫的組卷算法是題庫管理系統(tǒng)重要的建設基礎。本文分析了傳統(tǒng)的隨機組卷算法的工作原理及特點，在此基礎之上提出了一種改進的隨機組卷算法。

2 傳統(tǒng)的隨機組卷算法

隨機算法是根據(jù)已經(jīng)確定的組卷方案進行隨機地抽取試題，最終合成試卷。隨機組卷算法也有多種算法結構，一種隨機算法是先計算出試題的總數(shù)N，生成一個1到N之間的隨機數(shù)，然后將這個隨機數(shù)作為試題序號來抽取題庫中的試題，并在確定當前題不與已有試題重復之后，將該試題放入試卷中，此過程不斷重復，直到抽滿所需要的試題個數(shù)，完成制卷；另一種常見的隨機算法，對前一種方式進行了改進，它將被抽取到的每一道試題都進行標記，這樣抽取新的試題時不需要再與已有試題查重，而只需要查看其標記就知道該題是否已經(jīng)抽取過，采用這種算法減少了試題查重的比較運算，但需要在數(shù)據(jù)庫中增加一個標記屬性列，且每道題仍需要判斷標記的值，若已抽取過，則需要重新生成一個隨機數(shù)，繼續(xù)循環(huán)。

傳統(tǒng)的隨機組卷算法中，抽題方法雖然相對簡單，但因為要避免重復抽取相同試題的情況，所以每抽取一道試題都需要將其與已有試題進行查重判斷，存在大量的查重比較，需要耗費大量的時間，且因為存在重復抽題的可能性無法控制，試題抽取的次數(shù)將可能遠遠超過實際所需的試題量，最終導致組卷效率低下。

3 改進的隨機組卷算法

3.1 獲取一組互不相同的隨機試題

經(jīng)過分析，隨機算法的關鍵是在于能高效地產(chǎn)生一組互不相同的隨機數(shù)，將這一組隨機數(shù)看成試題編號集，這樣就可以實現(xiàn)對于同一類題型就的批量抽取，且省略了試題查重判斷的步驟，從而大大提高隨機組卷算法的效率。

《Programming pearls》一書提供了一個非常經(jīng)典的隨機算法，這個算法可以快速地生成一組互不相同的隨機數(shù)，關鍵代碼如下：

for(i=0;i<=n;i++)

{ x[i]=i;}//初始化

for(i=0;i<=n;i++)

{

t=rand(i,n);//產(chǎn)生一個i到n之間的隨機數(shù)swap(x[i],x[t]);//交換值

out(x[i]);//輸出一個隨機數(shù)

}

上述算法的核心思想是把生成的隨機數(shù)從目標集合中剔除出來，從而得到指定范圍內互不重復的隨機數(shù)。在隨機

組卷算法中，從試題表中將滿足課程名稱、知識點要求、題型要求等組卷約束的試題集先篩選出來，得到一個中間結果集，將結果集中的試題編號賦值給數(shù)組變量（數(shù)組初始化操作），然后采用上述算法得到一組互不相同的、指定范圍內的試題編號的集合。本算法如果在數(shù)據(jù)庫服務器端采用存儲過程的方式來實現(xiàn)，數(shù)組初始化的操作則需要通過游標遍歷，將滿足條件的所有試題編號保存到數(shù)組中。

除此之外，在SQL Server數(shù)據(jù)庫中，可以直接通過top n結合order by newId（）子句來實現(xiàn)隨機抽題。newId()函數(shù)自動為關系表中每一條記錄生成一個隨機的uniqueIdentifier類型的唯一值，按照newId()對記錄進行排序，可以實現(xiàn)為數(shù)據(jù)表中的記錄進行隨機排序，通過選擇前n行試題來組成試卷。當處理的記錄行較多時，使用該子句也比較消耗系統(tǒng)資源，通常在一定的數(shù)據(jù)處理的基礎之上再使用此子句進行隨機抽取記錄。用order by newId()子句隨機訪問不需要循環(huán)判斷，它只是在數(shù)據(jù)表隨機重排后讀取，因此速度相對較快，本文的組卷算法采用的就是這種方式。

3.2 數(shù)據(jù)庫設計

為了方便客戶端（Client）和服務器端（Server）數(shù)據(jù)傳遞的方便，數(shù)據(jù)的傳遞都以長字符串的形式進行，客戶端和服務器端分別按照約定的規(guī)則進行組碼和解碼。例如，組卷約束表中，將命題方案表示成“110；205；303；502”，表示本試卷中“第一種題型出10道，第2種題型出5道，第3種題型出3道，第5種題型出2道”；在試卷表中將構成一份試卷的所有試題的編號按相同題型排在一起的原則表示成“編號；編號；編號；……”的形式進行保存，輸出試卷時根據(jù)命題方案分解出題型及題量。因此，在組卷算法中大量地用到了臨時表和游標來進行中間數(shù)據(jù)的處理。

組卷算法中主要涉及到三張表，分別是試題表、組卷約束表、試卷表。即根據(jù)組卷約束向試題表中抽取試題，將試題編號集保存至試卷表中。在數(shù)據(jù)庫設計中，一張試題表包含所有類型的試題，一個組卷約束可以根據(jù)需要生成多份試卷，一份試卷表示為一條記錄。

3.3 算法設計

結合上述分析，改進后的隨機組卷算法流程如圖1所示。本算法在SQL Server數(shù)據(jù)庫服務器端設計成為存儲過程，可以根據(jù)組卷要求生成N份試卷，如成功，則將組卷要求保存至組卷約束表（tMakePaper）中，并將組出的N份試卷保存至試卷表（tPaper）中，否則返回組卷失敗的提示信息。

圖1 隨機組卷算法流程圖

4 兩種隨機組卷算法的比較

改進后的隨機算法可以實現(xiàn)批量地抽題，省略了大量的試題查重判斷，算法的效率要明顯高出傳統(tǒng)的隨機算法。將兩種算法在SQL Server 2008中進行比較，用于測試的試題表中試題數(shù)量為1000道，在組卷約束條件一致的情況下各組20份試卷，改進后的隨機組卷算法耗時27秒，普通隨機組卷算法耗時69秒，改進的隨機組卷算法具有明顯的優(yōu)勢。

[1]江明清．論標準化試題數(shù)據(jù)庫的建設[J]．時代教育，2015(12)：248-250．

[2]張輝．基于.NET的題庫管理與智能組卷系統(tǒng)設計與實現(xiàn)[J]．教育理論與實踐，2012，32(18)：50-52．

[3]王少豪．校園網(wǎng)絡考試系統(tǒng)中組卷算法的研究[J]．電腦知識與技術，2013，9(29)：6618-6620．

[4]莫家慶，林瑜華．基于.NET的題庫管理系統(tǒng)設計與實現(xiàn)[J]．計算機時代，2014(10)：78-80．

[5]李勇．教育考試題庫監(jiān)測與評估的內容及機制研究[J]．教育理論與實踐，2014，34(25)：25-28． An Efficient Randomized Algorithm for Generating Test Paper

Zhou Wenjun
(Hunan Vocational Institute of Safety Technology,Changsha 410151,Hunan)

For achieving better educational measurement,the construction of item bank system is actively carried out in all colleges and universities.As the core of the system,the algorithm for generating test paper is a hot research topic.This paper analyzes the short comings of the traditional randomized algorithm for generating test paper,and proposes an improved randomized algorithm.The experimental results show that the algorithm can generate the required test paper quickly.

item bank system;algorithm for generating test paper;stored procedure

TP311.2

A

1008-6609(2016)07-0049-02

周文君，女，湖南祁東人，碩士，講師，研究方向：計算機應用技術。