面向问题求解的实践教学模式

摘要：“算法与数据结构”是计算机科学与技术专业重要的专业基础课，是一门理论性与实践性都很强的课程。针对多年课程教学过程中发现学生普遍认为课程内容过于抽象，学习兴趣不大，学完后不仅理论基础不扎实，而且分析和解决实际问题的能力差的状况，提出面向问题求解的实践教学模式，并在近三年的课程教学中加以实践，取得明显效果。

关键词：数据结构；算法；问题求解；实践教学；改革

中图分类号：G 文献标识码：B

文章编号：1672-5913（2007）07-0029-03

1 “算法与数据结构”课程的性质与特点

“算法与数据结构”是计算机科学与技术专业重要的专业基础课，是非数值计算程序设计的基础，也是设计和实现各种应用软件的重要基础。本课程主要以抽象数据类型为主线，研究常用的数据结构的逻辑结构、存储结构及其所支持的运算操作；研究解决常用实际问题的经典算法；学习基本的算法分析方法，对算法进行时间复杂度和空间复杂度的分析。为学生后续课程的学习以及进行计算机软件的设计和开发打下坚实的基础。

2 传统课程教学存在的问题及原因

“算法与数据结构”是一门理论性和实践性都很强的课程。在传统的课程教学过程中，授课教师大多重理论而轻实践，而且由于该课程内容较抽象，不好讲解，若非精心准备，很难取得好的课堂教学效果。对学生而言，虽然也知道该课程的重要性，但枯燥的课堂教学实在无法激发他们的学习兴趣，课后的上机实践也因目标不明确而几乎流于形式。

近几年各个学校都在进行该课程的教学改革，其中很重要的一个改革就是实践教学改革，提倡要加强实践环节的训练，在每个章节的理论教学后要求学生完成若干上机实验作业，想由此达到提高学生实践能力，深化理论教学的目的。然而，由于以下几个主要原因，使得改革的辐射面太窄，少数上进的学生从中受益，大部分学生却收效甚微，与实践教学改革的既定目标相差甚远。

（1）实验作业较少面向实际问题，无法激起学生的学习兴趣；

（2）实验作业要求不够明确，学生无法验证所完成实践作业的正确性和优劣性；

（3）教学过程中缺少合适的监督机制和奖惩制度，大多学生由于程序设计基本功不扎实，当无法完成任务时采取“copy”方式来敷衍了事。

3 面向问题求解的实践教学模式

针对传统教学存在的问题，课程教学组经过调研、分析后决定开展课程实践教学改革，构建面向问题求解的实践教学模式，以实际问题求解为主线索来组织和设计实践教学内容，增加设计型实验和综合型实验，锻炼学生综合运用所学理论知识进行问题分析、设计和实现的能力，在实践中强化创新意识。

为了切实有效地推进《算法与数据结构》实践教学改革，我们专门开发了课程的网络教学系统（），用于辅助课堂教学和实践教学。该系统可实现作业、提交、在线评测、成绩公布、优秀作业评选、疑难解答等多项功能。

面向问题求解的实践教学模式主要包括以下几个方面：

3.1 面向实际问题，精心设计实践教学内容

以问题求解为主线索，针对每个教学单元的重要知识点，精心设计8~15题有代表性、难易搭配的上机实验作业，这些作业包括仅要求对数据结构和算法进行实现的验证型实验，以及要求运用所学理论知识设计求解典型或有趣实际问题的设计型实验和综合型实验。这些实验作业将以随机的方式分给学生，每位学生必须在规定的时间内独立完成2~3题。在期中和期末考试时还设计两套上机实验综合测试题，用于检查学生的综合运用能力。

3.2 作业自动评测

为了对大量的学生实验作业进行有效的评价，我们开发作业自动评测系统，采取离线和在线作业自动评测相结合。先用离线作业自动评测系统测试学生提交的作业，测出每次作业的成绩，并在网站上公布评测结果，平时作业成绩将是期末成绩的重要组成部分。成绩公布后，开放在线作业自动评测系统，作业成绩不理想的学生可再次改进自己的作业，并利用在线评测系统进行评测。

3.3 解题报告交流

针对每个教学单元的实验作业，我们都开展优秀解题报告交流活动，把每道作业成绩前三名的学生定为优秀作业候选人，并要求他们准备解题报告。解题报告的内容主要包括：问题的思考过程、问题的数学化、数据结构和算法设计策略的选取、算法正确性的证明、算法复杂性的分析，算法的优化及改进、程序的设计与实现等。这些解题报告将在课程讨论课上展示，从而实现作业资源的共享和优秀解题思路的交流。

3.4 优秀作业评选

我们对每道实验作业题都进行了优秀作业的评选。讨论课之后，优秀作业候选人的解题报告和源程序都放到课程网站上，全体同学都必须进行投票。最后由任课教师综合作业成绩、报告情况、解决问题算法的复杂性和创新性等几个方面来确定每道题的优秀作业，并对评上优秀作业的同学给予作业成绩双倍的奖励。

除此之外，我们还开发雷同作业检测系统，建立“雷同作业黑名单”。对进入黑名单的学生采取警告、扣分等方式，督促他们独立完成实验作业。

4 实践教学改革的成效

面向问题求解的实践教学模式先后在计算机科学与技术专业2003级、2004级全体学生和学校综合班2004级学生的“算法与数据结构”课程教学中得以实施，并取得了显著的效果。

4.1 激发了学生的学习兴趣

利用所学的数据结构和算法解决有趣的实际问题，在很大程度上激发了学生的学习兴趣和主动性。如利用循环链表解决猴子选大王问题，利用栈帮助小鼠走出迷宫，利用Huffman算法设计文件解压缩软件和利用图的最短路径算法寻找换车次数最少的公交线路问题、套汇问题等。

4.2 深化理论教学

4.2.1 典型问题的设计，使抽象的数据结构形象化

在组织和设计实践教学内容时，尽量设计与每种数据结构的逻辑模型相似的经典问题作为学生实验作业的一部分。如要求学生用表求解多项式的相关问题；利用栈实现算术表达式求值问题；利用队列模拟机场飞行跑道上飞机的调度；利用图的最小生成树理论设计具有最小耗费的通信网络；利用堆实现圆形操场的石子合并问题等等。这些经典问题便于学生从直观上理解各种数据结构的本质特征。

4.2.2 一题多解，便于学生比较不同数据结构和算法的优缺点

在组织和设计实践教学内容时，让同一个问题在不同教学单元多次出现，如等价类问题可看做是线性表的应用，也是并查集应用的一个经典例子；迷宫问题既可用栈来求解，也可用队列来求解；欧拉回路问题也分别出现在线性表和图这两个教学单元的实践教学中。

以上两种手段的实施，在很大程度上使学生加深对课堂教学内容的理解，达到通过实践教学深化理论教学的目的。

4.3 提高了学生分析和解决实际问题的能力

从近三年的改革实践来看，大部分同学经过一个学期的学习与训练，已经具备在一定的时间内独立解决问题的能力，能够在规定的时间内选择合适的数据结构和算法设计策略，并在计算机上编程实现。我校计算机专业学生在各类与程序设计相关的学科竞赛中频获佳绩。令人兴奋的是，我校ACM/ICPC代表队在2005年亚洲区杭州赛区的比赛中喜获第6名，并在第30届ACM国际大学生程序设计竞赛全球总决赛中获得第39名。这些都得益于该课程实践教学改革的直接影响。

5 结束语

实践教学考试改革的实施深化了课堂理论改革，提高了人才培养质量，但同时无疑给老师增加了许多额外工作量。为了保证改革的顺利进行，必须制定相应的激励政策，充分调动广大教师的积极性和主动性。

参考文献：

[1] 刘亚波，刘大有，高滢.以实验教学深化“数据结构”理论教学[J]. 吉林大学学报（信息科学版），2005，23（8）：135-137.

[2] 殷人昆，邓俊辉.清华大学“数据结构”精品课程介绍[J]. 计算机教育，2006，(5):20-22.

[3] 廖明宏,等，哈尔滨工业大学“数据结构与算法”精品课程介绍[J]. 计算机教育，2006，(5):17-19.

收稿日期：2007-1-16

作者简介：吴英杰（1979-），男，福建安溪人，助教，硕士，研究方向为数据结构，算法的设计与分析。