基于ACM競賽的數據結構實驗課程教學研究

張少仲 白英 王小妹 陳媛嫄

摘? 要： 分析了目前數據結構實驗課程教學的現狀和存在的問題，提出將ACM競賽理念與數據結構實驗教學相結合。根據數據結構實驗課程特點，重新優化實驗內容，構建基于ACM競賽的實驗題集。針對不同層次的學生，給出基于ACM競賽的不同級別的實驗題目，從而有益于各層次學生的編程能力、分析與解決問題能力以及溝通能力的提高。

關鍵詞： 數據結構實驗; ACM競賽; 實驗教學; 實驗題集

中圖分類號：G642.0? ? ? ? ? 文獻標識碼：A? ? ? 文章編號：1006-8228（2020）10-73-03

Abstract： This paper analyzes the current situation and existing problems of the teaching of data structure experiment course， and proposes to combine the concept of ACMICPC （Association for Computing Machinery， International Collegiate Programming Contest） with the teaching of data structure experiment course. According to the characteristics of data structure experiment course， the experiment content is re-optimized to construct the experiment question set based on ACMICPC. According to the students of different levels， experiment questions of different levels based on ACMICPC are given， which is beneficial to the improvement of the abilities of programming， analysis and problem-solving as well as the communication ability of students in different levels.

Key words： data structure experiment; ACMICPC; experiment teaching; experiment question set

0 引言

數據結構課程是計算機相關專業的基礎課程，在專業課程體系中起著承上啟下的作用。課程對培養學生的數據模型抽象能力、算法設計能力和復雜的程序設計能力具有重要的作用。課程知識內容和算法技術，無論對于后續學習其他專業課程，或是將來從事軟件開發相關工作，都是必須掌握的基礎內容[1]。

“程序設計基礎”這門課是對數據結構課程影響最大的先修課程，這門課學完后，學生的編程能力差異很明顯，有部分學生已經掌握了一定的編程技巧，但有更多的學生甚至不怎么會編程[2]。在基礎不牢的情況下來學習數據結構知識，理論和實驗難以兼顧。

為了改善數據結構課程教學質量，課題組以實驗教學為突破口，進行了積極有益的探索，實現了各個層次的學生都有收獲的實驗教學。以尊重學生個體差異性為前提，力求使學生發揮各自的潛能，取得更好的學習效果，達到提升整體教學水平的目的。

ACM 國際大學生程序設計競賽（簡稱 ACMICPC）是由國際計算機界歷史最悠久、最具權威性的計算機組織ACM學會（Association for Computer Machinery）主辦，是世界上公認的規模最大、水平最高的國際大學生程序設計競賽，其目的在于讓大學生運用計算機來充分展示自己在壓力情況下，分析問題、解決問題的能力。該項競賽從1970年開始舉辦，薈萃了世界各大洲的精英，受到國際知名公司的關注[3]。ACM競賽具有較長的歷史，方法成熟，將ACM競賽模式應用于數據結構課程實驗教學過程中，對于改變和完善具體實驗訓練項目，推動大學生科技創新教育，提升高校人才培養質量具有重要的現實意義[4]。

1 傳統實驗教學中存在的問題

傳統的實驗教學模式下，教師在課堂上提前將實驗內容布置給學生，所有的學生做同樣的實驗題目，提交的時間和實驗結果參差不齊。這導致實驗教學面臨如下問題。

⑴ 由于學生的編程能力差距大，對不同層次的學生起不到因材施教的效果。數據結構實驗課程是用程序設計語言對理論課程中的算法編程實現，因此，學生必須具有一定的編程能力以解決實際問題。現在的數據結構教材的實驗部分大多是基于C語言編寫的，課程中涉及了大量C語言中的重點和難點。很多學生對這部分知識點掌握不牢固，用起來生疏，導致了對算法的思路是清晰的，但卻難以用C語言將算法實現出來[4]。學生的程序設計語言基礎和編程能力差距大，相同的實驗題目會讓不同層次的學生獲得的實驗效果不同。編程基礎好的同學完成得快，質量很高;多數學生編程不夠熟練，阻礙了學生對算法思想的驗證和對綜合設計性問題的解決;個別同學還有抄襲情況發生。

⑵ 相同的實驗題目難以科學地量化和評價教學效果。傳統的數據結構實驗課程的考核方式多為：平時實驗態度+編程能力+實驗結果+實驗報告。但是相同的實驗題目導致實驗結果和實驗報告內容也基本相同。對于實驗態度良好的學生，基本只能靠編程能力的評判來區分學習成績了。而對編程能力的評判基本是看代碼提交時間、運行時間、占用內存、以及代碼編寫規范程度。而這部分內容只占總分的一部分，結果就是學生的考核分數相對集中，難以對課程教學效果給出科學評價。

⑶ 對每一屆學生都用相同的實驗內容，影響學生學習的積極性。編程基礎好的同學完成得快，課堂時間就能順利完成;而大多數同學還需要課余時間來完成。這樣不能激起學生的學習興趣，對不同層次的學生起不到因材施教的效果。加上原有的實驗考核方式缺乏精準性，對同學間的抄襲、互聯網上的抄襲甄別困難，不僅影響學生學習的積極性，也達不到教學目標。

⑷ 實驗內容的設置難以達到培養學生的工程實踐能力的能力目標。傳統的數據結構實驗題目基本上是針對某一章的課堂講授內容設計的，學生只需應用該部分的知識即可完成實驗題目，不需要思考是否還有其他的解決方案，更談不上選擇最優的方案來解決問題，無法培養學生的工程實踐能力，難以達到課程設置的能力目標[5]。

總之，實驗題目的單一化、統一化是導致上述實驗教學問題的主要根源。鑒于此，將不同層次的實驗題目匯聚在一起，由淺入深，構建一個用于數據結構實驗教學的實驗題集，是解決問題的一個方法。課題組針對ACM競賽的題目，有選擇性地匯聚成一個實驗題集，用于數據結構的實驗教學中，從而改革了傳統的實驗教學模式，激發了學生的積極性，使不同層次的學生都能有所收獲，也達到了因材施教的效果。

2 基于ACM競賽的數據結構實驗課程改革

ACM競賽的題目有如下特點：有實際背景，趣味性和實用性較強;考查的知識范圍較全面;層次性較好，分不同水平的題目;靈活、新穎，絕大部分題沒有定解，留有廣闊的思維空間。ACM競賽的題目以解決問題為目標，而解題方法不受限制，可以讓學生有更多的創新思維空間。將ACM競賽的題目匯聚成一個實驗題集，引入到數據結構的實踐教學中，可激發學生的學習熱情和潛力，提高學生自主學習能力、創新能力，也有利于團隊精神的培養。在具體運用中采取了以下幾條措施。

2.1 實驗內容分級，實驗題目靈活化，多樣化

首先我們將實驗內容分級，分成初級（單一算法的練習）、中級（需要用算法解決實際問題）和高級（結合若干算法來解決一個較大規模的問題）題目。學生可以根據自身情況選擇不同級別的題型和題目數量來完成。這樣可以滿足學生學習過程中不同層次的需求，充分調動他們學習的主動性和積極性。除此之外，很多實際問題是有多解的，這樣的實驗題目充分激發了學生的學習主動性和積極性，將被動學習化為主動學習，更好地達到實驗教學目的。

2.2 將傳統的ACM競賽題目改編為實驗題目

根據ACM競賽題目的特點，我們從中精心挑選相關題目，或將原有數據結構實驗題目改造為ACM競賽題目形式，形成了與數據結構實驗要求相對應的初、中、高級實驗題集，將其作為實驗題目。將傳統的以算法為主線的實驗教學體系改為以問題為主線的實驗教學體系，通過具體問題描述給出題目，讓學生自主選擇合理的數據結構和算法進行求解，加深學生對基礎知識和算法的深入理解，以“學以致用”的方式來牢固掌握所學知識。

2.3 考核方式靈活，綜合評定學生

學生對分數非常敏感，恰當的實驗成績評分標準有利于激發學生的學習動力，反之有可能會挫傷其學習積極性。將學生提交的程序由ACM在線測評系統進行評測，不僅考察其正確性，還對代碼的運行時間、占用內存、輸入輸出格式加以限制等，可以綜合考察學生對算法的靈活運用。

我校的數據結構實驗課已經與理論課拆分，成為一門獨立課程，而且比原來增加了4學時。共計12次課，24學時，滿分100分。實驗評分標準的制訂，需考慮對學生具有激勵作用，經過新的教學模式的探索，課題組決定采用以完成實驗題目為主的評分方式。

⑴ 對實驗題目的完成占總分的90%，實驗態度和實驗報告占10%。

⑵ 完成初、中、高級題目的分數占比是1：2：4;即完成一個高級題相當于完成兩個中級題，完成一個中級題相當于完成兩個初級題。

⑶ 完成兩個高級題即可獲得60分，以后每完成一個高級題加10分。加到80分以后，每完成一個高級題加5分。加到90分后為止。

該評分標準為學生設立較低的及格目標，使學生更容易進入完成實驗題目的狀態;其次完成6個高級實驗題目就能拿滿分，更能激發學生挑戰更高級別實驗任務的動力。同時即使12次實驗課中完成12個初級實驗題目，成績也只能是及格多一點，要想取得好成績還遠遠不夠。從而確保了該評分標準在總體上不降低實驗教學的要求。這樣，不僅在成績評定上做到了客觀、公正，還更好地發掘了學生的創新能力，提高他們對知識點的掌握程度。

2.4 加強師生之間、學生之間的有益互動，培養良好的團隊合作精神

傳統的手工批改作業的任務非常繁重，學生的作業量以及作業反饋時間都會受到限制，在一定程度上打擊了教師和學生的積極性。而ACM競賽模式的在線評測系統可以對學生的作業進行自動評測，從而減輕教師的指導負擔。學生在自主完成實驗任務的過程中，遇到困難可以尋求教師個別指導，為學生提供解決問題的有關線索;同時，鼓勵學生之間、師生之間的討論和交流，用來豐富、矯正和加深對當前實驗問題的解決方案，培養了良好的團隊合作精神和溝通能力。

3 結束語

將ACM競賽的題目選編成一個實驗題集，引入到數據結構的實驗教學中，一改傳統實驗授課全員實驗題目統一模式為獨立選擇實驗題目模式，不同層次的學生采用不同的實驗題目，使不同層次的學生都能得到提高。實驗題目選擇個性化，將全體授課與個別指導相結合，可激發學生的學習熱情和潛力，提高學生自主學習能力、創新能力，也有利于團隊精神的培養。實驗課引入相對自動化的實驗考核方式，減輕了教師負擔，使教師把更多精力投入到輔導學生方面。這種基于ACM競賽的數據結構實驗教學方式也有助于培養學生的工程實踐能力、團隊合作精神和協同能力。今后，我們還將繼續將教學改革深入下去，以期培養高水平、高素質的優秀創新人才。

參考文獻（References）：

[1] 張安勤，田秀霞等.數據驅動的數據結構課程案例設計研究與實踐[J].軟件工程，2020.23（4）：54-56

[2] 劉忠民，李廣瑞.數據結構課程實驗分層教學的探索和實踐[J].計算機教育，2018.6：128-130

[3] 韓建民，鐘發榮等.基于ACM-ICPC訓練模式的數據結構實踐教學探索[J].計算機教育，2013.5：103-107

[4] 李涵，吳秋新.基于ACM模式的數據結構實踐教學改革的探索與思考[J].山東青年，2012.9：39-40，42

[5] 楊彬，王青正.工程教育專業認證背景下的數據結構教學改革[J].計算機時代，2020.4：61-63，67