M L= P;
(3) D
(4) D
(5) D
(6) A

7 试分别以不同的存储结构实现单线表的就地逆置算法，即在原表的存储空间将线性表

（a

1

,a

2

,…,a

n

）逆置为(a

n

,a

n-1

,…,a

1

)。

【解答】（1）用一维数组作为存储结构
     void  invert(SeqList  *L,  int  *num)

{  
  int  j;
  ElemType  tmp;

for(j=0;j<=(*num-1)/2;j++)

{ tmp=L[j];

L[j]=L[*num-j-1];

L[*num-j-1]=tmp;}

}

（2）用单链表作为存储结构

   void  invert(LinkList  L)
  {

Node  *p, *q, *r;

    if(L->next ==NULL)  return;          /*链表为空*/

    p=L->next;    
    q=p->next;               

p->next=NULL;              /* 摘下第一个结点，生成初始逆置表

 */

while(q!=NULL)             /* 从第二个结点起依次头插入当前逆置表

 */

   {

r=q->next;
q->next=L->next;

L->next=q;
q=r;

  }
}

11 将 线 性 表 A=(a1,a2,……am),   B=(b1,b2,……bn) 合 并 成 线 性 表 C,   C=(a1,b1,……
am,bm,bm+1,…….bn)  当 m<=n 时，或

 C=(a1,b1, ……an,bn,an+1,……am)当 m>n 时,线

性表 A、B、C 以单链表作为存储结构，且 C 表利用 A 表和 B 表中的结点空间构成。注意：

单链表的长度值 m 和 n 均未显式存储。

【解答】算法如下：
LinkList  merge(LinkList  A,  LinkList B,  LinkList  C)

{ Node  *pa, *qa, *pb, *qb, *p;
  pa=A->next;                    /*pa 表示 A 的当前结点*/
  pb=B->next;  

p=A;  / *利用 p 来指向新连接的表的表尾，初始值指向表 A 的头结点*/
                 

  while(pa!=NULL  &&  pb!=NULL)   /*利用尾插法建立连接之后的链表*/

{   qa=pa->next; 

qb=qb->next;

  p->next=pa;   /*交替选择表 A 和表 B 中的结点连接到新链表中；*/

p=pa;

p->next=pb;
p=pb;                       

pa=qa;

3