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

摘要：本文針對“數(shù)據(jù)結(jié)構(gòu)”課程的傳統(tǒng)教學(xué)方法存在的問題，就綜合性課程設(shè)計(jì)的內(nèi)容選擇、實(shí)施方法與激勵(lì)手段等方面進(jìn)行了一系列的改革探索。

關(guān)鍵詞：數(shù)據(jù)結(jié)構(gòu)；課程設(shè)計(jì)；啟發(fā)式教學(xué)

中圖分類號：G642

文獻(xiàn)標(biāo)識(shí)碼：B

1引言

“數(shù)據(jù)結(jié)構(gòu)”作為實(shí)踐性很強(qiáng)的計(jì)算機(jī)專業(yè)的基礎(chǔ)課，教學(xué)中必然離不開實(shí)踐。針對數(shù)據(jù)結(jié)構(gòu)的課程設(shè)計(jì)實(shí)踐不僅可以幫助學(xué)生鞏固和加深對課程內(nèi)容的理解，更重要的是可以進(jìn)一步鍛煉程序設(shè)計(jì)的技能，并初步感受軟件開發(fā)的規(guī)范，更能全面培養(yǎng)學(xué)生綜合運(yùn)用知識(shí)的能力、文獻(xiàn)檢索與分析能力、工程化能力、進(jìn)行研究性學(xué)習(xí)的能力、創(chuàng)新能力以及團(tuán)隊(duì)合作的能力等。本文是作者所在教學(xué)團(tuán)隊(duì)八年來的課程設(shè)計(jì)實(shí)踐小結(jié)，介紹了在“數(shù)據(jù)結(jié)構(gòu)”綜合性課程設(shè)計(jì)的內(nèi)容選擇、實(shí)施方法與激勵(lì)手段等方面進(jìn)行的一系列改革探索。

2傳統(tǒng)教學(xué)方法存在的問題及解決思路

數(shù)據(jù)結(jié)構(gòu)的課程實(shí)踐可分為一般性實(shí)驗(yàn)和綜合性課程設(shè)計(jì)。在傳統(tǒng)的課程教學(xué)中，往往采用一般性實(shí)驗(yàn)作為課程實(shí)踐的主要內(nèi)容，即布置針對本次課堂教學(xué)內(nèi)容的小型練習(xí)題，讓學(xué)生獨(dú)立完成程序設(shè)計(jì)與實(shí)現(xiàn)。這樣的實(shí)踐主要存在兩方面問題：

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

第二，學(xué)生獨(dú)立完成小型程序，雖然可以在一定程度上鍛煉編程能力，但這個(gè)鍛煉的層次和涉及面都比較窄?，F(xiàn)代軟件開發(fā)的規(guī)模，使得團(tuán)隊(duì)合作在大多數(shù)情況下成為必須。而且部分?jǐn)?shù)據(jù)結(jié)構(gòu)只有在處理大規(guī)模輸入的復(fù)雜問題時(shí)才能體現(xiàn)出優(yōu)勢，編寫小型程序很難使學(xué)生真正認(rèn)識(shí)到該數(shù)據(jù)結(jié)構(gòu)存在的意義。

針對上述問題，我們在設(shè)計(jì)較大規(guī)模的綜合性課程設(shè)計(jì)時(shí)就必須注意兩個(gè)方面：

第一，課程設(shè)計(jì)題目覆蓋的知識(shí)點(diǎn)應(yīng)盡可能避免單一，要采用啟發(fā)式的設(shè)計(jì)思路，引導(dǎo)學(xué)生圍繞課程設(shè)計(jì)目標(biāo)，通過查找與分析有關(guān)參考資料，進(jìn)行探究式的學(xué)習(xí)，激發(fā)創(chuàng)造的意識(shí)和能力。所以，在題目設(shè)計(jì)和實(shí)施中，不應(yīng)該只是“手把手”地教，要給學(xué)生留出發(fā)揮想象力和創(chuàng)造力的空間。

第二，題目的規(guī)模應(yīng)充分大，并且努力使學(xué)生對規(guī)范性的軟件開發(fā)有初步體驗(yàn)，在一定程度上使得學(xué)生的工程化能力和團(tuán)隊(duì)合作能力得到鍛煉。

而上述兩方面的考慮若要取得真正好的效果，還必須有一套行之有效的激勵(lì)機(jī)制，既可以公平地判定每個(gè)學(xué)生作為個(gè)體的能力，又可以鼓勵(lì)團(tuán)隊(duì)精神，同時(shí)還可以鼓勵(lì)學(xué)生開拓創(chuàng)新思維，主動(dòng)進(jìn)行研究性學(xué)習(xí)。

3課程設(shè)計(jì)的內(nèi)容選擇、實(shí)施方法與激勵(lì)手段

3.1內(nèi)容選擇

綜合性課程設(shè)計(jì)應(yīng)強(qiáng)調(diào)知識(shí)的綜合運(yùn)用，鍛煉學(xué)生對復(fù)雜問題進(jìn)行分析與求解的能力，所以在選擇內(nèi)容時(shí)可以從以下三方面考慮：

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

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

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

在內(nèi)容選擇方面，我們還建議參考?xì)v屆ACM國際大學(xué)生程序設(shè)計(jì)競賽的題目，該競賽特別強(qiáng)調(diào)考察參賽選手對各種算法的應(yīng)用能力，題目的綜合性較強(qiáng)，非常適合輔助學(xué)生學(xué)習(xí)體會(huì)數(shù)據(jù)結(jié)構(gòu)的妙用。浙江大學(xué)建設(shè)有全球著名的程序設(shè)計(jì)競賽練習(xí)網(wǎng)站(http://acm.zju.edu.cn/)，提供在線自動(dòng)裁判系統(tǒng)，簡稱ZOJ，目前擁有各類競賽練習(xí)題目近2000道，為數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)提供了豐富的題庫資源。本課程組設(shè)計(jì)的多道課程設(shè)計(jì)題目就取自或改編自該網(wǎng)站的練習(xí)題。

3.2實(shí)施方法

綜合性課程設(shè)計(jì)不僅僅是以實(shí)現(xiàn)相應(yīng)的程序?yàn)槟繕?biāo)，更重要的是培養(yǎng)學(xué)生今后從事軟件開發(fā)所需要的各種能力與素質(zhì)，包括測試能力和文檔寫作的能力。因此，在課程設(shè)計(jì)實(shí)施中，我們將學(xué)生分成三人小組，分工負(fù)責(zé)程序編寫、測試以及實(shí)驗(yàn)報(bào)告撰寫工作。

一份完整的實(shí)驗(yàn)報(bào)告至少應(yīng)包含以下四部分內(nèi)容：

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

(二)算法說明：這一部分需詳細(xì)描述解決問題所需要用到的算法和重要的數(shù)據(jù)結(jié)構(gòu)，即該實(shí)驗(yàn)到底應(yīng)該怎么做。

(三)測試結(jié)果：這一部分需根據(jù)題目類型設(shè)計(jì)提供相應(yīng)的測試方法和結(jié)果。對于需要比較不同算法性能優(yōu)劣的題目，應(yīng)設(shè)計(jì)并填寫一張性能比較表格，列出不同算法在同一指標(biāo)下的性能表現(xiàn)。對于需要利用某算法解決某問題的題目，應(yīng)設(shè)計(jì)并填寫一張測試用例表。每個(gè)測試用例應(yīng)包括測試輸入、測試目的、正確輸出、實(shí)際輸出、錯(cuò)誤原因等等。

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

其中第一、二部分以及全文統(tǒng)稿由文檔員負(fù)責(zé)，第三、四部分由測試員負(fù)責(zé)。整個(gè)學(xué)期發(fā)布的課程設(shè)計(jì)題目數(shù)應(yīng)該是3的倍數(shù)，使得每組的三個(gè)學(xué)生有機(jī)會(huì)均衡體驗(yàn)三種不同的角色。

3.3激勵(lì)手段

大學(xué)教育心理學(xué)研究表明，學(xué)習(xí)興趣通過適當(dāng)?shù)囊龑?dǎo)，會(huì)引發(fā)學(xué)生的需要和動(dòng)機(jī)，進(jìn)一步產(chǎn)生持續(xù)不斷的興奮，從而激發(fā)積極的行為反應(yīng)，努力去實(shí)現(xiàn)預(yù)訂目標(biāo)。而讓學(xué)生產(chǎn)生濃厚的學(xué)習(xí)興趣，就必須建立有效的激勵(lì)機(jī)制。

首先程序員、測試員、文檔員的工作難度不同，其工作的分?jǐn)?shù)分配也應(yīng)不同。例如我們采用50:30:20的分配制度，這樣只有在三個(gè)課程設(shè)計(jì)中將三種角色分別體驗(yàn)一遍，才有可能得到滿分100。

其次教師應(yīng)對“分析與探討”部分特別關(guān)注，及時(shí)發(fā)現(xiàn)并鼓勵(lì)學(xué)生的創(chuàng)新思維。一句簡單的鼓勵(lì)就可能對學(xué)生的主動(dòng)學(xué)習(xí)熱情起到非常大的引導(dǎo)和推動(dòng)作用。

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

當(dāng)然，分組實(shí)驗(yàn)的另一個(gè)目的，是鍛煉學(xué)生的溝通與團(tuán)隊(duì)合作能力。這個(gè)目的可以通過教師的激勵(lì)來達(dá)到，即教師在點(diǎn)評每道題目的完成情況時(shí)，對個(gè)別優(yōu)秀的組提出表揚(yáng)，而只有三項(xiàng)工作都完美的組，才會(huì)獲此殊榮。這時(shí)學(xué)生會(huì)在完成了自己工作的情況下，對隊(duì)友提供一定幫助，以獲得團(tuán)隊(duì)的榮譽(yù)。

4成果

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

參考文獻(xiàn)

[1] 教育部高等學(xué)校計(jì)算機(jī)科學(xué)與技術(shù)教學(xué)指導(dǎo)委員會(huì). 高等學(xué)校計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)發(fā)展戰(zhàn)略研究報(bào)告暨專業(yè)規(guī)范(試行)[M]. 北京:高等教育出版社，2006.

[2] 何欽銘，馮雁，陳越. 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)[M]. 杭州:浙江大學(xué)出版社，2007.

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