资源描述：
《数据结构第章习题.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、数据结构第三章习题3．1单项选择题2.一个栈的入栈序列a,b,c,d,e,则栈的不可能的输出序列是。A.edcbaB.DecbaC.DceabD.abcde3.若已知一个栈的入栈序列是1，2，3，………..n,其输出序列为p1,p2,p3,……,pn,若p1=n,则pi为。A.i.B.n=IC.n-i+1D.不确定4．栈结构通常采用的两种存储结构是。A.顺序存储结构和链表存储结构B.散链方式和索引方式C.链表存储结构和数组D.线性存储结构和非线性存储结构5．判定一个栈ST（最多元素为m0）为空的条件是。A.ST->top<>0B.ST->top=0C.ST->top<>m0D.ST
2、->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->front==QU->rearD.QU->front==QU->rear
3、+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==QU->rearD.QU->front！=QU->rear12.判定一个循环队列QU（最多元素为m0）为满队列的条件是。A.QU->front
4、==（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;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
5、->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.在一个链队中，假设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
6、．在具有个单元的循环队列中，队满时共有个元素9.在栈顶指针为HS的链栈中，判定栈空的条件是。10.在栈顶指针为HS的链栈中，计算该链站中结点个数的函数时。11.在HQ的链队中，判定只有一个结点的条件是。12.在HQ的链队中，计算该链队中结点个数的函数是。3.3顺序栈习题解析1.对于一个栈，给出输入项A,B,C.如果输入项序列由A,B,C所组成，是给出全部可能的输出序列。解：本题利用栈的“后进先出”的特点，有如下几种情况：A进A出B进B出C进C出产生输出序列ABCA进A出B进C进C出B出产生输出序列ACBA进B进B出A出C进C出产生输出序列BACA进B进B出C进C出A出产生输出序列B
7、CAA进B进C进C出B出A出产生输出序列CBA不可能产生的输出序列CAB2.有两个栈s1和s2共享存储空间c[1,m],其中一个栈底设在c[1]处，另一个栈底设在c[m0]处，分别编写s1和s2的进栈push(i,x)、退栈pop(i)和设置栈空setnull(i)的函数，其中i=1,2。注意：仅当整个空间c[1,m0]占满时才产生上溢。解：该共享栈的结构如图2.3所示，两栈的最多元素个数为m0,top1是栈1的栈指针，top2是栈2的栈指针，当top2=top1+1
