計(jì)算機(jī)考試系統(tǒng)隨機(jī)生成算法的研究與應(yīng)用

陳磊

（渤海船舶職業(yè)學(xué)院，遼寧興城125105）

計(jì)算機(jī)考試系統(tǒng)隨機(jī)生成算法的研究與應(yīng)用

陳磊

（渤海船舶職業(yè)學(xué)院，遼寧興城125105）

隨著計(jì)算機(jī)應(yīng)用技術(shù)的不斷發(fā)展，開發(fā)計(jì)算機(jī)考試系統(tǒng)實(shí)現(xiàn)無紙化考試，成為近年來一個非?；钴S的研究領(lǐng)域，而隨機(jī)生成試題的功能是計(jì)算機(jī)考試系統(tǒng)的重要組成部分?；赩isual FoxPro程序設(shè)計(jì)語言的計(jì)算機(jī)考試系統(tǒng)中兩種隨機(jī)生成試題的算法，實(shí)現(xiàn)了隨機(jī)生成題號和抽題功能的分離，簡單實(shí)用且適合于多種計(jì)算機(jī)考試系統(tǒng)。

計(jì)算機(jī)考試系統(tǒng)；隨機(jī)生成；算法；哈希函數(shù)法

在學(xué)校的教學(xué)過程中，考試環(huán)節(jié)是重要的組成部分。傳統(tǒng)的考試方式在命題、組織考試、閱卷和統(tǒng)計(jì)分?jǐn)?shù)的過程中，工作量大，要花費(fèi)大量的時間和精力，而且工作效率比較低，也容易出現(xiàn)錯誤。

隨著科學(xué)技術(shù)的不斷發(fā)展，信息技術(shù)的不斷進(jìn)步，考試的載體和手段也發(fā)生了革命性的變化。如何運(yùn)用計(jì)算機(jī)考試系統(tǒng)，客觀、準(zhǔn)確地評估應(yīng)試者的知識和能力水平，已成為這個領(lǐng)域研究的重要內(nèi)容。

1 隨機(jī)生成試題的算法

作為一個完善的計(jì)算機(jī)考試系統(tǒng)，隨機(jī)生成試題的功能必不可少。它是防止考生作弊、保證考試公平的一個重要手段。開發(fā)一個離散度高，效率也高的隨機(jī)生成試題算法是隨機(jī)生成試題功能的關(guān)鍵。

1.1 哈希函數(shù)法

在記錄的存儲位置和它的關(guān)鍵字key之間建立一個確定的對應(yīng)關(guān)系即一個函數(shù)關(guān)系H(key)，使每個關(guān)鍵字key和結(jié)構(gòu)中一個唯一的存儲位置相對應(yīng)，通常稱這個函數(shù)H(key)為哈希函數(shù)。哈希函數(shù)是一個映像，即將關(guān)鍵字的集合映射到某個地址集合上，它的設(shè)置很靈活，只要這個地址集合的大小不超出允許范圍即可。

由于哈希函數(shù)是一個壓縮映像，因此在一般情況下很容易產(chǎn)生沖突。即key1≠key2，而H(key1)=H(key2)。因此，在設(shè)計(jì)哈希函數(shù)時，一方面要考慮選擇一個好的哈希函數(shù)；另一方面要選擇一種處理沖突的方法。所謂正確的哈希函數(shù)，指的是對于集合中的任意一個關(guān)鍵字，經(jīng)哈希函數(shù)得到的哈希地址盡可能均勻地分布在線性表中的n個連續(xù)內(nèi)存單元地址上，從而減少沖突，同時使計(jì)算過程盡可能簡單以達(dá)到盡可能高的時間效率。

以筆者開發(fā)的計(jì)算機(jī)考試系統(tǒng)為例，原始題庫是以二維表的形式存在的，以計(jì)算機(jī)基礎(chǔ)題庫為例，單選題60個，題號1至60。通過隨機(jī)算法將60個單選題的原始順序打亂生成一組新的排列順序，然后按照這組新序列抽題、組題。哈希函數(shù)的構(gòu)造方法采用隨機(jī)數(shù)和除留余數(shù)綜合的方法。1至60的數(shù)據(jù)集合作為關(guān)鍵字的集合，用i代表關(guān)鍵字，通過隨機(jī)函數(shù)產(chǎn)生一個隨機(jī)數(shù)rd作為因子乘以關(guān)鍵字i再除以一個等于或大于哈希表長度n的整數(shù)p后得到的余數(shù)作為此關(guān)鍵字的哈希地址，該地址保存到數(shù)組中。見以下表達(dá)式：

整數(shù)p選擇了與n相鄰的大于或等于n的質(zhì)數(shù)，比如本例中單選題60個，p取值為質(zhì)數(shù)61，因?yàn)橘|(zhì)數(shù)是除了1和該數(shù)本身再也不能被其他數(shù)整除的數(shù)，所以連續(xù)的數(shù)據(jù)集合除以p取余數(shù)，產(chǎn)生沖突的可能性非常小，并且所得地址小于61，能夠均勻地分布在1至60區(qū)間。經(jīng)實(shí)驗(yàn)證明本例使用這種方法沖突率為0。

但是這種方法有一個弱點(diǎn)，它的理想狀態(tài)是題目總數(shù)的下一個數(shù)恰好是質(zhì)數(shù)，此時函數(shù)值的沖突率為0，且完全均勻地分布在指定區(qū)間。如果不是理想狀態(tài)，就會出現(xiàn)兩種情況，第一種情況，p值取題目總數(shù)的下一個數(shù)但不是一個質(zhì)數(shù)，則函數(shù)值沖突率不為0；第二種情況，p值取大于或等于題目總數(shù)的相鄰質(zhì)數(shù)，但該質(zhì)數(shù)不是題目總數(shù)的下一個數(shù)（比如共有55道題，大于等于55的相鄰質(zhì)數(shù)為59），則函數(shù)值不能完全均勻地分布在指定區(qū)間。

針對上述問題處理沖突的基本思想是：當(dāng)發(fā)生沖突時，將待插入函數(shù)值存入另一個不產(chǎn)生沖突的地址中，從而解決沖突。本例采用的處理沖突的方法是開放地址法。所謂開放地址即未填入數(shù)據(jù)的空閑地址。開放地址法就是為產(chǎn)生沖突的記錄求得一個地址序列：

增量di有三種取法：線性探測再散列、二次探測再散列（也稱平方探測再散列）和隨機(jī)探測再散列，本例采用線性探測再散列：di=i即di=1，2，3，…

增量di具有下面的特性：產(chǎn)生的Hi均不相同，且所產(chǎn)生的s(m-1)個Hi值能覆蓋數(shù)組中所有的地址。

1.2 數(shù)組下標(biāo)隨機(jī)抽取法

首先將原始題號保存在數(shù)組ord（ns） 中，變量ns為題目總數(shù)，也是循環(huán)結(jié)構(gòu)的終值，然后在循環(huán)中通過表達(dá)式int(rand()*(ns-i+1)+ 1)依次生成隨機(jī)下標(biāo)保存在變量idx中，在Visual FoxPro中隨機(jī)函數(shù)rand()的函數(shù)值為大于等于0并且小于1的數(shù)，乘數(shù) (ns-i+1)說明數(shù)組使用的長度不斷縮小。通過表達(dá)式r(i)=ord (idx)，將隨機(jī)下標(biāo)對應(yīng)的數(shù)組值保存到r(i)，將原始題號數(shù)組ord（ns） 中已抽取的數(shù)據(jù)ord (idx)依次與該數(shù)組后面的數(shù)據(jù)回溯交換，這樣已用過的數(shù)組值被交換到后面去，未用過的數(shù)組值被交換到前面來，在從未使用的關(guān)鍵字中，獲得新的關(guān)鍵字，直到循環(huán)結(jié)束。

在這種方法中，雖然下標(biāo)idx可能是重復(fù)的即產(chǎn)生沖突，但是按此下標(biāo)抽取的數(shù)組值卻是全新的，避免了沖突并且完全均勻地分布在指定區(qū)間。同時這種方法不受題目數(shù)量的影響，調(diào)整方便。程序代碼如下：

2 隨機(jī)數(shù)的產(chǎn)生方法

隨機(jī)生成一組不重復(fù)的題目，這個過程關(guān)鍵是由隨機(jī)數(shù)來實(shí)現(xiàn)的，雖然在很多高級程序設(shè)計(jì)語言中提供了相當(dāng)于rand（）這樣產(chǎn)生隨機(jī)數(shù)的函數(shù)，但是它產(chǎn)生的隨機(jī)數(shù)并不能完全符合實(shí)際應(yīng)用的要求，我們知道計(jì)算機(jī)不可能產(chǎn)生完全隨機(jī)的數(shù)字，電腦中的隨機(jī)數(shù)發(fā)生器都是通過設(shè)計(jì)的算法對事先預(yù)設(shè)的隨機(jī)種子做相應(yīng)的運(yùn)算，最后得到的結(jié)果用來模擬完全隨機(jī)數(shù)。這種隨機(jī)數(shù)被稱作偽隨機(jī)數(shù)，偽隨機(jī)數(shù)是以相同的概率從一組有限的數(shù)字中選取的，這會導(dǎo)致多名學(xué)生抽到相同的試卷，或同一個學(xué)生在不同的時間運(yùn)行計(jì)算機(jī)考試系統(tǒng)會抽到相同的試卷。所以如何避免產(chǎn)生重復(fù)隨機(jī)數(shù)就成了我們必須解決的問題。

解決的方法之一是采用計(jì)算機(jī)內(nèi)部時鐘的秒數(shù)當(dāng)種子，因?yàn)殡娔X內(nèi)部時間的秒數(shù)時刻都在變化，所以產(chǎn)生的隨機(jī)數(shù)種子相同的可能性就很小，在Visual FoxPro中獲取時鐘的秒數(shù)的表達(dá)式如下：

該表達(dá)式中提取的秒數(shù)除以10取余數(shù)，可將隨機(jī)種子的范圍限定在0到9之間，秒數(shù)的取值范圍為0到59，可根據(jù)實(shí)際需要對不同的數(shù)值進(jìn)行除留余數(shù)的運(yùn)算，以調(diào)整隨機(jī)種子的范圍。

3 SQL語句左連接操作抽取試題

隨機(jī)生成的試題順序有了，接下來要解決的就是如何把原始試題按隨機(jī)順序抽取出來，首先創(chuàng)建一個具有“題號”字段的數(shù)據(jù)表cf2，通過循環(huán)結(jié)構(gòu)和replace命令將隨機(jī)生成的試題順序加入到表cf2的“題號”字段中，SQL語句的select-from-left join左連接操作，即結(jié)果中只出現(xiàn)左表中出現(xiàn)的記錄，右表若無滿足連接條件的記錄，則相關(guān)字段的值取空值。連接過程中表cf2定義為左表，原始表定義為右表，通過左連接操作將原始表中的相關(guān)字段按照表cf2的題號順序連接成一個新表，即可完成抽取試題的功能。然后關(guān)閉并刪除表cf2，將新表的題號按照從小到大的順序重新排列，程序代碼如下：

replace record i題號with r(i)

next

select cf2.題號,cf.題型,cf.試題,cf.學(xué)生答案, cf.答案,cf.對錯,cf.選項(xiàng)數(shù);

from cf2 left join cf;

on cf2.題號=cf.題號into dbf cf3

*執(zhí)行上面sql語句，不論cf2和cf是否打開，涉及到的三個表都會被打開，所以要關(guān)閉指定表

use in cf

use in cf2

drop table cf2&&用完刪除cf2

for i=1 to an &&將題號重新按順序排列

replace record i題號with i

next

4 分析與思考

上面介紹的兩種隨機(jī)生成試題的算法，都是用數(shù)組保存生成的隨機(jī)數(shù)字。在生成隨機(jī)數(shù)字的過程中沒有同時抽取數(shù)據(jù)表中的記錄，與一邊生成隨機(jī)數(shù)字一邊訪問數(shù)據(jù)庫記錄的算法相比，實(shí)現(xiàn)了隨機(jī)生成題號和抽題功能的分離，便于后期的維護(hù)與完善，對于計(jì)算機(jī)考試系統(tǒng)的運(yùn)行效率也有了很大提高。

[1]秦玉平,馬靖善.《數(shù)據(jù)結(jié)構(gòu)》(C語言版)(第二版)[M].北京:清華大學(xué)出版社,2012.

[2]周麗韞.基于ASP的在線考試系統(tǒng)隨機(jī)生成不重復(fù)試題算法的研究[J].黑龍江科技信息,2011(9):92.

[3]段興.Visual FoxPro實(shí)用程序100例[M].北京:人民郵電出版社,2002.

[4]熊發(fā)涯.Visual FoxPro程序設(shè)計(jì)[M].北京:中國鐵道出版社,2005.?

［責(zé)任編輯：宋艷華］

Research and Application of Random Generating Algorithm in Computer Examination System

CHEN Lei
(Bohai Shipbuilding Vocational College,Xingcheng 125105,China)

With the continious development of computer application technology,it has become a very active research field in recent years to develop computer examination system to realize paperless examination.The function of randomly generated examination questions is an important part of computer examination system. Based on Visual FoxPro programming language computer test system,the two randomly generated test questions algorithm can achieve the separation of random qid and test extraction function,be simple and practical and suitable for a variety of computer test system.

computer examination system;random generation;algorithm;hash function method

TP312

A

2095-5928（2016）06-30-03

2016-09-15

遼寧省職業(yè)技術(shù)教育學(xué)會2015年立項(xiàng)課題（LZY15412）

陳磊（1982-），男，山東金鄉(xiāng)人，講師，學(xué)士，研究方向：計(jì)算機(jī)應(yīng)用。

10.16850/j.cnki.21-1590/g4.2016.06.009