if(!p||j>i) return ERROR; *e= (2) ; return OK;
}
答案：(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
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;k
L->slist[k]= （1） ;
（2） ; 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） )&&(j
if(p->next==NULL||j>i-1) return ERROR; q=p->next; （2） ; *s=q->data; free(q); return OK; }/*listDelete*/
6
答案：(1)p->next!=NULL (2)p->next=q->next 5、写出算法的功能。
int L(head){ node * head; 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; 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];
7
L->elem [L->length -i-1]=t; }/*for*/
}/*invert_list*/
2、有两个循环链表，链头指针分别为L1和L2，要求写出算法将L2链表链到L1链表之后，且连接后仍保持循环链表形式。
答案：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; }
}
4、编写算法,将一个头指针为head不带头结点的单链表改造为一个单向循环链表，并分析算法的时间复杂度。 答案：
void linklist_c(Lnode *head) {Lnode *p; p=head; if(!p) return ERROR;
while(p->next!=NULL)
p=p->next; p->next=head; }
设单链表的长度（数据结点数）为N，则该算法的时间主要花费在查找链表最后一个结点上（算法中的while循环），所以该算法的时间复杂度为O（N）。
5、已知head为带头结点的单循环链表的头指针，链表中的数据元素依次为（a1，a2,a3,a4,…,an）,A为指向空的顺序表的指针。阅读以下程序段，并回答问题：
8
（1）写出执行下列程序段后的顺序表A中的数据元素； （2）简要叙述该程序段的功能。
if(head->next!=head) {
p=head->next; A->length=0;
while(p->next!=head) {
p=p->next;
A->data[A->length ++]=p->data; if(p->next!=head)p=p->next; }
}
答案：
(1) (a2, a4, …, )
(2)将循环单链表中偶数结点位置的元素值写入顺序表A
6、设顺序表va中的数据元数递增有序。试写一算法，将x插入到顺序表的适当位置上，以保持该表的有序性。 答案：
void Insert_sq(Sqlist va[], ElemType x) {int i, j, n; n=length(va[]); if(x>=va[n-1])
va[n]=x; else
{i=0;
while(x>va[i]) i++; for(j=n-1;j>=I;j--)
va[j+1]=va[j]; va[i]=x; } n++; }
试编写一个算法，在一个递增有序排列的单链表中插入一个新结点x，并保持有序。
struct Linknode{
int data ;
struct Linknode *next ; };
typedef struct Linknode *Link; Link insert(Link head) {
int i,e,j ; Link pointer,s;
printf(\
9
scanf(\ pointer= head;
while (pointer->next && e>=pointer->next->data)/*在链表中确定插入的位置*/
pointer=pointer->next; if (!pointer->next) { s=(Link)malloc(sizeof(struct Linknode)); s->data=e; s->next=NULL; pointer->next=s; } else {
s=(Link)malloc(sizeof(struct Linknode));
s->data=e; /*为插入的结点建立链接关系*/ s->next=pointer->next; pointer->next=s; }/*if*/ return head; }/*LinkList_insert*/
7、假设线性表采用顺序存储结构，表中元素值为整型。阅读算法f2，设顺序表L=(3,7,3,2,1,1,8,7,3),写出执行算法f2后的线性表L的数据元素，并描述该算法的功能。
void f2(SeqList *L){
int i,j,k; k=0;
for(i=0;i
for(j=0;j
if(j==k){
if(k!=i)L->data[k]=L->data[i];
k++; }
}
L->length=k; }
答案：
(3,7,2,1,8) 删除顺序表中重复的元素
8、已知线性表中的元素以值递增有序排列，并以单链表作存储结构。试写一算法，删除表中所有大于x且小于y的元素（若表中存在这样的元素）同时释放被删除结点空间。 答案：
10
数据结构试题集（含答案）
