數(shù)據(jù)結(jié)構(gòu)在線考試系統(tǒng)研究

劉城霞

（北京信息科技大學(xué) 計(jì)算機(jī)學(xué)院，北京 100101）

0 引 言

數(shù)據(jù)結(jié)構(gòu)在線學(xué)習(xí)系統(tǒng)的考核中,不但要有對(duì)數(shù)據(jù)結(jié)構(gòu)基本概念的考核,基于邏輯結(jié)構(gòu)應(yīng)用的考核,還要有對(duì)數(shù)據(jù)結(jié)構(gòu)程序設(shè)計(jì)的考核,而基于網(wǎng)絡(luò)去做這些考核存在許多問題,比如技術(shù)實(shí)現(xiàn)有困難或?qū)Υ鸢傅臋C(jī)器評(píng)價(jià)有歧義。如何做到真正的網(wǎng)上合理考核,是主要研究和探討的內(nèi)容。

隨著網(wǎng)絡(luò)教學(xué)平臺(tái)的發(fā)展與推廣,越來越多的學(xué)生和教育機(jī)構(gòu)選擇網(wǎng)絡(luò)教學(xué)來完成知識(shí)的傳遞。比如美國(guó)很多大學(xué)運(yùn)用網(wǎng)絡(luò)完成了很多的在線教育任務(wù),學(xué)生足不出戶就可以完成全部的教學(xué)任務(wù),對(duì)于留學(xué)生來說更是提供了很大的便利,也節(jié)省了許多支出。再比如,國(guó)內(nèi)各個(gè)高校也都紛紛建立自己的在線教學(xué)體系,在專門的網(wǎng)站上開設(shè)各種課程學(xué)習(xí)。

在線教學(xué)中,如何正確有效地評(píng)價(jià)學(xué)生在線學(xué)習(xí)的效果尤為重要,正確地評(píng)價(jià)能促進(jìn)學(xué)生學(xué)習(xí)積極性并將學(xué)生不足的地方指出,指導(dǎo)學(xué)生進(jìn)一步地學(xué)習(xí)。目前評(píng)價(jià)學(xué)生學(xué)習(xí)效果主要通過在線考試來完成。在線考試與傳統(tǒng)紙質(zhì)考試比起來更靈活、更公平、更省資源、更高效。很多學(xué)者也在在線考試方面做了探索[1-2],但如何真正做到合理、有效、準(zhǔn)確地考試并評(píng)價(jià),要著重研究和探索。

1 數(shù)據(jù)結(jié)構(gòu)在線考試題目的分類

在對(duì)數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)系統(tǒng)研究之后[3-5],如何對(duì)數(shù)據(jù)結(jié)構(gòu)進(jìn)行在線考試成為一個(gè)關(guān)鍵的問題。數(shù)據(jù)結(jié)構(gòu)在線考試系統(tǒng)中題目如何劃分,是首先要考慮的問題。傳統(tǒng)的數(shù)據(jù)結(jié)構(gòu)考試中,一般包括選擇題、填空題、判斷題、簡(jiǎn)答題、應(yīng)用題、編程題、算法分析題等。而在線考試系統(tǒng)中,大致可以分為客觀題和主觀題兩大類,見圖1。其中客觀題是答案確定且易于判斷的題目,比如選擇題、填空題、判斷題;主觀題是答案大意確定但具體文字描述不確定的題目,比如簡(jiǎn)答題、編程題、應(yīng)用題及算法分析題。

客觀題目非常適合計(jì)算機(jī)進(jìn)行機(jī)考,很多在線考試試題中題目都是客觀題,但對(duì)于數(shù)據(jù)結(jié)構(gòu)課程來說,只有客觀題遠(yuǎn)遠(yuǎn)不足以評(píng)價(jià)考生的真實(shí)水平,所以需要增加主觀題幫助對(duì)考生進(jìn)行全面評(píng)判。而主觀題進(jìn)行線上考試時(shí)會(huì)出現(xiàn)自動(dòng)評(píng)判困難、需要人工復(fù)核等,這就使得線上考試的優(yōu)勢(shì)被磨滅了。如何正確地自動(dòng)評(píng)價(jià)是在線考試迫切需要解決的問題。

圖1 在線考試題目類型圖

2 數(shù)據(jù)結(jié)構(gòu)在線考試的評(píng)價(jià)體系

如何準(zhǔn)確地評(píng)價(jià)學(xué)生的學(xué)習(xí)效果,需要作為數(shù)據(jù)結(jié)構(gòu)在線考試系統(tǒng)重點(diǎn)考慮。評(píng)價(jià)體系主要涉及3個(gè)部分:①日常學(xué)習(xí)的評(píng)價(jià)②考試成績(jī)的評(píng)價(jià);③綜合能力的評(píng)價(jià)。

2.1日常學(xué)習(xí)評(píng)價(jià)

日常學(xué)習(xí)包括學(xué)生對(duì)課程內(nèi)容的學(xué)習(xí),完成每章作業(yè),進(jìn)行章節(jié)測(cè)試等,對(duì)日常學(xué)習(xí)的評(píng)價(jià)主要在于作業(yè)的完成度及完成質(zhì)量的評(píng)價(jià)、章節(jié)測(cè)試結(jié)果等。日常學(xué)習(xí)及評(píng)價(jià)過程如圖2所示。

圖2 日常學(xué)習(xí)及評(píng)價(jià)過程

當(dāng)內(nèi)容學(xué)習(xí)完成后去完成章節(jié)作業(yè),作業(yè)完成后進(jìn)行測(cè)試,測(cè)試通過后學(xué)生可以進(jìn)入下一章節(jié)學(xué)習(xí),否則需要重新進(jìn)行本章節(jié)學(xué)習(xí)。測(cè)試題主要由客觀題和答案固定的主觀題構(gòu)成,客觀題目可直接給出成績(jī),答案固定的主觀題可由答案對(duì)比結(jié)果給出參考成績(jī)。

2.2 考試成績(jī)的評(píng)價(jià)

考試是指在線考試,在完成各章學(xué)習(xí)后,可以進(jìn)行在線考試,考試題目包含上述主觀題和客觀題。對(duì)于客觀題的評(píng)價(jià)只需要和答案進(jìn)行對(duì)比即可。對(duì)于主觀題的評(píng)價(jià)需要由3方面構(gòu)成:①答案對(duì)比(如簡(jiǎn)答題、算法分析題);②運(yùn)行結(jié)果對(duì)比(如編程題);③關(guān)鍵點(diǎn)匹配(如應(yīng)用題、編程題、算法分析題)。具體可見圖3。有的題目需要由2個(gè)或3個(gè)方面一起進(jìn)行評(píng)價(jià),綜合給出最終題目成績(jī)。另外設(shè)置申訴機(jī)制,如對(duì)評(píng)判結(jié)果有異議,可以提出申訴,申訴后由老師人工進(jìn)行復(fù)核,以期更正自動(dòng)評(píng)分中出現(xiàn)的錯(cuò)誤。

圖3 考試主觀題的評(píng)價(jià)方法

2.3 綜合能力的評(píng)價(jià)

綜合能力的評(píng)價(jià)包含以上兩種評(píng)價(jià)結(jié)果,主要評(píng)價(jià)學(xué)生綜合運(yùn)用知識(shí)的能力。這里綜合能力評(píng)價(jià)會(huì)將前兩種評(píng)價(jià)的結(jié)果進(jìn)行綜合,并且根據(jù)一定的分析給出一個(gè)綜合分?jǐn)?shù)。綜合能力評(píng)價(jià)中還有一些開放性題目,這些開放性題目主要涉及實(shí)際工程應(yīng)用中的問題,學(xué)生可以尋找資料后自由回答,沒有標(biāo)準(zhǔn)的答案,由人工進(jìn)行評(píng)價(jià)。開放性題目作為學(xué)生學(xué)習(xí)能力及創(chuàng)新能力的評(píng)價(jià),提供學(xué)生自由選擇,不作為考試成績(jī)。見圖4、圖5所示。

圖4 綜合能力評(píng)價(jià)組成部分

3 數(shù)據(jù)結(jié)構(gòu)在線考試系統(tǒng)的設(shè)計(jì)

數(shù)據(jù)結(jié)構(gòu)在線考試系統(tǒng)主要涉及作業(yè)題、章節(jié)自測(cè)題及考試題目部分,開放性題目不作為考試系統(tǒng)的內(nèi)容。該系統(tǒng)可以實(shí)現(xiàn)根據(jù)要求自動(dòng)組卷及自動(dòng)評(píng)分,如此既可以減少教師出題及閱卷的工作量,又可以讓學(xué)生更加靈活的學(xué)習(xí)和考試。在學(xué)生某項(xiàng)知識(shí)較薄弱時(shí)還可以針對(duì)該薄弱知識(shí)點(diǎn)章節(jié)進(jìn)行針對(duì)性的復(fù)習(xí)測(cè)試,提高學(xué)生學(xué)習(xí)的效果和效率。

3.1 考試系統(tǒng)功能設(shè)計(jì)

系統(tǒng)中包括兩類用戶,教師和學(xué)生。基于此將系統(tǒng)分成兩大模塊:一個(gè)模塊用于教師部分,教師主要負(fù)責(zé)進(jìn)行個(gè)人信息及學(xué)生信息的管理,對(duì)題庫(kù)、考試、成績(jī)進(jìn)行管理;另外一個(gè)模塊用于學(xué)生部分,學(xué)生的主要功能就是進(jìn)行在線考試和查詢考試成績(jī)等。

具體系統(tǒng)應(yīng)該實(shí)現(xiàn)的功能:用戶根據(jù)不同的身份登錄到系統(tǒng)上,對(duì)于教師來說,可以進(jìn)行如下管理工作。

(1)考試管理:教師可以添加考試,由教師規(guī)定考試所適用的班級(jí)、考試的日期和考試限時(shí),教師還可以設(shè)置考試范圍。

(2)試題管理:教師可以對(duì)題庫(kù)中的試題進(jìn)行基本的增刪改查的操作:添加新的試題和刪除舊的試題,其中試題類型包括程序題、填空題和選擇題;對(duì)于不同類型的試題,教師可以設(shè)置除了題目、章節(jié)、難度、答案之外的備選項(xiàng)、關(guān)鍵字等不同的屬性值。

(3)成績(jī)管理:教師可以查看考生的所有考試成績(jī)進(jìn)行確認(rèn)、調(diào)整及修改,并打印輸出等。

(4)學(xué)生管理:教師可以對(duì)選課學(xué)生的資料進(jìn)行添加、修改、刪除,確認(rèn)學(xué)生是否為選修該課程學(xué)生,確認(rèn)學(xué)生是否有考試資格等。

對(duì)于學(xué)生身份來說,可以進(jìn)行如下工作。

(1)在線考試:學(xué)生可以在教師規(guī)定的時(shí)間內(nèi)進(jìn)行在線考試。最晚不得超過開考時(shí)間后的半個(gè)小時(shí)。考試開始半個(gè)小時(shí)內(nèi),考生可以在確認(rèn)交卷之前返回考試界面,重新點(diǎn)擊考試更換試卷,但是考試時(shí)間不會(huì)延長(zhǎng)?？荚嚱Y(jié)束后,系統(tǒng)將進(jìn)行在線閱卷?？忌稍诳荚嚭罅⒓粗揽荚嚱Y(jié)果。

(2)查詢考試成績(jī):學(xué)生可以在線查詢以前參加過的考試成績(jī),同一場(chǎng)考試多次參加只顯示幾次考試中的最高成績(jī)。

3.2 考試系統(tǒng)試卷的生成策略

考試系統(tǒng)需要自動(dòng)地生成試卷,一般情況下由老師輸入一些組卷參數(shù), 系統(tǒng)根據(jù)這些參數(shù)抽出相應(yīng)的試題, 組成能用來考試的試卷。定義這些參數(shù)以及對(duì)參數(shù)進(jìn)行變換的算法, 我們稱之為組卷策略。在考試系統(tǒng)中組卷效率和組卷質(zhì)量主要取決于組卷策略,因此許多學(xué)者也對(duì)組卷策略進(jìn)行了研究[6-9],這也是本項(xiàng)目中的一個(gè)重要內(nèi)容。

目前,常用的組卷算法有隨機(jī)法、回溯法、遺傳算法和隨機(jī)定位搜索法。文獻(xiàn)[10]中也對(duì)這幾種組卷算法進(jìn)行了研究,本項(xiàng)目中對(duì)章節(jié)測(cè)試采用隨機(jī)法進(jìn)行組卷,而對(duì)最終的考試采用遺傳算法進(jìn)行組卷,最終實(shí)現(xiàn)了試題的生成。

1)隨機(jī)法。

隨機(jī)法是組卷算法中一個(gè)比較基礎(chǔ)的算法,采用隨機(jī)的題目抽取方法,抽出題目后,再判斷題目的各項(xiàng)內(nèi)容是否滿足要求,滿足則保留,不滿足則舍棄。這其中可能存在抽取試題重復(fù)的情況,所以抽取完成后還需要驗(yàn)證組合的試卷是否存在題目重復(fù)問題。

隨機(jī)法算法的基本過程是由計(jì)算機(jī)隨機(jī)生成一個(gè)隨機(jī)數(shù)r,這個(gè)隨機(jī)數(shù)即題目編號(hào)ID,從數(shù)據(jù)庫(kù)中取出題目ID為r的題目,判斷該題目是否滿足要求,若滿足則放入試卷,否則重新產(chǎn)生隨機(jī)數(shù)。不斷從試卷表中抽取題目,直到達(dá)到試卷總題目數(shù),即試卷生成完畢。算法流程圖如圖6所示。

圖6 隨機(jī)法組卷過程

2)遺傳算法。

遺傳算法是組卷算法中效果較好的算法,它采用遺傳學(xué)原理對(duì)整套試卷題目進(jìn)行變換,以得到效果最好的題目。遺傳算法首先生成一個(gè)種群,種群中有固定個(gè)數(shù)的個(gè)體,個(gè)體即試卷,個(gè)體的基因即試題編號(hào)。再通過賭輪法把適應(yīng)度值較高的個(gè)體選擇出來,進(jìn)行交叉和變異,即進(jìn)行試題的交換和替換。流程圖如圖7所示。

遺傳算法的基本操作主要包括:①初始化,隨機(jī)生成滿足“題目數(shù)量”和“題型”要求的一套考試試卷;②通過適應(yīng)度函數(shù)計(jì)算出試卷的“難度系數(shù)”和“知識(shí)點(diǎn)分布”是否合理;③選擇,通過賭輪法選擇,適應(yīng)度高的試卷更容易被選擇;④交叉,隨機(jī)選擇類型、分值一樣的題目進(jìn)行交換,形成新的試卷;⑤變異是指改變?cè)嚲碇械膫€(gè)別題目,從而形成新的試卷。

4 在線考試系統(tǒng)的測(cè)試

圖7 遺傳法組卷過程

老師登錄系統(tǒng)后左側(cè)會(huì)有教師的操作目錄,包括教師信息管理、學(xué)生信息管理、題目管理、考試管理、組卷策略管理等,如題目的管理功能,老師可以進(jìn)行題目的錄入包括主觀題和客觀題的錄入;題目?jī)?nèi)容的查看;題目?jī)?nèi)容的修改以及題目的刪除等。再如組卷管理功能,老師可以錄入組卷要求,也可以修改之前已有的組卷要求。根據(jù)組卷要求,生成試卷時(shí)采用隨機(jī)法或者遺傳算法,生成需要的試卷,供學(xué)生考試需要。學(xué)生登錄后可以進(jìn)行考試,考試后學(xué)生可以查看考試成績(jī),以及查看以往考試成績(jī)。

經(jīng)過學(xué)生進(jìn)行模擬考試測(cè)試后,學(xué)生能夠通過該考試系統(tǒng)的各級(jí)考試發(fā)現(xiàn)自己的不足之處并逐漸地改進(jìn)。如編程題目在線考試部分,它相對(duì)于紙質(zhì)的編程考試要求更高、更細(xì),不再是靜態(tài)地看語(yǔ)句,而是動(dòng)態(tài)地執(zhí)行,學(xué)生在此類考試時(shí)就會(huì)更注重代碼的規(guī)范性和正確性。再如學(xué)生考試后系統(tǒng)會(huì)自動(dòng)評(píng)分,包括日常學(xué)習(xí)的評(píng)分(通過章節(jié)測(cè)試完成)及考試的評(píng)分,系統(tǒng)會(huì)綜合兩類評(píng)分結(jié)果,給出學(xué)生的綜合評(píng)分及學(xué)習(xí)重點(diǎn)的建議,這樣可以讓學(xué)生更有針對(duì)性地學(xué)習(xí),取得更好的學(xué)習(xí)效果及考試結(jié)果。

5 結(jié) 語(yǔ)

筆者主要探索研究了如何有效地實(shí)現(xiàn)一個(gè)數(shù)據(jù)結(jié)構(gòu)在線考試系統(tǒng),老師可以在線管理考試,學(xué)生能夠在線進(jìn)行考試,并且對(duì)考試組卷策略進(jìn)行了分析和選擇,對(duì)考試評(píng)價(jià)方法進(jìn)行了探索及分級(jí)綜合,最終使學(xué)生能在在線學(xué)習(xí)后對(duì)其學(xué)習(xí)效果進(jìn)行評(píng)價(jià)。