1.解

（1）算法的基本设计思想

将数组A[]中的m+n个元素（假设元素为int型）看成两个顺序表：表L和表R。将数组当前状态看作起始状态，即此时表L由A[]中前m个元素构成，表R由A[]中后n个元素构成。要使A[]中m+n个元素整体有序，只需将表R中的元素逐个插入表L中的合适位置即可。

插入过程：取表R中的第一个元素A[m]存入辅助变量temp中，让temp逐个与A[m-1]，…，A[0]进行比较，当temp＜A[j]（0≤j≤m-1）时，将A[j]后移一位，否则将temp存入A[j+1]中。重复上述过程，继续插入A[m+1]，A[m+2]，…，A[m+n]，最终A[]中元素整体有序。

（2）算法描述

（3）算法的时间和空间复杂度

1）本题的规模由m和n共同决定。取最内层循环中A[j+1]=A[j]；这一句作为基本操作，其执行次数在最坏的情况下为R中的每个元素都小于L中的所有元素；又因R中元素递增有序，所以对于每个R中的元素，要将其插入正确位置都必须进行m次移动，R中共有n个元素，因此有：

由此可见，本算法的时间复杂度为O（mn）。(www.daowen.com)

2）算法所需额外存储空间与数据规模m和n无关，变化属于常量级，因此空间复杂度为O（1）。

2.解

（1）算法的基本设计思想

只需从A中删去A与B中共有的元素即可。由于两个链表中的元素是递增有序的，因此可以这么做：设置两个指针p、q开始时分别指向A和B的开始结点。循环进行以下判断和操作：如果p所指结点的值小于q所指结点的值，则p后移一位；如果q所指结点的值小于p所指结点的值，则q后移一位；如果两者所指结点的值相同，则删除p所指结点。最后，p与q任一指针为NULL时算法结束。

（2）算法描述

（3）算法的时间复杂度分析

由算法描述可知，算法规模由m和n共同确定。算法中有一个单层循环，循环内的所有操作都是常数级的，因此可以用循环执行的次数作为基本操作执行的次数。可见循环执行的次数即为p、q两指针沿着各自链表移动的次数，考虑最坏的情况，即p、q都走完了自己所在的链表，循环执行m+n次，因此时间复杂度为O（m+n）。