陳磊

（渤海船舶職業(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)無紙化考試，成為近年來一個(gè)非?；钴S的研究領(lǐng)域，而隨機(jī)生成試題的功能是計(jì)算機(jī)考試系統(tǒng)的重要組成部分?；赩isual FoxPro程序設(shè)計(jì)語言的計(jì)算機(jī)考試系統(tǒng)中兩種隨機(jī)生成試題的算法，實(shí)現(xiàn)了隨機(jī)生成題號(hào)和抽題功能的分離，簡(jiǎn)單實(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)大量的時(shí)間和精力，而且工作效率比較低，也容易出現(xiàn)錯(cuò)誤。

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

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

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

1.1 哈希函數(shù)法

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

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

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

整數(shù)p選擇了與n相鄰的大于或等于n的質(zhì)數(shù)，比如本例中單選題60個(gè)，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。

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

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

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

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

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

首先將原始題號(hào)保存在數(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ù)組使用的長(zhǎng)度不斷縮小。通過表達(dá)式r(i)=ord (idx)，將隨機(jī)下標(biāo)對(duì)應(yīng)的數(shù)組值保存到r(i)，將原始題號(hào)數(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í)這種方法不受題目數(shù)量的影響，調(diào)整方便。程序代碼如下：

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

隨機(jī)生成一組不重復(fù)的題目，這個(gè)過程關(guān)鍵是由隨機(jī)數(shù)來實(shí)現(xiàn)的，雖然在很多高級(jí)程序設(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ì)的算法對(duì)事先預(yù)設(shè)的隨機(jī)種子做相應(yīng)的運(yùn)算，最后得到的結(jié)果用來模擬完全隨機(jī)數(shù)。這種隨機(jī)數(shù)被稱作偽隨機(jī)數(shù)，偽隨機(jī)數(shù)是以相同的概率從一組有限的數(shù)字中選取的，這會(huì)導(dǎo)致多名學(xué)生抽到相同的試卷，或同一個(gè)學(xué)生在不同的時(shí)間運(yùn)行計(jì)算機(jī)考試系統(tǒng)會(huì)抽到相同的試卷。所以如何避免產(chǎn)生重復(fù)隨機(jī)數(shù)就成了我們必須解決的問題。

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

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

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

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

replace record i題號(hào)with r(i)

next

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

from cf2 left join cf;

on cf2.題號(hào)=cf.題號(hào)into dbf cf3

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

use in cf

use in cf2

drop table cf2&&用完刪除cf2

for i=1 to an &&將題號(hào)重新按順序排列

replace record i題號(hào)with i

next

4 分析與思考

上面介紹的兩種隨機(jī)生成試題的算法，都是用數(shù)組保存生成的隨機(jī)數(shù)字。在生成隨機(jī)數(shù)字的過程中沒有同時(shí)抽取數(shù)據(jù)表中的記錄，與一邊生成隨機(jī)數(shù)字一邊訪問數(shù)據(jù)庫(kù)記錄的算法相比，實(shí)現(xiàn)了隨機(jī)生成題號(hào)和抽題功能的分離，便于后期的維護(hù)與完善，對(duì)于計(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].北京:中國(guó)鐵道出版社,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é)會(huì)2015年立項(xiàng)課題（LZY15412）

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

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