鮑宇 王凱馨 張艷群

摘要：分析課程測(cè)試系統(tǒng)試題的題干和問(wèn)題組成的基本特征，提出利用題干和問(wèn)題的智能匹配策略，通過(guò)模塊化組裝的形式與調(diào)整試題可變參數(shù)來(lái)生成問(wèn)題和題干并創(chuàng)建試題，最終依據(jù)題型與知識(shí)點(diǎn)章節(jié)的劃分來(lái)抽取和生成測(cè)評(píng)內(nèi)容。

關(guān)鍵詞：測(cè)評(píng)系統(tǒng)；背包算法；智能組裝方法

0、引言

隨著互聯(lián)網(wǎng)和信息科學(xué)技術(shù)的迅猛發(fā)展，網(wǎng)絡(luò)技術(shù)的應(yīng)用領(lǐng)域不斷拓寬，網(wǎng)絡(luò)自主學(xué)習(xí)與課堂教學(xué)的結(jié)合已成為當(dāng)代教學(xué)手段改革的主要方式。其中，利用網(wǎng)絡(luò)信息技術(shù)協(xié)助完成自主學(xué)習(xí)過(guò)程成為該類(lèi)教育技術(shù)革新的亮點(diǎn)之一。通過(guò)自主學(xué)習(xí)平臺(tái)中的自主測(cè)評(píng)來(lái)完成自主在線測(cè)評(píng)，以及系統(tǒng)自帶的自動(dòng)閱卷功能，使得被評(píng)測(cè)者能夠隨時(shí)隨地地進(jìn)行自我檢測(cè)，這無(wú)疑方便和促進(jìn)了使用者的學(xué)習(xí)。

經(jīng)研究發(fā)現(xiàn)，目前學(xué)習(xí)網(wǎng)站測(cè)評(píng)系統(tǒng)還存在尚未完善的地方。例如測(cè)評(píng)系統(tǒng)形成試卷的方式固定，采用的是從同一題庫(kù)中抽取現(xiàn)有試題組成試卷的方法。這種方法產(chǎn)生的試題類(lèi)別與數(shù)量有限，不易解決試題抽取重復(fù)率高的問(wèn)題。

1、選題與組卷算法沒(méi)汁

1.1組卷與背包問(wèn)題

組卷就是根據(jù)要求從試題庫(kù)中選擇試題組成—份符合要求的試卷。通過(guò)研究試卷的結(jié)構(gòu)，發(fā)現(xiàn)任何一份試卷都可以分成以下3個(gè)部分來(lái)描述：①試卷的總體結(jié)構(gòu)，用來(lái)描述試卷的整體信息，包括總體難度、試卷題型、試題數(shù)目等信息；②試卷單元，用來(lái)表示試卷所包含的題型，即每一題型為一試卷單元，包括題型、試題數(shù)、知識(shí)點(diǎn)章節(jié)分布，分?jǐn)?shù)等信息；③試卷單元所包含的若干小題，用來(lái)描述試卷單元中每個(gè)小題的詳細(xì)信息，包括每個(gè)小題的題型、分?jǐn)?shù)、所屬知識(shí)點(diǎn)章節(jié)。這樣，組卷過(guò)程實(shí)際上就是根據(jù)一定的約束條件，從試題庫(kù)中抽取若干小題組成一個(gè)個(gè)試卷單元，再由這若干個(gè)試卷單元構(gòu)成一張完整試卷。若將一個(gè)試卷單元作為一個(gè)背包，背包所能裝入的試題數(shù)為背包容量，試題小包中的試題為所有的物品，則該問(wèn)題的求解就轉(zhuǎn)變?yōu)楸嘲鼏?wèn)題的求解。每一試卷單元依據(jù)所屬題型匹配不同試題小包，得到每個(gè)試卷單元后，再將整張?jiān)嚲碜鳛橐粋€(gè)大的背包，將所得到的試卷單元裝入背包，直到裝滿(mǎn)為止，從而就得到了整個(gè)試卷的解。至此，組卷實(shí)際上就轉(zhuǎn)化為了背包問(wèn)題。

背包問(wèn)題是一個(gè)非常經(jīng)典的優(yōu)化問(wèn)題背包問(wèn)題約束如下：設(shè)有一個(gè)背包，可以放入重量為S。現(xiàn)有，n件物品，重量分別為Sl，S2…Sn且均為正數(shù)，從這n件物品中選擇若干物品放入此背包，使得放入總重量恰好為S。

與解決背包問(wèn)題類(lèi)似，可以利用“回溯”的設(shè)計(jì)思想來(lái)解決此組卷問(wèn)題。針對(duì)一個(gè)試卷單元，設(shè)其所要求包含試題數(shù)為S，從試題庫(kù)中選取小題，然后將所選小題i放入試卷單元中，如果已經(jīng)選取的試題數(shù)i小于s，則繼續(xù)選取第1+1道題放人試卷單元中，直到試卷單元中的試題數(shù)為S為止。如果剩余試題中找不到合適的小題放人試卷單元，則說(shuō)明剛剛裝入試卷單元的小題“不合適”，應(yīng)將它“棄置一邊”，繼續(xù)選擇“它之后”的小題。如此重復(fù)，直到求得滿(mǎn)足要求的解或者無(wú)解為止，這樣得到一個(gè)試卷單元。同理，將所得到的若干試卷單元依次裝入試卷，直到得到一張完整的符合要求的試卷。

1.2基于背包問(wèn)題的組卷算法設(shè)計(jì)

將組卷問(wèn)題轉(zhuǎn)化為背包問(wèn)題后，則組卷問(wèn)題就是依據(jù)一定的限制條件，合理地選擇試題“裝入”試卷中。對(duì)此，首先要?jiǎng)澐挚裳b入的試題。分析試卷結(jié)構(gòu)可知，一張完整試卷由若干題型組成，而每一題型又包含若干不同知識(shí)點(diǎn)章節(jié)的小題。所以，先依據(jù)不同的題型，將一整張?jiān)嚲韯澐譃閕個(gè)試卷單元Item（i），再依據(jù)所屬不同知識(shí)點(diǎn)章節(jié)，將每個(gè)試卷單元?jiǎng)澐譃閕部分，即對(duì)于每個(gè)試卷單元i包含j（j>=0）道題，分別來(lái)自于j個(gè)知識(shí)點(diǎn)章節(jié)。在選取j道試題填充試卷單元Item（i）時(shí)，由于是采用隨機(jī)數(shù)發(fā)生器來(lái)隨機(jī)地選取知識(shí)點(diǎn)章節(jié)，就有可能出現(xiàn)某些知識(shí)點(diǎn)在同一或不同試卷中重復(fù)出現(xiàn)，造成試卷知識(shí)點(diǎn)章節(jié)橫向縱向分布不均勻的問(wèn)題，所以這里為屬于同一知識(shí)點(diǎn)章節(jié)的任意類(lèi)型的試題設(shè)置相同的頻率參數(shù)ε，ε在這里代表該知識(shí)點(diǎn)章節(jié)試題出現(xiàn)的頻率。在進(jìn)行試題抽取前，所有題庫(kù)中試題的ε初始化為相同的值，如設(shè)置為l/μ，設(shè)某一知識(shí)點(diǎn)章節(jié)的試題被抽取次數(shù)為κ，則抽取κ次后該知識(shí)點(diǎn)章節(jié)的ε更新為：

εj=1+k/μ+k（1）

其余知識(shí)點(diǎn)章節(jié)的ε隨著更新為：

εm=1/μ+k（2）

隨抽取次數(shù)κ的增加，εj會(huì)最終大于εm，即k越大，εj大于εm的程度越大，在題庫(kù)中相對(duì)出現(xiàn)頻率越大。那么在隨后的抽取試題的過(guò)程中，會(huì)優(yōu)先選擇ε小的知識(shí)點(diǎn)裝入試卷單元Item（i），這樣可以使試卷結(jié)構(gòu)分布更均勻，避免同一或不同試卷知識(shí)點(diǎn)分布不均的現(xiàn)象。

綜上，將每道試題記為Item（i，j，εj），i表示題目類(lèi)型，j表示所屬知識(shí)點(diǎn)章節(jié)，εj表示該知識(shí)點(diǎn)章節(jié)試題出現(xiàn)的頻率。則基于背包問(wèn)題的組卷問(wèn)題就可看做，從已有的試題小包中抽取試題Item（ij，εj），將試卷單元Item（i）裝滿(mǎn)，再由Item（i）組成一張完整試卷的過(guò)程，試卷填充結(jié)構(gòu)如表l所示。

根據(jù)上述描述，設(shè)計(jì)基于背包問(wèn)題的組卷算法如下：

算法l：基于背包問(wèn)題的組卷算法

void getSolutions（試卷單元，試題小包）{

k-random（）xlOOOO%size； //size為試題小包中的物品個(gè)數(shù)

WHILE（試卷單元朱裝滿(mǎn)且有試題小包不空）{

IF（試題小包中的第κ個(gè)題可?。?/p>

將κ試題放入試卷單元內(nèi)；

k=random（）×lOOOO%size；//繼續(xù)考察試題小包中的下一個(gè)題

}

IF（試卷背包恰好裝滿(mǎn)）{求得一組解；}

退出試卷單元中的最后一道題k；

κ=random（）×lOOOO%size；//繼續(xù)考察試題小包中的下一道題

}

2、試題組裝及智能組裝策略

2.1試題組裝

解決了組卷問(wèn)題后，接下來(lái)我們要討論如何得到大量可選試題。若采用從固定題庫(kù)中抽題的方法，那么可以使用的試題數(shù)目非常有限，且容易重復(fù)，所以我們提出采用動(dòng)態(tài)組裝試題形成試題的方法來(lái)解決這個(gè)問(wèn)題。仔細(xì)觀察某些試題就會(huì)發(fā)現(xiàn)，一道試題從語(yǔ)法結(jié)構(gòu)上能劃分為若干部分，可以看做是多個(gè)前提、問(wèn)題約束及問(wèn)題的集合，即{前提1，前提2，……}、{問(wèn)題約束1，問(wèn)題約束2，……}，{問(wèn)題l，問(wèn)題2，……}，也就是說(shuō)每道題都由若干題干搭配組合而成。對(duì)于該類(lèi)試題，通過(guò)幾個(gè)題干集合的排列組合，形成不同的試題，若將每一集合分別拓展開(kāi)來(lái)，即由設(shè)計(jì)者預(yù)先定義好每一集合所包含的若干元素，按照一些組題策略，通過(guò)幾個(gè)子集中元素的組合搭配即可形成數(shù)量可觀的試題，很好地解決了傳統(tǒng)固定題庫(kù)抽題所帶來(lái)的問(wèn)題。對(duì)于試題組裝，本文作如下設(shè)置：

設(shè)題干小包Bagi（i=0，1，2，3）：

Bagl中元素為（Prebagl，Prebag2，Prebag3....），為前提小包Prebag，每一Prebagi內(nèi)容為一給定的大知識(shí)點(diǎn)范疇（如樹(shù)、圖、數(shù)組等），Prebagi中元素為ai；

Bag2中元素為（Tipbagl，Tipbag2，Tipbag3...），為問(wèn)題約束小包Tipbag，內(nèi)容涉及具體問(wèn)題約束，如相關(guān)算法、所提供的某些具體條件等；每一Tipbag包含若干可與 Prebagi中某一元素搭配的元素bi；

Bag3中元素為（Quebagl，Quebag2，Quebag3....），為問(wèn)題小包Qucbag，內(nèi)容為所提出的問(wèn)題，如“求解……A.B、C”等；每一Quebag包含若干可與Tipbag/中某一元素搭配的元素ci。

對(duì)于包含參數(shù)的試題來(lái)說(shuō)，還可以通過(guò)使用隨機(jī)數(shù)發(fā)生器，對(duì)題干所包含參數(shù)進(jìn)行隨機(jī)修改，形成新的題干元素，再按照試題組裝算法進(jìn)行試題組裝。在預(yù)先設(shè)置題干小包Bagi時(shí)，對(duì)其中元素所包含的參數(shù)進(jìn)行初始化，在形成試題過(guò)程中，再隨機(jī)生成數(shù)字，代替原有參數(shù)，這樣不僅增加了試題的數(shù)量，還可減少試題的重復(fù)性；也可將作為問(wèn)題的題干位置設(shè)為參數(shù)，進(jìn)行隨機(jī)化處理。

2.2組裝策略

依據(jù)題干的位置不同，可將組裝策略分為兩類(lèi)：題干視為參數(shù)型組裝策略、題干位置固定型組裝策略。第一種類(lèi)型中，將題于視為參數(shù)，并隨機(jī)選取問(wèn)題題干的位置，如問(wèn)題題干放到句末，或是將包含已知條件的題干作為問(wèn)題（可作選擇題、填空題）；第二種類(lèi)型為默認(rèn)問(wèn)題題干在最后給出。對(duì)于不同的類(lèi)型，有不同的組裝策略，先給出兩類(lèi)組裝策略的通用策略：

（1）題干組裝策略。在組題過(guò)程中，對(duì)每個(gè)上一層的題干小包中的元素，選取可搭配的題干小包。又每一元素有可能只與某些小包中的元素可搭配。所以，當(dāng)上一層小包中元素為空，或找不到可搭配的下一層小包時(shí)，就要采用回溯法返回到上一步，開(kāi)始新一輪的搜索匹配。

（2）參數(shù)隨機(jī)策略。如在選定Bagl中的Prebag后，Bag2中與其搭配的Tipbag不一定只有一個(gè)，這時(shí)就需要隨機(jī)選取一個(gè)Tipbag，對(duì)于接下來(lái)的小包或元素選取也采用同樣的隨機(jī)方法，以確保組題步驟的連續(xù)性和隨機(jī)性，特別是對(duì)于有參數(shù)題干中參數(shù)的隨機(jī)生成。這要求使用一個(gè)運(yùn)算速度快，分布均勻的隨機(jī)數(shù)發(fā)生器。

（3）語(yǔ)法語(yǔ)義判斷策略。由于組題完全由系統(tǒng)進(jìn)行，在組裝出的試題中有可能存在誤差，有些可組裝試題不一定符合語(yǔ)法規(guī)則，或在答案鏈表中搜索不到可匹配答案，這要求丟棄該類(lèi)試題，繼續(xù)進(jìn)行其他的試題組裝。

（4）題型選擇策略。生成一道完整試題后，若給出可選答案，即為選擇題；若無(wú)可選答案，則為綜合題；若題干中含有空缺部分，則為填空題。

以上策略對(duì)于兩種類(lèi)型的組裝方法都適用，接下來(lái)給出僅適用于題干視為參數(shù)型的組裝策略：①題干參數(shù)化策略：在這種類(lèi)型中，將題干的位置視為參數(shù)，即可以隨機(jī)生成題干位置，一個(gè)題干既可作為問(wèn)題約束部分，也可作為提出問(wèn)題部分。例如將來(lái)自3個(gè)小包中的題干元素ai，bi，ci視為參數(shù)，既可以由ai>bi>ci連接方式形成一道題，也可由ai>ci>bi的連接方式形成一道題。這里將題干的位置參數(shù)化，并設(shè)為隨機(jī)。②問(wèn)題題干截取策略：由題干組裝形成一完整試題后，隨機(jī)截取題干所給已知條件，并將所挖部分作為試題答案，以此生成選擇或填空題。

最后給出僅適用題干位置固定型的組裝策略：題干選擇策略，即當(dāng)Bagi題干小包的元素不為空，并且從中可找到與Bagi-l小包的元素搭配的元素時(shí)，則選取該元素；依照Prebag->Tipbag->Quebag的次序進(jìn)行題干選取，直到得到足以組裝成一道完整試題的若干題干，將其依序連接成一道完整試題。

2.3算法實(shí)現(xiàn)

在組裝試題時(shí)，分別從不同的Bagi中隨機(jī)選取元素小包，在不同的元素小包中隨機(jī)選取題干元素，依次進(jìn)行人棧。之后依次取出入棧的題干元素，按順序進(jìn)行鏈接，形成一道完整試題，然后進(jìn)行語(yǔ)義語(yǔ)法分析，看是否為可用試題。若經(jīng)過(guò)檢驗(yàn)，則將試題放入題庫(kù)，然后對(duì)所得題干元素進(jìn)行排列組合，選出符合語(yǔ)法規(guī)則的試題放入題庫(kù)（不包括之前得到的依序組裝的試題），以此實(shí)現(xiàn)組裝策略中的題干視為參數(shù)型的試題組裝；若沒(méi)有經(jīng)過(guò)檢驗(yàn)，所得試題不符合語(yǔ)法規(guī)則，則將棧頂?shù)念}干元素出棧，選擇其他的題干元素入棧，如此反復(fù)，得到試題庫(kù)。具體算法實(shí)現(xiàn)步驟如下：

算法2：試題組裝算法

Stepl：從Bagl中隨機(jī)選擇任一Prebagx；若為空，則組題過(guò)程結(jié)束；

Stcp2：若Prebagx非空，則從Prebagx中隨機(jī)選取元素am，將am入棧；若為空，返回Stepl；

Step3：從Bag2中搜尋可與am搭配的Tipbag小包，從搜尋結(jié)果中隨機(jī)選擇一Tipbagy；若為空，am出棧，返回Stcp2；

Step4：從Tipbagy巾隨機(jī)選擇元素bn，將bn人棧，若為空，返回Step3；

Step5：從Bag3 ff I搜尋可與bn搭配的Quebag小包，從搜尋結(jié)果中隨機(jī)選擇一Quebagz；若為空，6n出棧，返回Step4；

Step6：從Quebagz中隨機(jī)選擇元素ci，將Ci入棧，若為空，返同Step5；

Step7：獲取棧中元素，根據(jù)入棧順序連接元素am->bn->ci，進(jìn)行語(yǔ)義分析，若符合語(yǔ)法規(guī)則，則將該題目中所含參數(shù)進(jìn)行隨機(jī)具體化，并將其作為綜合題存入題庫(kù)；

注：由于整個(gè)組裝試題過(guò)程由程序來(lái)完成，試題是由幾個(gè)題干元素搭配而成，在連接成句時(shí)或多或少會(huì)存在語(yǔ)句不通，語(yǔ)義不搭的情況，所以連接后進(jìn)行語(yǔ)義語(yǔ)法分析是必要的。只有符合語(yǔ)法語(yǔ)義規(guī)則，且符合問(wèn)題邏輯的試題才可以作為可用試題存入題庫(kù)。

Step8：再將所得題干元素am，bn，ci視為參數(shù)，進(jìn)行隨機(jī)排列組合，對(duì)所得每一種結(jié)果（除Step7中所得試題）進(jìn)行語(yǔ)義分析，若通過(guò)檢驗(yàn)，則隨機(jī)挖取題干元素所給已知條件，并將所挖部分作為試題答案，以此生成選擇或填空題存入題庫(kù)；出棧ci，返同Step6。

3、應(yīng)用舉例

以數(shù)據(jù)結(jié)構(gòu)中圖及樹(shù)的有關(guān)知識(shí)點(diǎn)為例，進(jìn)行題干小包劃分，并實(shí)現(xiàn)題干組裝。

首先設(shè)置題干小包Bag/（這里取/=3）：對(duì)于Bagl，選取一元素Prebagl小包，Prebagl中元素為以“圖”及“樹(shù)”為范疇的知識(shí)點(diǎn)，記為ai；對(duì)于Bag2，其中可選擇元素為T(mén)ipbagl. Tipbag2，Tipbag3，Tipbag4，每個(gè)Tipbagi中包含若干可選元素，每一Tipbag中元素記為bij；對(duì)于Bag3，可選元素為Quebagl，Quebag2，Quebag3，每一Quebag/中含有可選元素，每一 Quebag中元素記為cij。

依據(jù)以上設(shè)置進(jìn)行一部分的題干小包初始化，部分題干小包排列組合結(jié)構(gòu)如圖l所示。

下面是一道試題的具體生成過(guò)程：

（1）隨機(jī)在Bagl中選取Prebag小包，獲得Prebagl小包，隨機(jī)取其中的元素，得到a3，并將其入棧；

（2）隨機(jī)在Bag2中選取可與元素a3搭配的Tipbag小包，獲得Tipbag2小包，隨機(jī)取其中的元素，得到62，并將其入棧；

（3）隨機(jī)在Bag3中選取可與冗素62搭配的Quebag小包，獲得Quebag2小包，隨機(jī)取其中的元素，得到c2；

（4）將元素a3，b2，c2出棧，依據(jù)人棧順序，將所得元素依次連接，組成一道試題，然后進(jìn)行試題語(yǔ)義語(yǔ)法分析，若符合語(yǔ)法規(guī)則，則使用隨機(jī)數(shù)發(fā)生器具體化其中的參數(shù)圖G（V.E）及結(jié)點(diǎn)vi；

（5）將試題作為綜合題存入題庫(kù)。至此，通過(guò)依次在Prcbagl，Tipbag2，Quebag2小包中分別選取題十元素a3，b2，c2，再將這些元素依次連接成句，并具體化其中的參數(shù)，進(jìn)而形成“已知圖Gl=（V，E）的鄰接表，依據(jù)最短路徑算法，找出vl到其余各頂點(diǎn)的最短距離”這道試題。

對(duì)圖1中題干排列組合進(jìn)行分析，可得題干組裝試題為：

al～a6->bll～b12->cl；

a1～a6->b2->c2：

al～a2->c31～c32：

al～a7->b31～b32->c4；

a6->b31～b32->c5：

a8->b41～b43->c4：

總共可組合形成試題數(shù)：N=6×2×1+6×1×1+2×2+7×2×1+1×2×1+1×3×1=41道。這里只給定了某些題干小包的一部分元素，并且組裝過(guò)程未包括題干視為參數(shù)的組裝過(guò)程?？梢韵胂?，如果完整地將數(shù)據(jù)結(jié)構(gòu)的所有知識(shí)點(diǎn)進(jìn)行題干劃分，按照本文所述題干組裝方法進(jìn)行試題組裝，將會(huì)動(dòng)態(tài)得到數(shù)量十分可觀的試題。并且，在這些試題中，抽取出現(xiàn)重復(fù)的概率很??；除此之外，由于產(chǎn)生的試題難度相差不會(huì)過(guò)大，可以同時(shí)提高評(píng)測(cè)的隨機(jī)性和公平性。

4、結(jié)語(yǔ)

智能出卷測(cè)評(píng)系統(tǒng)的實(shí)現(xiàn)打破了傳統(tǒng)從固定題庫(kù)中抽取試題組成試卷的出卷方式，在增加試題數(shù)量的同時(shí)，也使得試題重復(fù)的概率極小，使得測(cè)評(píng)系統(tǒng)出題更加智能化，試卷組成更加多樣化，服務(wù)學(xué)生更加個(gè)性化。我們提出的測(cè)評(píng)系統(tǒng)仍存在不完善的地方，比如設(shè)計(jì)者分析搭配關(guān)系需要很大的工作量；在組裝試題過(guò)程中會(huì)出現(xiàn)不符合語(yǔ)法語(yǔ)義的試題等。

總之，此種智能測(cè)評(píng)系統(tǒng)不僅可以極大地方便和豐富學(xué)生的試題訓(xùn)練，還可將其應(yīng)用在服務(wù)于其他群體的網(wǎng)站測(cè)評(píng)系統(tǒng)中，從而為大眾提供更高質(zhì)量的在線測(cè)評(píng)服務(wù)。