多层次的“数据结构”实践教学模式探讨

孙爱东 杨秋妹 肖媚燕

摘要:“数据结构”的实践教学不仅可以帮助学生巩固和加深对课程内容的理解,更重要的是可以进一步锻炼程序设计的技能,培养学生运用知识的能力,并初步感受软件开发的规范和培养团队合作精神。本文针对实践教学环节中存在的问题,设计与实现了由简单到复杂、由单一到综合的多层次实践教学模式。

关键词:数据结构;实践教学;多层次

中图分类号: 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.