“數據結構”綜合性課程設計教學探索與實踐

文章編號：1672-5913(2008)08-0054-02

摘要：本文針對“數據結構”課程的傳統教學方法存在的問題，就綜合性課程設計的內容選擇、實施方法與激勵手段等方面進行了一系列的改革探索。

關鍵詞：數據結構；課程設計；啟發式教學

中圖分類號：G642

文獻標識碼：B

1引言

“數據結構”作為實踐性很強的計算機專業的基礎課，教學中必然離不開實踐。針對數據結構的課程設計實踐不僅可以幫助學生鞏固和加深對課程內容的理解，更重要的是可以進一步鍛煉程序設計的技能，并初步感受軟件開發的規范，更能全面培養學生綜合運用知識的能力、文獻檢索與分析能力、工程化能力、進行研究性學習的能力、創新能力以及團隊合作的能力等。本文是作者所在教學團隊八年來的課程設計實踐小結，介紹了在“數據結構”綜合性課程設計的內容選擇、實施方法與激勵手段等方面進行的一系列改革探索。

2傳統教學方法存在的問題及解決思路

數據結構的課程實踐可分為一般性實驗和綜合性課程設計。在傳統的課程教學中，往往采用一般性實驗作為課程實踐的主要內容，即布置針對本次課堂教學內容的小型練習題，讓學生獨立完成程序設計與實現。這樣的實踐主要存在兩方面問題：

第一，練習題所需要用到的知識點就是課堂教學剛講授過的內容，學生只要直接拿來用就可以，不需要自己去考慮各種可能的解決方案并找到最合適的方法。這種實踐是驗證性的，比較簡單直接，學生受到的鍛煉相對較少。

第二，學生獨立完成小型程序，雖然可以在一定程度上鍛煉編程能力，但這個鍛煉的層次和涉及面都比較窄。現代軟件開發的規模，使得團隊合作在大多數情況下成為必須。而且部分數據結構只有在處理大規模輸入的復雜問題時才能體現出優勢，編寫小型程序很難使學生真正認識到該數據結構存在的意義。

針對上述問題，我們在設計較大規模的綜合性課程設計時就必須注意兩個方面：

第一，課程設計題目覆蓋的知識點應盡可能避免單一，要采用啟發式的設計思路，引導學生圍繞課程設計目標，通過查找與分析有關參考資料，進行探究式的學習，激發創造的意識和能力。所以，在題目設計和實施中，不應該只是“手把手”地教，要給學生留出發揮想象力和創造力的空間。

第二，題目的規模應充分大，并且努力使學生對規范性的軟件開發有初步體驗，在一定程度上使得學生的工程化能力和團隊合作能力得到鍛煉。

而上述兩方面的考慮若要取得真正好的效果，還必須有一套行之有效的激勵機制，既可以公平地判定每個學生作為個體的能力，又可以鼓勵團隊精神，同時還可以鼓勵學生開拓創新思維，主動進行研究性學習。

3課程設計的內容選擇、實施方法與激勵手段

3.1內容選擇

綜合性課程設計應強調知識的綜合運用，鍛煉學生對復雜問題進行分析與求解的能力，所以在選擇內容時可以從以下三方面考慮：

第一，題目應避免涉及單一知識點。例如“迷宮問題”，即輸入一個迷宮的布局，要求找到一條走出迷宮的路徑并用圖形界面顯示。學生可以選擇用不同的數據結構表示迷宮以及移動方向，可以選擇用深度優先或者寬度優先搜索的算法來得到路徑，同時還鍛煉了對圖形界面的編程技巧的掌握。又例如“宇宙旅行”，即給定兩星球間各個中轉空間站的臨時客流容量，求終點星球接待站的總客流容量。此題目的解法主要涉及網絡流算法；在每一步修正流量時，可以選擇剩余圖中從起點到終點的最短路徑，則又涉及到單源最短路徑算法；最后為了提高查找空間站名稱的效率，可以采用散列表進行名稱映射。

第二，為鍛煉學生進行研究性學習的能力，可設計算法效率分析比較類型的題目。例如比較普通的二叉搜索樹、平衡搜索樹和伸展樹的插入與刪除操作效率，要求通過實驗取得三者的實際運行時間，繪出三者復雜度函數的曲線，分析比較它們的效率并給出證明等等。

第三，采用啟發式教學思路，設計有多種解法的題目，可以給學生留出發揮想享力和創造力的空間，鍛煉學生靈活運用知識分析問題和解決問題的能力。例如“熊貓燒香”，即以著名病毒“熊貓燒香”的傳播規律為背景，要求計算整個網絡被各種病毒變種感染的情況。題目可以簡單地用廣度優先搜索解決，但是效率比較低。巧妙一點的方法可以將求單源最短路徑的Dijkstra算法略做修改，得到效率明顯提高的解決方案。更快的算法則是利用并查集。教師可以通過設計不同層次的測試數據來區分不同效率的算法，鼓勵學生自己去嘗試各種方案，找出最有效的解決辦法。

在內容選擇方面，我們還建議參考歷屆ACM國際大學生程序設計競賽的題目，該競賽特別強調考察參賽選手對各種算法的應用能力，題目的綜合性較強，非常適合輔助學生學習體會數據結構的妙用。浙江大學建設有全球著名的程序設計競賽練習網站(http://acm.zju.edu.cn/)，提供在線自動裁判系統，簡稱ZOJ，目前擁有各類競賽練習題目近2000道，為數據結構課程設計提供了豐富的題庫資源。本課程組設計的多道課程設計題目就取自或改編自該網站的練習題。

3.2實施方法

綜合性課程設計不僅僅是以實現相應的程序為目標，更重要的是培養學生今后從事軟件開發所需要的各種能力與素質，包括測試能力和文檔寫作的能力。因此，在課程設計實施中，我們將學生分成三人小組，分工負責程序編寫、測試以及實驗報告撰寫工作。

一份完整的實驗報告至少應包含以下四部分內容：

(一)實驗內容簡介：這一部分需簡單介紹題目內容，即該實驗到底要做什么。如果涉及明確的算法，最好再簡單介紹一下算法產生的背景。

(二)算法說明：這一部分需詳細描述解決問題所需要用到的算法和重要的數據結構，即該實驗到底應該怎么做。

(三)測試結果：這一部分需根據題目類型設計提供相應的測試方法和結果。對于需要比較不同算法性能優劣的題目，應設計并填寫一張性能比較表格，列出不同算法在同一指標下的性能表現。對于需要利用某算法解決某問題的題目，應設計并填寫一張測試用例表。每個測試用例應包括測試輸入、測試目的、正確輸出、實際輸出、錯誤原因等等。

(四)分析與探討：這一部分除了對測試結果進行分析外，還要求學生不局限于題目要求使用的算法，探討更多解決問題的途徑，或者提出自己的見解，給出改進算法以得到更好結果的建議。

其中第一、二部分以及全文統稿由文檔員負責，第三、四部分由測試員負責。整個學期發布的課程設計題目數應該是3的倍數，使得每組的三個學生有機會均衡體驗三種不同的角色。

3.3激勵手段

大學教育心理學研究表明，學習興趣通過適當的引導，會引發學生的需要和動機，進一步產生持續不斷的興奮，從而激發積極的行為反應，努力去實現預訂目標。而讓學生產生濃厚的學習興趣，就必須建立有效的激勵機制。

首先程序員、測試員、文檔員的工作難度不同，其工作的分數分配也應不同。例如我們采用50:30:20的分配制度，這樣只有在三個課程設計中將三種角色分別體驗一遍，才有可能得到滿分100。

其次教師應對“分析與探討”部分特別關注，及時發現并鼓勵學生的創新思維。一句簡單的鼓勵就可能對學生的主動學習熱情起到非常大的引導和推動作用。

另外，由于每個學生的能力水平不同，應使組內每個人的成績相對獨立，不依賴于其他組員的表現而得分。例如程序員只要正確完成了自己的程序，且注釋充分，就可以得滿分；測試員的測試計劃和測試用例設計都不依賴于源代碼，即使程序員無法提供程序，測試員只要完成了測試計劃的設計，對算法進行了理論上的分析，就可以得到滿分；文檔員的工作相對獨立，只要完成了自己負責的章節并將手頭所有資料整合為一體，就可以獲得滿分。這樣做的目的是體現評分的公平性，盡量避免能力強的學生為了自己的成績不受影響而“包辦”全組的工作。

當然，分組實驗的另一個目的，是鍛煉學生的溝通與團隊合作能力。這個目的可以通過教師的激勵來達到，即教師在點評每道題目的完成情況時，對個別優秀的組提出表揚，而只有三項工作都完美的組，才會獲此殊榮。這時學生會在完成了自己工作的情況下，對隊友提供一定幫助，以獲得團隊的榮譽。

4成果

課程組在浙江大學八年的不斷探索和改革取得了良好的成效。最為明顯的效果是，學生參與各級程序設計競賽的積極性逐年增長，從2001年48隊100多學生參加首屆浙江大學程序設計競賽，到2007年286隊近千名學生參賽，競賽規模在7年中增長迅猛。而浙江大學參加ACM國際大學生程序設計競賽的隊伍，在沒有常規輔導的情況下，憑借扎實的數據結構基本功，也連年在國際競賽中取得出色的成績。

參考文獻

[1] 教育部高等學校計算機科學與技術教學指導委員會. 高等學校計算機科學與技術專業發展戰略研究報告暨專業規范(試行)[M]. 北京:高等教育出版社，2006.

[2] 何欽銘，馮雁，陳越. 數據結構課程設計[M]. 杭州:浙江大學出版社，2007.

[3] 林正范. 大學心理學[M]. 杭州:浙江大學出版社，2000.