北邮数据结构实验题目

2.2 题目2——基础实验

根据二叉排序树的抽象数据类型的定义，使用二叉链表实现一个二叉排序树。提示：二叉排序树的理论内容见教材第7章。

二叉排序树的基本功能： 1、二叉排序树的建立 2、二叉排序树的查找 3、二叉排序树的插入 4、二叉排序树的删除 5、二叉排序树的销毁

编写测试main()函数测试二叉排序树的正确性。

思考问题（选作）：

1、 如何判断建立的二叉排序树是否平衡？编写一个函数，完成该功能。

3代码要求

1、必须要有异常处理，比如删除空链表时需要抛出异常； 2、保持良好的编程的风格：

? 代码段与段之间要有空行和缩近 ? 标识符名称应该与其代表的意义一致 ? 函数名之前应该添加注释说明该函数的功能 ? 关键代码应添加注释说明其功能 3、递归程序注意调用的过程，防止栈溢出

4、代码中需要标注每一个函数的时间复杂度

实验四 图

1 实验目的

通过完成图的相关算法的实现，掌握如下内容：

? 掌握图的两种基本的存储结构，以及图的基本算法的实现方法 ? 了解最小生成树的思想和相关概念 ? 了解最短路径的思想和相关概念 ? 学习使用图解决实际问题的能力

2 实验内容

2.1 题目1——基础实验

根据图的抽象数据类型的定义，使用邻接矩阵或邻接表实现一个图。 图的基本功能：

1、图的建立 2、图的销毁 3、深度优先遍历图 4、广度优先遍历图

5、使用普里姆算法生成最小生成树 6、使用克鲁斯卡尔算法生成最小生成树 7、求指定顶点到其他各顶点的最短路径 编写测试main()函数测试图的正确性

思考问题（选作）：

1、若测试数据量较大，如何使得栈不溢出？使用非递归方式编写新的深度优先遍历函数。提示：可以使用STL中的stack来辅助实现。

2、最短路径D算法，是否可以优化？请写出优化的思路并计算时间复杂度，同时实现一个新的优化的最短路径算法。

题目2——图的应用

问题：设某个田径运动会共有七个项目的比赛，分别为100米、200米、跳高、跳远、铅球、铁饼和标枪。每个选手最多参加3个项目，现有六名选手参赛，他们选择的项目如表1-1所示。考虑到每个选手的参加的各个项目不能同时进行，则如何设计合理的比赛日程，使运动会在尽可能短的时间内完成？

测试数据： 提示：

1、利用图的着色思想解决该问题

2、可以使用STL相关内容辅助解决该问题 3、参考《数据结构与STL》第一章1.5小节

姓名 张凯 王刚 李四 张三 王峰 李杰 项目1 跳高 100m 跳高 跳远 铅球 100m 项目2 跳远 200m 铅球 标枪 标枪 跳远 项目3 铁饼 铁饼 3代码要求

1、必须要有异常处理，比如删除空链表时需要抛出异常； 2、保持良好的编程的风格：

? 代码段与段之间要有空行和缩近 ? 标识符名称应该与其代表的意义一致 ? 函数名之前应该添加注释说明该函数的功能 ? 关键代码应添加注释说明其功能 3、递归程序注意调用的过程，防止栈溢出

实验五 排序

1 实验目的

通过选择下面两个题目之一，学习、实现、对比各种排序算法，掌握各种排序算法的优劣，以及各种算法使用的情况。

2 实验内容

2.1 题目1

使用简单数组实现下面各种排序算法，并进行比较。 排序算法：

1、插入排序 2、希尔排序 3、冒泡排序 4、快速排序 5、简单选择排序 6、堆排序（选作） 7、归并排序（选作） 8、基数排序（选作） 9、其他

要求：

1、测试数据分成三类：正序、逆序、随机数据

2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换计为3次移动）。

3、对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微秒（选作）

4、对2和3的结果进行分析，验证上述各种算法的时间复杂度

编写测试main()函数测试线性表的正确性。

2.2 题目2

使用链表实现下面各种排序算法，并进行比较。 排序算法：