数据结构实验指导书

《数据结构与算法》实验指导书

实验5 二叉树

一、实验目的

（1）掌握二叉树的生成，以及前、中、后序遍历算法。 （2）掌握应用二叉树递归遍历思想解决问题的方法。

二、实验要求

（1）调试程序要记录调试过程中出现的问题及解决办法； （2）给出每个问题的算法或画出流程图；

（3）编写程序要规范、正确，上机调试过程和结果要有记录，并注意调试程序集成环境的掌握及应用，不断积累编程及调试经验； （4）做完实验后给出本实验的实验报告。

三、实验设备、环境

奔腾以上计算机，装有Turbo C 2.0或Visual C++软件

四、实验步骤及内容

实验步骤：

1．根据题目，编写程序。 2．上机调试通过。

3．按照实验报告格式，撰写各实验报告。 实验内容：

（1）建立一棵二叉树。对此树进行前序遍历、中序遍历及后序遍历，输出遍历序列。 （2）求二叉树中叶结点的个数。

（3）假设通讯电文由8个字母组成，字母在电文中出现的频率分别为：7，19，2，6，32，3，21，10。试为这8个字母设计哈夫曼编码。

五、讨论、思考题

1、二叉树是如何存储的？

2、二叉树有哪些遍历算法？这些遍历算法有何特点？ 3、找出分别满足下面条件的所有二叉树： （1）前序序列和中序序列相同； （2）前序序列和后序序列相同； （3）后序序列和中序序列相同；

4、若以二叉链表作存储结构，如何求二叉树高度？提示：用递归的方法。

157

《数据结构与算法》实验指导书

实验6 图

一、实验目的

（1）熟练掌握图的基本概念、构造及其存储结构。

（2）熟练掌握对图的深度优先搜索遍历和广度优先搜索遍历的算法。

二、实验要求

（1）调试程序要记录调试过程中出现的问题及解决办法； （2）给出每个问题的算法或画出流程图；

（3）编写程序要规范、正确，上机调试过程和结果要有记录，并注意调试程序集成环境的掌握及应用，不断积累编程及调试经验； （4）做完实验后给出本实验的实验报告。

三、实验设备、环境

奔腾以上计算机，装有Turbo C 2.0或Visual C++软件

四、实验步骤及内容

实验步骤：

1．根据题目，编写程序。 2．上机调试通过。

3．按照实验报告格式，撰写各实验报告。 实验内容：

1．构造一个无向图，要求用邻接矩阵表示存储结构。

2．对上面构造的无向图，进行深度优先遍历和广度优先遍历，分别输出遍历序列。 3．构造一个连通网络，分别用PRIM算法和KRUSKAL算法构造该网络的最小生成树。

五、讨论、思考题

1、图是如何存储的？

2、如何从一个无向图的邻接矩阵（或邻接表）中，判断图中有多少条边？任意两个顶点i和j是否有边相连？任意一个顶点的度是多少？ 3、图有哪些遍历算法，这些算法之间有何区别？

158

《数据结构与算法》实验指导书

实验7 排序

一、实验目的

（1）熟练掌握希尔排序、堆排序、直接插入排序、起泡排序、快速排序、直接选择排序、归并排序和基数排序的基本概念。 （2）掌握以上各种排序的算法。 （3）区分以上不同排序的优、缺点。

二、实验要求

（1）调试程序要记录调试过程中出现的问题及解决办法； （2）给出每个问题的算法或画出流程图；

（3）编写程序要规范、正确，上机调试过程和结果要有记录，并注意调试程序集成环境的掌握及应用，不断积累编程及调试经验； （4）做完实验后给出本实验的实验报告。

三、实验设备、环境

奔腾以上计算机，装有Turbo C 2.0或Visual C++软件

四、实验步骤及内容

实验步骤：

1．根据题目，编写程序。 2．上机调试通过。

3．按照实验报告格式，撰写各实验报告。 实验内容：

用随机数产生100000个待排序数据元素的关键字值。测试下列各排序函数的机器实际执行时间（至少测试两个）：直接插入排序、希尔排序（增量为4，2，1）、冒泡排序、快速排序、直接选择排序、二路归并排序、堆排序和基于链式队列的基数排序。

五、讨论、思考题

1、排序方法有哪些？各有哪些特点？

2、什么是排序方法的稳定性？哪些排序方法是稳定的，哪些又是不稳定的？

159

《数据结构与算法》实验指导书

实验8 查找

一、实验目的

（1）掌握顺序表查找、有序表查找、索引顺序表查找的各种算法。 （2）掌握哈希表设计。

二、实验要求

（1）调试程序要记录调试过程中出现的问题及解决办法； （2）给出每个问题的算法或画出流程图；

（3）编写程序要规范、正确，上机调试过程和结果要有记录，并注意调试程序集成环境的掌握及应用，不断积累编程及调试经验； （4）做完实验后给出本实验的实验报告。

三、实验设备、环境

奔腾以上计算机，装有Turbo C 2.0或Visual C++软件

四、实验步骤及内容

实验步骤：

1．根据题目，编写程序。 2．上机调试通过。

3．按照实验报告格式，撰写各实验报告。 实验内容：

（1）在一个递增有序的线性表中利用二分查找法查找数据元素X。

（2）构造一个哈希表，哈希函数采用除留余数法，哈希冲突解决方法采用链地址法。设计一个测试程序进行测试。

五、讨论、思考题

1、二分查找的前提是什么？ 2、如何合理设计哈希函数？

160