淺談如何通過在線判題考查基礎數據結構

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

【關鍵詞】考生，在線判題，數據結構

1、為什么使用在線判題

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

同時，通過在線判題也能夠給考生提供實時的訓練機會。無論何時何地，只要有計算機和網絡，考生就能夠練習數據結構。

在線判題還有一特點就是系統、全面。在線判題匯聚了諸多類型的題目，并系統的將數據結構的各類知識匯聚在一起。

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

2、題目類型分析

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

2.1輸出中間過程題

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

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

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

任務：將每行插入后的狀態輸出來。

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

輸出：每組測試數據輸出相應的m+1行，這m+1行中的第1行輸出Case n：，n是輸出的第幾組序號。第i+1（0

2.2直接運用題

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

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

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

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

3、結論

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

參考文獻：

[1]徐孝凱，魏榮《數據結構》，機械工業出版社，1996年

[2]徐孝凱《數據結構簡明教程》，清華大學出版社，1995年

[3]陳文博，朱青《數據結構與算法》，機械工業出版社，1996年

[4]許卓群，張乃孝，楊冬青，唐世渭《數據結構》，高等教育出版社，1988年

[5]李廉治，姜文清，郭福順《數據結構》，大連理工大學出版社，1989年

作者簡介：

冷雪琳（1989-）女，遼寧省營口市，現就讀于浙江傳媒學院新媒體學院信息管理與信息系統專業。