基于OJ的《数据结构》探究式实验教学探索

2015-06-07范立新黄龙军唐开山

绍兴文理学院学报(自然科学版) 2015年1期

关键词：数据结构竞赛题目

范立新黄龙军唐开山

(绍兴文理学院计算机系,浙江绍兴312000)

基于OJ的《数据结构》探究式实验教学探索

范立新黄龙军唐开山

(绍兴文理学院计算机系,浙江绍兴312000)

讨论以自主开发的Online Judge(OJ)为实验平台,在数据结构实践教学过程中,引入学习团队和分层次教学,运用探究式教学模式,以OJ上的问题为核心与载体,在课堂内、外的自主探究与合作探究中凸现学生学习的主体性、实践性,提高学生的实践能力,以及改革实验考核方式来提高教学质量.若将这些教学方法融入课程质量标准,可长期保障教学质量.

探究式教学;分层次教学;学习团队;Online Judge;课程质量标准

0 引言

《数据结构》课程是计算机科学与技术专业的核心课程之一,理论性和实践性都很强.《数据结构》课程的理论知识具有内容多、抽象性强等特点,不容易被学生理解和掌握,必须配备实验教学来使学生加深理解和巩固理论知识;而《数据结构》的教学目标就是让学生在扎实掌握理论知识的基础上选择并设计合理的数据结构,应用相关算法去解决问题.在传统的《数据结构》实验教学中,很多学生习惯于从教材或课件中抄写源程序或翻译伪代码,对学生的能力培养作用不大,学生在学完相关知识甚至整门课程后,并不能灵活运用数据结构的知识求解具体问题.郭嵩山、琚生根等人[1]提出以ACM国际大学生程序设计竞赛[1,2](ACM/ ICPC,Association of Computing Machinery International Collegiate Programming Contest)为契机,推进教学改革;陶影[3]认为《数据结构》实验教学应该重视培养算法设计与分析能力;李月军[4]在实践教学中引入程序设计竞赛内容,并将来源于ACM/ICPC的竞赛问题为主要练习题目,但其所用的平台是其他学校的(北京大学),不便于各校进行特色实践教学.贾银江[5]则从目标分层、评价分层、分层教学法等方面讨论数据结构实验的分层次教学,而范立新等人[6]则给出了《高级语言》课程用OJ平台进行探究式教学的探索经验.

在绍兴文理学院计算机科学与技术专业的《数据结构》实验教学过程中,以自主开发的Online Judge (在线判题系统[7],简称OJ)为教学平台,激发学生的学习兴趣;建立学习团队进行团队学习,降低学生的畏难情绪;引入分层教学法,对实验内容、实验要求、实验评价进行分层,尽量消除学生的畏难情绪;将探究式教学模式引入并运用到实验教学中,以OJ上的问题为核心和载体,凸现学生在学习过程中的主体性、实践性,注重实验教学过程中的自主探究和合作探究,从而加深学生对理论知识的理解、掌握并提高学生的实践能力和创新能力.

1 数据结构实验内容改革

我们把《数据结构》的实验内容分为基础性实验、提高性实验及综合性实验等三种类型.其中,基础性实验主要涉及线性表、栈与队列、树、图等数据结构及常用查找、排序方法的基本知识及其简单应用,如链表操作、进制转换、二分查找等;提高性实验则要求合理设计数据结构去求解具体问题以及利用数据结构和算法去求解ACM/ICPC竞赛题;综合性实验则需要综合运用多种数据结构求解实际问题,如停车场管理、交通咨询系统、教学计划编制等,这部分内容属于后续课程《数据结构课程设计》的范畴.本文重点讨论以OJ为实验教学平台的基础性实验和提高性实验,这两类实验的实验内容通常以问题的形式由教师预先添加到OJ系统上.

1.1 OJ简介

OJ一般是指在各类大学生程序设计竞赛中用来评测参赛选手的程序的正确性及其时空效率的程序和评测程序所依托的网络环境[7].OJ既可以作为竞赛平台又可以作为实践平台,不同用户可以同时在线提交采用C、C++等程序设计语言编写的源代码,OJ能对所提交源代码进行编译和执行,并通过出题者预先设计的测试数据来检验源代码的正确性[7].对于正确的程序,用户能立即看到成功的状态(Accepted);对于不正确的程序,用户能根据所得到的错误状态提示(如Wrong Answer、Time Limit Exceeded、Memory Limit Exceeded等,其中后两个错误信息可以引导学生考虑所用算法的时间复杂度和空间复杂度),进行程序的修改、调试、重新提交.

绍兴文理学院自主开发的OJ(SXUOJ)中,用户分为“管理员”、“教师”、“学生”等角色.“管理员”或“教师”角色的用户,能够方便地在OJ添加和完善各类问题,主要包括《高级语言》、《数据结构》、《算法分析与设计》等课程相关的题目.利用OJ为平台,教师可以随时查看学生实践的情况,极大地减少了教师作业批改的负担,提高了工作效率和准确性.

SXUOJ每天24小时都开放,为学生提供了开放式的网络教学平台.SXUOJ上的问题是学生探究式学习的核心和载体,“学生”角色的用户拥有自己的独立账号,能针对SXUOJ上的实际问题进行探究,编写、调试、修改、提交程序.以SXUOJ为实践平台,学生能实时得到评测结果和最新排名,学习兴趣得到激发,分析问题和解决问题的能力也得到提高.

1.2 以SXUOJ上的问题为实验内容

数据结构实验的内容都是SXUOJ上的具体问题,SXUOJ上的问题由教师预先添加,且可以动态维护,这些问题构成数据结构实验练习集,分为基础性实验和提高性实验两类,实验内容从实验练习集中选择,两类题目所占的比例约为80%和20%,满足数据结构实验内容的分层.选定实验练习集的一部分作为必做实验,而其余的题目则作为选做题和备选考试题.

基础性实验是常用数据结构及查找、排序方法的基础知识与简单应用.图1所示为任课教师(同时也是实验指导教师)根据所用教材的课后习题添加到SXUOJ中的线性表这一章的部分问题,这些问题中的一部分作为数据结构的作业题目,一部分可以作为数据结构实验的基础性实验题目.

图1 部分基础性实验题目

提高性实验题主要由两部分构成:一部分来自ACM/ICPC竞赛题目,包括浙江省大学生程序设计竞赛真题、北京大学OJ(POJ)、浙江大学OJ(ZOJ)、杭州电子科技大学OJ(HDUOJ)等国内知名OJ上提供的其他真题.但省级以上的程序设计竞赛题目中直接使用数据结构知识进行求解的题目数量不多,因此,提高性实验题的第二个来源则是绍兴文理学院每年的程序设计竞赛题目.出于教学和竞赛有机结合的目的,任课教师往往有意在校赛中提供1～2道和数据结构相关的赛题,这些赛题也是提高性实验题的主要组成部分.如表1所示为SXUOJ上数据结构实验的部分提高性实验题目.

表1 部分提高性实验题目

2 数据结构实验探究式教学

探究式教学[8]是以探究为主的教学,注重探讨与研究.探究式教学在教师引导的基础上,强调学生的主体地位,突出学生的自主能力.探究式教学的基本操作程序可分为四步[8]:(1)激趣引题,自学探究;(2)解疑导拨,合作探究;(3)明理强化,实践探究;(4)激励评价,引伸探究.

2.1 数据结构实验探究式教学方法

数据结构实验探究式教学首先需要构建以OJ为主要平台的全天候开放的教学环境并完善OJ的相关问题,同时建立教学论坛方便交流、讨论;然后,把OJ上的问题作为核心和载体,以学生为主体进行探索、研究.在开放的网络环境下,学生既可以在课堂内又可以在课堂外进行探究式学习.数据结构实验的课堂探究式教学的主要过程如下:

(1)设置激趣问题,引导自主探究

教师以OJ上的具体问题(激趣问题)进行问题驱动,激发学生的学习兴趣,刺激学生进行自主探究.学生在阅读实验题目后,思考求解方法,查阅、整理资料.当教师发现学生的自主探究遇到阻碍时,进行适当的引导.

所选激趣问题可以是ACM程序设计竞赛相关的题目、有趣的实际问题(如六度分离、迷宫求解等).由于竞赛题目属于提高性实验,难度较大,会使程序设计能力一般的学生产生畏难情绪;对于这类学生,可以不要求完成提高性实验,即在教学要求上实现分层,引导这类学生的题目可以是简单的应用性问题.

(2)引入学习团队,强调合作探究

探究式教学强调合作探究,既包括师生之间的合作探究,又包括学生之间的合作探究.为便于学生之间在实验教学的课堂内外进行合作探究,参照ACM/ICPC参赛选手组队参赛的形式,每三个学生(根据编程能力强弱及学生特点进行搭配)组建一个学习团队,队长具有较强的编程能力和较好的管理能力.对于有一定难度的问题,可以通过学习团队内部甚至学习团队之间的讨论、交流及相互学习,提高探究式学习的效率.对于学生求解过程中所遇到的问题,可以通过自主探究、学生之间的合作探究寻求解决方案,也可以通过教师适时点拨、师生之间的合作探究解决.对于同一个问题,求解的方法可以各不相同,例如“六度分离”可以考虑采用Floyd算法、Dijkstra算法、深度/广度优先搜索等方法求解.学习团队内部、学习团队之间可以交流、讨论各自的想法、结论,合作探究;教师适时参与讨论、交流,为学生解惑并引导探究方向.

(3)理顺探究思路,实现实践探究

实践探究是对探究效果的检验[8],是巩固、扩大知识的过程,也是吸收、内化知识[8]为能力的过程.通过自主探究和合作探究,学生深入理解了相关知识,理顺了思路.这样,学生就可以编写程序求解激趣问题及OJ上相关的同类问题,进行实践探究,巩固、扩展并运用知识.如果学生在实践探究过程中遇到新的困惑,可以就所遇困惑作进一步的自主探究和合作探究.

(4)自我总结评价,提升探究效果

在大部分学生基本完成实践探究之后,对实验进行总结和评价.学生或学习团队整理出的总结报告,包括实践经验与收获、学习团队成员贡献率(作为考核中合作探究得分的依据)等.评价包括自我评价,其他学生或学习团队的评价,教师评价.教师进行必要的总结,布置若干课外自主实验题目,以巩固探究效果;通过布置ACM程序设计竞赛题目,引导学有余力且有志参加各类ACM程序设计竞赛的学生进一步探究.例如课内完成问题“六度分离”的探究式教学后,教师可以布置若干设计、应用“图”数据结构的题目(可以在SXUOJ、ZOJ、HDUOJ、POJ等不同OJ上),供学生进一步探究式学习.

2.2 数据结构实验探究式教学效果

我们对三个班级的数据结构实验课程进行了对比,其中:A班总人数35人,进行了教学模式改革试点;B班总人数32人,未引入分层教学法和学习团队,属于对照平行班;C班总人数42人,仅引入OJ作为教学平台且未进行过程考核.这三个班在SXUOJ上的实验情况对比如表2所示,由表2可见,通过教学模式改革,学生的学习兴趣、积极性、实践能力等各方面都得到较大的提高,体现出数据结构实验教学模式改革的初步成效.

表2 计算机121班与计算机122班、111班OJ实验情况对比表

基于OJ的数据结构实验探究式教学,学生应用数据结构知识解决OJ上的具体问题,体会到所学知识和所编程序的价值,激发了学生的学习兴趣;成功解题后能得到Accepted的反馈信息,增强了学生的自信心和成功感.分层次教学与学习团队的引入,尽量消除了学生的畏难情绪.以OJ为实践平台,有利于培养学生的实践动手能力和创新能力,有利于培养学生综合运用所学知识解决实际问题的能力.数据结构实验探究式教学以学生为主体,使学生从被动学习转变为主动学习,调动了学生的学习积极性.学生在学习过程中进行自主探究和合作探究,培养了学生的探索、研究的精神和团队合作精神.

3 数据结构实验考核评价改革探索

在传统的数据结构实验考核中,教师主要按学生的实验报告评定实验成绩,这种考核方式,对学生来说没有压力,实验报告中程序代码抄袭现象严重,另外,考核成绩存在人为因素[4],导致成绩不够公正.因此,我们的数据结构实验考核将不再采用单纯的纸质实验报告的形式.

在数据结构实验教学中运用探究式教学,必须逐步建立起完善的评价与管理机制,才能保证教学质量.数据结构实验的考核宜用实验报告和上机考试相结合的形式,而且必须强调过程考核.实验的总评成绩=上机考试得分×40%+实验报告成绩×20%+过程考核成绩×40%.

上机考试可在局域网内的OJ系统上进行,每个学生独立进行考试;考试题共10题,其中,40%选自要求做的基础性实验原题(C类题),40%为基础性实验题目的改编及实验题集中的备选考题(B类题), 20%选自实验题集的提高性实验题目(A类题,不一定是要求做的实验原题);学生每成功求解一道题得20分,最高解题得分为100分;根据学生解出的题包含A、B、C类题的情况确定权重系数β,所解题仅含C类题时β=0.8,所解题含B、C类题时β=0.9,所解题含A类题时β=1,最终上机考试得分为解题得分乘以权重系数β.权重系数的使用,体现出了评价方面的分层.

要求上交的实验报告共2份,全部是基于学生在OJ上成功求解的实验题目,主要目的是促使学生练习并学会撰写实验报告,为学生撰写后续的数据结构课程设计报告、软件开发文档打下基础.

过程考核成绩=上机测验得分×40%+进步排行榜得分×30%+合作探究得分×30%.上机测验的形式与上机考试相同,题目选自基础性实验,要求在一堂课(45分钟)内进行求解,正确完成1道即可获得该次测验的分数,共进行3次.数据结构实验安排为16周,总课时为32课时,每周2课时.为便于检查学生实验情况,可通过网站提供的查询功能,每2周统计一次学生的实验完成情况,推出8期进步排行榜,综合8期的上榜情况进行评分.合作探究得分中学习团队的队长及其他队员评定的分数占80%,教师评定的分数占20%.

对于在教学过程中表现优异的学生,特别是提高性实验完成情况好的学生,则考虑选入绍兴文理学院程序设计竞赛集训队,将有机会参加各类ACM程序设计竞赛,而且在考核成绩中给予一定的奖励分.为了避免在平时的实验过程中出现直接拷贝他人程序并提交的现象,我们引入惩罚机制,在考核成绩中进行较大力度的罚分.这种考核方式,要求学生认真地完成实验要求,深入地理解算法知识,熟练地编写算法实现的代码,能提高学生分析、解决具体问题的能力,保证教学质量.

4 结束语

针对传统数据结构实验教学过程中学生学习兴趣不浓、学习积极性不高、实践动手能力不强等情况,我们构建以OJ为主要平台的开放教学环境,在基于OJ的数据结构实验探究式教学过程中,以OJ上问题为载体和核心,对实验内容、实验要求、考核评价进行分层,以学习团队的方式保障探究效果,突出学生的主体地位,激发了学生的学习兴趣和积极性,提高了学生的实践动手能力,培养了学生的团队合作精神,有利于应用型人才培养.以OJ为教学平台,采用探究式教学法,引入学习团队,进行分层教学等改革措施适当调整后也应用于数据结构的理论教学.而将这些有效的方法和措施融入课程质量标准,将对长期保障《数据结构》课程教学质量起到积极的作用.

[1]郭嵩山,王磊,张子臻.ACM/ICPC与创新型IT人才的培养[J].实验室研究与探索,2007,26(12):188 -192+196.

[2]琚生根,廖勇,周刚,etal.ACM竞赛与实验教学创新[J].实验技术与管理,2009,26(05):125-126 +131.

[3]陶影,张斌.数据结构实验教学应重视算法设计与分析能力的培养[J].实验室研究与探索,2008,27 (12):119-122.

[4]李月军,李娟,李英玉.融入ACM/ICPC竞赛内容的数据结构教学改革与实践探讨[J].内蒙古师范大学学报(教育科学版),2012,25(03):137-140.

[5]贾银江,贺莉莉,郑萍.数据结构实验的分层次教学[J].计算机教育,2014,(04):60-62+72.

[6]范立新,黄龙军.利用OJ平台进行探究式教学模式的探索[J].教育教学论坛,2014,(15):216-217.

[7]黄龙军,范立新.合作式教学在高级语言教学中的运用[J].绍兴文理学院学报(教育教学研究),2013, 33(11):17-19.

[8]张崇善.探究式:课堂教学改革之理想选择[J].教育理论与实践,2001,21(11):39-42.

(责任编辑鲁越青)

G642.4

1008-293X(2015)07-0091-05

10.16169/j.issn.1008-293x.k.2015.07.19