数据结构试题库及答案 - 图文

素(1?i?n)

C.删除第i个元素(1?i?n) D.对顺序表中元素进行排序 13、已知指针p和q分别指向某单链表中第一个结点和最后一个结点。假设指针s指向另一个单链表中某个结点，则在s所指结点之后插入上述链表应执行的语句为（）。

A.q->next=s->next；s->next=p； B.s->next=p；q->next=s->next； C.p->next=s->next；s->next=q； D.s->next=q；p->next=s->next； 14、在以下的叙述中，正确的是（）。 A.线性表的顺序存储结构优于链表存储结构 B.线性表的顺序存储结构适用于频繁插入/删除数据元素的情况 C.线性表的链表存储结构适用于频繁插入/删除数据元素的情况 D.线性表的链表存储结构优于顺序存储结构 15、在表长为n的顺序表中，当在任何位置删除一个元素的概率相同时，删除一个元素所需移动的平均个数为（）。 A.(n-1)/2 B.n/2 C.(n+1)/2 D.n 16、在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入一个结点s，则执行（）。 A.s->next=p->next;p->next=s; B.p->next=s->next;s->next=p; C.q->next=s;s->next=p; D.p->next=s;s->next=q; 17、在单链表中，指针p指向元素为x的结点，实现删除x的后继的语句是（）。 A.p=p->next; B.p->next=p->next->next; C.p->next=p; D.p=p->next->next; 18、在头指针为head且表长大于1的单循环链表中，指针p指向表中某个结点，若p->next->next==head，则（）。 A.p指向头结点 B.p指向尾结点 C.p的直接后继是头结点

D.p的直接后继是尾结点 二、填空题

1、设单链表的结点结构为（data,next）。已知指针p指向单链表中的结点，q指向新结点，欲将q插入到p结点之后，则需要执行的语句：；。 答案：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个元素，请在空格处将算法补充完整。 intGetElem(LinkListL,inti,Elemtype*e){ LinkListp；intj； p=L->next;j=1; while(p&&ji)returnERROR; *e=(2); returnOK; }

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

2、函数实现单链表的插入算法，请在空格处将算法补充完整。 intListInsert(LinkListL,inti,ElemTypee){ LNode*p,*s;intj; p=L;j=0;

while((p!=NULL)&&(jnext;j++; } -来源网络，仅供个人学习参考

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

}/*ListInsert*/

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

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

intListDelete_sq(Sqlist*L,inti){ intk; if(i<1||i>L->length)returnERROR; for(k=i-1;klength-1;k++) L->slist[k]=（1）; （2）; returnOK; } 答案：（1）L->slist[k+1]（2）--L->Length 4、函数实现单链表的删除算法，请在空格处将算法补充完整。 intListDelete(LinkListL,inti,ElemType*s){ LNode*p,*q; intj; p=L;j=0; while((（1）)&&(jnext;j++; } if(p->next==NULL||j>i-1)returnERROR; q=p->next; （2）; *s=q->data; free(q); returnOK;

}/*listDelete*/

答案：(1)p->next!=NULL(2)p->next=q->next 5、写出算法的功能。 intL(head){ node*head; intn=0; node*p; p=head; -来源网络，仅供个人学习参考

while(p!=NULL) {p=p->next; n++; } return(n); }

答案：求单链表head的长度 五、综合题

1、编写算法，实现带头结点单链表的逆置算法。 答案：voidinvent(Lnode*head) {Lnode*p,*q; if(!head->next)returnERROR; p=head->next;q=p->next;p->next=NULL; while(q) {p=q;q=q->next;p->next=head->next;head->next=p;} } 2、有两个循环链表，链头指针分别为L1和L2，要求写出算法将L2链表链到L1链表之后，且连接后仍保持循环链表形式。 答案：voidmerge(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域的值递增排序。 答案：voidassending(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不带头结点的单链表改造为一个单向循环链表，并分析算法的时间复杂度。 答案：

voidlinklist_c(Lnode*head) {Lnode*p;p=head; if(!p)returnERROR;

while(p->next!=NULL)

p=p->next; p->next=head; } 设单链表的长度（数据结点数）为N，则该算法的时间主要花费在查找链表最后一个结点上（算法中的while循环），所以该算法的时间复杂度为O（N）。 5、已知head为带头结点的单循环链表的头指针，链表中的数据元素依次为（a1，a2,a3,a4,…,an）,A为指向空的顺序表的指针。阅读以下程序段，并回答问题： （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插入到顺序表的适当位置上，以保持该表的有序性。 答案：

voidInsert_sq(Sqlistva[],ElemTypex) {inti,j,n;

n=length(va[]); if(x>=va[i])

va[n]=x; else -来源网络，仅供个人学习参考