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

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

中圖分類號(hào)：G 文獻(xiàn)標(biāo)識(shí)碼：B

文章編號(hào)：1672-5913（2007）07-0029-03

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

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

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

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

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

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

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

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

3 面向問(wèn)題求解的實(shí)踐教學(xué)模式

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

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

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

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

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

3.2 作業(yè)自動(dòng)評(píng)測(cè)

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

3.3 解題報(bào)告交流

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

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

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

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

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

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

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

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

4.2 深化理論教學(xué)

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

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

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

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

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

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

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

5 結(jié)束語(yǔ)

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

參考文獻(xiàn)：

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

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

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

收稿日期：2007-1-16

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