《数据结构基础.doc》由会员分享，可在线阅读，更多相关《数据结构基础.doc（7页珍藏版）》请在金锄头文库上搜索。
1、数据结构基础毁灭友情的方式有许多，最彻底的一种是借钱数据结构基础所属课程名称：数据结构基础英文名称： Fundamentals of Data Structure所属课程编号：0901202面向专业： 计算机及电类专业课程总学时： 64 ；实验学时 32 ；课程学分： 4.5 一. 实验目的通过上机实验，使学生深刻理解基础数据结构和算法的概念并能实际应用和进一步拓展教学内容，系统掌握典型数据结构和算法的设计与分析方法，培养用数据结构对现实对象进行建模并解决实际问题的能力，掌握数据结构的定义、表示以及操作实现相互关联的规律，增强动手能力，增强专业性程序设计和构建软件系统的能力，提高分析问题和解决
2、问题的能力，提高专业素质，培养协作精神和创新能力。二. 实验内容、学时分配与组织序号实验项目名称内容提要实验性质实验类型学时分配每组人数备注1随机漫游用数组count表示蟑螂到达每块地砖的次数，蟑螂位置用 (i, j) 表示，八个方向的随机游走通过生成均匀分布随机数k（0k7）模拟。每到达一块地砖，相应次数加1。当蟑螂至少到达每块地砖一次时，模拟完成。应打印最终的count数组。专业基础提高型42选做2环链单变量多项式系统设计和实现一个用带头结点的环链表表示单变量多项式的系统。应使用局部资源管理技术。实现并测试的操作包括：输入、输出、复制构造、赋值、析构、相加、相减、相乘和计算多项式的值。专业
3、基础提高型62必做3双链环表定义带头结点的双链环表的模板类，包括DblListNode，DblList和DblIterator三个模板类。除了实现游标成员函数First( )，Next( )，NotNull( )和NextNotNull( )之外，再实现一个成员函数Previous( )。专业基础提高型42选做4基于模板的二叉树类写出基于模板的二叉树类定义，并进一步定义二叉树的中序、前序、后序和按层次遍历游标类，最后写一个函数分别以上述4种顺序打印所有树元素。专业基础提高型62必做5命题演算公式系统设计一种命题演算公式的符号表示，写一个函数，读入一个公式的符号表示并生成其二叉树表示。分析并测试
4、该函数的计算时间。专业基础研究创新型42选做6优先队列的实现方法比较分别用最大堆、无序线性表和有序线性表实现优先队列，并比较这三种实现的运行性能。专业基础研究创新型42必做7深度优先搜索分别用邻接矩阵和邻接表表示图，设计实现深度优先搜索的完整算法，并用适当的实例测试其正确性。专业基础提高型42必做8最小生成树写出实现最小生成树算法的完整程序，并用适当的实例测试其正确性。专业基础提高型42选做9AOE网络设计一个算法，输入AOE网络，输出：所有事件及其最早开始时间和最迟开始时间，所有活动及其最早开始时间、最迟开始时间和关键度，关键网络。专业基础提高型42必做10排序方法性能研究用随机排列生成器生
5、成平均情况数据，测量插入排序、快速排序、归并排序、堆排序和基数排序的平均运行时间。专业基础研究创新型62必做11生成归并段用随机数生成器生成输入记录表，测量并分析生成归并段算法生成的归并段的平均长度。专业基础研究创新型42选做12二叉查找树性能研究设计一个算法，对一棵初始为空的二叉查找树作n次插入。每次插入的关键字值由均匀随机生成器生成，测量所生成二叉树的高度h，并将h/log2n作为n的函数用曲线画出。专业基础研究创新型42选做13B树用合理的外存地址模拟指针，实现B树的查找、插入和删除算法。专业基础研究创新型62选做三. 教学管理模式与注意事项 1. 实验任务由任课教师课堂教学中下达。 2
6、. 学生在实验前必须理解和掌握课程有关内容，深入分析实验问题，提出并尽可能优化解决方案，设计实验必须的全部数据结构和算法，规划生成实验测试数据的方法。 3. 任课教师适当提示实验要求及注意事项，并检查预习情况。 4. 研究生助教现场辅导学生上机实验。 5. 实验小组人数一般为2人，每个实验的时间为4-6小时，由学生独立上机完成，所有实验都要求能够通过程序设计实现，并运行正确。 6. 要求学生熟悉C+程序设计语言及相应的开发环境，逐项记录数据，并完成实验报告。 7. 学生在完成全部必做实验的同时，可根据自己的实际情况，选择选做实验。实验时间按学校计算机实验中心排定的计划，同时鉴于目前多数学生已拥
7、有自己的计算机，也可用其它时间完成实验。 8. 注意诚信教育，鼓励学生之间开展讨论和交流，但坚决反对抄袭行为。四. 成绩评定与占课程总成绩的比例1 任课教师和研究生助教小组根据每个学生实验预习情况、必做实验完成情况、软件质量、实验数据的准确性、选做实验的数量和完成情况，以及对实验报告的批改，按优秀、良好、中等、及格和不及格档次进行评分，并将成绩记录在册。2任课教师汇总实验成绩，实验成绩与平时作业成绩占课程总成绩的30%。五. 设备与器材配置1 微机 （要求安装C+语言及开发环境） 1台/每个学生2 打印机（多组学生共享）3 耗材 若干六. 实验任务书与参考资料1. 金远平. 数据结构（C+描述）.清华大学出版社，20052. 徐冬梅. 数据结构实验指导书，东南大学讲义，20043. E. Horowitz, S. Sahni, D. Mehta. Fundamentals of Data Structures in C+. Computer Science Press.19954. 殷人昆等.数据结构（用面向对象方法与C+描述）.清华大学出版社.2001 毁灭友情的方式有许多，最彻底的一种是借钱
