“数据结构”综合性课程设计教学探索与实践摘要：本文针对“数据结构”课程的传统教学方法存在的问题，就综合性课程设计的内容选择、实施方法与激励手段等方面进行了一系列的改革探索。 关键词本文来自：计算机毕业网 ：数据结构；课程设计；启发式教学1 引言 “数据结构”作为实践性很强的计算机专业的基础课，教学中必然离不开实践。针对数据结构的课程设计实践不仅可以帮助学生巩固和加深对课程内容的理解，更重要的是可以进一步锻炼程序设计的技能，并初步感受软件开发的规范，更能全面培养学生综合运用知识的能力、文献检索与分析能力、工程化能力、进行研究性学习的能力、创新能力以及团队合作的能力等。本文是作者所在教学团队八年来的课程设计实践小结，介绍了在“数据结构”综合性课程设计的内容选择、实施方法与激励手段等方面进行的一系列改革探索。 2 传统教学方法存在的问题及解决思路 数据结构的课程实践可分为一般性实验和综合性课程设计。在传统的课程教学中，往往采用一般性实验作为课程实践的主要内容，即布置针对本次课堂教学内容的小型练习题，让学生独立完成程序设计与实现。这样的实践主要存在两方面问题： 第一，练习题所需要用到的知识点就是课堂教学刚讲授过的内容，学生只要直接拿来用就可以，不需要自己去考虑各种可能的解决方案并找到最合适的方法。这种实践是验证性的，比较简单直接，学生受到的锻炼相对较少。 第二，学生独立完成小型程序，虽然可以在一定程度上锻炼编程能力，但这个锻炼的层次和涉及面都比较窄。现代软件开发的规模，使得团队合作在大多数情况下成为必须。而且部分数据结构只有在处理大规模输入的复杂问题时才能体现出优势，编写小型程序很难使学生真正认识到该数据结构存在的意义。 针对上述问题，我们在设计较大规模的综合性课程设计时就必须注意两个方面： 第一，课程设计题目覆盖的知识点应尽可能避免单一，要采用启发式的设计思路，引导学生围绕课程设计目标，通过查找与分析有关参考资料，进行探究式的学习，激发创造的意识和能力。所以，在题目设计和实施中，不应该只是“手把手”地教，要给学生留出发挥想象力和创造力的空间。 第二，题目的规模应充分大，并且努力使学生对规范性的软件开发有初步体验，在一定程度上使得学生的工程化能力和团队合作能力得到锻炼。 而上述两方面的考虑若要取得真正好的效果，还必须有一套行之有效的激励机制，既可以公平地判定每个学生作为个体的能力，又可以鼓励团队精神，同时还可以鼓励学生开拓创新思维，主动进行研究性学习。 3 课程设计的内容选择、实施方法与激励手段 3.1 内容选择 综合性课程设计应强调知识的综合运用，锻炼学生对复杂问题进行分析与求解的能力，所以在选择内容时可以从以下三方面考虑： 第一，题目应避免涉及单一知识点。例如“迷宫问题” ，即输入一个迷宫的布局，要求找到一条走出迷宫的路径并用图形界面显示。学生可以选择用不同的数据结构表示迷宫以及移动方向，可以选择用深度优先或者宽度优先搜索的算法来得到路径，同时还锻炼了对图形界面的编程技巧的掌握。又例如“宇宙旅行” ，即给定两星球间各个中转空间站的临时客流容量，求终点星球接待站的总客流容量。此题目的解法主要涉及网络流算法；在每一步修正流量时，可以选择剩余图中从起点到终点的最短路径，则又涉及到单源最短路径算法；最后为了提高查找空间站名称的效率，可以采用散列表进行名称映射。 第二，为锻炼学生进行研究性学习的能力，可设计算法效率分析比较类型的题目。例如比较普通的二叉搜索树、平衡搜索树和伸展树的插入与删除操作效率，要求通过实验取得三者的实际运行时间，绘出三者复杂度函数的曲线，分析比较它们的效率并给出证明等等。 第三，采用启发式教学思路，设计有多种解法的题目，可以给学生留出发挥想享力和创造力的空间，锻炼学生灵活运用知识分析问题和解决问题的能力。例如“熊猫烧香” ，即以著名病毒“熊猫烧香”的传播规律为背景，要求计算整个网络被各种病毒变种感染的情况。题目可以简单地用广度优先搜索解决，但是效率比较低。巧妙一点的方法可以将求单源最短路径的 Dijkstra 算法略做修改，得到效率明显提高的解决方案。更快的算法则是利用并查集。教师可以通过设计不同层次的测试数据来区分不同效率的算法，鼓励学生自己去尝试各种方案，找出最有效的解决办法。 在内容选择方面，我们还建议参考历届 ACM 国际大学生程序设计竞赛的题目，该竞赛特别强调考察参赛选手对各种算法的应用能力，题目的综合性较强，非常适合辅助学生学习体会数据结构的妙用。浙江大学建设有全球著名的程序设计竞赛练习网站(http:/acm.zju.edu.cn/)，提供在线自动裁判系统，简称 ZOJ，目前拥有各类竞赛练习题目近 2000 道，为数据结构课程设计提供了丰富的题库资源。本课程组设计的多道课程设计题目就取自或改编自该网站的练习题。 3.2 实施方法 综合性课程设计不仅仅是以实现相应的程序为目标，更重要的是培养学生今后从事软件开发所需要的各种能力与素质，包括测试能力和文档写作的能力。因此，在课程设计实施中，我们将学生分成三人小组，分工负责程序编写、测试以及实验报告撰写工作。 一份完整的实验报告至少应包含以下四部分内容： (一)实验内容简介：这一部分需简单介绍题目内容，即该实验到底要做什么。如果涉及明确的算法，最好再简单介绍一下算法产生的背景。 (二)算法说明：这一部分需详细描述解决问题所需要用到的算法和重要的数据结构，即该实验到底应该怎么做。 (三)测试结果：这一部分需根据题目类型设计提供相应的测试方法和结果。对于需要比较不同算法性能优劣的题目，应设计并填写一张性能比较表格，列出不同算法在同一指标下的性能表现。对于需要利用某算法解决某问题的题目，应设计并填写一张测试用例表。每个测试用例应包括测试输入、测试目的、正确输出、实际输出、错误原因等等。 (四)分析与探讨：这一部分除了对测试结果进行分析外，还要求学生不局限于题目要求使用的算法，探讨更多解决问题的途径，或者提出自己的见解，给出改进算法以得到更好结果的建议。 其中第一、二部分以及全文统稿由文档员负责，第三、四部分由测试员负责。整个学期发布的课程设计题目数应该是 3 的倍数，使得每组的三个学生有机会均衡体验三种不同的角色。 3.3 激励手段 大学教育心理学研究表明，学习兴趣通过适当的引导，会引发学生的需要和动机，进一步产生持续不断的兴奋，从而激发积极的行为反应，努力去实现预订目标。而让学生产生浓厚的学习兴趣，就必须建立有效的激励机制。 首先程序员、测试员、文档员的工作难度不同，其工作的分数分配也应不同。例如我们采用 50:30:20 的分配制度，这样只有在三个课程设计中将三种角色分别体验一遍，才有可能得到满分 100。 其次教师应对“分析与探讨”部分特别关注，及时发现并鼓励学生的创新思维。一句简单的鼓励就可能对学生的主动学习热情起到非常大的引导和推动作用。 另外，由于每个学生的能力水平不同，应使组内每个人的成绩相对独立，不依赖于其他组员的表现而得分。例如程序员只要正确完成了自己的程序，且注释充分，就可以得满分；测试员的测试计划和测试用例设计都不依赖于源代码，即使程序员无法提供程序，测试员只要完成了测试计划的设计，对算法进行了理论上的分析，就可以得到满分；文档员的工作相对独立，只要完成了自己负责的章节并将手头所有资料整合为一体，就可以获得满分。这样做的目的是体现评分的公平性，尽量避免能力强的学生为了自己的成绩不受影响而“包办”全组的工作。 当然，分组实验的另一个目的，是锻炼学生的沟通与团队合作能力。这个目的可以通过教师的激励来达到，即教师在点评每道题目的完成情况时，对个别优秀的组提出表扬，而只有三项工作都完美的组，才会获此殊荣。这时学生会在完成了自己工作的情况下，对队友提供一定帮助，以获得团队的荣誉。 4 成果 课程组在浙江大学八年的不断探索和改革取得了良好的成效。最为明显的效果是，学生参与各级程序设计竞赛的积极性逐年增长，从 2001 年 48 队 100 多学生参加首届浙江大学程序设计竞赛，到2007 年 286 队近千名学生参赛，竞赛规模在 7 年中增长迅猛。而浙江大学参加 ACM 国际大学生程序设计竞赛的队伍，在没有常规辅导的情况下，凭借扎实的数据结构基本功，也连年在国际竞赛中取得出色的成绩。 参考文献 1 教育部高等学校计算机科学与技术教学指导委员会. 高等学校计算机科学与技术专业发展战略研究报告暨专业规范(试行)M. 北京:高等教育出版社,2006. 2 何钦铭,冯雁,陈越. 数据结构课程设计M. 杭州:浙江大学出版社,2007. 3 林正范. 大学心理学M. 杭州:浙江大学出版社,2000. 摘要：“计算机图形学”是计算机专业的一门非常重要的基础课程，但在教学中存在很多问题，本文总结了两种结合方式的教学方法，分析和探讨了其在教学中的应用。 关键词：计算机图形学；教学方法；教学与实验 1 引言 “计算机图形学”在计算机科学与技术专业的一门基础课，其课程涉及图形硬件设备、图形系统、交互技术、基本图形生成算法、几何变换、真实感图形生成等内容。在笔者的教学实践当中发现教学过程中普遍存在以下两个问题。 1.1 理论知识掌握方面 由于“计算机图形学”具有较强理论性，部分算法比较抽象不易理解。所以学生在学习的时候很难将抽象算法与具体的三维图像结合起来，经常表现出畏难情绪。 1.2 实践能力培养方面 由于“计算机图形学”课程的教学主要精力放在了图形的基本概念和算法原理的讲解上，上机实践环节滞后；另外，现在大部分的教材中仍然是以 Turbo C 作为上机实习的平台，但是由于 Turbo C 再实际应用中早已不作为开发工具使用，学生并不能够在实验中获得未来就业环境下真是需要掌握的编程知识，需要二次学习才能适应社会的需求。 针对以上问题，给出以下解决方案。 2 理论讲解与具体开发工具的使用相结合 图形通常由点、线、面、体等几何元素和灰度、色彩、线型、线宽等非几何属性组成。如何在计算机中表示图形以及利用计算机进行图形的计算、处理和显示的相关原理与算法，构成了计算机图形学的主要研究内容。目前，大部分计算机图形学教材都是以计算机图形学的基本概念、基本理论、基本原理及经典算法作为主要内容，以丰富学生的基础知识，培养学生的独立研究能力。然而，在微型计算机日益普及的今天，随着计算机科学及技术的发展，出现了很多功能完善的图形软件标准和图形软件，如何利用他们培养学生的学习兴趣，提高实际应用的能力，则是当今教学的重点。 为了能够更加广泛地接触和学习图形软件，笔者在以 Turbo C 语言作为开发工具来介绍基本图元的经典画法的同时，将 OpenGL 引入到计算机图形学的学习中。 OpenGL 是近 10 年来发展起来的一个性能卓越的、通用共享的三维图形标准，已得到广泛应用。OpenGL 提供十分清晰明了的图形函数，所以图形绘制可以通过它的各种函数来实现。OpenGL 具有标准型、稳定性、可扩展性、可缩放性、易用性、可靠性和可移植性等特点。与其他图形程序包相比，OpenGL 应用程序代码行数少，又封装了有关基本硬件的信息，因此在很多领域都得到广泛的应用。 在教学过程中，为了让学生对“计算机图形学”中所讲解的知识能够更好的理解和掌握，可以从三个步骤来进行讲解： 2.1 理论讲解基本概念、原理及算法 理论讲解过程中，我们可以把 OpenGL 与之结合起来。例如：我们在讲解直线的扫描算法时，首先介绍经典的中点绘制直线算法和 Bressman 算法，通过这两个算法的原理的介绍可以使学生了解到在计算机中怎样以像素作为处理单位来实现直线的绘制。然后，我们可以介绍一下 OpenGL 中对直线