分類分段回溯試探算法在計(jì)算機(jī)基礎(chǔ)在線考試系統(tǒng)中的應(yīng)用

高歡歡

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

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

DOIDOI：10.11907/rjdk.1511643

中圖分類號(hào)：TP319

文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1672-7800（2016）005-0157-03

0 引言

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

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

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

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

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

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

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

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

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

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

2 組卷

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

（1）分值：每道試題的分值，小題設(shè)置的分值與該題型的題量乘積即是該大題總分。設(shè)計(jì)試卷滿分為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操作題等。給出試題類型，自動(dòng)組卷將在給定的數(shù)據(jù)庫(kù)表中搜索，縮小了搜索范圍，加快了組卷速度。

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

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

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

3 實(shí)驗(yàn)結(jié)果

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

4 結(jié)語(yǔ)

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

參考文獻(xiàn)：

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

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

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

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

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

[6]嚴(yán)思靜，常紅春.蟻群算法在組卷中的應(yīng)用[J].職大學(xué)報(bào)，2014（6）：83- 87.

（責(zé)任編輯：杜能鋼）