信息科学与工学院计算机教学试验中心实验教学大纲《计算机算法分析》课程一、制定实验教学大纲依据本大纲根据「计算机算法分析教学大纲」对学生实验能力培养要求而制定。二、本课程实验教学的地位和作用计算机算法分析课程是一门比较抽象的课程，同时又是一门实验性非常强的课程。本课程实验是巩固和补充课堂讲授的理论知识的必要环节，通过实验，培养学生编写较大程序的能力和运用所学理论知识解决问题的能力，为学好后续课程，从事专业技术工作和科学研究打下必要基础。三、本课程实验教学基本理论与技术内容图的基本概念；图的应用；图的特性；抽象数据类型Graph和Digraph；类的定义。图的搜索算法：BFS（宽度优先搜索）和DFS（深度优先搜索）。应用：寻找路径；连通图及其构件；生成树。图是数据结构中比较复杂、比较难懂的部分，又是与生产、生活密切相关的。通过本实验，将所学数据结构知识连贯起来，头文件经过调试通过后，可以作为实用软件提供给他人使用。四、学生应达到的实验能力标准1．学习使用软件开发工具VisualC++或BorlandC++。2．四次实验内容相互间有着紧密联系，最终实现一个软件包，即用邻接压缩表描述的加权有向图头文件。3．通过本实验，进一步加深对用邻接矩阵和链表实现的图描述的认识。五、学时、教学文件及教学形式学时：本课程总学时为54学时，其中实验9学时，占总学时16.7％。教学文件：（美）SartajSahni著《数据结构、算法与应用─C++语言描述》。实验报告自拟。教学形式：本课程实验为验证性实验。要求学生课前预习实验指导书，指导教师作针对性指导，具体实验步骤和结果分析由学生独立完成。六、实验考试方法与成绩评定根据学生的实验预习、实验纪律、实验动手能力及实验报告结果，进行综合评定，给出A、B、C。七、实验项目、适用专业及学时分配序号实验项目实验学时实验类型实验类别适用专业及要求信息与计算科学1设计一个C++类PackedAdjGraph，用邻接压缩表描述无向图，从LinearList类中派生此类3验证专业必修2设计一个C++类PackedAdjWGraph，用邻接压缩表描述加权无向图，从LinearList类中派生此类2验证专业必修3设计一个C++类PackedAdjDiGraph，用邻接压缩表描述有向图，从LinearList类中派生此类2验证专业必修4设计一个C++类PackedAdjWDiGraph，用邻接压缩表描述加权有向图，从LinearList类中派生此类2验证专业必修八、本课程实验用主要仪器设备及仪表微机及相应的C++编程环境。