基于ACM—ICPC訓(xùn)練模式的數(shù)據(jù)結(jié)構(gòu)實(shí)踐教學(xué)探索

摘要：針對(duì)目前數(shù)據(jù)結(jié)構(gòu)課程實(shí)踐教學(xué)上的不足，提出基于ACM-ICPC訓(xùn)練模式的數(shù)據(jù)結(jié)構(gòu)課程系統(tǒng)化的實(shí)踐教學(xué)方案。

關(guān)鍵詞：ACM-ICPC；數(shù)據(jù)結(jié)構(gòu)；實(shí)踐教學(xué)

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

數(shù)據(jù)結(jié)構(gòu)是一門實(shí)踐性很強(qiáng)的課程，它不但要求學(xué)生掌握各種常用數(shù)據(jù)結(jié)構(gòu)的定義、特點(diǎn)以及基于這些數(shù)據(jù)結(jié)構(gòu)的基本算法，更重要的是要求學(xué)生不斷提高自身算法設(shè)計(jì)的能力。學(xué)生只有經(jīng)過系統(tǒng)化的訓(xùn)練，才能真正地理解和掌握課程的內(nèi)容，才能在實(shí)際問題求解中靈活地選擇合適的數(shù)據(jù)結(jié)構(gòu)，找到更好的求解方法。目前，國(guó)內(nèi)外針對(duì)該課程的教學(xué)方法和教學(xué)模式的研究，雖然認(rèn)識(shí)到實(shí)踐教學(xué)的重要性，但并未給出系統(tǒng)化的訓(xùn)練方案。筆者在總結(jié)多年教學(xué)經(jīng)驗(yàn)的基礎(chǔ)上，提出了系統(tǒng)化實(shí)踐教學(xué)的方案，并基于ACM-ICPC訓(xùn)練模式，對(duì)該方案進(jìn)行了實(shí)施，收到了很好的效果。

1 ACM-ICPC模式

1.1 ACM-ICPC模式的優(yōu)勢(shì)

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

將ACM-ICPC訓(xùn)練模式引入數(shù)據(jù)結(jié)構(gòu)的教學(xué)中，可以鼓勵(lì)學(xué)生多動(dòng)手、多動(dòng)腦、多實(shí)踐，相對(duì)于傳統(tǒng)的實(shí)踐教學(xué)具有以下幾方面的優(yōu)勢(shì)：

1）實(shí)踐教學(xué)在網(wǎng)絡(luò)上進(jìn)行，不受時(shí)間和空間的限制。

教師可以通過在線評(píng)測(cè)系統(tǒng)布置實(shí)訓(xùn)內(nèi)容，學(xué)生可以根據(jù)自己的情況選擇合適的時(shí)間完成訓(xùn)練題目。學(xué)生完成編程后提交程序代碼就可以立刻得到評(píng)測(cè)結(jié)果，激發(fā)了學(xué)生的學(xué)習(xí)熱情。教師也可以分析學(xué)生提交的程序，以便在課堂上補(bǔ)充講解。

2）有利于創(chuàng)造學(xué)生之間良好的學(xué)術(shù)交流氛圍。

ACM-ICPC訓(xùn)練模式讓學(xué)生在課余時(shí)間自主進(jìn)行算法和程序的交流，通過網(wǎng)上發(fā)帖的方式，實(shí)現(xiàn)學(xué)生與教師、學(xué)生與學(xué)生之間的交流和互動(dòng)，有助于創(chuàng)造良好的學(xué)習(xí)交流氛圍。

3）減輕教師的指導(dǎo)負(fù)擔(dān)。

為讓學(xué)生更好地掌握數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容，教師會(huì)在課程的教學(xué)中，布置大量算法設(shè)計(jì)方面的作業(yè)。傳統(tǒng)的手工批改作業(yè)的任務(wù)非常繁重，學(xué)生的作業(yè)量以及作業(yè)反饋時(shí)間都會(huì)受到限制，在一定程度上打擊了學(xué)生的積極性。而ACM-ICPC訓(xùn)練模式的在線評(píng)測(cè)系統(tǒng)可以對(duì)學(xué)生的作業(yè)進(jìn)行評(píng)測(cè)，從而減輕教師的指導(dǎo)負(fù)擔(dān)。

1.2 在線評(píng)測(cè)技術(shù)

我們將ACM-ICPC在線評(píng)測(cè)技術(shù)引入數(shù)據(jù)結(jié)構(gòu)的教學(xué)中，開發(fā)了數(shù)據(jù)結(jié)構(gòu)實(shí)訓(xùn)系統(tǒng)。該系統(tǒng)可對(duì)學(xué)生提交的程序源代碼進(jìn)行編譯和執(zhí)行，并通過預(yù)先設(shè)計(jì)的測(cè)試數(shù)據(jù)檢驗(yàn)程序的正確性。這大大減輕了教師的工作負(fù)擔(dān)，縮短了作業(yè)的反饋時(shí)間，激發(fā)了學(xué)生實(shí)踐訓(xùn)練的激情。

在線評(píng)測(cè)系統(tǒng)流程如圖1所示。學(xué)生提交程序源碼后，系統(tǒng)首先將源碼保存到數(shù)據(jù)庫(kù)，插入待評(píng)測(cè)隊(duì)列。如果系統(tǒng)評(píng)測(cè)內(nèi)核run.exe正常運(yùn)行，則將源碼傳遞到評(píng)測(cè)內(nèi)核進(jìn)行編譯。如果源碼編譯錯(cuò)誤直接輸出結(jié)果提示用戶程序編譯錯(cuò)誤。源碼在編譯通過之后，若運(yùn)行超時(shí)則直接輸出超時(shí)錯(cuò)誤，否則評(píng)測(cè)程序?qū)⒃摮绦蜻\(yùn)行的結(jié)果與預(yù)置的結(jié)果文件內(nèi)容進(jìn)行比較，如果完全一致，系統(tǒng)將輸出程序正確，反之輸出程序錯(cuò)誤。無論哪一種情況，系統(tǒng)都會(huì)將評(píng)測(cè)結(jié)果保存到數(shù)據(jù)庫(kù)。

2 ACM-ICPC訓(xùn)練模式的數(shù)據(jù)結(jié)構(gòu)實(shí)踐教學(xué)方案的設(shè)計(jì)

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

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

3 ACM-ICPC訓(xùn)練模式的數(shù)據(jù)結(jié)構(gòu)實(shí)踐教學(xué)方案的實(shí)施與效果

數(shù)據(jù)結(jié)構(gòu)系統(tǒng)化實(shí)踐教學(xué)方案的實(shí)施分以下幾個(gè)步驟：

1）數(shù)據(jù)結(jié)構(gòu)實(shí)訓(xùn)系統(tǒng)的研發(fā)。

數(shù)據(jù)結(jié)構(gòu)系統(tǒng)化實(shí)踐教學(xué)方案實(shí)施的第一步是基于ACM-ICPC的在線評(píng)測(cè)技術(shù)，開發(fā)數(shù)據(jù)結(jié)構(gòu)實(shí)訓(xùn)系統(tǒng)。該系統(tǒng)的用戶可分為3種角色：管理員、教師、學(xué)生。管理員的功能包括：學(xué)生批量注冊(cè)、題目維護(hù)等；教師的功能包括：題目瀏覽、程序提交、代碼查看、討論版發(fā)帖等功能；學(xué)生的功能包括：題目瀏覽、程序提交、討論版發(fā)帖等功能。

2）面向數(shù)據(jù)結(jié)構(gòu)的ACM-ICPC訓(xùn)練題目的設(shè)計(jì)。

根據(jù)數(shù)據(jù)結(jié)構(gòu)教學(xué)大綱的要求，我們?cè)O(shè)計(jì)了系統(tǒng)化的數(shù)據(jù)結(jié)構(gòu)訓(xùn)練題目。這些題目均以ACM訓(xùn)練題目的形式添加到數(shù)據(jù)結(jié)構(gòu)實(shí)訓(xùn)系統(tǒng)中。另外，我們也從ACM-ICPC競(jìng)賽題中挑選相關(guān)題目，將實(shí)驗(yàn)教學(xué)中傳統(tǒng)的以算法為主線的體系結(jié)構(gòu)改為以問題為主線的體系結(jié)構(gòu)，使學(xué)生自主選擇合理的數(shù)據(jù)結(jié)構(gòu)和算法進(jìn)行計(jì)算機(jī)解題，加深學(xué)生對(duì)基本概念和基礎(chǔ)知識(shí)的理解，通過學(xué)以致用牢固掌握所學(xué)知識(shí)。數(shù)據(jù)結(jié)構(gòu)實(shí)訓(xùn)系統(tǒng)部分題目如表1所示。

3）以ACM-ICPC訓(xùn)練模式進(jìn)行數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)教學(xué)。

實(shí)驗(yàn)前，程序設(shè)計(jì)評(píng)測(cè)系統(tǒng)中給出實(shí)驗(yàn)題目，并要求學(xué)生在有限的時(shí)間內(nèi)完成實(shí)驗(yàn)題目。學(xué)生設(shè)計(jì)好程序后提交給自動(dòng)判題系統(tǒng)來判斷，系統(tǒng)會(huì)實(shí)時(shí)返回判斷結(jié)果。如評(píng)判沒有通過，學(xué)生可修改程序并再次提交。對(duì)多次提交不成功的學(xué)生，實(shí)驗(yàn)教師可給予及時(shí)輔導(dǎo)。實(shí)驗(yàn)結(jié)束時(shí)，學(xué)生可通過系統(tǒng)清楚地知道自己的排名。這樣的實(shí)驗(yàn)環(huán)境迫使學(xué)生在課前認(rèn)真做好準(zhǔn)備，課后強(qiáng)化與數(shù)據(jù)結(jié)構(gòu)內(nèi)容相關(guān)的試題，而且充分調(diào)動(dòng)學(xué)生的學(xué)習(xí)興趣，從而達(dá)到熟練掌握所學(xué)內(nèi)容解決問題的實(shí)踐教學(xué)目的。

基于ACM-ICPC訓(xùn)練模式的系統(tǒng)化實(shí)踐教學(xué)方案從2010年開始實(shí)施，分別應(yīng)用于浙江師范大學(xué)2010級(jí)和2011級(jí)計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)、軟件工程專業(yè)和網(wǎng)絡(luò)工程專業(yè)的數(shù)據(jù)結(jié)構(gòu)課程的教學(xué)中。方案實(shí)施前后學(xué)生完成數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)題目情況的比較如表2所示。由表2可以看出，該方案的實(shí)施，大大地提高了學(xué)生對(duì)數(shù)據(jù)結(jié)構(gòu)理論的掌握程度，提高了學(xué)生的實(shí)踐能力。浙江師范大學(xué)2011級(jí)部分學(xué)生在數(shù)據(jù)結(jié)構(gòu)實(shí)訓(xùn)系統(tǒng)上完成題目的情況如表3所示。

4 結(jié)語

基于ACM-ICPC訓(xùn)練模式的數(shù)據(jù)結(jié)構(gòu)實(shí)踐教學(xué)將理論學(xué)習(xí)和實(shí)驗(yàn)有機(jī)結(jié)合，注重算法設(shè)計(jì)能力的提高和解題思維能力的訓(xùn)練，同時(shí)引入競(jìng)爭(zhēng)機(jī)制，為學(xué)生提供了因材施教的途徑，激發(fā)了學(xué)生自主研究的興趣。通過兩年的實(shí)施，收到了很好的教學(xué)效果。

參考文獻(xiàn)：

[1]李冬梅，孟偉。數(shù)據(jù)結(jié)構(gòu)課程的教學(xué)改革與教材建設(shè)[J].計(jì)算機(jī)教育，2012（14）：38-41.

[2]徐薇，王志海。數(shù)據(jù)結(jié)構(gòu)課程研究性教學(xué)理論及方法探索[J].計(jì)算機(jī)教育，2012（1）：35-38.

[3]王淮亭.數(shù)據(jù)結(jié)構(gòu)實(shí)踐教學(xué)探討與實(shí)踐[J].計(jì)算機(jī)教育，2009（12）：133.134，145.

[4]陳瑛.從數(shù)據(jù)結(jié)構(gòu)課程特征本質(zhì)談實(shí)踐教學(xué)改革[J].計(jì)算機(jī)教育，2012（6）：33-35，40.

[5]中華，肖瑩瑩.數(shù)據(jù)結(jié)構(gòu)課程的實(shí)踐性教學(xué)模式[J].計(jì)算機(jī)教育，2012f4）：103.105.