数据结构习题

1、数据结构第三章习题3.1单项选择题2 .一个栈的入栈序列a,b,c,d,e,则栈的不可能的输出序列是。A.edcbaB.DecbaC.DceabD.abcde3 .若已知一个栈的入栈序列是1,2,3,若p1=n,贝Upi为oA.i.B.n=I4 .栈结构通常采用的两种存储结构是A.顺序存储结构和链表存储结构C.链表存储结构和数组.n,其输出序列为p1,p2,p3,pn,C.n-i+1D.不确定B.散链方式和索引方式D.线性存储结构和非线性存储结构B.ST->top=0D.ST->top=m05 .判定一个栈ST（最多元素为m0）为空的条件是A.ST->top<>0

2、C.ST->top<>m06 .判定一个栈ST（最多元素为m0）为栈满的条件是。A.ST->top!=0B.ST->top=0C.ST->top!=m0D.ST->top=m07 .栈的特点是,队列的特点是。A先进先出B.先进后出8 .一个队列的入栈序列是1,2,3,4,则队列的输出序列是A.4,3,2,1B.1,2,3,4C.1,4,3,2D.3,2,4,19 .判定一个队列QU（最多元素为m0）为空的条件是。A.QU->rear-QU->front=m0B.QU->rear-QU->front-1=m0C.QU->fr

3、ont=QU->rearD.QU->front=QU->rear+110 .判定一个队列QU(最多元素为m0)为满队列的条件是A.QU->rear-QU->front=m0B.QU->rear-QU->front-1=m0C.QU->front=QU->rearD.QU->front=QU->rear+111 .判定一个循环队列QU(最多元素为m0)为空的条件是A. QU->front=(QU->rear+1)%m0B. QU->front!=(QU->rear+1)%m0C.QU->front=Q

4、U->rearD.QU->front!=QU->rear12 .判定一个循环队列QU(最多元素为m0)为满队列的条件是A. QU->front=(QU->rear+1)%m0B. QU->front!=(QU->rear+1)%m0C.QU->front=QU->rearD.QU->front!=QU->rear+112 .向一个栈顶指针为HS的链栈中插入一个s所指结点时，则执行。HS->next=s;A. s->next=HS->next;HS->next=s;B. s->next=HS;HS=s

5、;C. s->next=HS;HS=HS->next;13 .从一个栈顶指针为HS的链栈中删除一个结点时，用x保存被删结点的值，则执行。Ax=HS;HS=HS->next;B. x=HS->data;C. HS=HS->next;x=HS->data;D. x=HS->data;HS=HS->next;14 .在一个链队中，假设f和r分别为队首和队尾指针，则插入s所指结点的运算时。A. f->next=s;f=s;B. r->next=s;r=s;C. s->next=r;r=s;D. s->next=f;f=s;15 .

6、在一个链队中，假设f和r分别为队首和队尾指针，则删除一个结点的运算时。A. r=f->next;B. r=r->next;C. f=f->next;D. f=r-next;3 .2填空题4 .向栈中压入元素的操作是5 .对栈进行退栈的操作是6 .在一个循环队列中，队首指针指向队首元素的7 .从循环队列中删除一个元素时，其操作是8 .在具有个单元的循环队列中，队满时共有个元素9 .在栈顶指针为HS的链栈中，判定栈空的条件是一。10 .在栈顶指针为HS的链栈中，计算该链站中结点个数的函数时。11 .在HQ的链队中，判定只有一个结点的条件是。12 .在HQ的链队中，计算该链队中结点

7、个数的函数是。3.3顺序栈习题解析给出输入项A,B,C.如果输入项序列由1 .对于一个栈，全部可能的输出序列。解：本题利用栈的“后进先出”的特点,A进A出B进B出C进C出A进A出B进C进C出B出A进B进B出A出C进C出A进B进B出C进C出A出A进B进C进C出B出A出不可能产生的输出序列CABA,B,C所组成，是给出有如下几种情况：产生输出序列ABC产生输出序列ACB产生输出序列BAC产生输出序列BCA产生输出序列CBA2 .有两个栈si和s2共享存储空间c1,m,其中一个栈底设在c1处，另一个栈底设在cm0处，分别编写si和s2的进栈push(i,x)、退栈pop(i)和设置栈空setnull

8、(i)的函数，其中i=1,2。注意：仅当整个空间c1,m0占满时才产生上溢。解：该共享栈的结构如图2.3所示，两栈的最多元素个数为m0,top1是栈1的栈指针，top2是栈2的栈指针，当top2=top1+1时出现上溢出，当top1=0时栈1出现下溢出，当top2=m0+1时栈2出现下溢出。根据上述原理得到如下函数：top1top2栈1底栈1顶图2.3共享栈/*top1,top2和m0均为已赋初值的voidpush(x,i)栈2顶栈2底int型全局变量*/a1a2anbmb2b1c的元素序号12.nm0-1m0intx,I(if(top1=top2-1)printf(上溢出！n");

9、elseif(i=1)/*对第一个栈进行入栈操作*/(top1+;ctop1=x;)else/*对第二个栈进行入栈操作*/(top2-;ctop2=x;)/*函数pop*/voidpop(i)inti;(if(i=1)/*对第一个栈进行出栈操作*/if(top1=0)printf(栈1下溢出！n”)；else(pop=ctop1;top1-;)else/*对第二个栈进行出栈操作*/if(top2=m0+1)printf(栈2下溢出！n");else(pop=ctop2;top2+;)/*函数setnull*/setnull(i)inti;(if(i=1)top1=0;elsetop2

10、=m0+1;)4.证明：有可能从初始输入序列1,2,.n,利用一个栈得到输出序列p1,p2,.,pn(p1,p2星n1,2,-.n的一种排列)的充分必要条件是：不存在这样的i,j,k,满足i<j<k同时pj<pk<pi.证明：【充分条件】如果不存在这样的i,j,k满足i<j<k同时pj<pk<pi,即对于输入序列：pj,pk-pi,(pj<pk<pi)不存在这样的输出序列：,，pi,pj，,pk，,，(或简单地对于输入序列1,2,3不存在输出序列3,1,2)从中看到，pi后进先出，是满足栈的特点，因为pi最大也就是在pj和pk之后进入

11、，却在输出序列中排在pj和pk之前，同时也说明，在pk之前先进入的pj不可能在pk之后出来，反过来说明满足先进后出的特点，所以构成一个栈。【必要条件】如果初始输入序列是1,2,n,假设是进栈，又同时存在i,j,k满足i<j<k同时pj<pk<pi,即对于输入序列：一pj,pk-pi,(pj<pk<pi)存在这样的输出序列：一pi,pj-pk,从中看到，pi先进后出，是满足栈的特点，因为pi最大也就是在pj和pk之后进入，同时看到在pk之前先进入的pj却在pk之前出来，反过来说明不满足先进后出的特点，与前面的假设是栈不一致，本题即证。6.已知两个整数集合A和B

12、,它们的元素分别依元素值递增有序存放在两个单链表HA和HB中，编写一个函数求出这两个集合的并集C,并要求表示集合C的链表的结点仍依元素值递增有序存放。解：假设HA和HB的头指针分别为ha和hb,先设置一个空的循环单链表HC,头指针为hc,之后依次比较HA和HB的当前结点的元素值，将较小元素值的结点复制一个并链接到HC的末尾，若相等，则将其中之一复制一个并链接到HC的末尾。当HA或HB为空后，把另一个链表的余下结点都复制并链接到HC的末尾。实现本题功能的函数如下：voidunion(ha,hb,hc)node*ha,*hb,*hc;node*p,*q,*r,*s;hc=node*malloc(s

13、izeof(node);/*建立一个头结点，r总是指向HC链表的最后一个结点*/r=hc;p=ha;q=hb;while(p!=NULL&&q!=NULL)if(p->data<q->data)s=(node*)malloc(sizeof(node);s->data=p->data;r->next=s;r=s;p=p->next;elseif(p->data>q->data)s=(node*)malloc(sizeof(node);s->data=q->data;r->next=s;r=s;q=q-&

14、gt;next;else/*p->data=q->data的情况/s=node*malloc(sizeof(node);q=q->next;if(p=NULL)/*把q及之后的结点复制到HC中*/while(q!=NULL)s=(node*)malloc(sizeof(node);s->data=p->data;r->next=s;r=s;p=p->next;r->next=NULL;s=hc;hc=hc->next;free(s);/*删除头结点*/15.假设在长度大于1的循环单链表中，既无头结点也无头指针，p为指向该链表中某个结点的指针，编写一个函数删除该结点的前驱结点。解：本题利用循环单链表的特点，通过p指针可循环找