数据结构试题集（含答案）(3)

答案：(1)p=p->next (2)p->data

2、函数实现单链表的插入算法，请在空格处将算法补充完整。

int ListInsert(LinkList L,int i,ElemType e){ LNode *p,*s;int j; p=L;j=0;

while((p!=NULL)&&(j

}

p=p->next;j++;

if(p==NULL||j>i-1) return ERROR; s=(LNode *)malloc(sizeof(LNode)); s->data=e;

(1) ; (2) ; return OK; }/*ListInsert*/

答案：(1)s->next=p->next (2)p->next=s

3、函数ListDelete_sq实现顺序表删除算法，请在空格处将算法补充完整。

int ListDelete_sq(Sqlist *L,int i){ int k;

if(i<1||i>L->length) return ERROR;

for(k=i-1;klength-1;k++)

L->slist[k]= （1） ;

（2） ;

11

return OK; }

答案：（1）L->slist[k+1] （2） --L->Length

4、函数实现单链表的删除算法，请在空格处将算法补充完整。 int ListDelete(LinkList L,int i,ElemType *s){ LNode *p,*q; int j; p=L;j=0;

while(( （1） )&&(jnext;j++; }

if(p->next==NULL||j>i-1) return ERROR; q=p->next; （2） ; *s=q->data; free(q); return OK; }/*listDelete*/

答案：(1)p->next!=NULL (2)p->next=q->next 5、写出算法的功能。

int L(head){

node * head;

12

}

int n=0; node *p; p=head; while(p!=NULL) { p=p->next; n++; } return(n);

答案：求单链表head的长度

五、综合题

1、编写算法，实现带头结点单链表的逆置算法。 答案：void invent(Lnode *head)

{Lnode *p,*q,*r;

if(!head->next) return ERROR;

p=head->next; q=p->next; p->next =NULL; while(q)

{ r=q->next;

13

q->next=p; head->next=q; p=q; q=r;

}

}

试编写一个算法，将一个顺序表逆置，并使用最少的辅助存储空间实现。

答案：typedef struct { ElemType *elem; int length; }Sqlist;

Invert_list(Sqlist *L)/*将顺序表进行逆置*/ { int i; ElemType t;

for(i=0;i<(L->length-1)/2;i++){ t=L->elem[i];

L->elem [i]= L->elem [L->length-i-1]; L->elem [L->length -i-1]=t; }/*for*/ }/*invert_list*/

2、有两个循环链表，链头指针分别为L1和L2，要求写出算法将L2链表链到L1链表之后，且连接后仍保持循环链表形式。

14

答案：void merge(Lnode *L1, Lnode *L2)

{Lnode *p,*q ; while(p->next!=L1)

p=p->next; while(q->next!=L2)

q=q->next;

q->next=L1; p->next =L2; }

3、设一个带头结点的单向链表的头指针为head，设计算法，将链表的记录，按照data域的值递增排序。

答案：void assending(Lnode *head)

{Lnode *p,*q , *r, *s;

p=head->next; q=p->next; p->next=NULL; while(q)

{r=q; q=q->next; if(r->data<=p->data)

{r->next=p; head->next=r; p=r; } else

{while(!p && r->data>p->data)

{s=p; p=p->next; } r->next=p; s->next=r;}

p=head->next; }

15