10级数据结构实验题目
一、实验题目
1、 设有两个无头结点的单链表，头指针分别为ha，hb，链中有数据域data，链域next，两链表的数据都按递增序存放，现要求将hb表归到ha表中，且归并后ha仍递增序，归并中ha表中已有的数据若hb中也有，则hb中的数据不归并到ha中，hb的链表在算法中不允许破坏。
2、 结合书上第41页的例子（一元多项式相加），采用链式存储结构，将两个线性链表表示的一元多项式相加，并输出。
3、 二叉树的动态二叉链表结构中的每个结点有三个字段：data，lchild，rchild。其中指针lchild
下标 1 2 3 4 5 6 7 data A B C D E F G lchild 2 3 0 5 0 0 0 rchild 6 4 0 0 0 7 0 和rchild的类型为bitre。静态二叉链表是用数组作为存储空间，每个数组元素存储二叉树的一个结点，也有三个字段：data，lchild，rchild。所不同的是，lchild和rdhild 为integer型，分别用于存储左右孩子的下标，如果没有左右孩子，则相应的值为0。例如，二叉树的静态二叉链表如上图所示。编写算法由二叉树的动态二叉链表构造出相应的静态二叉链表a[1..n]，并写出其调用形式和有关的类型描述。其中n为一个确定的整数。 4、 设无向图G有n个点e条边，编写算法建立G的邻接表，并按照深度优先搜索输出顶点，要求该算法时间复杂性为O（n+e），且除邻接多表本身所占空间之外只用O（1）辅助空间。 5、 二叉排序树采用二叉链表存储。写一个算法，删除结点值是X的结点。要求删除该结点后,此树仍然是一棵二叉排序树，并且高度没有增长（注：可不考虑被删除的结点是根的情况）。
二、实验报告填写要求
1、实验报告开头写明实验日期和实验题目 2、中间部分写上算法 3、最后写上实验结果