分類分段回溯試探算法在計算機基礎在線考試系統中的應用

高歡歡

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

關鍵詞：在線考試系統；回溯試探算法；組卷

DOIDOI：10.11907/rjdk.1511643

中圖分類號：TP319

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

0 引言

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

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

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

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

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

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

1 數據庫設計

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

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

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

2 組卷

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

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

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

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

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

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

3 實驗結果

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

4 結語

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

參考文獻：

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

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

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

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

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

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

（責任編輯：杜能鋼）