喬亞男， 程 航， 薄鈞戈

(西安交通大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，陜西 西安 710049)

0 引言

大學(xué)計(jì)算機(jī)類(lèi)課程是非常重要的高校公共基礎(chǔ)必修課程，該類(lèi)課程以計(jì)算思維培養(yǎng)為目標(biāo)，在教學(xué)內(nèi)容中滲透計(jì)算思維的基本理念，為學(xué)生展示計(jì)算機(jī)學(xué)科的輪廓和相關(guān)技術(shù)，提升學(xué)生利用計(jì)算機(jī)解決本專(zhuān)業(yè)應(yīng)用問(wèn)題的能力，同時(shí)為未來(lái)可能的學(xué)科交叉研究打下基礎(chǔ)?；谟?jì)算機(jī)學(xué)科的自身特點(diǎn)，在培養(yǎng)高素質(zhì)專(zhuān)門(mén)人才和拔尖創(chuàng)新型人才的大背景下，推動(dòng)教學(xué)評(píng)價(jià)改革成為計(jì)算機(jī)基礎(chǔ)課程教學(xué)改革的重中之重。隨著高校校園網(wǎng)建設(shè)的不斷完善，考試的方式、載體發(fā)生了比較大的變化，由傳統(tǒng)的線(xiàn)下考試轉(zhuǎn)變?yōu)闊o(wú)紙化線(xiàn)上考試，經(jīng)過(guò)長(zhǎng)時(shí)間的考試在電子化試題庫(kù)中積累了相當(dāng)量的試題，傳統(tǒng)人工組卷方式不僅耗時(shí)耗力、效率低下，并且不能保證所組試卷科學(xué)合理[1～2]。

自動(dòng)組卷是指根據(jù)出題人所指定的約束條件，從題庫(kù)中自動(dòng)篩選滿(mǎn)足條件的試題，從而代替人工選題的過(guò)程[3]。大學(xué)計(jì)算機(jī)類(lèi)課程包含數(shù)門(mén)課程，涉及軟硬件系統(tǒng)、網(wǎng)絡(luò)、數(shù)據(jù)庫(kù)、程序設(shè)計(jì)、多媒體技術(shù)等眾多知識(shí)點(diǎn)，不同課程的考核范圍既不同又有一定交叉。并且正常教學(xué)活動(dòng)中，組織一門(mén)課程的考試通常要準(zhǔn)備數(shù)份甚至數(shù)十份試卷。這些特點(diǎn)決定了計(jì)算機(jī)自動(dòng)組卷若要滿(mǎn)足教學(xué)需求必須解決以下幾個(gè)問(wèn)題：①如何保證多份試卷在難度、結(jié)構(gòu)、考核范圍等方面一致；②如何提高算法性能。

近年來(lái)，已有多位學(xué)者針對(duì)組卷問(wèn)題開(kāi)展自動(dòng)組卷方法研究。目前的自動(dòng)組卷方法主要分為三大類(lèi)：第一類(lèi)為借助于某種隨機(jī)算法進(jìn)行組卷,如Marzukhi和Kiran對(duì)傳統(tǒng)隨機(jī)抽題算法進(jìn)行了改進(jìn)，利用洗牌算法避免了重復(fù)性抽題[4～5]。第二類(lèi)是基于深度優(yōu)先搜索算法DFS(Depth-first Search)或者廣度優(yōu)先搜索算法BFS(Breadth-first Search)進(jìn)行組卷，如陳雷等人[6]針對(duì)回溯抽題算法時(shí)間復(fù)雜度和空間復(fù)雜度較大的問(wèn)題進(jìn)行了改進(jìn)，提出了“目標(biāo)終止回溯試探法”和“縮減深度回溯試探法”，在實(shí)驗(yàn)中證明了兩種算法在特定試題庫(kù)中提高了組卷效率，但所組試卷中仍有部分重復(fù)試題，并且算法適應(yīng)情況較窄。最后一類(lèi)則是借助于智能啟發(fā)式搜索算法進(jìn)行組卷,如Zhang等人[7]在試題庫(kù)建設(shè)中使每種題型在數(shù)據(jù)庫(kù)中對(duì)應(yīng)一張表，并在原始仿生學(xué)遺傳算法中對(duì)初始種群的生成采取了約束，采用實(shí)數(shù)編碼代替了傳統(tǒng)的二進(jìn)制編碼，提高了算法的收斂度。Hu等人[8]將遺傳算法與粒子群算法兩種算法相結(jié)合，通過(guò)實(shí)驗(yàn)數(shù)據(jù)分析了影響組卷的因素。此外，基于遺傳算法和蟻群算法，國(guó)內(nèi)多位研究者在智能考試和組卷算法上也進(jìn)行了深入的研究[9～11]。

針對(duì)上述存在的問(wèn)題，本文通過(guò)對(duì)組卷問(wèn)題建模，對(duì)自動(dòng)組卷中的難點(diǎn)問(wèn)題進(jìn)行深入研究，對(duì)傳統(tǒng)隨機(jī)抽取算法進(jìn)行了改進(jìn)，提出了一種針對(duì)大學(xué)計(jì)算機(jī)類(lèi)課程知識(shí)體系結(jié)構(gòu)的自動(dòng)組卷方法。

1 設(shè)計(jì)思想

1.1 題庫(kù)參數(shù)設(shè)計(jì)

題庫(kù)是選擇組卷算法及能否實(shí)現(xiàn)組卷的關(guān)鍵因素，一個(gè)好的題庫(kù)設(shè)計(jì)在一定程度上可以提高算法的執(zhí)行效率。

在試題表中，每道試題題干、答案以XML格式儲(chǔ)存，特別地，當(dāng)題型為編程題時(shí)，額外擁有測(cè)試用例字段，該字段也以XML格式存儲(chǔ)。根據(jù)組卷要求，每道試題Qi擁有多個(gè)約束屬性，包括難度、題型、知識(shí)點(diǎn)、章節(jié)等，具體可表示為式(1)。

Qi= (QIDi,CIDi,Ti,Si,Pi,Di,...)

(1)

QIDi作為主鍵表示當(dāng)前的試題編號(hào)，是每個(gè)試題的唯一標(biāo)識(shí)，CIDi表示此試題對(duì)應(yīng)的課程編號(hào)，作為外鍵與課程表相關(guān)聯(lián)，Ti表示該試題的題型，Si表示該試題在相應(yīng)課程編號(hào)下對(duì)應(yīng)的章節(jié)，Pi表示該試題在對(duì)應(yīng)課程對(duì)應(yīng)章節(jié)下的所屬知識(shí)點(diǎn)，Di表示該試題的難度等級(jí)。其中試題的難度系數(shù)與難度等級(jí)對(duì)應(yīng)關(guān)系，如表1所示。

表1 難度等級(jí)與難度系數(shù)對(duì)應(yīng)關(guān)系

在數(shù)據(jù)庫(kù)中，將試題的題型以int類(lèi)型存儲(chǔ)，以提高檢索效率。試題的題型表示與題型描述對(duì)應(yīng)關(guān)系如表2所示。

表2 題型對(duì)應(yīng)關(guān)系

在知識(shí)點(diǎn)標(biāo)注時(shí)，采用分段實(shí)數(shù)編碼的方式，具體可表示為式(2)。

Pi=CIDiSiKi

(2)

其中，CIDi表示該知識(shí)點(diǎn)對(duì)應(yīng)的課程編號(hào)，Si表示該知識(shí)點(diǎn)對(duì)應(yīng)的章節(jié)，Ki表示為該知識(shí)點(diǎn)的序號(hào)。例如：450102,45則為編號(hào)為45的課程，01代表該課程的第一章，02代表該課程第一章的第二個(gè)知識(shí)點(diǎn)。

1.2 候選試題數(shù)據(jù)結(jié)構(gòu)

組卷時(shí)，系統(tǒng)根據(jù)用戶(hù)所設(shè)定組卷需求預(yù)先將數(shù)據(jù)庫(kù)中的試題信息自動(dòng)讀入內(nèi)存中，生成供隨機(jī)選題用的候選試題數(shù)據(jù)結(jié)構(gòu)。

抽題算法主要數(shù)據(jù)結(jié)構(gòu)包括兩個(gè)部分，第一部分為章數(shù)組字典IDAndChapter，數(shù)組下標(biāo)代表題型，每個(gè)字典中的鍵值對(duì)代表試題編號(hào)與章的對(duì)應(yīng)；第二部分為知識(shí)點(diǎn)數(shù)組字典IDAndKP，數(shù)組下標(biāo)代表題型，每個(gè)字典中的鍵值對(duì)代表試題編號(hào)與知識(shí)點(diǎn)的對(duì)應(yīng)。

2 組卷算法描述

采用此方法組卷的一般過(guò)程如下：

(1)根據(jù)組卷?xiàng)l件，判斷當(dāng)前題庫(kù)情況是否滿(mǎn)足組卷要求，若滿(mǎn)足條件則開(kāi)始組卷；否則重新設(shè)置組卷參數(shù)；

(2)采用一種基于知識(shí)體系結(jié)構(gòu)的改進(jìn)型隨機(jī)抽取算法，依次循環(huán)為各試卷抽取指定題型中之前未被抽取過(guò)的題目，直到抽取完條件要求的全部題目；

(3)題目抽取完成后，計(jì)算各試卷中每類(lèi)題型的平均難度值，確定是否符合設(shè)定要求。如果不符合，則采用一種循環(huán)替換算法進(jìn)行難度值調(diào)整，直到滿(mǎn)足設(shè)定要求。整體流程如圖1所示。

圖1 組卷整體流程圖

2.1 條件判斷及預(yù)處理

根據(jù)用戶(hù)所設(shè)置組卷?xiàng)l件，判斷當(dāng)前題庫(kù)試題是否滿(mǎn)足組卷要求，若滿(mǎn)足條件則進(jìn)入下一步開(kāi)始組卷，否則重新設(shè)置組卷參數(shù)。這里的組卷?xiàng)l件可通過(guò)瀏覽器登錄組卷系統(tǒng)設(shè)置。包括的參數(shù)有：

(1)課程(Course)：本次組卷針對(duì)的具體課程；

(2)試卷數(shù)量(PaperNum)：需要同時(shí)組成的試卷套數(shù)；

(3)考核范圍(Scope)：試題涉及的章范圍；

(4)題型(QType)：各試卷所包含的題目類(lèi)型。題型包括：?jiǎn)芜x、多選、判斷、填空、問(wèn)答、編程、綜合。

(5)每種類(lèi)型題目數(shù)量(QTNum)：每套試卷中單種題型的題目數(shù)量。

(6)題目分值(Score)：每種題型的單道題目分值。不同題型的單道題目分值可以不同。

(7)題型難度值(QDegree)：試卷中每種類(lèi)型題目的平均難度值。不同題型的QDegree可以不同。

其中，“試卷數(shù)量”是指同時(shí)組成的試卷數(shù)，該數(shù)量與實(shí)際需要及題庫(kù)容量有關(guān)。在Scope設(shè)定的前提下，若用Sumf表示用戶(hù)所設(shè)置的試卷總分值，SumS表示題庫(kù)中設(shè)定考核范圍的總題量，Sumt表示題庫(kù)中考核范圍內(nèi)任意一種題型的題目數(shù)量，n表示要求的題型種類(lèi)數(shù)，對(duì)同時(shí)組成的每套試卷，其n值相同。則允許同時(shí)組成的試卷數(shù)量應(yīng)同時(shí)滿(mǎn)足公式(3)、公式(4)和公式(5)，否則需要重新調(diào)整組卷參數(shù)。

(3)

(4)

Sumt≥PaperNum×QTNum

(5)

其中，公式(3)的含義是：每套試卷總分值應(yīng)與用戶(hù)所設(shè)置試卷總分值相等；公式(4)的含義是：題庫(kù)中指定考核范圍的試題總量應(yīng)大于等于所需試卷題目數(shù)量之和；公式(5)的含義是：題庫(kù)中每種題型的題目數(shù)量應(yīng)大于等于所需試卷每種題型題目數(shù)量之和。

2.2 基于知識(shí)體系結(jié)構(gòu)的抽題算法

這里的知識(shí)體系歸屬于計(jì)算機(jī)教學(xué)領(lǐng)域，其結(jié)構(gòu)包含課程(Course)、章(Scope)、知識(shí)點(diǎn)(Point)及相互之間的對(duì)應(yīng)關(guān)系，課程、章、知識(shí)點(diǎn)是特定領(lǐng)域約定俗成的術(shù)語(yǔ)，三者為包含關(guān)系，滿(mǎn)足如下表達(dá)式(6)。

Point?Scope?Course

(6)

按照公式(6)可得計(jì)算機(jī)領(lǐng)域知識(shí)體系拓?fù)浣Y(jié)構(gòu)圖，包含：課程(Course)、章(Scope)、知識(shí)點(diǎn)(Point)，它們之間滿(mǎn)足公式(6)所述關(guān)系。拓?fù)浣Y(jié)構(gòu)圖如圖2所示。

圖2 計(jì)算機(jī)領(lǐng)域知識(shí)體系拓?fù)浣Y(jié)構(gòu)圖

定義二維數(shù)組MIsChoosed和PIsChoosed，分別表示某類(lèi)題型中某章是否已抽取，以及某章中某知識(shí)點(diǎn)是否已抽?。欢x整型變量Count表示某題型已抽取的題目數(shù)量，初始化為0；定義Sum表示某類(lèi)題型所需題目數(shù)量。具體流程為：

(1)選定準(zhǔn)備抽取的題目類(lèi)型；

(2)選擇已抽取章的下一章(初始時(shí)默認(rèn)為第1章)作為當(dāng)前抽取章，采用算法2依次為各試卷抽取一道題目。

(3)判斷各試卷該題型題目數(shù)量是否達(dá)到要求，如果沒(méi)有，則繼續(xù)(2)。否則進(jìn)行過(guò)程(4)

(4)判斷是否所有題型題目均已抽取完畢，如果沒(méi)有，繼續(xù)(1)，選擇下一種題型；否則，表示各試卷所有題型題目都已抽取完畢。

所有試卷抽題流程算法偽代碼如下所示。

1)算法1

輸入：某課程下所有試題QIdList，組卷約束條件。

輸出：所組多份試卷paperList。

//i為當(dāng)前題型

For each i [0,6] do

Define Count = 0

While (Count < Sumi) do

//chaps為用戶(hù)所選定章節(jié)

For each chap chaps

KSA();//算法2

End while

End for

Return paperList

其中，一次為每套試卷抽取一題的算法思想為：根據(jù)圖1所示領(lǐng)域知識(shí)體系，在已構(gòu)建領(lǐng)域知識(shí)體系基礎(chǔ)上，按照章及章內(nèi)知識(shí)點(diǎn)順序，遵循未被抽取過(guò)題目的知識(shí)點(diǎn)優(yōu)先原則，依次循環(huán)為各試卷抽取指定題型中之前未被抽取過(guò)的題目，直到抽取完條件要求的全部題目，詳細(xì)步驟如下算法所示。

基于知識(shí)體系結(jié)構(gòu)的改進(jìn)型隨機(jī)抽取算法

輸入 某課程下所有試題QIdList，組卷約束條件。

輸出 符合出題人設(shè)定的多份試卷paperList。

步驟1：判斷當(dāng)前抽取章curChap中當(dāng)前題型i是否還有未被抽取過(guò)的題目，若全部題目均已被抽取，則進(jìn)入步驟4；否則，基于知識(shí)體系結(jié)構(gòu)，從該章中按順序選擇一個(gè)知識(shí)點(diǎn)curKP，執(zhí)行步驟2；

步驟2：判斷該知識(shí)點(diǎn)是否有未被抽取過(guò)的該題型題目。若有，執(zhí)行步驟3；否則，選擇該知識(shí)點(diǎn)所對(duì)應(yīng)章節(jié)的下一個(gè)知識(shí)點(diǎn)，重新執(zhí)行步驟2；

步驟3：從選定的知識(shí)點(diǎn)中隨機(jī)抽取一道未被抽取過(guò)的題目QId；

步驟4：選擇下一章作為當(dāng)前抽取章(初始時(shí)默認(rèn)抽取第一章)，若全部章被抽取完，則將所有章置為未抽取狀態(tài)，選擇第一章作為當(dāng)前抽取章，重新返回步驟1；

步驟5：判斷各試卷是否均已抽取一道指定題型的題目，如果沒(méi)有，轉(zhuǎn)向步驟2；否則，將所抽取的題目及其知識(shí)點(diǎn)標(biāo)記為“已抽取”，將包含該知識(shí)點(diǎn)的章設(shè)為已抽取章。完成為每套試卷抽取一道指定題型題目工作，偽代碼如算法2所示。

2)算法2

輸入：某課程下所有試題QIdList，組卷約束條件。

輸出：所組多份試卷paperList。

Define paper = 0 ;//當(dāng)前試卷

If(!Mischoosed[chap]) do

//KPs為當(dāng)前章下所有知識(shí)點(diǎn)

Define KPs getKPs(chap)

For each kp KPs do

If(!PisChoosed[i][kp]) do

While(paper

QId Random();

PisChoosed[i][chap] = True;

MisChoosed[chap] = True;

paperList[paper].add(QId);

End while

paper = 0;

End if

End for

End if

2.3 循環(huán)難度調(diào)整算法

對(duì)按照算法1所抽取的各試卷，分別計(jì)算各試卷中每類(lèi)題型的平均難度值，并與用戶(hù)所設(shè)定的各題型難度值進(jìn)行比較，判斷某試卷某題型的平均難度值與該題型對(duì)應(yīng)難度值偏差是否處于允許范圍內(nèi)。若不符合，則采用一種循環(huán)難度調(diào)整算法遵循知識(shí)點(diǎn)、章、其它章的搜尋順序進(jìn)行試題難度調(diào)整，直到滿(mǎn)足設(shè)定要求。

設(shè)Dai為表示第i套試卷選定題型的平均難度值，Di為該題型設(shè)定難度值，f為允許誤差值，參照算法2，試卷難度調(diào)整的具體方法為：

輸入 基于上述抽題算法的所組試卷paperList

輸出 符合用戶(hù)所設(shè)定難度的試卷paperList`

依次處理paperList中的每套試卷，以第一份試卷為例，按序選定試卷題型，計(jì)算該試卷該題型的平均難度值Dai，并與該題型設(shè)定難度值Di進(jìn)行比較，則有以下三種情況：

(1)如果|Dai-Di|

(2)如果|Dai-Di|≥f且Dai>Di，則刪除第i套試卷該題型中難度值最大的題目，重新抽取難度值較小、且在本次組卷中未被抽取過(guò)的同類(lèi)型題目替換，直到滿(mǎn)足要求為止。

(3)如果|Dai-Di|≥f且Dai

所訴情況(2)的循環(huán)難度調(diào)整算法包括如下具體步驟：

步驟1：刪除該題型當(dāng)前難度值最大的題目MaxQId，從題目屬性中獲取待替換題目關(guān)聯(lián)的知識(shí)點(diǎn)MaxQIdKP，查找題庫(kù)中同一知識(shí)點(diǎn)中是否有未被抽取過(guò)、難度值小于被刪除題的同類(lèi)型題目。若有，則執(zhí)行步驟5，否則繼續(xù)步驟2；

步驟2：從包含該知識(shí)點(diǎn)的章中查找是否有未被抽取過(guò)、難度值小于被刪除題的同類(lèi)型題目。若有，則執(zhí)行步驟5，否則繼續(xù)步驟3；

步驟3：從其它章中查找是否有未被抽取過(guò)、難度值小于被刪除題的同類(lèi)型題目。若有，則執(zhí)行步驟5，否則繼續(xù)步驟4；

步驟4：按照上述原則仍沒(méi)有找到符合條件的題目，則難度調(diào)整失敗，重新組卷。

步驟5：隨機(jī)抽取一道滿(mǎn)足條件的題目ranQId替換原題。計(jì)算當(dāng)前題型的平均難度值，若符合難度范圍要求，則結(jié)束；否則繼續(xù)轉(zhuǎn)向步驟1。

所述情況(3)采用類(lèi)似的循環(huán)難度調(diào)整算法，依次替換題型中難度值最小的題目，直到該題型難度值滿(mǎn)足要求。

當(dāng)所有題型均滿(mǎn)足|Dai-Di|

3)算法3

輸入：基于前述改進(jìn)型隨機(jī)抽題算法的所組試卷paperList。

輸出：經(jīng)難度調(diào)整的paperList`。

Define f

For each curQType [0,6] do

//i為當(dāng)前試卷

For i= 0;i

If(|Dai-Di|

Continue;

While(|Dai-Di|≥f&&Dai>Di)do

paperList[i].remove(MinQId)

ranQId Random();

paperList[i].add(ranQId);

End while

While(|Dai-Di|≥f&&Dai

paperList[i].remove(MaxQId)

ranQId Random();

paperList[i].add(ranQId);

End while

End for

End for

Return paperList`

3 實(shí)驗(yàn)過(guò)程及分析

3.1 實(shí)驗(yàn)條件

為了驗(yàn)證本課題所提出的基于知識(shí)體系結(jié)構(gòu)組卷算法KSA(knowledge structure algorithm)的有效性，采用“大學(xué)計(jì)算機(jī)基礎(chǔ)”這一課程題庫(kù)作為測(cè)試數(shù)據(jù)，題目數(shù)量共計(jì)803道，其中單選題318道，多選題32道，判斷題134道，填空題169道，程序題130道，綜合題20道。

測(cè)試環(huán)境：

1)軟件環(huán)境

操作系統(tǒng)：Windows 7 64bit

開(kāi)發(fā)語(yǔ)言：C#+HTML+JavaScript

開(kāi)發(fā)環(huán)境：Microsoft Visual Studio 2017

數(shù)據(jù)庫(kù)：Sql Server 2012

瀏覽器：Google Chrome

2)硬件環(huán)境

CPU：Intel(R) Core(TM) i5-4590 CPU @ 3.30GHz

RAM：8G

3.2 試卷參數(shù)

(1)課程：大學(xué)計(jì)算機(jī)基礎(chǔ)。

(2)章范圍：第1-8章。

(3)試卷總分：100分。

(4)試卷題型及各題分值：?jiǎn)芜x題16題，每題2分，共計(jì)32分；判斷題10題，每題2分，共計(jì)20分；填空題2題，每題7分，共計(jì)14分；編程題3題，每題8分，共計(jì)24分；綜合題1題，每題10分，共計(jì)10分。各題型難度值設(shè)定除判斷題題型為2，其余題型均為3。

(5)組卷份數(shù)：5份。

3.3 實(shí)驗(yàn)結(jié)果及分析

應(yīng)用本文提出的KSA組卷算法與傳統(tǒng)遺傳算法GA(genetic algorithm)在組卷效果與執(zhí)行效率上進(jìn)行了對(duì)比實(shí)驗(yàn)，每個(gè)算法實(shí)驗(yàn)共進(jìn)行5次，每次均以上述試卷參數(shù)為基準(zhǔn)進(jìn)行組卷。以實(shí)驗(yàn)中試卷的難度值方差來(lái)衡量各試卷難度的離散程度，以限定題目數(shù)量下的知識(shí)點(diǎn)重復(fù)率衡量多套試卷知識(shí)點(diǎn)的重復(fù)情況，以各試卷間知識(shí)點(diǎn)走勢(shì)及擬合程度衡量知識(shí)點(diǎn)平衡情況，以算法執(zhí)行時(shí)間衡量算法性能。對(duì)比實(shí)驗(yàn)結(jié)果如下所示。

1)兩種算法難度值方差對(duì)比

每次實(shí)驗(yàn)的難度值方差說(shuō)明了各試卷之間難度的偏離程度，該方差數(shù)值越小，代表多份試卷難度基本持衡。兩種算法難度值方差對(duì)比實(shí)驗(yàn)數(shù)據(jù)如表3所示。

表3 難度值方差對(duì)比實(shí)驗(yàn)

從表中可以看出，KSA算法的方差值高于GA，主要原因是：GA算法中種群進(jìn)化時(shí)會(huì)優(yōu)先挑選適應(yīng)度高的個(gè)體進(jìn)入下一代，在不斷的雜交之后，種群多樣性銳減，導(dǎo)致個(gè)體相似度過(guò)高，即試卷中試題重復(fù)率過(guò)高，故所組試卷之間難度值方差極小。

2)兩種算法知識(shí)點(diǎn)重復(fù)率對(duì)比

在一份質(zhì)量較高的試卷中，每道試題應(yīng)有對(duì)應(yīng)的知識(shí)點(diǎn)且互相不重復(fù)。這里題庫(kù)中的知識(shí)點(diǎn)標(biāo)注以該題最想考察的知識(shí)點(diǎn)為主。取每次實(shí)驗(yàn)中重復(fù)率最高的試卷作對(duì)比，對(duì)比結(jié)果如圖3所示：

從圖中可以看出，以KSA算法所組試卷的知識(shí)點(diǎn)重復(fù)率遠(yuǎn)低于GA，最大差值為32%，提高了試卷的質(zhì)量。

圖3 難度值方差對(duì)比實(shí)驗(yàn)

3)知識(shí)點(diǎn)走勢(shì)及擬合程度

分別以KSA算法和GA算法為核心所組試卷中隨機(jī)抽樣一次實(shí)驗(yàn)進(jìn)行分析，圖4給出了32道題目同時(shí)組5份試卷的章、知識(shí)點(diǎn)分布情況。

(a)KSA知識(shí)點(diǎn)走勢(shì)及擬合程度

(b)GA知識(shí)點(diǎn)走勢(shì)及擬合程度圖4 知識(shí)點(diǎn)重復(fù)率對(duì)比實(shí)驗(yàn)

由上圖可以看出，圖(a)較之于圖(b)，5份所組試卷的知識(shí)點(diǎn)曲線(xiàn)走勢(shì)更趨于擬合，這說(shuō)明了KSA算法在組多份試卷的情況下能夠考慮到試卷之間的知識(shí)點(diǎn)平衡關(guān)系，為考試提供了一定的公平性。但從上圖也可以看出，在個(gè)別題目上曲線(xiàn)走勢(shì)分歧較大，如：1-3題、9-11題，主要原因是：該知識(shí)點(diǎn)下沒(méi)有足額未抽取的試題以供組卷。當(dāng)組卷數(shù)目大于某知識(shí)點(diǎn)下題目總數(shù)時(shí)，KSA算法會(huì)優(yōu)先抽取該知識(shí)點(diǎn)下試題，剩下的差額試題會(huì)自動(dòng)從下一個(gè)知識(shí)點(diǎn)下抽取，當(dāng)該章下所有知識(shí)點(diǎn)均標(biāo)記為已抽取狀態(tài)，則從該章的下一章抽取。

4)算法性能對(duì)比

以組卷執(zhí)行時(shí)間代表算法性能，由圖5可以看出兩種算法性能大致一般，組卷時(shí)間在2s內(nèi)，滿(mǎn)足高校教師的需求。

圖5 知識(shí)點(diǎn)走勢(shì)對(duì)比實(shí)驗(yàn)

由以上所有對(duì)比實(shí)驗(yàn)可知，本文與傳統(tǒng)的遺傳算法相比，極大的降低了知識(shí)點(diǎn)的重復(fù)率，利用預(yù)定義的字典數(shù)組MIsChoosed和PIsChoosed實(shí)現(xiàn)了篩選試題無(wú)重復(fù)。實(shí)際運(yùn)用中，組卷時(shí)間和體驗(yàn)符合高校教師的基本組卷需求，基于知識(shí)體系結(jié)構(gòu)的隨機(jī)抽取算法在組卷系統(tǒng)中得到了成功的運(yùn)用。

4 結(jié)語(yǔ)

組卷是試題庫(kù)建設(shè)和在線(xiàn)考試系統(tǒng)的核心內(nèi)容，設(shè)計(jì)一種高效、科學(xué)、魯棒的組卷算法則是重中之重。本文針對(duì)現(xiàn)有算法未考慮組多份難度一致、知識(shí)點(diǎn)均衡試卷的情況而提出基于知識(shí)體系結(jié)構(gòu)的隨機(jī)抽取算法和循環(huán)難度調(diào)整算法，全面考慮知識(shí)點(diǎn)、難度控制，組卷結(jié)果更加符合正常的教學(xué)活動(dòng)。在與傳統(tǒng)遺傳算法的對(duì)比實(shí)驗(yàn)中，表現(xiàn)出了更好的組卷效果。

基于本文方法開(kāi)發(fā)的題庫(kù)管理系統(tǒng)和考試系統(tǒng)已經(jīng)在西安交通大學(xué)的教學(xué)環(huán)境中得到了實(shí)際應(yīng)用，提升了教學(xué)體驗(yàn)，得到了師生的一致好評(píng)，我?！按髮W(xué)計(jì)算機(jī)”系列課程，最近幾年相繼被評(píng)為國(guó)家級(jí)“一流課程”，和該部分的教學(xué)改革是分不開(kāi)的。首先，按照知識(shí)點(diǎn)比例進(jìn)行考試題目分布，對(duì)教師的教學(xué)和學(xué)生的學(xué)習(xí)都有了更高的要求，通過(guò)對(duì)平時(shí)習(xí)題和考前模擬的綜合分析，教師可以充分了解學(xué)生對(duì)知識(shí)點(diǎn)的掌握情況，對(duì)知識(shí)點(diǎn)進(jìn)行有針對(duì)性的講解，達(dá)到提升教學(xué)質(zhì)量的目標(biāo)。而學(xué)生在反復(fù)練習(xí)的過(guò)程中，也可以查漏補(bǔ)缺，優(yōu)化解題思路，鞏固知識(shí)點(diǎn)掌握。其次，通過(guò)對(duì)知識(shí)點(diǎn)的全面覆蓋，也可以確?？荚嚬苊鈱W(xué)生復(fù)習(xí)的片面性，降低考前“押題”、“猜題”的收益率，提升學(xué)生學(xué)習(xí)水平和考試成績(jī)的相關(guān)性。

雖然實(shí)際測(cè)試結(jié)果已表明本文方法優(yōu)于傳統(tǒng)遺傳算法，但還存在著一些欠考慮的情況，如：是否可以繼續(xù)降低知識(shí)點(diǎn)重復(fù)率，是否可以在大型題庫(kù)中快速組卷。這些還需要進(jìn)一步的實(shí)驗(yàn)以完善算法。