基于PCOJ的數據結構實驗教學探索

張仕 吳聞 郭躬德 嚴宣輝 嚴曉明

文章編號：1672-5913（2015）03-0030-03

中圖分類號：G642

摘要：針對數據結構課程實踐教學中的若干問題，在自主開發的程序設計競賽在線測試平臺上有針對性地提出平臺改進、試題設計和教學改革的方法，闡述這些方法應用到實際教學工作中對數據結構課程教學的促進作用，最后說明取得的良好效果。

關鍵詞：數據結構；實驗教學；教學改革；程序設計競賽在線測試平臺

0 引 言

ACM國際大學生程序設計競賽（ACM inter-national collegiate programming contest，簡稱ACM-ICPC或ICPC）是由美國計算機協會（ACM）主辦的，一項旨在展示大學生創新能力、團隊精神和在壓力下編寫程序、分析和解決問題能力的年度競賽。福建師范大學從2003年開始組織學生參加ICPC，同時組織開發了程序設計競賽在線測試（ programming contest online judge，PCOJ）平臺，用于程序競賽的訓練工作。

實踐教學是計算機專業教學過程中一個必不可少的環節。數據結構課程便是計算機科學與技術專業中理論和實踐緊密結合的一門核心課程，其主要研究內容是數據的邏輯結構、存儲結構及操作，教學目的在于培養學生的數據抽象能力，為解決實際問題時進行數據的組織和操作奠定基礎。要學好數據結構這門課，不但需要從理論上理解和掌握相關知識，而且需要通過實驗和實踐環節提高實際動手能力和在實際問題中應用數據結構抽象、解決實際問題的能力。

1 研究現狀

雖然多年的教學實驗改革使計算機實踐教學逐步受到重視，在實驗室建設和教學實踐中有了長足的發展，但是學生仍然存在理論學習與程序設計能力嚴重脫節的情況。通過對學生的訪談、日常教學中的觀察，筆者總結出這種理論與實踐脫節的問題主要有以下幾方面。

（1）重理論學習，輕實踐動手。教學過程中教師布置的多是書面作業，學生完成編程后不需要進行嚴格的程序檢查和調試運行，只需理論可行，忽視實踐動手的培養。

（2）程序問題不能及時解決。學生在編程練習遇到問題時沒有通暢的溝通渠道，不能及時得到教師的指導，而教師在課上與學生的溝通有限。

（3）實踐動手要求低。實驗課的練習只有一些代表性案例，學生雖然完成了實驗，但是實踐工作量嚴重不足；另一方面，實驗題目難度不大，這對于學有余力、對自己有更高要求的學生而言缺少了練習的強度。

（4）程序bug多。學生編寫的程序只用少量數據進行簡單的測試，不能全面測試到程序中的所有指令調用，這導致完成的實驗代碼可能存在大量的bug，但學生卻不能及時發現并改正，程序的實用程度大大降低。

（5）考核不合理。當前對數據結構課程的考核大多是對書面作業、理論知識的考核，對實驗環節的考核則主要是通過實驗報告。教師很難了解學生對知識與技能的實際掌握情況，實驗報告也很難客觀真實地反映學生的實驗情況。

（6）現有的把ICPC和教學結合的教學改革，更加側重的是利用ICPC對現行的教學方法、教學體系進行改革，鼓勵學生通過競賽練習提高程序設計水平和解決問題的能力，鮮有把ICPC競賽平臺加以改進再結合到實驗教學中的思路。

2 PCOJ平臺的改進

福建師范大學計算機系組織開發了程序設計競賽在線測試平臺（ PCOJ），用于ICPC競賽的日常訓練工作。競賽訓練平臺給學生提供大量的試題，讓學生能夠通過大量的訓練，熟練利用綜合知識分析并通過編程序解決實際問題。

和競賽目的不同，數據結構實驗教學的目標是要求學生能夠解決特定的問題，更是要培養學生組織程序的能力、按照規定抽象數據類型定義要求實現特定數據結構的能力、按照預定義接口實現函數的能力、規范化程序書寫的習慣。用一句話概括它們的區別：程序競賽要求的是“學生具有特別突出的解決問題能力”，數據結構教學則是為學生“打好寬闊扎實的基礎”。基于此，要把該平臺應用到數據結構課程的教學中，需要根據具體的需求對該系統做以下兩點改進。

（1）程序競賽時所要求提交的是一個單一的文件，該文件包括解決特定問題的完整程序。文件提交到平臺后，測試平臺先編譯該程序，生成可執行文件，平臺會自動讀出數據作為該可執行文件的輸入，允許該可執行文件運行，產生結果和預先設定的結果對比。在數據結構的實驗環節中，，教師需要讓學生掌握程序設計的方法，還要求學生掌握程序組織方法、具體數據結構實現重用思想，這些要求不同于競賽要求。為此，平臺改進的第一個方面是要允許學生利用文件組織具體的應用，單獨的文件反映的是某一個具體內容，要允許學生針對一個試題提交多個文件，所提交的文件可以包括完整可運行的程序，也可以是某個模塊的實現。

（2）學生的組織方式，原有PCOJ平臺沒有對學生按照班級管理的功能，改進后的平臺針對具體課程，教師可以注冊賬號、開設班級，學生也可以申請賬號，加入某一個班級，實現以班級為單位的管理。這大大方便了教師了解學生的實驗完成情況、練習和討論參與情況等，為課程成績的評定提供多維參考。

3 基+PCOJ的實驗教學改革

3.1 分層次的實驗教學體系

對于同一門課程，學生掌握的程度不同，針對不同層次的學生要指定不同難度的練習，因此我們把實驗分為必做和提高兩人類必做實驗重點考核學生對基礎知識的掌握情況；而提高類題目針對學有余力的學生，有的放矢，為他們提供一個更高的目標。

例如二叉樹的遍歷實驗，我們設置的必做實驗是利用遞歸思想完成先序、中主序和后序遍歷提高類實驗則要求在前面章節實現的線性表、棧和隊列基礎上，完成二叉樹先序、中序和后序遍歷操作的非遞歸實現。在排序和查找部分，提高類實驗要求學生能夠利用多線程提高算法的效率。

3.2 分類的試題設計

數據結構課程的教學目的除了要求學生掌握線性、樹、圖等結構組織和操作知識外，還要訓練學生進行復雜程序設計的基本技能，培養良好的程序設計習慣（如面向接口的編程思想），加深對數據結構定義、算法、算法應用的理解，提高實踐能力。基于此，我們把數據結構實驗試題分為三大類：數據結構應用類、數據結構實現類、算法設計實現類，如圖l所示

數據結構應用類試題指已經按ADT定義并實現了某個數據結構，再提出基于該數據結構的應用題目，要求利用該數據結構解決相應的問題并提交平臺測試和判定。例如利用棧實現迷宮問題的求解，對該類試題，實驗平臺發布的試題說明中包括可以使用的具體數據結構的類型定義（.h文件）、所要實現的具體應用說明、測試數據例。學生根據實驗題目要求，在所定義數據結構實現的基礎上，應用該數據結構實現應用要求。學生可以提交多個程序文件，其中一個是包含main（）的程序，其他文件則是在主程序文件中引用到的定義和實現。實驗平臺將利用存在的數據結構和學生提交的文件進行編譯、運行、測試，并根據最后測試結果返回相關信息。

數據結構實現類試題是指已經設定好了數據結構的應用程序，學生應按照要求的ADT實現特定的數據結構，以便應用程序得到支撐，如一個基于線性表的學生管理程序。對于該類試題，實驗平臺發布的試題說明中包括數據結構的抽象數據類型定義（ ADT）、數據結構應用需要的接口、數據結構應用簡單例、測試數據例。其中，具體數據結構的抽象類型定義ADT清楚說明了所需要實現的數據結構各類操作。學生在實驗過程中可以提交多個程序文件，其中對于數據結構應用需要的數據結構定義文件要按照要求進行命名：實驗平臺將利用系統中的數據結構應用程序和提交的相關文件進行編譯，再利用平臺中的數據集對應用進行測試并根據最后測試結果返回相關信息。

算法設計實現類試題是指已經有一個特定的應用，該應用基于某一數據結構，但是在這一數據結構實現中還缺少某一關鍵算法，要求學生根據算法的定義設計和實現該算法，以便應用完整的某一數據結構支撐應用程序的運行，如線性表的插入操作實現。對于該類試題，實驗平臺發布的試題說明中包括數據結構的抽象數據類型定義（ ADT）、數據結構的類型定義、特定算法的函數頭定義和算法需要實現的功能。學生在實驗過程中只需要將該算法的實現提交到系統上測試和判定，這類試題適用于平時的小作業以及以算法設計為側重的數據結構和算法實驗。

3.3 基于論壇的師生交流

在實驗教學體系中，我們還提供論壇作為師生交流的平臺。很多時候，教師不但會回答本班學生的提問，而且會回答其他班級學生的提問。教師通過論壇可以更好地了解學生對知識的掌握情況，發現不足，在課堂上加以彌補。論壇的設置緩解了學生碰到問題不能夠及時交流的問題，增加了師生的交流和了解，促進教師實施更有針對性的課堂教學。

3.4 基于平臺的實驗測試

針對當前學生對實驗程序測試不完全，導致程序中存在大量未被發現的bug的問題，我們利用實驗平臺的自動測試功能發現問題。學生所編寫的程序可以提交到平臺上進行自動編譯、測試和運行，而運行所使用的數據集是針對特定問題特別設計的。由于在設計實驗試題測試數據時可以綜合考慮各方面特別是一些邊界情況、規模問題，自動測試會幫助發現更多潛在bug并給出相應提示。對程序測試的高要求自然會在潛移默化中培養學生程序設計的嚴密性，促使其重視程序設計中的細節問題。

3.5 基于平臺的實驗考核

有了這個實驗平臺，教師布置的實驗不再局限于每次實驗的單個題目，還可以把平常的課堂作業也用實驗試題（主要為算法設計實現類）的方式反映在實驗平臺上，這樣學生完成的作業也就有更加客觀的考核和評價，同時減輕了教師的負擔，讓教師有更多時間與學生就相關實驗進行交流。對學生學習的評價，則可以充分利用學生使用實驗平臺過程中產生的行為記錄，包括從該生平時所做練習、實驗、提高實驗和交流情況等進行綜合考慮，從而提高評價的客觀性。

4 結語

我們通過把PCOJ的軟硬件平臺和數據結構實驗教學相結合并改進，形成一個完整的數據結構實驗教學體系；加強該數據結構實驗平臺的建設和應用使數據結構的實踐教學方法、平臺應用、實驗內容、考核方式等越來越系統化，能夠服務于多層次、多角度的實驗教學活動。數據結構實驗教學改革不但能使學生對數據結構課程理論加深理解，也大大提高了學生的動手能力，形成了理論和實踐相互促進的良好態勢。實驗平臺的使用能夠更好地訓練學生進行復雜程序設計的基本技能，培養良好的程序設計習慣，為后續課程實驗奠定更加堅實的基礎。當然，在未來的教學過程中還不斷會有新的問題和挑戰出現，這些都會促進我們對實踐教學方法、手段繼續完善，使數據結構的實踐教學水平不斷提高。