基于ACM—ICPC訓練模式的數據結構實踐教學探索

摘要：針對目前數據結構課程實踐教學上的不足，提出基于ACM-ICPC訓練模式的數據結構課程系統化的實踐教學方案。

關鍵詞：ACM-ICPC；數據結構；實踐教學

數據結構是計算機專業的一門重要的專業基礎課。該課程要求學生掌握程序設計所用到的各種數據結構的邏輯結構、存儲結構及算法。數據結構是編譯程序、操作系統、數據庫系統以及其他系統軟件和應用軟件的基礎。鑒于該課程在計算機專業課程中的重要地位，很多高校對該課程的教學模式和方法展開了深入的研究。文獻[1]結合教學實踐，提出在教學內容、教學方法、教學手段、教材建設等方面進行全方位改革的思路；文獻[2]對研究性教學理論與方法進行研究，提出數據結構教學中的協同教學和多元教學等方法；文獻[3]分析了目前在課程教學中存在的不足之處，為加強數據結構實踐教學，給出實踐教學的9個案例；文獻[4]研究了數據結構課程實踐教學的特征，并給出一些實踐教學改革的具體實施方法；文獻[5]提出一種實踐性教學模式，并給出課堂理論教學、實驗設計及實施、課程課外實踐活動、形成性考核等教學實踐中的4個環節的實施方法。

數據結構是一門實踐性很強的課程，它不但要求學生掌握各種常用數據結構的定義、特點以及基于這些數據結構的基本算法，更重要的是要求學生不斷提高自身算法設計的能力。學生只有經過系統化的訓練，才能真正地理解和掌握課程的內容，才能在實際問題求解中靈活地選擇合適的數據結構，找到更好的求解方法。目前，國內外針對該課程的教學方法和教學模式的研究，雖然認識到實踐教學的重要性，但并未給出系統化的訓練方案。筆者在總結多年教學經驗的基礎上，提出了系統化實踐教學的方案，并基于ACM-ICPC訓練模式，對該方案進行了實施，收到了很好的效果。

1 ACM-ICPC模式

1.1 ACM-ICPC模式的優勢

ACM國際大學生程序設計競賽（簡稱ACM-ICPC）是由國際計算機界歷史最悠久、最具權威性的計算機組織ACM學會（Association for Computer Machinery）主辦，是世界上公認的規模最大、水平最高、最為公平的國際大學生程序設計競賽，其目的在于讓大學生運用計算機來充分展示自己在壓力情況下，分析問題、解決問題的能力。該項競賽從1970年開始舉辦，薈萃了世界各大洲的精英，受到國際知名公司的關注。

將ACM-ICPC訓練模式引入數據結構的教學中，可以鼓勵學生多動手、多動腦、多實踐，相對于傳統的實踐教學具有以下幾方面的優勢：

1）實踐教學在網絡上進行，不受時間和空間的限制。

教師可以通過在線評測系統布置實訓內容，學生可以根據自己的情況選擇合適的時間完成訓練題目。學生完成編程后提交程序代碼就可以立刻得到評測結果，激發了學生的學習熱情。教師也可以分析學生提交的程序，以便在課堂上補充講解。

2）有利于創造學生之間良好的學術交流氛圍。

ACM-ICPC訓練模式讓學生在課余時間自主進行算法和程序的交流，通過網上發帖的方式，實現學生與教師、學生與學生之間的交流和互動，有助于創造良好的學習交流氛圍。

3）減輕教師的指導負擔。

為讓學生更好地掌握數據結構課程的內容，教師會在課程的教學中，布置大量算法設計方面的作業。傳統的手工批改作業的任務非常繁重，學生的作業量以及作業反饋時間都會受到限制，在一定程度上打擊了學生的積極性。而ACM-ICPC訓練模式的在線評測系統可以對學生的作業進行評測，從而減輕教師的指導負擔。

1.2 在線評測技術

我們將ACM-ICPC在線評測技術引入數據結構的教學中，開發了數據結構實訓系統。該系統可對學生提交的程序源代碼進行編譯和執行，并通過預先設計的測試數據檢驗程序的正確性。這大大減輕了教師的工作負擔，縮短了作業的反饋時間，激發了學生實踐訓練的激情。

在線評測系統流程如圖1所示。學生提交程序源碼后，系統首先將源碼保存到數據庫，插入待評測隊列。如果系統評測內核run.exe正常運行，則將源碼傳遞到評測內核進行編譯。如果源碼編譯錯誤直接輸出結果提示用戶程序編譯錯誤。源碼在編譯通過之后，若運行超時則直接輸出超時錯誤，否則評測程序將該程序運行的結果與預置的結果文件內容進行比較，如果完全一致，系統將輸出程序正確，反之輸出程序錯誤。無論哪一種情況，系統都會將評測結果保存到數據庫。

2 ACM-ICPC訓練模式的數據結構實踐教學方案的設計

數據結構實踐教學以培養學生算法設計能力為目的，要求學生學會選擇合理的數據結構，設計出相應問題的求解算法，學會如何把理論知識用于解決實際問題，提高自身分析問題、解決問題的能力，從而具備計算機軟件工作所需要的基本能力。但傳統的數據結構實驗大體上只有3-5個實驗，學生僅受到部分知識的訓練，在課后也很少有渠道獲得練習的機會。

針對以上問題，我們設計了系統化的數據結構實踐教學方案和數據結構實訓系統。系統化的實踐訓練內容包括線性表、棧及隊列、串、數組與廣義表、樹與二叉樹、圖、順序折半查找、內部排序等。數據結構實驗教學實訓內容如圖2所示，其中包含20個基礎性實驗題目。除了基礎性實驗外，方案增加了一些提高性訓練題目和高級數據結構題目，比如并查集、線段樹、樹狀數組、自動機等，供能力較強的學生學習訓練。實驗訓練題目均是設計型，教師可根據學生的實際情況，組織實驗課的教學內容。為了更好地實施實驗教學，我們把這些題目均放在數據結構實訓系統上，學生可隨時提交程序，系統也會及時反饋所提交的算法是否正確。該系統的使用提高了學生的學習興趣，減輕了教師的負擔，而且方便教師了解學生的實踐課題完成情況。

3 ACM-ICPC訓練模式的數據結構實踐教學方案的實施與效果

數據結構系統化實踐教學方案的實施分以下幾個步驟：

1）數據結構實訓系統的研發。

數據結構系統化實踐教學方案實施的第一步是基于ACM-ICPC的在線評測技術，開發數據結構實訓系統。該系統的用戶可分為3種角色：管理員、教師、學生。管理員的功能包括：學生批量注冊、題目維護等；教師的功能包括：題目瀏覽、程序提交、代碼查看、討論版發帖等功能；學生的功能包括：題目瀏覽、程序提交、討論版發帖等功能。

2）面向數據結構的ACM-ICPC訓練題目的設計。

根據數據結構教學大綱的要求，我們設計了系統化的數據結構訓練題目。這些題目均以ACM訓練題目的形式添加到數據結構實訓系統中。另外，我們也從ACM-ICPC競賽題中挑選相關題目，將實驗教學中傳統的以算法為主線的體系結構改為以問題為主線的體系結構，使學生自主選擇合理的數據結構和算法進行計算機解題，加深學生對基本概念和基礎知識的理解，通過學以致用牢固掌握所學知識。數據結構實訓系統部分題目如表1所示。

3）以ACM-ICPC訓練模式進行數據結構實驗教學。

實驗前，程序設計評測系統中給出實驗題目，并要求學生在有限的時間內完成實驗題目。學生設計好程序后提交給自動判題系統來判斷，系統會實時返回判斷結果。如評判沒有通過，學生可修改程序并再次提交。對多次提交不成功的學生，實驗教師可給予及時輔導。實驗結束時，學生可通過系統清楚地知道自己的排名。這樣的實驗環境迫使學生在課前認真做好準備，課后強化與數據結構內容相關的試題，而且充分調動學生的學習興趣，從而達到熟練掌握所學內容解決問題的實踐教學目的。

基于ACM-ICPC訓練模式的系統化實踐教學方案從2010年開始實施，分別應用于浙江師范大學2010級和2011級計算機科學與技術專業、軟件工程專業和網絡工程專業的數據結構課程的教學中。方案實施前后學生完成數據結構實驗題目情況的比較如表2所示。由表2可以看出，該方案的實施，大大地提高了學生對數據結構理論的掌握程度，提高了學生的實踐能力。浙江師范大學2011級部分學生在數據結構實訓系統上完成題目的情況如表3所示。

4 結語

基于ACM-ICPC訓練模式的數據結構實踐教學將理論學習和實驗有機結合，注重算法設計能力的提高和解題思維能力的訓練，同時引入競爭機制，為學生提供了因材施教的途徑，激發了學生自主研究的興趣。通過兩年的實施，收到了很好的教學效果。

參考文獻：

[1]李冬梅，孟偉。數據結構課程的教學改革與教材建設[J].計算機教育，2012（14）：38-41.

[2]徐薇，王志海。數據結構課程研究性教學理論及方法探索[J].計算機教育，2012（1）：35-38.

[3]王淮亭.數據結構實踐教學探討與實踐[J].計算機教育，2009（12）：133.134，145.

[4]陳瑛.從數據結構課程特征本質談實踐教學改革[J].計算機教育，2012（6）：33-35，40.

[5]中華，肖瑩瑩.數據結構課程的實踐性教學模式[J].計算機教育，2012f4）：103.105.