数据结构试题库集及答案

导读:1、设单链表的结点结构为(data,next),答案:q->next=p->nextp->next=q,2、线性表的逻辑结构是,答案:线性结构长度,答案:L->prior==L->next==L,答案:head->next==NULL,1、单链表不是一种随机存储结构,头指针指向链表的第一个数据结点,4、顺序存储方式只能用于存储线性结构,5、在线性表的顺序存储

数据结构试题库集及答案

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= _ ___;

三、判断题

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<i){

(1) ;++j;

}

if(!p||j>i) return ERROR; *e= (2) ;

}

答案:(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<i-1)){ p=p->next;j++;

}

if(p==NULL||j>i-1) return ERROR;

s=(LNode *)malloc(sizeof(LNode));

s->data=e;

(1) ;

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->length-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<i-1)){

p=p->next;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;

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;

if(!head->next) return ERROR;

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链表之后,且连接后仍保持循环链表形式。

答案: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为指向空的顺序表的指针。阅读以下程序段,并回答问题:

(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[i])

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++;

}

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<L->length;i++){

for(j=0;j<k && L->data[i]!=L->data[j];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的元素(若表中存在这样的元素)同时释放被删除结点空间。

答案:

void Delete_list(Lnode *head, ElemType x, ElemType y)

{Lnode *p, *q;

if(!head) return ERROR;

p=head; q=p;

while(!p)

{if(p->data>x) && (p->data<y)}i++;

if(p==head)

{head=p->next; free(p);

p=head; q=p; }

else

{q->next=p->next; free(p);

p=q->next; }

else

{q=p; p=p->next; }

}

}

9、在带头结点的循环链表L中,结点的数据元素为整型,且按值递增有序存放。给定两个整数a和b,且a<b,编写算法删除链表L中元素值大于a且小于b的所有结点。

第三章 栈和队列

一、选择题

1、一个栈的输入序列为:a,b,c,d,e,则栈的不可能输出的序列是()。

A. a,b,c,d,e B. d,e,c,b,a

C. d,c,e,a,b D. e,d,c,b,a

2、判断一个循环队列Q(最多n个元素)为满的条件是()。

A. Q->rear==Q->front B. Q->rear==Q->front+1

C. Q->front==(Q->rear+1)%n D. Q->front==(Q->rear-1)%n

3、设计一个判别表达式中括号是否配对的算法,采用()数据结构最佳。

A. 顺序表 B. 链表 C. 队列 D. 栈

4、带头结点的单链表head为空的判定条件是()。

A. head==NULL B. head->next==NULL

C. head->next!=NULL D. head!=NULL

5、一个栈的输入序列为:1,2,3,4,则栈的不可能输出的序列是()。

A. 1243 B. 2134 C. 1432 D. 4312 E. 3214

五星文库wxphp.com包含总结汇报、办公文档、IT计算机、考试资料、文档下载、党团工作、资格考试、教程攻略、计划方案、教学研究以及数据结构试题库集及答案等内容。

本文共54页12345>>54