通用題庫數據結構與組卷算法設計

【摘要】題庫的數據結構和組卷算法決定了題庫的適用范圍，該文根據不同課程試卷及其試題屬性的構成，提出一種新的題庫數據結構，并在分析組卷控制模型的基礎上，對組卷算法進行詳細設計。

【關鍵詞】試題庫結構；組卷目標；控制模型；組卷算法

【中圖分類號】G40-057 【文獻標識碼】B 【論文編號】1009—8097 (2008) 08—0101—04

一 引言

智能題庫系統是教育測量標準化、規范化的重要組成部分，其通用性主要取決于題庫的數據結構和組卷算法。一方面，題庫數據結構要能滿足不同課程的需要，冗余度盡可能??；另一方面，組卷算法要能適用于不同的題庫條件。根據這兩方面要求，本文提出一種新的題庫數據結構和組卷控制模型，并對組卷算法進行詳細設計。

二 題庫數據結構設計

不同課程雖然其試卷考查內容、使用對象不同，但都有試卷總分、考查章節、題型構成、試卷難度、區分度、考試時間等指標要求，并且試卷中的每道試題均具有知識點、認知分類、難度、題型、題分、試題內容、答案等屬性。與此同時，不同試題其內容和答案的構成元素差別也很大，簡單的只有文本，復雜的除文本之外，還包含圖像、公式等。

因此，為滿足不同課程試卷及其組卷算法的需要，我們設計了如下表結構：

（1） 題型表tb_itemType：保存題型信息，由題型代碼（主鍵，1個字符，取值a~z）、題型名稱（30個字符）和題型說明（200個字符）組成。

（2） 難度級別表tb_difficulty：保存題庫的試題難度信息，由難度級別（主鍵，最低難度級別為1，隨著難度的增加，難度級別依次加1）、難度級別名稱（10個字符）。

（3） 章節表tb_chapter：保存課程的章節信息，由章節代碼（主鍵）和章節名稱（30個字符）組成。

（4） 知識點表tb_knowledge：保存各章知識點信息，由知識點代碼（1個字符，取值a~z，多于26個知識點用希臘字母表示）、章節代碼和知識點名稱（30個字符）組成。知識點代碼和章節代碼聯合作主鍵，章節代碼參照章節表中的章節代碼。

（5） 試題屬性表tb_itemProperties：保存試題屬性信息，由試題編號（自動編號，主鍵）、題型代碼、章節代碼、難度級別、知識點代碼集（15個字符）、題分、抽取次數、抽取時間、停用標志（1-停用，0-未停用，默認值為0）組成。

題型代碼參照題型表中的題型代碼，章節代碼參照章節表中的章節代碼，難度級別參照難度級別表中的難度級別。知識點代碼集的編碼規則為章節代碼＋知識點代碼，比如3fk12ejk表示該題涉及的知識點包括第3章的f、k知識點和第12章的e、j、k知識點。

（6） 試卷屬性表tb_paperProperties：保存已組試卷的屬性信息，由試卷序號（自動編號，主鍵）、試卷說明（200個字符）、題型順序（20個字符，用題型代碼表示）、題型集（50個字符）、章節集（100個字符）、難度集（50個字符）、已用標志（1-已用，0-未用，默認值為0）、使用對象（100個字符）、組卷時間組成。

題型順序保存各題型在卷面中出現的順序。題型集保存組卷目標中各題型分數設定值，編碼規則為：題型代碼＋題型分數＋$組卷誤差百分比，比如a15b20d10e25f20g10$10表示擬組試卷中題型a、b、d、e、f、g的分數設定為15、20、10、25、20、10分，各題型分數的組卷誤差不超過其分值的10%。章節集保存組卷目標中各章節分數設定值，編碼規則為：c＋章代碼＋s＋章分數＋$組卷誤差百分比，比如c1s15c2s15c7s20c10s20c12s30$10表示擬組試卷中第1、2、7、10、12章的分數分別為15、15、20、20、30分，各章節分數的組卷誤差不超過其分值的10%。難度集保存組卷目標中各難度分數設定值，編碼規則為：d＋難度級別＋s＋難度級別分數＋$組卷誤差百分比，比如d1s15d2s20d3s30d4s20d5s15$0表示擬組試卷中難度級別為1、2、3、4、5的試題分數分別為15、20、30、20、15分，各難度組卷誤差為0。

（7） 試卷試題表tb_paperItems：保存已抽取的試題信息，由試卷序號、試題編號組成。試卷序號參照試卷屬性表中的試卷序號，試題編號參照試題屬性表中的試題編號。

（8） 題庫文檔表tb_documt：保存題庫的試題內容文檔和答案文檔[1]，由試題編號、試題內容（image類型，保存試題的內容文檔）和試題答案（image類型，保存試題的答案文檔）組成，試題編號參照試題屬性表中的試題編號。

三 組卷控制模型

1 試卷難度控制

試卷難度控制可通過離散型隨機變量的二項分布函數B(n，p)實現[2]，即：

2 組卷目標設定與檢查

擬定一份試卷首先要確定試卷的總體目標，包括試卷總分、試卷難度、章節分數、題型分數、試卷區分度、考試時間，然后從題庫中抽出滿足總體目標要求的試題。這些目標中，試卷區分度與試卷難度相關，難度太高或太低的試卷其區分度不高，只有合適的試卷難度才能獲得較高的試卷區分度；考試時間與試卷總分和試卷難度相關，試卷總分高、難度大則需要的考試時間長。

因此，我們選取試卷分數、試卷難度、章節分數、題型分數作為組卷目標，并按試卷總分、章節分數、試卷難度、題型分數的順序設定各目標值。同時為避免組卷目標設定的盲目性，我們還根據題庫條件對所有的組卷目標值進行滿足性檢查[3]。

各組卷目標值的設定順序和檢查方法如下：

（1） 設定擬組試卷的總分S。

（2） 統計題庫中各章節無重復知識點的試題總分數S_Chap(i)。

（3） 設定擬組試卷中各章節分數SS_Chap(i)及其組卷誤差的允許值，要求SS_Chap(i)≦S_Chap(i)且∑SS_Chap(i)= S。

（4） 統計題庫中在所考核的章節范圍內各難度級別無重復知識點的試題總分數S_ND(j)。

（5） 設定試卷難度Q及其組卷誤差允許值，利用難度控制模型和Q值計算出試卷中各難度級別的試題分數SS_ND(j)（或直接設定擬組試卷中各難度級別的試題分數），要求SS_ND(j)≦S_ND(j)且∑SS_ND(j)= S。

（6） 統計題庫中在所考核的章節和難度級別范圍內各題型無重復知識點的試題總分數S_TX(k)。

（7） 設定擬組試卷中各題型分數SS_TX(k)及其組卷誤差允許值，要求SS_TX(k)≦S_TX(k)且∑SS_TX(k)= S。

3 組卷目標匹配順序控制

理想情況下，題庫中有分布均勻且題量足夠多的試題以供選擇，但實際往往并非如此，不同的組卷目標對應的試題分布范圍和選擇余地差別很大，所以組卷目標的匹配順序直接影響組卷成功率。

在設定的組卷目標中，試卷難度可以體現在各章節試題中，而各章節分數只能體現在本章節試題中，故章節的選擇余地小于試卷難度；此外，按分值從高到低的順序進行題型匹配，能夠為章節、難度和試卷總分的匹配留出盡可能大的選擇余地。因此我們采取了如下匹配順序：

（1） 按照平均分值從高到低的順序選擇待匹配的題型。

（2） 在當前匹配題型中按照各章節無重復知識點的試題數從少到多的順序循環匹配各章節，如果當前匹配的章節只有當前匹配題型的試題，則在當前章節匹配中完成該章節全部的抽題任務，否則至多抽取該章節一道試題。

（3） 在當前匹配的題型和章節中，按照各難度級別無重復知識點的試題數從少到多的順序進行難度級別匹配。

4 組卷目標匹配誤差控制

為實現組卷控制的靈活性，我們引入了組卷目標匹配誤差控制。設第i個組卷目標的設定分數為SS(i)，誤差允許值為e_set(i)，其未抽分數為NS(i)，則該目標的匹配誤差為：

如果e(i)≦e_set(i)，則第i個組卷目標完成匹配任務。當所有組卷目標的匹配誤差都處于誤差允許范圍內時，則匹配結束。

組卷開始時NS(i)=SS(i)，組卷過程中每抽取一道分數為s的試題，則該題對應的所有組卷目標的未抽分數都減少s。

5 已抽試題回調

所有組卷目標匹配結束時，如果已抽試卷總分小于設定值，則通過調換部分已抽試題的方法，使已抽試卷總分等于設定值。用于調換的試題需滿足如下條件：

（1） 能使已抽試卷總分向著設定值的方向變化。

（2） 不能使試卷出現重復知識點。

（3） 不能使組卷目標的組卷誤差超出各自允許范圍。

回調過程結束后，如果已抽試卷總分等于設定值，則組卷成功，否則組卷失敗。

四 組卷算法設計

1 臨時表變量

為了提高數據的處理速度，我們把組卷過程中需要的中間數據全部保存在SQL Server的表變量中[4]。所需的表變量如下：

（1） 試題屬性表@Items：保存參與組卷的試題屬性信息，按抽取次數和抽取時間升序排列，字段包括試題編號、題型代碼、章節代碼、難度級別、知識點代碼集、題分、可抽標志（bit，1-可抽，0-不可抽，默認值為1）。

（2） 考試題型表@examTX：保存題型組卷目標的抽題信息，按各題型平均分值降序排列，字段包括ID（自動編號）、題型代碼、設定分數、未抽分數、可抽題數。

（3） 考試章節表@examChap：保存章節組卷目標的抽題信息，按各章節可抽題數升序排列，字段包括ID（自動編號）、章節代碼、設定分數、未抽分數、可抽題數。

（4） 考試難度表@examND：保存難度組卷目標的抽題信息，按各難度可抽題數升序排列，字段包括ID（自動編號）、難度級別、設定分數、未抽分數、可抽題數。

（5） 題型章節表@TXChap：保存各題型各章節中無重復知識點的可抽試題數量，字段包括題型代碼、章節代碼、可抽題數。

（6） 章節難度表@ChapND：保存各章節各難度級別中無重復知識點的可抽試題數量，字段包括章代碼、難度級別、可抽題數。

（7） 題型難度表@TXND：保存各題型各難度級別中無重復知識點的可抽試題數量，字段包括題型代碼、難度級別、可抽題數。

（8） 試卷表@paperItems：保存被抽試題的部分屬性信息，字段包括：ID（自動編號）、試卷序號、試題編號、題型代碼、章節代碼、難度級別、題分、知識點代碼集。

2 組卷算法

本組卷算法基于存儲過程和表變量實現。存儲過程的輸入參數包括擬組試卷的總分、題型集、章節集、難度集、試卷題型順序、使用對象、試卷說明，輸出參數為組卷結果標志。核心算法如下：

（1） 取@examTX中第一個待匹配的題型代碼→@tx，@examChap中第一個待匹配的章節代碼→@chap，@examND中第一個待匹配的難度級別→@ND。

（2）若@chap章的組卷誤差大于其允許值 and @TXChap中題型代碼為@tx、章節代碼為@chap的可抽題數>0，則轉（3），否則轉（7）。

（3）若@ND難度的組卷誤差大于其允許值 and @ChapND中章節代碼為@chap、難度級別為@ND的可抽題數>0 and @TXND中題型代碼為@tx、難度級別為@ND的可抽題數>0，則轉（4），否則轉（6）。

（4） 若@Items中不存在題型代碼為@tx、章節代碼為@chap、難度級別為@ND、題分不大于當前組卷目標對應的最小未抽分數、可抽標志為1的試題，則轉（6），否則將該題的試題編號、題分、知識點代碼集插入@paperItems表中；將該題分數增加到已抽試題總分中；將@Items中所有與該題知識點相同的試題的可抽標志置為0；分別將@examChap中章節代碼為@chap，@examND中難度級別為@ND，@examTX中題型代碼為@tx對應的未抽分數減去被抽取的試題分數、可抽題數減1；分別將@TXChap中題型代碼為@tx、章節代碼為@chap，@TXND中題型代碼為@tx、難度級別為@ND，@ChapND中章節代碼為@chap、難度級別為@ND對應的可抽題數減1。

（5） 若 @chap章僅有@tx題型的試題 and @chap章的抽題誤差大于允許值，則轉（6），否則轉（7）。

（6） 循環取@examND中下一個待匹配的難度級別→@ND，然后轉（3）。

（7） 若@tx題型的組卷誤差大于允許值，則循環取@examChap中下一個待匹配的章節代碼→@chap，然后轉（2），否則轉（8）。

（8） 若已抽試題總分<試卷設定總分 and @examTX題型沒有匹配結束，則取@examTX中下一個待匹配的題型代碼→@tx，然后轉（2），否則轉（9）。

（9） 若已抽試題總分<試卷設定總分，則進行試題回調。

（10） 若已抽試題總分=試卷設定總分，則組卷成功，否則組卷失敗。

試題回調即從未抽試題中查找符合替換條件的試題并替換對應的已抽試題。算法如下：

（1） 試卷設定總分-已抽試題總分→@k，@paperItems中第一道試題的記錄編號→@i。

（2） 若@i所指試題對應的各組卷目標的未抽分數減少@k后其組卷誤差不超出允許范圍 and @Items中存在與@i所指試題同題型、同章節、同難度、分數多@k且與其它已抽試題無重復知識點的試題，則取該試題的試題編號→@itembh，然后轉（3），否則轉（4）。

（3） 將@i所指試題的試題編號改為@itembh、題分增加@k；將@tx題型、@chap章、@ND難度對應的未抽分數減少@k；已抽試題總分增加@k；若試卷設定總分-已抽試題總分<@k，則試卷設定總分-已抽試題總分→@k。

（4） 取@paperItems中下一道試題的記錄編號→@i，若@i≦@paperItems中最后一道試題的記錄編號 and 已抽試題總分!=試卷設定總分，則轉（2），否則轉（5）。

（5） 若試卷設定總分-已抽試題總分≧@k，則@k-1→@k。

（6） 若@k>0 and 已抽試題總分!=試卷設定總分，則@paperItems中第一道試題的記錄編號→@i，然后轉（2），否則回調結束。

五 算法測試

我們通過題量少且試題分布不均勻的模擬題庫對組卷算法進行測試。題庫中有100道試題（不同知識點的試題為50道），包括4種題型、5章、5級難度，第4章試題僅分布在c題型中，第5級難度試題僅分布在第5章中。在對該題庫進行的50次組卷實驗中，沒有經過試題回調而直接組卷成功的有42次，經過試題回調后組卷成功的有6次，組卷失敗2次，生成的試卷中除第4章試題外，其它各章、各難度的試題均能最大程度地分布在不同題型中。測試結果表明，本組卷算法對于題量少且試題分布不均勻的題庫仍然能夠取得很高的組卷成功率和組卷質量。

六 結論

本文給出的題庫數據結構通用性強、冗余度小，能夠滿足不同課程試卷的需要。同時，通過引入組卷目標的滿足性檢查、匹配順序控制、匹配誤差控制和已抽試題回調等控制策略，使得組卷算法能夠不受題庫中試題分布的限制，降低了算法對題庫題量的要求，提高了算法的適用性。

參考文獻

[1] 張文，陳世強.題庫系統試題存取方法的研究[J].計算機與現代化，2006，(3):97-99.

[2] 應繼儒，胡立新，龍毅等.試題庫隨機選題數學模型的構建及實現[J].計算機應用，2000，20(1):46-47.

[3] 朱守業.智能組卷中組卷目標的滿足性檢查與處理[J].微計算機信息，2007，23(21):268-269.

[4] SQL Server 2000聯機叢書[DB/DK].