1、 实现两个链表的合并

基本功能要求：

（1） 建立两个链表A和B，链表元素个数分别为m和n个。

（2） 假设元素分别为(x₁,x₂,…x_m)，和(y₁,y₂, …y_n)。把它们合并成一个线形表C，使得：

当m>=n时，C=x₁,y₁,x₂,y₂,…x_n,y_n,…,x_m

当n>m时，C=y₁,x₁,y₂,x₂,…y_m,x_m,…,y_n

输出线形表C

（3） 用直接插入排序法对C进行升序排序，生成链表D，并输出链表D。

测试数据：

（1） A表（30，41，15，12，56，80）

B表（23，56，78，23，12，33，79，90，55）

（2）A表（30，41，15，12，56，80，23，12，34）

B表（23，56，78，23，12）

2、 字符串的操作

基本功能要求：

（1） 字符串采用数组存储，建立两个字符串String1和String2。输出两个字符串。

（2） 将字符串String2的头n个字符添加到String1的尾部。输出结果。

（3） 查找串String3在串String1中的位置，若String3在String1中不存在，则插入String3在String1中的m位置上。输出结果。

测试数据：

（1） String1: “typedefstructArcBox”

String2: “VertexTypedata”

String3: “data”

n:6,m:7

（2） String1: “structArcBox”

String2: “VertexType”

String3: “Box”

n:3,m:3

4、稀疏矩阵的操作

基本功能要求：

（1） 稀疏矩阵采用三元组表示，求两个具有相同行列数的稀疏矩阵A和B的相加矩阵C，并输出C。

（2）求出A的转置矩阵D，输出D。

测试数据：

5、 建立二叉树，并对树进行操作

基本功能要求：

a) 利用完全二叉树的性质建立一棵二叉树。

b) 统计数叶子结点的个数。

c) 求二叉树的深度。

测试数据：

（1）

A

C

D

B

F

E

A

B

C

H

G

F

E

I

D

（2）

6、 图及其操作

基本功能要求：

（1） 图的建立，要求采用邻接矩阵作为存储结构。

（2） 输出结点的度（或出度和入度）

（3） 将图的存储结构邻接矩阵转换为邻接链表。

测试数据：

3

1

2

（1） （2）

1

3

5

4

2

以上题目选作一题，在本学期完成。报告要求：

1、 方案设计

2、 程序框图

3、 程序代码

4、 程序调试过程和结果

5、 总结

感谢那位高手来完成其中的一个题 谢谢拉! suntiechuang@126.com