高歡歡

摘要：組卷算法有很多，回溯試探法結(jié)合分類分段算法，有效縮小回溯搜索范圍，能解決試題重復率高、知識點覆蓋面小的問題，提高了組卷效率。采用分類法，按照不同題型把題庫分為5類，縮小了搜索范圍，解決了知識點覆蓋面問題。將試題按照章節(jié)、難度系數(shù)分段，將具有相同屬性的試題分配到一個集合中，再從每段中隨機抽取滿足約束條件的一定數(shù)量試題組卷，解決試題重復率問題。將這種算法應用到在線考試系統(tǒng)中，生成滿足需求的試卷。

關(guān)鍵詞：在線考試系統(tǒng)；回溯試探算法；組卷

DOIDOI：10.11907/rjdk.1511643

中圖分類號：TP319

文獻標識碼：A 文章編號：1672-7800（2016）005-0157-03

0 引言

計算機基礎(chǔ)課程是大學的必修課程，計算機基礎(chǔ)考試逐漸由傳統(tǒng)筆試向機試轉(zhuǎn)變，這種轉(zhuǎn)變既能考查學生基礎(chǔ)知識的掌握程度，又能考查學生的實際操作能力，減輕了教師負擔，保證考試的公平、公正。組卷技術(shù)是在線考試系統(tǒng)實現(xiàn)的核心，目前組卷算法很多，常見的類型主要有簡單隨機抽取算法、回溯試探算法、遺傳算法。

（1）簡單隨機抽取算法是從題庫中隨機抽取一定數(shù)量的滿足預先設(shè)定條件的試題組成試卷。這種方法實現(xiàn)簡單、容易理解、組卷速度較快，但是抽取的試題重復率高，尤其是題庫小的系統(tǒng)[1]。

（2）回溯試探法是隨機抽取算法的改進，它采用隨機抽取算法從題庫中抽取試題，如果滿足條件就將試題標記放入預先建立的棧中，如果抽取的試題不滿足條件，就返回到上一個成功狀態(tài)，繼續(xù)隨機搜索。它有效地解決了簡單隨機算法的試題重復抽取問題，實現(xiàn)簡單，但只適用于小型題庫系統(tǒng)。對于大型題庫來說，需要占用很大的內(nèi)存空間，且組卷時間長、效率低。

（3）遺傳算法是模仿生物界中遺傳、變異、交叉等過程，依照基因組合原理對染色體進行編碼，按照優(yōu)勝劣汰的原則得到最優(yōu)解。這種算法具有全局尋優(yōu)、智能搜索和收斂速度快等優(yōu)點，但是實現(xiàn)困難[2]。

柳浪濤、谷林[3]提出了一種“卷內(nèi)分塊、組塊分層”的組卷機制，按照題目類型分為若干塊，按塊分別抽題。按照題型分塊，即為題庫分類；塊內(nèi)分組，即為不同類型試題分組。分類算法是指按照題型設(shè)計將題庫分類，解決知識點覆蓋面的問題，而分段算法是將各類題型試題按照“知識點”、“難度系數(shù)”字段分組，從每組試題中按照試題數(shù)量比例抽取相應的試題，以解決試題重復抽取問題。題量越大，抽取效果越好。

綜合考慮算法難易、組卷速度、知識點覆蓋率、試題重復率等問題，本文采用分類分段回溯試探算法。分類分段算法結(jié)合回溯試探算法，綜合利用了兩者的優(yōu)點，彌補了兩者的不足。首先將題庫按照不同題型分類，然后再對不同類別的試題按照知識點、難度系數(shù)字段分段，最后對每類題庫根據(jù)預先設(shè)定條件隨機抽取試題?；厮菰囂剿惴ㄊ菍唵坞S機算法的改進，隨機抽取一道題加入試卷，系統(tǒng)將記錄下這道題的知識點、試題序號放入預先建立的棧中，再根據(jù)約束條件隨機抽取下一道題，將這道題的知識點、試題編號與上一道題記錄下的知識點、試題序號相比較，如果不同，則將試題加入試卷并釋放上一個記錄，并寫入這道題的屬性，如果相同則重新抽取試題，以此類推?；厮菰囂椒ńY(jié)合分類分段抽取法，有效縮小了回溯搜索的范圍，提高了組卷速度，解決了試題知識點覆蓋面、試題重復抽取以及知識點覆蓋面問題。

1 數(shù)據(jù)庫設(shè)計

題庫設(shè)計質(zhì)量的好壞對組卷成敗至關(guān)重要。本文采用分類分段回溯試探算法，在試題庫中按 “難度系數(shù)”排序，再按 “知識點”排序。排序后，同一個知識點的同一難度系數(shù)試題放在一起，組卷就是從同一知識點同一難度系數(shù)的題目中隨機抽取指定數(shù)量的題目[4]。

計算機基礎(chǔ)在線考試一般分為選擇題、填空題、Excel操作題、Word操作題、Windows操作題幾類。為了提高組卷效率，需要預先確定試卷為百分制，然后確定題型題量、小題分值、知識點分布等屬性，這些設(shè)置好的試卷屬性字段都統(tǒng)一存放在PaperSet數(shù)據(jù)表中。按照試卷屬性設(shè)置表中數(shù)據(jù)，每種題型分別從相應的題庫中抽取。題庫表分為選擇題及操作題。

選擇題題庫表結(jié)構(gòu)如表1所示，操作題題庫表結(jié)構(gòu)如表2所示。其中“questType”字段表示為題型設(shè)置編號，“1”代表選擇題，“2”代表填空題，“3”代表Excel操作題，“4”代表Word操作題，“5”代表Windows操作題。表2中的“OperateType”字段指每種操作題的操作類型，用數(shù)字代表不同的操作類型，例如Word操作題中“1”、“2”、“3”數(shù)字分別代表“表格操作”、“文本替換”、“段落縮進”操作類型，Excel題型主要設(shè)計有“單元格樣式”、“行列樣式”、“工作表操作”、“生成圖表”等操作類型， Windows操作題主要設(shè)計有“文件夾刪除”、“文件夾創(chuàng)建”、“文件夾重命名”、“文件復制”等操作類型。此外，題庫中的“Chapter”字段，用數(shù)字代表不同的知識點分布，用“Degree”難度系數(shù)劃分 “簡單”、“中等”、“較難”、“困難”，分別用數(shù)字“1”、“2”、“3”、“4”來存儲。

2 組卷

將在線考試系統(tǒng)設(shè)計的5種題型分為5個模塊，在頁面設(shè)置5個事件按鈕，考生點擊一個按鈕將隨機從相應題庫抽取確定數(shù)量的試題，如圖1所示。按照題型不同將題庫分為5類，在這5大題庫中又采用章節(jié)、難度系數(shù)的設(shè)定對每種題型進一步分組。題庫中的每道題至少有如下4個屬性，定義如下：

（1）分值：每道試題的分值，小題設(shè)置的分值與該題型的題量乘積即是該大題總分。設(shè)計試卷滿分為100分，根據(jù)題型設(shè)置，單選題30分，15題，每題2分；填空題20分，10題，每題2分；Word題20分，5題，每題4分；Excel題20分，5題，每題4分，Window題10分，4題，每題2.5分。

（2）題型：試題的類型一般分為選擇題、填空題、Excel操作題、Word操作題、Windows操作題等。給出試題類型，自動組卷將在給定的數(shù)據(jù)庫表中搜索，縮小了搜索范圍，加快了組卷速度。

（3）知識點：又稱為考核點，它涉及具體考核內(nèi)容，知識點按章節(jié)從前往后劃分。每種題型預先設(shè)計一定數(shù)量的知識點，每道試題考查內(nèi)容對應不同的知識點，每個考查的知識點錄入一定數(shù)量的試題。

（4）難度系數(shù)：指測試試題的難易程度。它的定義是qi=1-Ri/n，qi表示第i題的難度系數(shù)，Ri表示此題平均得分值，n是該題的滿分值[5]。試卷難度控制將容易、中等、困難試題所占比例進行設(shè)置。一般試卷的難度系數(shù)在中等才能使考試成績成正態(tài)分布。題目區(qū)分度與它的難度相關(guān)，通常過高或過低題目的區(qū)分度都較小，中等難度的區(qū)分度最優(yōu)[6]。

根據(jù)分類分段算法，按照題型設(shè)置，每種題型設(shè)置相應題庫，分5次隨機抽題。對于每類題庫，再按照知識點、難度系數(shù)字段屬性分配集合。根據(jù)回溯試探算法執(zhí)行抽題，每種題型抽題的組卷事件觸發(fā)按鈕點擊后，按照設(shè)定的難度系數(shù)、題型、題量等約束條件分別從相應的題庫中隨機抽取一道試題加入試卷中，將此試題的知識點、試題序號記錄下來，再抽取下一道題，將這道題的知識點與上一題相比較，如果相同就放棄加入試卷并繼續(xù)抽題，如果不一樣即釋放上一條記錄，更新為當前記錄。以此類推，直到完成組卷，算法描述如下：

3 實驗結(jié)果

分類分段回溯試探組卷算法相較于隨機抽取算法而言，解決了試題重復率高、知識點覆蓋率小的問題，相較于回溯試探法而言解決了搜索速度慢、組卷效率低等問題。本文算法綜合利用了分類分段隨機算法以及回溯試探算法的優(yōu)點，摒棄了它們的不足，代碼實現(xiàn)較為簡單，能夠生成需要的試卷。

4 結(jié)語

本文采用的分類分段回溯試探算法，結(jié)合了簡單隨機抽取算法和回溯試探算法的優(yōu)點，實現(xiàn)簡單，大大縮小了搜索范圍，組卷速度快且避免了試題重復率問題。在線考試組卷系統(tǒng)兼顧了題型、題量、分值、知識點分布、難度系數(shù)等試卷參數(shù)，能快速得到一份滿意的計算機基礎(chǔ)在線考試試卷。

參考文獻：

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

[2]高興媛，古輝.在線考試系統(tǒng)自動組卷技術(shù)的研究與實現(xiàn)[J].計算機與現(xiàn)代化，2011（3）：155-157.

[3]柳浪濤，谷林.自動組卷系統(tǒng)試題難度和知識點覆蓋控制算法[J].西安工程大學學報，2015，29（3）：321-324.

[4]雷勇.分類分段算法在組卷中的應用研究[J].實踐與經(jīng)驗，2014（19）：41-44.

[5]桂陽，王修信，農(nóng)京輝，等.大學物理試題庫智能組卷隨機抽取法的改進[J].廣西物理，2008，29（2）：23-25.

[6]嚴思靜，常紅春.蟻群算法在組卷中的應用[J].職大學報，2014（6）：83- 87.

（責任編輯：杜能鋼）