基于ACM競(jìng)賽模式的數(shù)據(jù)結(jié)構(gòu)實(shí)踐教學(xué)探討

范建中，王秀友

(阜陽(yáng)師范學(xué)院計(jì)算機(jī)與信息工程學(xué)院，安徽阜陽(yáng)236037)

數(shù)據(jù)結(jié)構(gòu)課程是計(jì)算機(jī)及相關(guān)專業(yè)的一門綜合性專業(yè)基礎(chǔ)課[1]，該課程的教學(xué)由理論教學(xué)和實(shí)踐教學(xué)兩部分構(gòu)成。實(shí)踐教學(xué)主要為驗(yàn)證理論教學(xué)中所學(xué)的算法為主，在理論教學(xué)時(shí)，大部分學(xué)生能理解課程中的一些基本概念和一些基本的算法設(shè)計(jì)，但實(shí)踐教學(xué)時(shí)，相當(dāng)一部分學(xué)生不能正確實(shí)現(xiàn)課程中的算法，更不要說(shuō)將課程中所學(xué)的數(shù)據(jù)結(jié)構(gòu)及相關(guān)算法用于分析解決實(shí)際問(wèn)題了。通過(guò)多年的教學(xué)及與學(xué)生的溝通、同行的交流，發(fā)現(xiàn)傳統(tǒng)數(shù)據(jù)結(jié)構(gòu)實(shí)踐教學(xué)中存在不少問(wèn)題。首先，數(shù)據(jù)結(jié)構(gòu)課程實(shí)踐教學(xué)課時(shí)較少，但實(shí)踐內(nèi)容較多；其次，程序設(shè)計(jì)基礎(chǔ)薄弱，計(jì)算思維能力不足；最后，實(shí)踐教學(xué)模式落后，達(dá)不到預(yù)期的教學(xué)效果。

1 數(shù)據(jù)結(jié)構(gòu)實(shí)踐教學(xué)改革的必要性

ACM競(jìng)賽的目的在于培養(yǎng)大學(xué)生的創(chuàng)新思維和團(tuán)隊(duì)協(xié)作精神，在強(qiáng)壓力下利用程序設(shè)計(jì)現(xiàn)場(chǎng)作答來(lái)展示自己分析問(wèn)題和解決問(wèn)題的能力。目前國(guó)內(nèi)許多知名的IT企業(yè)采用在線評(píng)測(cè)（機(jī)試）的方式來(lái)招聘職員，或者通過(guò)各種在線比賽和比賽平臺(tái)搜尋各類程序設(shè)計(jì)人才，如百度公司主辦的Astar百度之星程序設(shè)計(jì)大賽、美團(tuán)點(diǎn)評(píng)主辦的CodeM編程競(jìng)賽等等。計(jì)算機(jī)類專業(yè)研究生入學(xué)考試初試時(shí)數(shù)據(jù)結(jié)構(gòu)部分一般側(cè)重算法分析和設(shè)計(jì)能力，在面試時(shí)大都采用在線評(píng)測(cè)的方式來(lái)測(cè)試學(xué)生的編程水平。各類與程序設(shè)計(jì)相關(guān)的學(xué)科競(jìng)賽的考查內(nèi)容，也與數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容密切相關(guān)。因此在數(shù)據(jù)結(jié)構(gòu)實(shí)踐教學(xué)中引入ACM競(jìng)賽模式非常必要，它將有助于學(xué)生鞏固所學(xué)的理論知識(shí)并加以應(yīng)用，從而提高算法設(shè)計(jì)能力、就業(yè)競(jìng)爭(zhēng)力，也有助于學(xué)生熟悉程序設(shè)計(jì)類競(jìng)賽模式，掌握競(jìng)賽中程序的設(shè)計(jì)策略，在競(jìng)賽中獲得佳績(jī)。

2 數(shù)據(jù)結(jié)構(gòu)實(shí)踐教學(xué)改革措施探討

為解決傳統(tǒng)數(shù)據(jù)結(jié)構(gòu)實(shí)踐教學(xué)模式中存在的主要問(wèn)題，我們?cè)趯?shí)踐教學(xué)中引入ACM競(jìng)賽模式。ACM競(jìng)賽通常有兩種判題模式，第一種模式是采用基于C/S架構(gòu)的PC^2軟件來(lái)判題，常用于ACM競(jìng)賽正式比賽，試題需單獨(dú)發(fā)放，不方便進(jìn)行實(shí)踐教學(xué)；第二種模式采用的是基于B/S架構(gòu)的在線評(píng)測(cè)模式，多用于ACM競(jìng)賽練習(xí)或網(wǎng)絡(luò)賽，該模式非常適合數(shù)據(jù)結(jié)構(gòu)課程的實(shí)踐教學(xué)。隨著學(xué)科競(jìng)賽的蓬勃發(fā)展，各大高校、教育機(jī)構(gòu)都建立了許多開放的在線評(píng)測(cè)系統(tǒng)來(lái)訓(xùn)練自己的ACM選手，像浙江大學(xué)的“ZOJ”、杭州電子科技大學(xué)的“HDUOJ”等，這些系統(tǒng)里有非常豐富的題庫(kù)，能很好地鍛煉學(xué)生的程序設(shè)計(jì)能力，但不適合直接用于數(shù)據(jù)結(jié)構(gòu)的實(shí)踐教學(xué)。因?yàn)橄到y(tǒng)題庫(kù)是為培訓(xùn)ACM選手而設(shè)，對(duì)于大部分學(xué)生而言難度太大，容易挫傷學(xué)生的學(xué)習(xí)積極性和信心。要改善實(shí)踐教學(xué)效果，提高學(xué)生的分析、解決問(wèn)題及算法設(shè)計(jì)能力，就需要搭建自己的課程實(shí)踐教學(xué)平臺(tái)，設(shè)計(jì)合適的實(shí)踐教學(xué)內(nèi)容。

2.1 搭建數(shù)據(jù)結(jié)構(gòu)實(shí)踐教學(xué)平臺(tái)

采用開源的OJ(Online Judge)系統(tǒng)搭建平臺(tái)，由華中科技大學(xué)前ACM隊(duì)員Sempr等同學(xué)開發(fā)的HUSTOJ，它是一個(gè)出色的免費(fèi)開源系統(tǒng)，目前由zhblue維護(hù)，還在不斷更新。通過(guò)對(duì)HUSTOJ進(jìn)行配置和少量的開發(fā)就可以達(dá)到滿足數(shù)據(jù)結(jié)構(gòu)實(shí)踐教學(xué)和舉行校內(nèi)程序設(shè)計(jì)競(jìng)賽的要求。

基于HUSTOJ構(gòu)建的數(shù)據(jù)結(jié)構(gòu)實(shí)踐教學(xué)平臺(tái)，教師可以創(chuàng)建題庫(kù)、安排數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)、進(jìn)行數(shù)據(jù)結(jié)構(gòu)考試、程序設(shè)計(jì)競(jìng)賽、代碼抄襲檢測(cè)、成績(jī)統(tǒng)計(jì)、在線答疑等。學(xué)生通過(guò)瀏覽器查看要做的實(shí)驗(yàn)題目及課后作業(yè)，在規(guī)定的時(shí)間內(nèi)完成實(shí)驗(yàn)及課后作業(yè)。學(xué)生提交后的程序代碼由系統(tǒng)進(jìn)行在線評(píng)判，系統(tǒng)及時(shí)返回評(píng)判結(jié)果，如果返回AC狀態(tài)，則表明實(shí)驗(yàn)或作業(yè)被系統(tǒng)認(rèn)可，返回其他狀態(tài)，則意味著要重新修改代碼再次提交。如果代碼相似，系統(tǒng)也會(huì)標(biāo)記和哪個(gè)學(xué)生是相似的。學(xué)生如有疑問(wèn)可以發(fā)貼在討論版討論，也可以發(fā)即時(shí)消息給老師請(qǐng)求幫助。通過(guò)排行榜學(xué)生可看到自己的排名，教師可以看到整個(gè)實(shí)驗(yàn)情況，對(duì)于編程能力較差的同學(xué)，老師可以即時(shí)查看他的代碼，并進(jìn)行相應(yīng)的指導(dǎo)。

2.2 以學(xué)生為本，合理設(shè)計(jì)實(shí)踐教學(xué)內(nèi)容

數(shù)據(jù)結(jié)構(gòu)課程的教學(xué)目的是要求學(xué)生學(xué)會(huì)從問(wèn)題出發(fā)，分析其內(nèi)在的數(shù)據(jù)特性，根據(jù)問(wèn)題需求設(shè)計(jì)數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及相應(yīng)的操作算法，并初步掌握時(shí)間和空間分析技術(shù)。通過(guò)復(fù)雜程序設(shè)計(jì)的訓(xùn)練，使學(xué)生養(yǎng)成良好的代碼編寫習(xí)慣，具有分析問(wèn)題，解決問(wèn)題的能力。數(shù)據(jù)結(jié)構(gòu)實(shí)踐教學(xué)平臺(tái)是通過(guò)在線評(píng)判問(wèn)題正確與否的，傳統(tǒng)的實(shí)驗(yàn)內(nèi)容不合適直接放在實(shí)驗(yàn)平臺(tái)上，需要根據(jù)學(xué)生的基本情況，分類、分層次合理設(shè)計(jì)實(shí)驗(yàn)內(nèi)容[2-3]。

根據(jù)數(shù)據(jù)結(jié)構(gòu)實(shí)踐教學(xué)要求及學(xué)生程序設(shè)計(jì)能力不同，實(shí)驗(yàn)內(nèi)容分為必做和選做兩大類，必做類的實(shí)驗(yàn)內(nèi)容主要考查學(xué)生對(duì)數(shù)據(jù)結(jié)構(gòu)課程基本內(nèi)容的掌握情況，選做類的內(nèi)容主要針對(duì)學(xué)有余力的同學(xué)，一般為綜合應(yīng)用型或程序競(jìng)賽有關(guān)的一些問(wèn)題。例如線性表的必做實(shí)驗(yàn)是順序表和單鏈表的基本操作的實(shí)現(xiàn)，選做類的實(shí)驗(yàn)則為利用順序表進(jìn)行高精度的計(jì)算和利用單鏈表實(shí)現(xiàn)一元多項(xiàng)式的除法等。

必做類實(shí)驗(yàn)中數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)題目分兩個(gè)層次：基礎(chǔ)型、算法設(shè)計(jì)型?；A(chǔ)型的實(shí)驗(yàn)設(shè)計(jì)成填空的形式，例如在順序表的實(shí)驗(yàn)中，實(shí)驗(yàn)內(nèi)容為驗(yàn)證順序表的基本操作，可在實(shí)驗(yàn)平臺(tái)上提供問(wèn)題的相應(yīng)要求，測(cè)試用例樣例，給定主程序框架（完整的main()程序），在里面有相應(yīng)的順序表的基本操作調(diào)用，學(xué)生要做的是根據(jù)題目要求，自己定義順序表的數(shù)據(jù)結(jié)構(gòu)，及相應(yīng)的基本操作的實(shí)現(xiàn)。學(xué)生只須提交順序表數(shù)據(jù)結(jié)構(gòu)的定義及基本操作實(shí)現(xiàn)的程序代碼，不用提交包含main()的程序。實(shí)驗(yàn)平臺(tái)利用已經(jīng)設(shè)置好的后臺(tái)測(cè)試用例來(lái)測(cè)試提交的代碼，并返回相應(yīng)的信息。這個(gè)層次的實(shí)驗(yàn)適用于全體學(xué)生，可用于檢測(cè)學(xué)生對(duì)數(shù)據(jù)結(jié)構(gòu)理論知識(shí)的掌握情況。算法設(shè)計(jì)型實(shí)驗(yàn)是要求學(xué)生利用所學(xué)的數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)一個(gè)算法來(lái)解決一些簡(jiǎn)單的實(shí)際問(wèn)題，例如在線性表的實(shí)驗(yàn)中，可設(shè)置一個(gè)集合的交、并實(shí)現(xiàn)的問(wèn)題。這類問(wèn)題要求學(xué)生做到會(huì)對(duì)問(wèn)題進(jìn)行簡(jiǎn)單的分析，找出數(shù)據(jù)的特性及邏輯關(guān)系，并定義出相應(yīng)的數(shù)據(jù)結(jié)構(gòu)及相關(guān)的操作實(shí)現(xiàn)。學(xué)生在實(shí)驗(yàn)過(guò)程中只需定義所需的數(shù)據(jù)結(jié)構(gòu)，及相關(guān)操作的實(shí)現(xiàn)提交到系統(tǒng)上測(cè)試和判定。這個(gè)層次的試題可用于區(qū)分不同水平層次的學(xué)生，拉開實(shí)驗(yàn)成績(jī)的檔次，方便于挑選算法設(shè)計(jì)能力較好的同學(xué)進(jìn)行培訓(xùn)以參加程序設(shè)計(jì)競(jìng)賽。

2.3 學(xué)生強(qiáng)弱組合，分組實(shí)驗(yàn)

ACM程序設(shè)計(jì)大賽由3名隊(duì)員組成一隊(duì)，使用同一臺(tái)計(jì)算機(jī)協(xié)作共同解決競(jìng)賽的問(wèn)題，有助于培養(yǎng)學(xué)生的創(chuàng)造力和團(tuán)隊(duì)合作精神。在數(shù)據(jù)結(jié)構(gòu)實(shí)踐教學(xué)中，仿照程序設(shè)計(jì)競(jìng)賽的模式，兩人一組進(jìn)行實(shí)驗(yàn)，組隊(duì)時(shí)，先對(duì)班級(jí)學(xué)生進(jìn)行摸底測(cè)試，然后根據(jù)成績(jī)并結(jié)合自愿的原則進(jìn)行強(qiáng)弱搭配，為了讓不同層次的學(xué)生都有問(wèn)題可做，并且都有興趣去做，將每章的實(shí)驗(yàn)按難易程度編排3至5個(gè)題目，在這3至5個(gè)實(shí)驗(yàn)題目中至少有一個(gè)以上是基本的，基礎(chǔ)弱的同學(xué)是能完成的，基礎(chǔ)好的同學(xué)一般能解決所有問(wèn)題，但在兩節(jié)課的時(shí)間不一定能做完所有的題，這樣就要求組內(nèi)同學(xué)相互配合，才能完成所有問(wèn)題。通過(guò)分組，每個(gè)班級(jí)分成多個(gè)小組，組內(nèi)的同學(xué)是相互合作關(guān)系，組與組之間是競(jìng)賽關(guān)系，這樣可以促進(jìn)組內(nèi)同學(xué)團(tuán)隊(duì)合作、組與組之間相互競(jìng)爭(zhēng)，容易激發(fā)學(xué)生的學(xué)習(xí)興趣[4-5]。

2.4 定期進(jìn)行數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)測(cè)試

分組實(shí)驗(yàn)雖能促進(jìn)小組的同學(xué)相互合作、相互學(xué)習(xí)，但也可能存在一些問(wèn)題，實(shí)驗(yàn)只是其中一個(gè)同學(xué)完成，這樣的分組實(shí)驗(yàn)就失去了本義，定期進(jìn)行數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)測(cè)試就非常有必要。定期的數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)測(cè)試分兩種形式，一種是類似于平常實(shí)驗(yàn)方式，對(duì)平時(shí)的實(shí)驗(yàn)題進(jìn)行稍作變化，要求學(xué)生在規(guī)定的時(shí)間內(nèi)完成，用于檢查平時(shí)分組實(shí)驗(yàn)時(shí)學(xué)生是否認(rèn)真參與實(shí)驗(yàn)，以保證平時(shí)實(shí)驗(yàn)成績(jī)的客觀公正；另一種類似于期末考試，只不過(guò)采用機(jī)考形式來(lái)完成，考試的題型有選擇題、判斷題、填空題，這個(gè)過(guò)程在前述實(shí)踐教學(xué)平臺(tái)上無(wú)法實(shí)現(xiàn)，需借助浙江大學(xué)陳越老師的pintia（拼題A）系統(tǒng)來(lái)完成，該系統(tǒng)的基本功能是免費(fèi)給教師使用，即教師可免費(fèi)利用該系統(tǒng)組織考試。每次實(shí)驗(yàn)課，通過(guò)10分鐘的課間機(jī)考，能鞏固學(xué)生的理論基礎(chǔ)知識(shí)，方便教師了解學(xué)生的理論知識(shí)掌握情況，并根據(jù)學(xué)生的學(xué)習(xí)情況及時(shí)改進(jìn)教學(xué)方式，也方便教師統(tǒng)計(jì)平時(shí)考核成績(jī)。采用定期的數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)測(cè)試模式，學(xué)生須注重平時(shí)的實(shí)踐訓(xùn)練、及時(shí)復(fù)習(xí)理論知識(shí)，才能順利通過(guò)考核，從而有助于培養(yǎng)學(xué)生的自律自覺(jué)性，及程序設(shè)計(jì)實(shí)踐能力，避免實(shí)驗(yàn)考核結(jié)果不客觀，也就保證了實(shí)驗(yàn)考核不但有效有用，而且公平公正。

3 結(jié)束語(yǔ)

將ACM競(jìng)賽模式引入到數(shù)據(jù)結(jié)構(gòu)實(shí)踐教學(xué)中，借助數(shù)據(jù)結(jié)構(gòu)實(shí)踐教學(xué)平臺(tái)的全天候開放，學(xué)生可以隨時(shí)隨地進(jìn)行練習(xí)，提交程序代碼，有效地解決了實(shí)踐課的時(shí)間少、任務(wù)重的問(wèn)題。利用數(shù)據(jù)結(jié)構(gòu)實(shí)踐教學(xué)平臺(tái)進(jìn)行分組形式參與實(shí)驗(yàn)，可以形成組與組之間的競(jìng)爭(zhēng)和組內(nèi)交流的良好學(xué)習(xí)氛圍，充分使學(xué)生體會(huì)到團(tuán)隊(duì)合作的重要性。通過(guò)在數(shù)據(jù)結(jié)構(gòu)實(shí)踐教學(xué)平臺(tái)上的實(shí)踐訓(xùn)練，可使學(xué)生的分析實(shí)際問(wèn)題、解決實(shí)際問(wèn)題能力得以提高，利用系統(tǒng)進(jìn)行實(shí)踐考核，對(duì)學(xué)生的成績(jī)?cè)u(píng)定也更加公平公正。