多層次的“數據結構”實踐教學模式探討

孫愛東 楊秋妹 肖媚燕

摘要:“數據結構”的實踐教學不僅可以幫助學生鞏固和加深對課程內容的理解,更重要的是可以進一步鍛煉程序設計的技能,培養學生運用知識的能力,并初步感受軟件開發的規范和培養團隊合作精神。本文針對實踐教學環節中存在的問題,設計與實現了由簡單到復雜、由單一到綜合的多層次實踐教學模式。

關鍵詞:數據結構;實踐教學;多層次

中圖分類號: G642文獻標識碼:B

1引言

“數據結構”是計算機科學與技術及相關專業的一門重要的核心專業基礎課程,側重介紹軟件設計中的基本技術,包括程序設計中所涉及到的各種數據結構、基本運算、各種存儲結構以及算法實現和性能分析,排序和查找這兩種常用的運算以及遞歸技術等內容。通過這門課程的學習,幫助學生在軟件開發的過程中正確、合理地組織數據、選擇最優的存儲結構,有效甚至高效地設計算法,從而提高軟件整體質量。

“數據結構”的課程實踐不僅可以幫助學生鞏固和加深對課程內容的理解,更重要的是可以進一步鍛煉程序設計的技能,并初步感受軟件開發的規范,全面培養學生綜合運用知識的能力、進行研究性學習的能力、創新能力以及團隊合作的能力等。

2 “數據結構”實踐教學中存在的問題

“數據結構”實踐教學包括“數據結構”課程實驗和課程設計兩部分。按照專業教學要求,在第3學期安排“數據結構”教學72學時,其中52學時上課、20學時實驗;第4學期安排2周(40學時)的課程設計。

目前,“數據結構”實踐教學中存在兩個主要問題。

(1) 大部分學生對代碼編寫有恐懼心理,程序設計能力薄弱,不同學生基礎不同,不適宜一刀切做一樣的要求。

(2) 在當前的“數據結構”教學中有兩種爭論,一種是“數據結構”課程側重在教導學生怎樣實現基本的數據結構,另外一種看法是教會學生如何通過編程環境提供的API調用數據結構,如STL、JDK等。部分學生誤認為只需要掌握接口調用就行,但作為計算機專業的學生,應該要會自己實現基本的數據結構,從而可以在遇到實際應用時根據需求設計靈活高效的新結構。

針對以上存在的問題,在“數據結構”的實踐教學中設計由簡單到復雜、由單一到綜合的多層次實踐教學模式,將實踐內容分為驗證性基礎實驗、綜合性實驗和課程設計三個層次,每個階段完成相應的實踐目標,下面分別介紹這三部分的實施。

3多層次的“數據結構”實踐模式

3.1驗證性基礎實驗

“數據結構”的實踐教學遵循由淺入深,由易到難的規律。在學生剛接觸“數據結構”這門課時,為掌握課程基礎內容及完成對知識點的回顧,數據結構驗證性基礎實驗在實驗課程計劃學時內完成,主要圍繞教材上的重要數據結構上機實現,深化理解和掌握理論知識。鑒于計劃學時的限制,實驗以驗證性實驗為主,如循環隊列的建立空隊、入隊、出隊操作,利用二叉樹的先序遍歷生成二叉樹并完成先、中、后序遍歷及層次遍歷。算法基本上是教材中所介紹的,同時包括有簡單應用算法,如利用堆棧驗證括號的匹配問題等。驗證性實驗側重加深學生對基本數據結構的理解,不要求應用創新。

驗證性實驗是對書本的知識點進行實現,趣味性相對比較低,為了提高學生的積極性,這部分實驗采取類似ACM競賽的方式進行考核,把整個學期的驗證性實驗分成若干次比賽,每次比賽包含一定題量的題目,規定學生在限定時間內完成,并且按照完成時間的先后進行排名。在此階段,采用ACM/ICPC競賽中使用的Online Judge在線評判實驗系統對學生提交的代碼進行評判。Online Judge在線評判實驗系統采用程序黑箱子測試的方法,針對具體的題目預先設定若干組輸入數據以及其對應的正確的輸出結果,評判時,先編譯、運行被測程序,再將設定好的輸入數據通過輸入重定向的方式傳遞給運行的被測程序,被測程序輸出后的結果與設定的正確的輸出結果進行對比,所有的輸出結果均符合則判定程序正確。在這一過程中,只要設定的輸入數據有代表性且覆蓋面足夠廣,就可以保證評判具有足夠的正確度。系統還能夠自動進行運行結果統計分析和代碼相似度評判等功能。通過評判系統的使用,學生初步了解在測試方法及在輸入、輸出格式受限情況下完成程序設計的方法。

通過這一階段的實踐教學,學生基本掌握常用數據結構的編寫,并且養成了一定的接口規范意識。

3.2綜合性實驗

通過完成驗證性基礎實驗,學生對教學內容和要求有一定的了解并掌握初步實驗的方法。為了進一步引導、培養學生自己獲取知識的能力,在學期中后期,再布置1、2個綜合性實驗題目在課外開放實驗室完成。如題目一完成二叉排序樹的建立、遍歷、交換左右子樹、求深度、求葉子結點個數等各種操作。這個實驗安排在樹結構部分,因此要求將查找部分的二叉排序樹的基本操作提前在樹這部分內容中介紹。此實驗覆蓋樹、堆棧、隊列、遞歸等數據結構課程知識點,是名副其實的綜合性實驗。題目二完成各種排序算法效率分析。要求完成在正序、逆序、小規模數據量和大規模數據量情況下分析算法的效率,除教材中的排序算法外可以由學生自己設計多個排序算法。同時本題為團隊實驗,開始實驗前,成員協商安排函數參數等接口,并通過排序過程中的移動次數和比較次數衡量算法的效率。

綜合性實驗的檢驗方案分兩部分,首先,要求與驗證性試驗一致,學生要通過Online Judge在線評判實驗系統的黑箱子測試;其次,要求學生書寫實驗報告。綜合性實驗不僅僅是以實現相應的程序為目標,更重要的是培養學生今后從事軟件開發所需要的各種能力與素質,包括測試能力和文檔寫作的能力,因此,能夠較規范書寫綜合性實驗報告很重要。實驗報告要求有統一報告的版面格式、封面格式,同時只收電子版,即環保又易存放。 一份完整的實驗報告至少應包含需求分析、概要設計、詳細設計、測試分析、效率分析與算法完善和附錄等至少六個部分的內容。

3.3課程設計

課程設計在“數據結構”的課堂授課全部結束之后進行,做為一門獨立的實踐課程。對于沒有安排“數據結構課程設計”的學校可以做為數據結構實踐教學的實訓項目設計環節。這一階段主要目標是加深學生對數據結構的理解,能應用學習過的數據結構,并且可以根據實際的問題定義數據結構。由于在驗證性基礎實驗這一階段,已經訓練了學生實現基本數據結構的能力,所以在課程設計這一階段,可以引進STL的應用。

為彌補課內實驗的不足,課程設計題目覆蓋的知識點要盡可能覆蓋較多知識點,同時注意實用性、與其他課程后續課程如“操作系統”、“數據庫”和“編譯原理”等的知識銜接。要引導學生圍繞課程設計的目標,鍛煉對復雜問題進行分析與求解的能力,激發創造的意識和能力。根據多年課程設計實踐和從ACM題目庫中選取題目構建題目庫。題目按知識點分為幾種不同類型,每種類型的題目按難度有不同分值權重,此外還有團隊完成的題目。

課程設計涉及到的內容可以分成兩部分。第一部分,算法設計型,加強傳統的薄弱環節——樹、圖方面的練習。除此之外,引入對ACM競賽常用的高級數據結構的學習,如介紹并查集、線段樹等的應用,這部分主要從北大ACM題庫中選題,側重歷年的競賽題目。第二部分,應用工程型,增強學生數據結構的應用能力。這部分主要側重把數據結構的知識用于解決日常生活中遇到的問題,如使用散列表實現電話查找系統等。

為了更好地實現課程設計的目標,將不同基礎的學生分為三類:薄弱、較好和優秀,分類的依據是“數據結構”考試成績、驗證性基礎實驗和綜合性實驗的成績,其中較好的學生數居多,占總人數的80%左右。限定不同類型的學生只能選擇不同權重的題目。基礎薄弱的學生是教師指導的重點。鼓勵優秀的學生在團隊項目中挑戰自己,選擇圍繞數據挖掘的幾個算法如決策樹算法、遺傳算法等進行選題或自行設定的題目,通過查找與分析資料進行探索式學習,初步掌握科學研究的方法。課程設計成績由個人完成題目和團隊題目,比例為60:40,按選題的權重、運行情況和設計報告的質量給分。成績優異者最后要通過答辯,一方面鍛煉表達能力同時大家見識更多的算法,開闊視野。

3.4實驗中注意事項

即使同是計算機專業的學生,不同班級因為基礎、學風等因素,實驗基礎會有較大差別。任課和實驗指導教師要對學生進行摸底測驗,及時掌握學習狀態,合理安排實驗。

上課和實驗前首先讓學生了解整個教學與實驗的安排和考察方法,每個實驗的最遲完成期限,從而讓學生有一定緊迫感,合理安排實驗進度。自編的實驗指導書可以保證實踐教學的順利完成及節省時間。

驗證性基礎實驗與理論教學同時進行,而綜合性實驗只能利用實驗室開放時間,但適時的指導是必要的,所以數據結構實驗部分的指導與課程設計指導應由同一教師完成,由指導教師協調分配實驗指導時間。

4結束語

經過一系列的實踐教學,取得了不少寶貴的經驗和可喜的成績。多層次的實驗內容調動了學生學習的積極性,學生解決問題的能力得到提高。Online Judge系統的使用提高實踐教學指導效率,實驗報告的要求強化了學生的文檔書寫能力。今后,將進一步完善數據結構題庫的建設、豐富數據結構課程的實驗內容。另外,還需要在實踐教學中,重視新老教師經驗交流、方法創新,在教和學的過程中不斷探索和實踐,適時調整實踐教學內容、改進教學方法,使數據結構實踐教學質量提高到一個新的水平。

參考文獻:

[1] 陳越,何欽銘,馮雁. “數據結構”綜合性課程設計教學探索與實踐[J].計算機教育, 2008(8):54-55.

[2] 王德興,胡學鋼,張玉紅,等. 數據結構課程設計的改革與創新探討[J].合肥工業大學學報,2008,22(5):94-97.

[3] 陳湘驥,劉財興,陳志民. 在線評判系統在程序設計類課程大規模教學中的應用[C]// 張鳳祥.全國計算機新科技與計算機教育論文集(第16卷). 成都:西南交通大學出版社,2008.