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

C. p的直接后继是头结点 D. p的直接后继是尾结点

1、设单链表的结点结构为（data,next）。已知指针p指向单链表中的结点，q指向新结点，欲将q插入到p结点之后，则需要执行的语句： q->next=p->next ； p->next = q 。 二、填空题

答案：q->next=p->next p->next=q

2、线性表的逻辑结构是 线性结构 ，其所含元素的个数称为线性表的 长度 。 答案：线性结构 长度

3、写出带头结点的双向循环链表L为空表的条件 。 答案：L->prior==L->next==L

4、带头结点的单链表head为空的条件是 。 答案：head->next==NULL

5、在一个单链表中删除p所指结点的后继结点时，应执行以下操作：

q = p->next;

p->next= _q->next ___; 三、判断题

1、单链表不是一种随机存储结构。 对

2、在具有头结点的单链表中，头指针指向链表的第一个数据结点。错

3、用循环单链表表示的链队列中，可以不设队头指针，仅在队尾设置队尾指针。对 4、顺序存储方式只能用于存储线性结构。错

5、在线性表的顺序存储结构中，逻辑上相邻的两个元素但是在物理位置上不一定是相邻的。错

6、链式存储的线性表可以随机存取。错

四、程序分析填空题

1、函数GetElem实现返回单链表的第i个元素，请在空格处将算法补充完整。 int GetElem(LinkList L,int i,Elemtype *e){ LinkList p；int j；

p=L->next;j=1;

while(p&&j

(1) ;++j;

}

5

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)&&(jnext;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） ; 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*/

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