基于ACM競(jìng)賽的數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)課程教學(xué)研究

張少仲 白英 王小妹 陳媛嫄

摘? 要： 分析了目前數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)課程教學(xué)的現(xiàn)狀和存在的問題，提出將ACM競(jìng)賽理念與數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)教學(xué)相結(jié)合。根據(jù)數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)課程特點(diǎn)，重新優(yōu)化實(shí)驗(yàn)內(nèi)容，構(gòu)建基于ACM競(jìng)賽的實(shí)驗(yàn)題集。針對(duì)不同層次的學(xué)生，給出基于ACM競(jìng)賽的不同級(jí)別的實(shí)驗(yàn)題目，從而有益于各層次學(xué)生的編程能力、分析與解決問題能力以及溝通能力的提高。

關(guān)鍵詞： 數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn); ACM競(jìng)賽; 實(shí)驗(yàn)教學(xué); 實(shí)驗(yàn)題集

中圖分類號(hào)：G642.0? ? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A? ? ? 文章編號(hào)：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 引言

數(shù)據(jù)結(jié)構(gòu)課程是計(jì)算機(jī)相關(guān)專業(yè)的基礎(chǔ)課程，在專業(yè)課程體系中起著承上啟下的作用。課程對(duì)培養(yǎng)學(xué)生的數(shù)據(jù)模型抽象能力、算法設(shè)計(jì)能力和復(fù)雜的程序設(shè)計(jì)能力具有重要的作用。課程知識(shí)內(nèi)容和算法技術(shù)，無論對(duì)于后續(xù)學(xué)習(xí)其他專業(yè)課程，或是將來從事軟件開發(fā)相關(guān)工作，都是必須掌握的基礎(chǔ)內(nèi)容[1]。

“程序設(shè)計(jì)基礎(chǔ)”這門課是對(duì)數(shù)據(jù)結(jié)構(gòu)課程影響最大的先修課程，這門課學(xué)完后，學(xué)生的編程能力差異很明顯，有部分學(xué)生已經(jīng)掌握了一定的編程技巧，但有更多的學(xué)生甚至不怎么會(huì)編程[2]。在基礎(chǔ)不牢的情況下來學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)知識(shí)，理論和實(shí)驗(yàn)難以兼顧。

為了改善數(shù)據(jù)結(jié)構(gòu)課程教學(xué)質(zhì)量，課題組以實(shí)驗(yàn)教學(xué)為突破口，進(jìn)行了積極有益的探索，實(shí)現(xiàn)了各個(gè)層次的學(xué)生都有收獲的實(shí)驗(yàn)教學(xué)。以尊重學(xué)生個(gè)體差異性為前提，力求使學(xué)生發(fā)揮各自的潛能，取得更好的學(xué)習(xí)效果，達(dá)到提升整體教學(xué)水平的目的。

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

1 傳統(tǒng)實(shí)驗(yàn)教學(xué)中存在的問題

傳統(tǒng)的實(shí)驗(yàn)教學(xué)模式下，教師在課堂上提前將實(shí)驗(yàn)內(nèi)容布置給學(xué)生，所有的學(xué)生做同樣的實(shí)驗(yàn)題目，提交的時(shí)間和實(shí)驗(yàn)結(jié)果參差不齊。這導(dǎo)致實(shí)驗(yàn)教學(xué)面臨如下問題。

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

⑵ 相同的實(shí)驗(yàn)題目難以科學(xué)地量化和評(píng)價(jià)教學(xué)效果。傳統(tǒng)的數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)課程的考核方式多為：平時(shí)實(shí)驗(yàn)態(tài)度+編程能力+實(shí)驗(yàn)結(jié)果+實(shí)驗(yàn)報(bào)告。但是相同的實(shí)驗(yàn)題目導(dǎo)致實(shí)驗(yàn)結(jié)果和實(shí)驗(yàn)報(bào)告內(nèi)容也基本相同。對(duì)于實(shí)驗(yàn)態(tài)度良好的學(xué)生，基本只能靠編程能力的評(píng)判來區(qū)分學(xué)習(xí)成績(jī)了。而對(duì)編程能力的評(píng)判基本是看代碼提交時(shí)間、運(yùn)行時(shí)間、占用內(nèi)存、以及代碼編寫規(guī)范程度。而這部分內(nèi)容只占總分的一部分，結(jié)果就是學(xué)生的考核分?jǐn)?shù)相對(duì)集中，難以對(duì)課程教學(xué)效果給出科學(xué)評(píng)價(jià)。

⑶ 對(duì)每一屆學(xué)生都用相同的實(shí)驗(yàn)內(nèi)容，影響學(xué)生學(xué)習(xí)的積極性。編程基礎(chǔ)好的同學(xué)完成得快，課堂時(shí)間就能順利完成;而大多數(shù)同學(xué)還需要課余時(shí)間來完成。這樣不能激起學(xué)生的學(xué)習(xí)興趣，對(duì)不同層次的學(xué)生起不到因材施教的效果。加上原有的實(shí)驗(yàn)考核方式缺乏精準(zhǔn)性，對(duì)同學(xué)間的抄襲、互聯(lián)網(wǎng)上的抄襲甄別困難，不僅影響學(xué)生學(xué)習(xí)的積極性，也達(dá)不到教學(xué)目標(biāo)。

⑷ 實(shí)驗(yàn)內(nèi)容的設(shè)置難以達(dá)到培養(yǎng)學(xué)生的工程實(shí)踐能力的能力目標(biāo)。傳統(tǒng)的數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)題目基本上是針對(duì)某一章的課堂講授內(nèi)容設(shè)計(jì)的，學(xué)生只需應(yīng)用該部分的知識(shí)即可完成實(shí)驗(yàn)題目，不需要思考是否還有其他的解決方案，更談不上選擇最優(yōu)的方案來解決問題，無法培養(yǎng)學(xué)生的工程實(shí)踐能力，難以達(dá)到課程設(shè)置的能力目標(biāo)[5]。

總之，實(shí)驗(yàn)題目的單一化、統(tǒng)一化是導(dǎo)致上述實(shí)驗(yàn)教學(xué)問題的主要根源。鑒于此，將不同層次的實(shí)驗(yàn)題目匯聚在一起，由淺入深，構(gòu)建一個(gè)用于數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)教學(xué)的實(shí)驗(yàn)題集，是解決問題的一個(gè)方法。課題組針對(duì)ACM競(jìng)賽的題目，有選擇性地匯聚成一個(gè)實(shí)驗(yàn)題集，用于數(shù)據(jù)結(jié)構(gòu)的實(shí)驗(yàn)教學(xué)中，從而改革了傳統(tǒng)的實(shí)驗(yàn)教學(xué)模式，激發(fā)了學(xué)生的積極性，使不同層次的學(xué)生都能有所收獲，也達(dá)到了因材施教的效果。

2 基于ACM競(jìng)賽的數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)課程改革

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

2.1 實(shí)驗(yàn)內(nèi)容分級(jí)，實(shí)驗(yàn)題目靈活化，多樣化

首先我們將實(shí)驗(yàn)內(nèi)容分級(jí)，分成初級(jí)（單一算法的練習(xí)）、中級(jí)（需要用算法解決實(shí)際問題）和高級(jí)（結(jié)合若干算法來解決一個(gè)較大規(guī)模的問題）題目。學(xué)生可以根據(jù)自身情況選擇不同級(jí)別的題型和題目數(shù)量來完成。這樣可以滿足學(xué)生學(xué)習(xí)過程中不同層次的需求，充分調(diào)動(dòng)他們學(xué)習(xí)的主動(dòng)性和積極性。除此之外，很多實(shí)際問題是有多解的，這樣的實(shí)驗(yàn)題目充分激發(fā)了學(xué)生的學(xué)習(xí)主動(dòng)性和積極性，將被動(dòng)學(xué)習(xí)化為主動(dòng)學(xué)習(xí)，更好地達(dá)到實(shí)驗(yàn)教學(xué)目的。

2.2 將傳統(tǒng)的ACM競(jìng)賽題目改編為實(shí)驗(yàn)題目

根據(jù)ACM競(jìng)賽題目的特點(diǎn)，我們從中精心挑選相關(guān)題目，或?qū)⒃袛?shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)題目改造為ACM競(jìng)賽題目形式，形成了與數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)要求相對(duì)應(yīng)的初、中、高級(jí)實(shí)驗(yàn)題集，將其作為實(shí)驗(yàn)題目。將傳統(tǒng)的以算法為主線的實(shí)驗(yàn)教學(xué)體系改為以問題為主線的實(shí)驗(yàn)教學(xué)體系，通過具體問題描述給出題目，讓學(xué)生自主選擇合理的數(shù)據(jù)結(jié)構(gòu)和算法進(jìn)行求解，加深學(xué)生對(duì)基礎(chǔ)知識(shí)和算法的深入理解，以“學(xué)以致用”的方式來牢固掌握所學(xué)知識(shí)。

2.3 考核方式靈活，綜合評(píng)定學(xué)生

學(xué)生對(duì)分?jǐn)?shù)非常敏感，恰當(dāng)?shù)膶?shí)驗(yàn)成績(jī)?cè)u(píng)分標(biāo)準(zhǔn)有利于激發(fā)學(xué)生的學(xué)習(xí)動(dòng)力，反之有可能會(huì)挫傷其學(xué)習(xí)積極性。將學(xué)生提交的程序由ACM在線測(cè)評(píng)系統(tǒng)進(jìn)行評(píng)測(cè)，不僅考察其正確性，還對(duì)代碼的運(yùn)行時(shí)間、占用內(nèi)存、輸入輸出格式加以限制等，可以綜合考察學(xué)生對(duì)算法的靈活運(yùn)用。

我校的數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)課已經(jīng)與理論課拆分，成為一門獨(dú)立課程，而且比原來增加了4學(xué)時(shí)。共計(jì)12次課，24學(xué)時(shí)，滿分100分。實(shí)驗(yàn)評(píng)分標(biāo)準(zhǔn)的制訂，需考慮對(duì)學(xué)生具有激勵(lì)作用，經(jīng)過新的教學(xué)模式的探索，課題組決定采用以完成實(shí)驗(yàn)題目為主的評(píng)分方式。

⑴ 對(duì)實(shí)驗(yàn)題目的完成占總分的90%，實(shí)驗(yàn)態(tài)度和實(shí)驗(yàn)報(bào)告占10%。

⑵ 完成初、中、高級(jí)題目的分?jǐn)?shù)占比是1：2：4;即完成一個(gè)高級(jí)題相當(dāng)于完成兩個(gè)中級(jí)題，完成一個(gè)中級(jí)題相當(dāng)于完成兩個(gè)初級(jí)題。

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

該評(píng)分標(biāo)準(zhǔn)為學(xué)生設(shè)立較低的及格目標(biāo)，使學(xué)生更容易進(jìn)入完成實(shí)驗(yàn)題目的狀態(tài);其次完成6個(gè)高級(jí)實(shí)驗(yàn)題目就能拿滿分，更能激發(fā)學(xué)生挑戰(zhàn)更高級(jí)別實(shí)驗(yàn)任務(wù)的動(dòng)力。同時(shí)即使12次實(shí)驗(yàn)課中完成12個(gè)初級(jí)實(shí)驗(yàn)題目，成績(jī)也只能是及格多一點(diǎn)，要想取得好成績(jī)還遠(yuǎn)遠(yuǎn)不夠。從而確保了該評(píng)分標(biāo)準(zhǔn)在總體上不降低實(shí)驗(yàn)教學(xué)的要求。這樣，不僅在成績(jī)?cè)u(píng)定上做到了客觀、公正，還更好地發(fā)掘了學(xué)生的創(chuàng)新能力，提高他們對(duì)知識(shí)點(diǎn)的掌握程度。

2.4 加強(qiáng)師生之間、學(xué)生之間的有益互動(dòng)，培養(yǎng)良好的團(tuán)隊(duì)合作精神

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

3 結(jié)束語

將ACM競(jìng)賽的題目選編成一個(gè)實(shí)驗(yàn)題集，引入到數(shù)據(jù)結(jié)構(gòu)的實(shí)驗(yàn)教學(xué)中，一改傳統(tǒng)實(shí)驗(yàn)授課全員實(shí)驗(yàn)題目統(tǒng)一模式為獨(dú)立選擇實(shí)驗(yàn)題目模式，不同層次的學(xué)生采用不同的實(shí)驗(yàn)題目，使不同層次的學(xué)生都能得到提高。實(shí)驗(yàn)題目選擇個(gè)性化，將全體授課與個(gè)別指導(dǎo)相結(jié)合，可激發(fā)學(xué)生的學(xué)習(xí)熱情和潛力，提高學(xué)生自主學(xué)習(xí)能力、創(chuàng)新能力，也有利于團(tuán)隊(duì)精神的培養(yǎng)。實(shí)驗(yàn)課引入相對(duì)自動(dòng)化的實(shí)驗(yàn)考核方式，減輕了教師負(fù)擔(dān)，使教師把更多精力投入到輔導(dǎo)學(xué)生方面。這種基于ACM競(jìng)賽的數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)教學(xué)方式也有助于培養(yǎng)學(xué)生的工程實(shí)踐能力、團(tuán)隊(duì)合作精神和協(xié)同能力。今后，我們還將繼續(xù)將教學(xué)改革深入下去，以期培養(yǎng)高水平、高素質(zhì)的優(yōu)秀創(chuàng)新人才。

參考文獻(xiàn)（References）：

[1] 張安勤，田秀霞等.數(shù)據(jù)驅(qū)動(dòng)的數(shù)據(jù)結(jié)構(gòu)課程案例設(shè)計(jì)研究與實(shí)踐[J].軟件工程，2020.23（4）：54-56

[2] 劉忠民，李廣瑞.數(shù)據(jù)結(jié)構(gòu)課程實(shí)驗(yàn)分層教學(xué)的探索和實(shí)踐[J].計(jì)算機(jī)教育，2018.6：128-130

[3] 韓建民，鐘發(fā)榮等.基于ACM-ICPC訓(xùn)練模式的數(shù)據(jù)結(jié)構(gòu)實(shí)踐教學(xué)探索[J].計(jì)算機(jī)教育，2013.5：103-107

[4] 李涵，吳秋新.基于ACM模式的數(shù)據(jù)結(jié)構(gòu)實(shí)踐教學(xué)改革的探索與思考[J].山東青年，2012.9：39-40，42

[5] 楊彬，王青正.工程教育專業(yè)認(rèn)證背景下的數(shù)據(jù)結(jié)構(gòu)教學(xué)改革[J].計(jì)算機(jī)時(shí)代，2020.4：61-63，67