周志鋒+童凌+王浩茂

摘要：網(wǎng)上在線(xiàn)考試目前正在逐步取代傳統(tǒng)的考試方式。針對(duì)程序設(shè)計(jì)類(lèi)課程，實(shí)現(xiàn)了一種能夠進(jìn)行自動(dòng)組卷和判卷的在線(xiàn)考試系統(tǒng)。首先利用遺傳算法將試題模擬自然因子通過(guò)自然選擇機(jī)制，自動(dòng)組成符合要求的試卷。完成考試后，借鑒ACM在線(xiàn)測(cè)評(píng)機(jī)制自動(dòng)對(duì)試卷進(jìn)行評(píng)判，從而大大減輕了教師工作量。該系統(tǒng)具有實(shí)用性強(qiáng)、使用方便等優(yōu)點(diǎn)，在實(shí)際應(yīng)用中取得了良好效果。

關(guān)鍵詞：程序設(shè)計(jì)類(lèi)課程；在線(xiàn)考試系統(tǒng)；遺傳算法；自動(dòng)組卷；自動(dòng)判卷

DOIDOI：10.11907/rjdk.171014

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

文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1672-7800（2017）006-0066-04

0 引言

隨著計(jì)算機(jī)技術(shù)在教學(xué)中的廣泛應(yīng)用，考試方式由以前單一、固定試題和人工閱卷的傳統(tǒng)方式，逐漸向多樣化、靈活試題和計(jì)算機(jī)自動(dòng)評(píng)分的無(wú)紙化考試過(guò)渡。在數(shù)字化考試中，使用在線(xiàn)網(wǎng)絡(luò)考試是當(dāng)今主流的考試方式。在歐美地區(qū)，較有影響力的機(jī)構(gòu)如美國(guó)教育考試中心ETS舉辦的美國(guó)研究生入學(xué)考試GRE和計(jì)算機(jī)文化考試、高級(jí)就業(yè)計(jì)算機(jī)科學(xué)考試等，其考試形式即完全采用計(jì)算機(jī)在線(xiàn)進(jìn)行。除此之外，目前的托福和雅思等標(biāo)準(zhǔn)化英語(yǔ)水平能力測(cè)試也采用了網(wǎng)絡(luò)考試方式。很多職業(yè)資格認(rèn)證機(jī)構(gòu)、教育主管部門(mén)以及大型公司招聘應(yīng)屆生時(shí)都開(kāi)發(fā)了針對(duì)各自目標(biāo)考生的考試系統(tǒng)，如中國(guó)計(jì)算機(jī)學(xué)會(huì)計(jì)算機(jī)職業(yè)資格認(rèn)證（CCF）即采用了網(wǎng)上出題、在線(xiàn)編程提交的方式。在各大高校，在線(xiàn)網(wǎng)絡(luò)考試也得到了廣泛認(rèn)可，如清華大學(xué)、上海交通大學(xué)等高校都開(kāi)發(fā)出了符合學(xué)校需求的在線(xiàn)考試系統(tǒng)[1]。

在上述眾多考試系統(tǒng)中，大部分考試系統(tǒng)都實(shí)現(xiàn)了對(duì)客觀題的自動(dòng)評(píng)分，部分考試系統(tǒng)還研究出了對(duì)于不同種類(lèi)主觀題的評(píng)分方法。如在GRE考試中，美國(guó)教育考試中心根據(jù)近年來(lái)對(duì)作文的自動(dòng)評(píng)分研究機(jī)制，推出了對(duì)于考試寫(xiě)作部分的自動(dòng)化評(píng)分系統(tǒng)，減輕了閱卷人過(guò)去批改大量作文的負(fù)擔(dān)；中國(guó)計(jì)算機(jī)學(xué)會(huì)在其開(kāi)展的計(jì)算機(jī)職業(yè)資格認(rèn)證考試系統(tǒng)中，也對(duì)考生提交的代碼實(shí)行自動(dòng)評(píng)分。然而，實(shí)現(xiàn)主觀題評(píng)分的系統(tǒng)適用性很窄，無(wú)法將其項(xiàng)目推廣到程序設(shè)計(jì)類(lèi)課程考試中。針對(duì)這些問(wèn)題，本文提出一種借鑒ACM在線(xiàn)測(cè)評(píng)機(jī)制的自動(dòng)判卷功能方式，對(duì)程序設(shè)計(jì)類(lèi)的主觀編程試題進(jìn)行客觀評(píng)判。同時(shí)，自動(dòng)組卷也是實(shí)現(xiàn)在線(xiàn)考試的重要環(huán)節(jié)之一，本設(shè)計(jì)采用遺傳算法，按照教師對(duì)試卷構(gòu)成的期望，隨機(jī)、高效、快速地從試題庫(kù)中抽取試題，組成一套高質(zhì)量的試卷。通過(guò)自動(dòng)組卷與判卷兩者的結(jié)合，實(shí)現(xiàn)面向程序設(shè)計(jì)的高度自動(dòng)化的考試系統(tǒng)，進(jìn)一步擺脫了人工干預(yù)，提供了一個(gè)能更好地展示學(xué)生實(shí)踐和思維能力的平臺(tái)。

1 系統(tǒng)功能設(shè)計(jì)

本系統(tǒng)主要涉及3類(lèi)用戶(hù)：管理員、教師、學(xué)生。對(duì)于不同用戶(hù)，則需要設(shè)置用戶(hù)管理模塊來(lái)維系這種角色分級(jí)，并設(shè)置不同權(quán)限。對(duì)于學(xué)生角色，系統(tǒng)設(shè)置在線(xiàn)答卷模塊來(lái)管理整個(gè)考試過(guò)程；對(duì)于教師角色，需參與出卷、組卷、發(fā)布考試的考試準(zhǔn)備流程。因此，設(shè)置試卷管理模塊來(lái)實(shí)現(xiàn)對(duì)于試卷的常用操作，同時(shí)設(shè)置題庫(kù)管理模塊，由教師負(fù)責(zé)出題、管理題庫(kù)；管理員角色具備所有權(quán)限，主要涉及對(duì)各種關(guān)鍵實(shí)體的管理，因此設(shè)置了后臺(tái)管理模塊。系統(tǒng)自動(dòng)完成的模塊是自動(dòng)組卷模塊和自動(dòng)判卷模塊，該模塊是本系統(tǒng)的關(guān)鍵模塊。本系統(tǒng)的功能架構(gòu)如圖1所示。

2 核心功能設(shè)計(jì)

2.1 基于遺傳算法的自動(dòng)組卷

遺傳算法的機(jī)器自動(dòng)組卷，利用教師提供的參數(shù)，靈活建立相應(yīng)組卷模型，然后對(duì)題目進(jìn)行篩選，以自動(dòng)生成科學(xué)合理的試卷。

遺傳算法（Genetic Algorithm，簡(jiǎn)稱(chēng)GA）是一種借鑒生物進(jìn)化機(jī)制（適者生存、優(yōu)勝劣汰）的隨機(jī)搜索算法[2-4]。其通過(guò)建立計(jì)算模型，模擬達(dá)爾文的遺傳選擇和生物進(jìn)化過(guò)程，搜索出符合“環(huán)境”要求的最優(yōu)解，所以該算法常用來(lái)解決多約束下求最優(yōu)解的問(wèn)題。本系統(tǒng)在應(yīng)用遺傳算法之前，首先要將試卷解碼成“染色體”，然后抽取一定數(shù)量的攜帶遺傳物質(zhì)的試卷集合初始化為種群，再根據(jù)環(huán)境選擇、交叉、變異等一些基本的演化操作，模擬生物進(jìn)化行為，篩選出最適合“環(huán)境”生存的最優(yōu)試卷集。

該自動(dòng)組卷實(shí)現(xiàn)流程如圖2所示。

2.2.1 染色體編碼與初始群體設(shè)計(jì)

按照傳統(tǒng)的遺傳算法問(wèn)題，首先將要求解的問(wèn)題化成0、1形式的編碼染色體。染色體應(yīng)該按題型分段，因?yàn)楸疚尼槍?duì)的是程序設(shè)計(jì)類(lèi)考試，基本題型是單選、多選、判斷、程序設(shè)計(jì)4種類(lèi)型，所以分段染色（例如一個(gè)數(shù)據(jù)結(jié)構(gòu)試題有單選5、雙選5、判斷5、程序設(shè)計(jì)題2），如圖3所示。

2.2.3 遺傳算子設(shè)計(jì)

（1）選擇算子。選擇算子主要用于模擬自然選擇的選擇概率，確定該個(gè)體是否能夠“生存”。本文采用輪盤(pán)賭算法，每個(gè)個(gè)體的選擇概率為Aj/∑Nj=1Aj。其中Aj代表第j個(gè)個(gè)體的適應(yīng)度，適應(yīng)度高的個(gè)體將有更大機(jī)率“生存”下來(lái)。

（2）交叉算子。由于染色體是分段編碼，所以采用多點(diǎn)交叉，交叉率設(shè)為0.90～0.95比較合適。在“交叉”時(shí)必須保證互換的題目分?jǐn)?shù)一樣，分?jǐn)?shù)相加等于總分，而且不能在交叉點(diǎn)前出現(xiàn)題目，否則此次“交叉”不合法。

（3）變異算子。在遺傳中，一般較少發(fā)生變異，變異率設(shè)置在0.02～0.05范圍內(nèi)比較適宜。

2.3 自動(dòng)判卷

要實(shí)現(xiàn)較為客觀地考核學(xué)生的編程能力，程序設(shè)計(jì)類(lèi)考試的重點(diǎn)不是單純地將選擇、填空等客觀題搬到計(jì)算機(jī)上，而是包含代碼編寫(xiě)類(lèi)試題的考核，這類(lèi)試題可較為準(zhǔn)確、客觀地反映學(xué)生對(duì)程序設(shè)計(jì)思想和語(yǔ)言的掌握情況。本文根據(jù)程序設(shè)計(jì)試題代碼的特點(diǎn)，設(shè)計(jì)沙盒來(lái)真實(shí)運(yùn)行學(xué)生編寫(xiě)的代碼，并根據(jù)得到的結(jié)果智能評(píng)判該類(lèi)主觀題的得分。

本文設(shè)計(jì)的自動(dòng)判卷是面向程序設(shè)計(jì)類(lèi)的客觀題和主觀題。對(duì)于客觀題，系統(tǒng)可以直接通過(guò)與標(biāo)準(zhǔn)答案對(duì)比而得出對(duì)應(yīng)分?jǐn)?shù)[5-6]；對(duì)于主觀題，它的輸入和輸出也具備唯一性，其中一個(gè)輸入對(duì)應(yīng)一個(gè)輸出，利用預(yù)先設(shè)置的測(cè)試數(shù)據(jù)即輸入集，執(zhí)行輸入程序，得出輸出集。通過(guò)將輸出集的每個(gè)點(diǎn)與標(biāo)準(zhǔn)答案輸出集對(duì)比，即可將通過(guò)測(cè)試點(diǎn)作為該題的評(píng)分依據(jù)，得到該題的分?jǐn)?shù)。通過(guò)該方式可大大減少對(duì)主觀程序題的主觀性判斷，而是以更科學(xué)的客觀依據(jù)進(jìn)行判斷。在此期間，自動(dòng)判卷功能輔助子系統(tǒng)必須保持沉睡狀態(tài)，以等待喚醒。自動(dòng)判卷流程如圖4所示。

其中每層的解釋如下：

（1）試題程序傳入。首先利用Linux消息隊(duì)列方式，將試題中源程序的代碼、題號(hào)、所用語(yǔ)言等信息封裝在上述mesg上，寫(xiě)入Linux系統(tǒng)下的消息隊(duì)當(dāng)中。通過(guò)系統(tǒng)msgget函數(shù)[intmsgget（key_t key，intoflag）；]創(chuàng)建消息隊(duì)列，命名為key，并獲取消息隊(duì)列的標(biāo)識(shí)符，然后調(diào)用系統(tǒng)msgsnd函數(shù)[intmsgsnd（intmsqid，const void * ptr，size_t length，int flag）]將消息存入對(duì)應(yīng)的消息隊(duì)列中。

（2）試題程序接收。在接受消息時(shí)，通過(guò)系統(tǒng)msgget函數(shù)[intmsgget（key_t key，intoflag）；]獲取對(duì)應(yīng)key的消息隊(duì)列的標(biāo)識(shí)符，再通過(guò)系統(tǒng)msgrcv函數(shù)[ssize_tmsgrcv（intmsqid，void * ptr，size_t length，long type，int flag）；]讀取對(duì)應(yīng)標(biāo)識(shí)符消息隊(duì)列中的一條消息mesg，從而獲取隊(duì)列中的消息內(nèi)容。

（3）編譯。對(duì)GCC、JDK等編譯器進(jìn)行必要的安全處理，利用bash命令對(duì)C++/C、Pascal、Java等語(yǔ)言程序的程序源碼選擇對(duì)應(yīng)的編譯器進(jìn)行編譯。編譯成功則進(jìn)行下一步，否則返回結(jié)果到父進(jìn)程等待計(jì)算。

（4）鏈接。經(jīng)過(guò)編譯成功后，獲取對(duì)應(yīng)的obj二進(jìn)制代碼，通過(guò)調(diào)用ld鏈接命令，執(zhí)行自動(dòng)鏈接，產(chǎn)生可執(zhí)行代碼，提供給下一步使用。

（5）運(yùn)行。通過(guò)系統(tǒng)調(diào)用子進(jìn)程child_process，child_process運(yùn)行編譯鏈接后的程序，由父進(jìn)程監(jiān)控子進(jìn)程，一旦子進(jìn)程崩潰或正常退出，會(huì)發(fā)送相應(yīng)的SIGNAL給父進(jìn)程，此時(shí)父進(jìn)程進(jìn)行相應(yīng)處理。

（6）測(cè)試數(shù)據(jù)輸入。當(dāng)前位置主要是為了數(shù)據(jù)的輸入和輸出位置的轉(zhuǎn)換，通過(guò)調(diào)用Liunx的系統(tǒng)函數(shù)，將數(shù)據(jù)輸入從標(biāo)準(zhǔn)輸入Console轉(zhuǎn)換到標(biāo)準(zhǔn)測(cè)試文件輸入，并將標(biāo)準(zhǔn)輸出Console重定向到一個(gè)臨時(shí)文件中，供下一步進(jìn)行比較。

（7）比較。通過(guò)上述4步以后，轉(zhuǎn)入對(duì)比結(jié)果階段。本階段主要是進(jìn)行數(shù)據(jù)對(duì)比，通過(guò)調(diào)用bash命令diff，將該程序通過(guò)測(cè)試輸入產(chǎn)生的輸出臨時(shí)文件與標(biāo)準(zhǔn)輸出答案文件進(jìn)行對(duì)比，并得出正確率。

（8）獲取內(nèi)存資源等情況。通過(guò)父進(jìn)程監(jiān)控子進(jìn)程，可以通過(guò)wait4函數(shù)，獲取進(jìn)程狀態(tài)和資源占用情況等，判斷是否符合題目要求，一旦檢測(cè)出非法狀況，也當(dāng)作異常處理，轉(zhuǎn)去計(jì)算結(jié)果。

（9）計(jì)算總分并返回。通過(guò)將原試卷主觀題與客觀題分類(lèi)后，經(jīng)過(guò)兩個(gè)子進(jìn)程得到的總分相加，得到本試卷的分?jǐn)?shù)，并將其存入數(shù)據(jù)庫(kù)對(duì)應(yīng)試卷的學(xué)生id位置。消息隊(duì)列的交互如圖5所示。

3 系統(tǒng)實(shí)現(xiàn)

本系統(tǒng)采用B/S結(jié)構(gòu)模式，利用Apache服務(wù)器、MYSQL數(shù)據(jù)庫(kù)和SSH開(kāi)源框架進(jìn)行搭建。Apache服務(wù)器、MYSQL數(shù)據(jù)庫(kù)是開(kāi)源軟件，所以具有更好的穩(wěn)定性與安全性。SSH即Struts+Spring+Hibernate，利用該體系設(shè)計(jì)系統(tǒng)，能夠?yàn)檎麄€(gè)系統(tǒng)后期的維護(hù)、擴(kuò)展等提供更多便利，程序的結(jié)構(gòu)脈絡(luò)更加清晰明了。實(shí)際應(yīng)用結(jié)果表明，該系統(tǒng)運(yùn)行性能良好。

4 結(jié)語(yǔ)

本項(xiàng)目旨在讓目前高校計(jì)算機(jī)程序設(shè)計(jì)類(lèi)課程考試脫離傳統(tǒng)紙質(zhì)考試的限制。平臺(tái)采用了一種自動(dòng)組卷算法，能夠大大提高組卷效率以及卷面題目構(gòu)成的合理性，以符合教師的組卷期望。同時(shí)，針對(duì)程序設(shè)計(jì)類(lèi)課程的特點(diǎn)，引入并實(shí)現(xiàn)了特殊的自動(dòng)裁判評(píng)分機(jī)制。該在線(xiàn)考試系統(tǒng)可大大減輕教師的工作量，在實(shí)踐中更加有效地考核并提升學(xué)生的編碼能力。

參考文獻(xiàn)：

[1]余穎，李曉昀，左貴啟，等. 基于自適應(yīng)遺傳算法的自動(dòng)組卷策略研究[J]. 南華大學(xué)學(xué)報(bào)：自然科學(xué)版，2016（3）：61-65.

[2]呂苗苗. 基于遺傳算法的自動(dòng)組卷系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[D].南京：南京理工大學(xué)，2012.

[3]張琨，楊會(huì)菊，宋繼紅，等. 基于遺傳算法的自動(dòng)組卷系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[J]. 計(jì)算機(jī)工程與科學(xué)，2012（5）：178-183.

[4]袁鋒. 遺傳算法在自動(dòng)組卷系統(tǒng)中的應(yīng)用[J]. 山東師范大學(xué)學(xué)報(bào)：自然科學(xué)版，2006（1）：53-56.

[5]楊志偉，曾艷姍. 基于Linux的ACM在線(xiàn)評(píng)測(cè)系統(tǒng)研究[J]. 計(jì)算機(jī)與現(xiàn)代化，2010（6）：166-169.

[6]鄭傳生. 基于B/S結(jié)構(gòu)的程序設(shè)計(jì)競(jìng)賽自動(dòng)測(cè)評(píng)系統(tǒng)的設(shè)計(jì)[J]. 計(jì)算機(jī)與現(xiàn)代化，2007（12）：109-111.

[7]楊呈永. 基于B/S結(jié)構(gòu)的大學(xué)英語(yǔ)在線(xiàn)考試系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)[D].成都：電子科技大學(xué)，2011.

[8]李佳. 《計(jì)算機(jī)基礎(chǔ)》課程上機(jī)考試系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[D].成都：電子科技大學(xué)，2011.

[9]顏?lái)? 基于B/S模式的單獨(dú)招生在線(xiàn)考試系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)[D].成都：電子科技大學(xué)，2013.

[10]樓玉萍. 基于B/S模式的計(jì)算機(jī)基礎(chǔ)考試系統(tǒng)的研究與實(shí)現(xiàn)[D].長(zhǎng)沙：國(guó)防科學(xué)技術(shù)大學(xué)，2005.

[11]李亦松. 在線(xiàn)考試系統(tǒng)分析與設(shè)計(jì)[D].昆明：云南大學(xué)，2012.

[12]李敏. 在線(xiàn)考試系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)[D].濟(jì)南：山東大學(xué)，2013.

[13]劉楠，孫國(guó)道，田賢忠. ACM在線(xiàn)評(píng)判系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)[J]. 計(jì)算機(jī)時(shí)代，2010（2）：34-35，38.

[14]趙磊，吳玉培，廖彬. 基于ACM/ICPC在線(xiàn)測(cè)評(píng)系統(tǒng)的設(shè)計(jì)[J]. 電腦知識(shí)與技術(shù)，2013（8）：5004-5006.

[15]張良銀. 淺論C/S和B/S體系結(jié)構(gòu)[J]. 工程地質(zhì)計(jì)算機(jī)應(yīng)用，2006（4）：20-23，28.

[16]陳鵬. 在線(xiàn)評(píng)判系統(tǒng)的設(shè)計(jì)和實(shí)現(xiàn)[D].南京：東南大學(xué)，2015.

[17]余穎，李曉昀，歐陽(yáng)純萍. 一種SSH框架的在線(xiàn)程序自動(dòng)評(píng)判系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[J]. 南華大學(xué)學(xué)報(bào)：自然科學(xué)版，2012（4）：65-68.

（責(zé)任編輯：黃 ?。?/p>

英文摘要Abstract：Online Testing System has gradually replaced the paper-based examination in actual institutions nowadays. With regard to the language programming course， We designed and realized an online examination system based on an automated questions assemblage technique. First， the system generated high-quality examination papers by means of adopting genetic algorithm which conducts natural selection according to question dataset. We borrowed the merit of online judge which deals with codes and marks programming-based test papers automatically. With high efficiency and convenience， the system could be applied to other test systems and achieve a great applicability.

英文關(guān)鍵詞Key Words： Language Programming Course； Genetic Algorithm； Automatic Question-assemblage System； Automatic Grading System