淺談如何通過在線判題考查基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)

【摘要】要考察考生程序的健壯性時要考察程序能夠很好地應(yīng)對大輸入量，老師就很難給予如此多的輸入測試而計算機卻可以。同時，通過在線判題也能夠給考生提供實時的訓練機會。在線判題還有一個特點就是系統(tǒng)、全面。在線判題匯聚了諸多類型的題目，并且具有系統(tǒng)性，能夠?qū)?shù)據(jù)結(jié)構(gòu)的各類知識匯聚在一起。

【關(guān)鍵詞】考生，在線判題，數(shù)據(jù)結(jié)構(gòu)

1、為什么使用在線判題

在線判題就是利用計算機自行判斷考生提交的代碼是否符合題目的要求，來減少老師的工作量，提高考生的代碼編寫能力。通過在線判題還能做到老師難以做到的事情。比如：要考察考生程序的健壯性時要考察程序能夠很好地應(yīng)對大輸入量，老師就很難給予多次的輸入測試而計算機卻可以。

同時，通過在線判題也能夠給考生提供實時的訓練機會。無論何時何地，只要有計算機和網(wǎng)絡(luò)，考生就能夠練習數(shù)據(jù)結(jié)構(gòu)。

在線判題還有一特點就是系統(tǒng)、全面。在線判題匯聚了諸多類型的題目，并系統(tǒng)的將數(shù)據(jù)結(jié)構(gòu)的各類知識匯聚在一起。

在線判題系統(tǒng)又是如何提高考生的編程能力的呢？我們先列舉出如圖1.1的步驟。

2、題目類型分析

針對考察考生算法理解和運用階段的不同，題目類型當然不同。由于數(shù)據(jù)結(jié)構(gòu)還需要考慮算法的時間以及空間復(fù)雜度，因而有一些差別。接下來介紹幾類運用于在線判題的題型。

2.1輸出中間過程題

此類題目是考察考生是否了解算法步驟。如直接插入排序的考查就適合使用此類題型。

直接插入排序是將序列分為有序序列和無序序列，將無序序列中的第一個數(shù)插入到前面有序序列中，在有序序列中比剛才選出的數(shù)大的往后移動，直到選出的數(shù)能夠放在合適的位置。如圖2.1。排序的效果就是將某個序列有序化，對于函數(shù)庫中已有的函數(shù)，用直接插入排序較為復(fù)雜，因此無法在算法復(fù)雜度上面考察直接插入排序。所以最好的做法就是通過輸出中間過程來考察考生是否有效掌握了直接插入排序。于是就可以出下面的題目：

題目描述：直接插入排序的做法是將原始序列分為有序序列和無序序列兩組。開始時有序序列中沒有元素，而無序序列包含原始序列中的所有元素。每次從無序序列中將第一個元素取出插入有序序列中，有序序列中比取出的元素大的元素相應(yīng)往后移動，如圖2.1。

任務(wù)：將每行插入后的狀態(tài)輸出來。

輸入：輸入數(shù)據(jù)首先是一個整數(shù)N，代表有N組測試數(shù)據(jù)。每組測試數(shù)據(jù)有兩行，第一行是一個整數(shù)m，代表這組序列有m個元素，第二行是這組序列中的m個元素。

輸出：每組測試數(shù)據(jù)輸出相應(yīng)的m+1行，這m+1行中的第1行輸出Case n：，n是輸出的第幾組序號。第i+1（0

2.2直接運用題

直接運用題考查的是考生直接運用某種算法的能力。這種題目對于考生來說并不困難，但對出題人來說較麻煩，若在線判題的題目使考生可運用其他算法解決，就無法達到出題目的。因此須切中考點，限定考生使用特定算法。例如可以出以下題目：

題目描述：金和歐比旺在納步星（Naboo）受到敵人的攻擊，逃亡途中他們得到了一份秘密文件。奇怪的是文件里只有數(shù)字、空格和加（+）、減（-）、乘（*）、除（/）四種符號。經(jīng)過愛因斯坦的鑒定，得知這些數(shù)字和符號組成的原來是矮人國流傳已久的后綴表達式。只要將這些后綴表達式解出就可避免一場腥風血雨。

輸入：有多組輸入數(shù)據(jù)，每組數(shù)據(jù)一行。每行就是一個后綴表達式。每個運算符都是雙目運算符。數(shù)字之間、運算符之間以及數(shù)字與運算符之間用空格隔開。

輸出：求解出這些后綴表達式，每行后綴表達式的結(jié)果輸出到一行。

3、結(jié)論

由于在線判題就是利用計算機自行判斷考生提交的代碼是否符合題目的要求，減少了老師的工作量，提高了考生的代碼編寫能力，可以解決老師難以解決的問題。無論何時何地，只要有計算機和網(wǎng)絡(luò)，考生就能夠練習數(shù)據(jù)結(jié)構(gòu)，有著非常廣泛的實用性，并且具有可操作性，應(yīng)用前景十分看好。

參考文獻：

[1]徐孝凱，魏榮《數(shù)據(jù)結(jié)構(gòu)》，機械工業(yè)出版社，1996年

[2]徐孝凱《數(shù)據(jù)結(jié)構(gòu)簡明教程》，清華大學出版社，1995年

[3]陳文博，朱青《數(shù)據(jù)結(jié)構(gòu)與算法》，機械工業(yè)出版社，1996年

[4]許卓群，張乃孝，楊冬青，唐世渭《數(shù)據(jù)結(jié)構(gòu)》，高等教育出版社，1988年

[5]李廉治，姜文清，郭福順《數(shù)據(jù)結(jié)構(gòu)》，大連理工大學出版社，1989年

作者簡介：

冷雪琳（1989-）女，遼寧省營口市，現(xiàn)就讀于浙江傳媒學院新媒體學院信息管理與信息系統(tǒng)專業(yè)。