范建中，王秀友

(阜陽師范學院計算機與信息工程學院，安徽阜陽236037)

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

1 數(shù)據(jù)結構實踐教學改革的必要性

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

2 數(shù)據(jù)結構實踐教學改革措施探討

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

2.1 搭建數(shù)據(jù)結構實踐教學平臺

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

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

2.2 以學生為本，合理設計實踐教學內(nèi)容

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

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

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

2.3 學生強弱組合，分組實驗

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

2.4 定期進行數(shù)據(jù)結構實驗測試

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

3 結束語

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