摘要：“算法與數(shù)據(jù)結(jié)構(gòu)”是計算機科學(xué)與技術(shù)專業(yè)重要的專業(yè)基礎(chǔ)課，是一門理論性與實踐性都很強的課程。針對多年課程教學(xué)過程中發(fā)現(xiàn)學(xué)生普遍認為課程內(nèi)容過于抽象，學(xué)習(xí)興趣不大，學(xué)完后不僅理論基礎(chǔ)不扎實，而且分析和解決實際問題的能力差的狀況，提出面向問題求解的實踐教學(xué)模式，并在近三年的課程教學(xué)中加以實踐，取得明顯效果。

關(guān)鍵詞：數(shù)據(jù)結(jié)構(gòu)；算法；問題求解；實踐教學(xué)；改革

中圖分類號：G 文獻標識碼：B

文章編號：1672-5913（2007）07-0029-03

1 “算法與數(shù)據(jù)結(jié)構(gòu)”課程的性質(zhì)與特點

“算法與數(shù)據(jù)結(jié)構(gòu)”是計算機科學(xué)與技術(shù)專業(yè)重要的專業(yè)基礎(chǔ)課，是非數(shù)值計算程序設(shè)計的基礎(chǔ)，也是設(shè)計和實現(xiàn)各種應(yīng)用軟件的重要基礎(chǔ)。本課程主要以抽象數(shù)據(jù)類型為主線，研究常用的數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及其所支持的運算操作；研究解決常用實際問題的經(jīng)典算法；學(xué)習(xí)基本的算法分析方法，對算法進行時間復(fù)雜度和空間復(fù)雜度的分析。為學(xué)生后續(xù)課程的學(xué)習(xí)以及進行計算機軟件的設(shè)計和開發(fā)打下堅實的基礎(chǔ)。

2 傳統(tǒng)課程教學(xué)存在的問題及原因

“算法與數(shù)據(jù)結(jié)構(gòu)”是一門理論性和實踐性都很強的課程。在傳統(tǒng)的課程教學(xué)過程中，授課教師大多重理論而輕實踐，而且由于該課程內(nèi)容較抽象，不好講解，若非精心準備，很難取得好的課堂教學(xué)效果。對學(xué)生而言，雖然也知道該課程的重要性，但枯燥的課堂教學(xué)實在無法激發(fā)他們的學(xué)習(xí)興趣，課后的上機實踐也因目標不明確而幾乎流于形式。

近幾年各個學(xué)校都在進行該課程的教學(xué)改革，其中很重要的一個改革就是實踐教學(xué)改革，提倡要加強實踐環(huán)節(jié)的訓(xùn)練，在每個章節(jié)的理論教學(xué)后要求學(xué)生完成若干上機實驗作業(yè)，想由此達到提高學(xué)生實踐能力，深化理論教學(xué)的目的。然而，由于以下幾個主要原因，使得改革的輻射面太窄，少數(shù)上進的學(xué)生從中受益，大部分學(xué)生卻收效甚微，與實踐教學(xué)改革的既定目標相差甚遠。

（1）實驗作業(yè)較少面向?qū)嶋H問題，無法激起學(xué)生的學(xué)習(xí)興趣；

（2）實驗作業(yè)要求不夠明確，學(xué)生無法驗證所完成實踐作業(yè)的正確性和優(yōu)劣性；

（3）教學(xué)過程中缺少合適的監(jiān)督機制和獎懲制度，大多學(xué)生由于程序設(shè)計基本功不扎實，當無法完成任務(wù)時采取“copy”方式來敷衍了事。

3 面向問題求解的實踐教學(xué)模式

針對傳統(tǒng)教學(xué)存在的問題，課程教學(xué)組經(jīng)過調(diào)研、分析后決定開展課程實踐教學(xué)改革，構(gòu)建面向問題求解的實踐教學(xué)模式，以實際問題求解為主線索來組織和設(shè)計實踐教學(xué)內(nèi)容，增加設(shè)計型實驗和綜合型實驗，鍛煉學(xué)生綜合運用所學(xué)理論知識進行問題分析、設(shè)計和實現(xiàn)的能力，在實踐中強化創(chuàng)新意識。

為了切實有效地推進《算法與數(shù)據(jù)結(jié)構(gòu)》實踐教學(xué)改革，我們專門開發(fā)了課程的網(wǎng)絡(luò)教學(xué)系統(tǒng)（http://ds.fzu.edu.cn），用于輔助課堂教學(xué)和實踐教學(xué)。該系統(tǒng)可實現(xiàn)作業(yè)發(fā)布、提交、在線評測、成績公布、優(yōu)秀作業(yè)評選、疑難解答等多項功能。

面向問題求解的實踐教學(xué)模式主要包括以下幾個方面：

3.1 面向?qū)嶋H問題，精心設(shè)計實踐教學(xué)內(nèi)容

以問題求解為主線索，針對每個教學(xué)單元的重要知識點，精心設(shè)計8~15題有代表性、難易搭配的上機實驗作業(yè)，這些作業(yè)包括僅要求對數(shù)據(jù)結(jié)構(gòu)和算法進行實現(xiàn)的驗證型實驗，以及要求運用所學(xué)理論知識設(shè)計求解典型或有趣實際問題的設(shè)計型實驗和綜合型實驗。這些實驗作業(yè)將以隨機的方式分給學(xué)生，每位學(xué)生必須在規(guī)定的時間內(nèi)獨立完成2~3題。在期中和期末考試時還設(shè)計兩套上機實驗綜合測試題，用于檢查學(xué)生的綜合運用能力。

3.2 作業(yè)自動評測

為了對大量的學(xué)生實驗作業(yè)進行有效的評價，我們開發(fā)作業(yè)自動評測系統(tǒng)，采取離線和在線作業(yè)自動評測相結(jié)合。先用離線作業(yè)自動評測系統(tǒng)測試學(xué)生提交的作業(yè)，測出每次作業(yè)的成績，并在網(wǎng)站上公布評測結(jié)果，平時作業(yè)成績將是期末成績的重要組成部分。成績公布后，開放在線作業(yè)自動評測系統(tǒng)，作業(yè)成績不理想的學(xué)生可再次改進自己的作業(yè)，并利用在線評測系統(tǒng)進行評測。

3.3 解題報告交流

針對每個教學(xué)單元的實驗作業(yè)，我們都開展優(yōu)秀解題報告交流活動，把每道作業(yè)成績前三名的學(xué)生定為優(yōu)秀作業(yè)候選人，并要求他們準備解題報告。解題報告的內(nèi)容主要包括：問題的思考過程、問題的數(shù)學(xué)化、數(shù)據(jù)結(jié)構(gòu)和算法設(shè)計策略的選取、算法正確性的證明、算法復(fù)雜性的分析，算法的優(yōu)化及改進、程序的設(shè)計與實現(xiàn)等。這些解題報告將在課程討論課上展示，從而實現(xiàn)作業(yè)資源的共享和優(yōu)秀解題思路的交流。

3.4 優(yōu)秀作業(yè)評選

我們對每道實驗作業(yè)題都進行了優(yōu)秀作業(yè)的評選。討論課之后，優(yōu)秀作業(yè)候選人的解題報告和源程序都放到課程網(wǎng)站上，全體同學(xué)都必須進行投票。最后由任課教師綜合作業(yè)成績、報告情況、解決問題算法的復(fù)雜性和創(chuàng)新性等幾個方面來確定每道題的優(yōu)秀作業(yè)，并對評上優(yōu)秀作業(yè)的同學(xué)給予作業(yè)成績雙倍的獎勵。

除此之外，我們還開發(fā)雷同作業(yè)檢測系統(tǒng)，建立“雷同作業(yè)黑名單”。對進入黑名單的學(xué)生采取警告、扣分等方式，督促他們獨立完成實驗作業(yè)。

4 實踐教學(xué)改革的成效

面向問題求解的實踐教學(xué)模式先后在計算機科學(xué)與技術(shù)專業(yè)2003級、2004級全體學(xué)生和學(xué)校綜合班2004級學(xué)生的“算法與數(shù)據(jù)結(jié)構(gòu)”課程教學(xué)中得以實施，并取得了顯著的效果。

4.1 激發(fā)了學(xué)生的學(xué)習(xí)興趣

利用所學(xué)的數(shù)據(jù)結(jié)構(gòu)和算法解決有趣的實際問題，在很大程度上激發(fā)了學(xué)生的學(xué)習(xí)興趣和主動性。如利用循環(huán)鏈表解決猴子選大王問題，利用棧幫助小鼠走出迷宮，利用Huffman算法設(shè)計文件解壓縮軟件和利用圖的最短路徑算法尋找換車次數(shù)最少的公交線路問題、套匯問題等。

4.2 深化理論教學(xué)

4.2.1 典型問題的設(shè)計，使抽象的數(shù)據(jù)結(jié)構(gòu)形象化

在組織和設(shè)計實踐教學(xué)內(nèi)容時，盡量設(shè)計與每種數(shù)據(jù)結(jié)構(gòu)的邏輯模型相似的經(jīng)典問題作為學(xué)生實驗作業(yè)的一部分。如要求學(xué)生用表求解多項式的相關(guān)問題；利用棧實現(xiàn)算術(shù)表達式求值問題；利用隊列模擬機場飛行跑道上飛機的調(diào)度；利用圖的最小生成樹理論設(shè)計具有最小耗費的通信網(wǎng)絡(luò)；利用堆實現(xiàn)圓形操場的石子合并問題等等。這些經(jīng)典問題便于學(xué)生從直觀上理解各種數(shù)據(jù)結(jié)構(gòu)的本質(zhì)特征。

4.2.2 一題多解，便于學(xué)生比較不同數(shù)據(jù)結(jié)構(gòu)和算法的優(yōu)缺點

在組織和設(shè)計實踐教學(xué)內(nèi)容時，讓同一個問題在不同教學(xué)單元多次出現(xiàn)，如等價類問題可看做是線性表的應(yīng)用，也是并查集應(yīng)用的一個經(jīng)典例子；迷宮問題既可用棧來求解，也可用隊列來求解；歐拉回路問題也分別出現(xiàn)在線性表和圖這兩個教學(xué)單元的實踐教學(xué)中。

以上兩種手段的實施，在很大程度上使學(xué)生加深對課堂教學(xué)內(nèi)容的理解，達到通過實踐教學(xué)深化理論教學(xué)的目的。

4.3 提高了學(xué)生分析和解決實際問題的能力

從近三年的改革實踐來看，大部分同學(xué)經(jīng)過一個學(xué)期的學(xué)習(xí)與訓(xùn)練，已經(jīng)具備在一定的時間內(nèi)獨立解決問題的能力，能夠在規(guī)定的時間內(nèi)選擇合適的數(shù)據(jù)結(jié)構(gòu)和算法設(shè)計策略，并在計算機上編程實現(xiàn)。我校計算機專業(yè)學(xué)生在各類與程序設(shè)計相關(guān)的學(xué)科競賽中頻獲佳績。令人興奮的是，我校ACM/ICPC代表隊在2005年亞洲區(qū)杭州賽區(qū)的比賽中喜獲第6名，并在第30屆ACM國際大學(xué)生程序設(shè)計競賽全球總決賽中獲得第39名。這些都得益于該課程實踐教學(xué)改革的直接影響。

5 結(jié)束語

實踐教學(xué)考試改革的實施深化了課堂理論改革，提高了人才培養(yǎng)質(zhì)量，但同時無疑給老師增加了許多額外工作量。為了保證改革的順利進行，必須制定相應(yīng)的激勵政策，充分調(diào)動廣大教師的積極性和主動性。

參考文獻：

[1] 劉亞波，劉大有，高瀅.以實驗教學(xué)深化“數(shù)據(jù)結(jié)構(gòu)”理論教學(xué)[J]. 吉林大學(xué)學(xué)報（信息科學(xué)版），2005，23（8）：135-137.

[2] 殷人昆，鄧俊輝.清華大學(xué)“數(shù)據(jù)結(jié)構(gòu)”精品課程介紹[J]. 計算機教育，2006，(5):20-22.

[3] 廖明宏，等，哈爾濱工業(yè)大學(xué)“數(shù)據(jù)結(jié)構(gòu)與算法”精品課程介紹[J]. 計算機教育，2006，(5):17-19.

收稿日期：2007-1-16

作者簡介：吳英杰（1979-），男，福建安溪人，助教，碩士，研究方向為數(shù)據(jù)結(jié)構(gòu)，算法的設(shè)計與分析。