11 数据结构实验题目.docx

第1页：数据结构实验题目封面

数据结构实验题目（第一次实验）题目1单链表相关算法的实验验证。[实验目的]验证单链表及其上的基本操作。[实验内容及要求]1、定义单链表类。2、实验验证如下算法的正确性、各种功能及指标：1创建单链表；2插入操作：分别在当前结点后、表头、表尾插入值为x的结点；3删除操作：分别删除表头结点、表尾结点和当前结点的后继结点；

4存取操作：分别存取当前结点的值和单链表中第k个结点的值；5查找操作：查找值为x的元素在单链表中的位置（下标）。3、为便于观察程序的运行结果，设计的输出函数能在输出设备上以图形或表格或其它直观的形式展现、存储计算结果。4、测试程序时，对所有输入变量取遍各种有代表性的值。5、为了增强程序的可读性，程序中要有适当的注释。

题目2分别给出堆栈、队列相关算法的实验验证。[实验目的]验证堆栈、队列及其上的基本操作。[实验内容及要求]（以队列为例）1、定义队列类。2、实验验证如下算法的正确性、各种功能及指标：1创建队列；2插入操作：向队尾插入值为x的元素；3删除操作：删除队首元素；4存取操作：读取队首元素。3、为便于观察程序的运行结果，设计的输出函数能在输出设备上以图形或表格或其它直观的形式展现、存储计算结果。

4、测试程序时，对所有输入变量取遍各种有代表性的值。5、为了增强程序的可读性，程序中要有适当的注释。

第2页：数据结构实验题目（续）

（第二次实验）题目1二叉树相关算法的实验验证。[实验目的]验证二叉树的链接存储结构及其上的基本操作。[实验内容及要求]1、定义链接存储的二叉树类。2、实验验证如下算法的正确性、各种功能及指标：1创建一棵二叉树，并对其初始化；2先根、中根、后根遍历二叉树(递归算法)；3在二叉树中搜索给定结点的父结点；

4搜索二叉树中符合数据域条件的结点；5从二叉树中删除给定结点及其左右子树。3、为便于观察程序的运行结果，设计的输出函数能在输出设备上以图形或表格或其它直观的形式展现、存储计算结果。4、测试程序时，对所有输入变量取遍各种有代表性的值。5、为了增强程序的可读性，程序中要有适当的注释。题目2树和森林的遍历算法的实验验证。

[实验目的]验证树和森林的遍历算法。[实验内容及要求]1、定义左儿子—右兄弟链接存储的树类和森林类。2、实验验证如下算法的正确性、各种功能及指标：1创建树和森林；2树和森林的先根遍历的递归和迭代算法；3树和森林的后根遍历的递归和迭代算法；4树和森林的层次遍历算法。3、为便于观察程序的运行结果，设计的输出函数能在输出设备上以图形或表格或其它直观的形式展现、存储计算结果。

4、测试程序时，对所有输入变量取遍各种有代表性的值。5、为了增强程序的可读性，程序中要有适当的注释。题目3二叉查找树的验证实验。[实验目的]验证二叉查找树及其相关操作。[实验内容及要求]

第3页：定义二叉查找树的类

1、定义二叉查找树的类。2、实验验证如下算法的正确性、各种功能及指标：1实现二叉查找树结构；2实现二叉查找树的查找、插入和删除等算法；3、为便于观察程序的运行结果，设计的输出函数能在输出设备上以图形或表格或其它直观的形式展现、存储计算结果。4、测试程序时，对所有输入变量取遍各种有代表性的值。5、为了增强程序的可读性，程序中要有适当的注释。

第4页：定义二叉查找树的类（图）

（第三次实验）题目1邻接表存储的图相关算法的实验验证。[实验目的]验证邻接表存的图及其上的基本操作。[实验内容及要求]1、定义邻接表存储的图类。2、实验验证如下算法的正确性、各种功能及指标：1创建一个邻接表存储的图；2返回图中指定边的权值；3返回图中某顶点的第一个邻接顶点；4返回图中某顶点关于另一个顶点的下一个邻接顶点的序号；

5插入操作：向图中插入一个顶点，插入一条边；6删除操作：从图中删除一个顶点，删除一条边。3、为便于观察程序的运行结果，设计的输出函数能在输出设备上以图形或表格或其它直观的形式展现、存储计算结果。4、测试程序时，对所有输入变量取遍各种有代表性的值。5、为了增强程序的可读性，程序中要有适当的注释。题目2图的遍历算法的实验验证。

[实验目的]验证图的遍历算法。[实验内容及要求]1、定义邻接表存储的图。2、实验验证如下算法的正确性、各种功能及指标：1创建一个图；2图的深度优先遍历的递归算法；3图的深度优先遍历的迭代算法；4图的广度优先遍历算法。3、为便于观察程序的运行结果，设计的输出函数能在输出设备上以图形或表格或其它直观的形式展现、存储计算结果。

4、测试程序时，对所有输入变量取遍各种有代表性的值。5、为了增强程序的可读性，程序中要有适当的注释。

第5页：定义二叉查找树的类（续）

（第四次实验）题目1设计并实现对半插入排序算法。[实验目的]实现验证对半插入排序算法。[实验内容及要求]对半插入排序的思想是：在插入Ri时（这时R1，R2，…，Ri–1已经排序），取K⌊i/2⌋与Ki进行比较，如果Ki<K⌊i/2⌋，则Ri只能插在R1与R⌊i/2⌋之间，故可以在R1与R⌊i/2⌋–1之间递归上述过程，否则可以在R⌊i/2⌋+1与Ri–1之间递归上述过程。

如此进行直到最后确定插入位置为止。设计对半插入排序算法；编制程序实现该算法，制定测试方案，并调试通过。1、设计并实现对半插入排序算法。2、理论分析并实验验证算法的时间复杂度，即关键词的比较次数和记录的移动次数。题目2快速排序算法的实验验证。[实验目的]验证快速排序算法。[实验内容及要求]1、实现快速排序算法。

2、理论分析并实验验证快速排序算法的时间复杂度。3、为便于观察程序的运行结果，设计的输出函数能在输出设备上以图形或表格或其它直观的形式展现、存储计算结果。4、为程序制定测试方案。5、测试程序时，对所有输入变量取遍各种有代表性的值。6、为了增强程序的可读性，程序中要有适当的注释。题目3堆排序算法的实验验证。

[实验目的]验证堆排序算法。[实验内容及要求]1、实现堆排序算法。2、理论分析并实验验证堆排序算法的时间复杂度。3、为便于观察程序的运行结果，设计的输出函数能在输出设备上以图形或表格或其它直观的形式展现、存储计算结果。4、为程序制定测试方案。5、测试程序时，对所有输入变量取遍各种有代表性的值。6、为了增强程序的可读性，程序中要有适当的注释。