2010级数据结构实验题目
一．实验题目
1.设有两个无头结点的单链表，头指针分别为ha,hb。

链中有数据域data，链域next。

两链
表的数据都按递增序存放。

现要求将hb表归到ha表中，且归并后ha仍递增，归并中ha表中已有的数据若hb中也有，则hb中的数据不归并到ha中，hb的链表在算法中不允许破坏。

2.结合书上第41页的例子（一元多项式相加），采用链式存储结构，将两个线性表表示的
一元多项式相加，并输出。

3.二叉树的动态二叉链表结构中的每个结点有三个字段：data，lchild，rchild。

其中指针lchild
和rchild的类型为bitre。

静态二叉链表是用数组作为存储空间，每个数组元素存储二叉树的一个结点，也有三个字段：data，lchild，rchild。

有所不同的是lchild和rchild为integer 型，分别用于存储左右孩子的下标，如果没有左右孩子，则相应的值为0。

例如，二叉树的静态二叉链表如下图所示。

编写算法由二叉树的动态二叉链表构造出相应的静态二叉链表a[1…n]，并写出其调用形式和有关的类型描述。

其中n为一个确定的整数。

4.设无向图G有n个点e条边，编写算法建立G的邻接表，并按照深度优先搜索输出顶
点，要求该算法时间复杂性为O（n+e），且除邻接多表本身所占空间之外只用O（1）辅助空间。

5.二叉排序树采用二叉链表储存。

写一个算法，删除结点值是X的结点。

要求删除该结点
后，此树仍是一颗二叉排序树，并且高度没有增长（注：可不考虑被删除结点是根的情况）。

二．实验报告填写要求
1.实验报告开头写明实验日期和实验题目
2.中间部分写上实验算法
3.最后写上实验结果。