BS-datastructureBexperiment-syllabusrequirements.docVIP

PAGE  PAGE 5 《数据结构B》课程实验教学大纲 课程编号：B0300052S课程名称：数据结构B课内总学时：40实验学时：8一、实验课程的性质、目的和任务 性质：本实验课程是非计算机专业的专业基础课《数据结构B》的配套实验。 目的和任务：实验目的：《数据结构B》课程的目标之一是使得学生学会如何从问题出发，分析数据，构造求解问题的数据结构和算法，培养学生进行较复杂程序设计的能力。本课程实践性较强，为实现课程目标，要求学生完成一定数量的上机作业。从而一方面使得学生加深对课内所学的各种数据的逻辑结构、存储表示和运算的方法等基本内容的理解，学习如何运用所学的数据结构和算法知识处理应用问题的方法；另一方面，在程序设计方法、C++语言编程环境以及程序的调试和测试等方面得到必要的训练。 实验任务：1、学习使用面向对象分析方法，分析问题空间中存在哪些类，了解这些类之间的关系。2、使用面向对象设计方法，将系统中存在的各个类合理组织成类层次结构，并明确定义各个类。确定类的主要数据结构和外部接口。3、熟练使用C++语言环境来实现或重用类，从而实现类的层次结构。类的实现包括类的数据成员的定义和成员函数的及实现，必要时需要增加内部函数和数据结构。4、学会利用数据结构知识设计结构清晰的算法和程序，并学习分析所设计的算法的时间和空间复杂度。 二、实验内容、学时分配及基本要求 序号实验项目名称学时实验内容及要求开出 组数每组人数实验 类型选 做必 做备注1线性表的基本运算及多项式的算术运算2内容： 实现顺序表和单链表的基本运算，多项式的加法和乘法算术运算。 要求： 能够正确演示线性表的查找、插入、删除运算。实现多项式的加法和乘法运算操作。1401验证√2二叉树的基本操作及哈夫曼编码译码系统的实现2内容： 创建一棵二叉树，实现先序、中序和后序遍历一棵二叉树，计算二叉树结点个数等操作。哈夫??编码/译码系统。 要求： 能成功演示二叉树的有关运算，运算完毕后能成功释放二叉树所有结点占用的系统内存。1401验证√3图的基本运算及飞机换乘次数最少问题2内容： 包括邻接矩阵和邻接表两种方法。图的深度优先和宽度优先遍历等。学生可选做使用Dijkstra算法实现飞机最少换乘次数问题。 要求： 成功演示图的基本运算。在两种存储结构上均实现深度优先和宽度优先遍历算法。将飞机最小换乘问题一般化，以解决一类最短寻径问题。1401设计√参见《综合性、设计性实验教学大纲》4各种内排序算法的实现及性能比较2内容： 验证教材的各种内排序算法。分析各种排序算法的时间复杂度。 要求： 使用随机数产生器产生大数据集合，运行上述各种排序算法，使用系统时钟测量各算法所需的实际时间，并进行比较。1401验证√ 三、考核及实验报告 （一）考核 实验课考核方式分两个部分：程序演示和实验报告。程序演示考察设计的科学、合理性；程序执行的正确性；程序算法的执行效能以及程序的健壮性等。实验报告考察设计报告是否正确合理地反应系统设计流程；文档内容的详实程度；文档格式规范和排版美观等。 实验课考核成绩确定分为两个部分：程序演示和实验报告，这两部分各占实验课考核总成绩的50%。 实验课成绩占课程总成绩的比例为10%。 （二）实验报告 实验报告的内容： 1、实验名称：_________班级_________姓名_________学号_________日期_________。 2、实验目的：扼要而准确地描述所求解的实习题的目的。 3、实验任务：明确实习题的任务和演示程序的主要功能。 4、实验内容：使用UML图表示系统分析和设计的结果，描述类层次结构，给出函数之间的调用关系和数据传递方式，给出核心算法的C++源代码，并加上详细注释，分析主要算法的时间复杂度，必要时分析空间复杂度，给出算法分析的计算过程。 5、实验过程描述：列出实习所用的测试用例和相应的程序运行结果，总结本次实习，包括对测试结果的分析，测试和调试过程遇到问题的回顾和分析，软件设计与实现的经验和体会，进一步改进的设想。 实验报告的要求： 按照教材第12章中给出的实习报告样例编写。 四、主要仪器设备 硬件：PC机。 软件：VC++ 6.0 集成开发环境。 五、教材及参考书 教材 陈慧南．数据结构—使用C++描述(第2版)．北京：人民邮电出版社，2008 参考书 [1] Sahni S著，汪诗林，孙晓东译．数据结构、算法与应用－C++语言描述．北京：机械工业出版社，2000 [2] Preiss B R著，胡广斌等译．数据结构与算法－面向对象C++设计模式．北京：电子工业出版社，2000 [3] 殷人昆，陶永雷