资源描述：
《数据结构练习3(栈和队列)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、数据结构练习（栈和队列）一、选择题1．有5个元素a,b,c,d,e依次进栈，允许任何时候出栈，则可能的出栈序列是C。A．baecdB．dceabC．abedcD．aebcd2．下列有关递归的叙述，不正确的是B。A．在计算机系统内，执行递归函数是通过自动使用栈来实现的。B．在时间和空间效率方面，递归算法比非递归算法好。C．递归函数的求解过程分为递推（进栈）和回推（出栈）两个阶段。D．在递归函数中必须有终止递归的条件。3．栈和队列均属于哪一种逻辑结构A。A．线性结构B．顺序结构C．非线性结构D．链表结构4．设输入元
2、素为1、2、3、P和A，输入次序为123PA，元素经过栈后得到各种输出序列，则可以作为高级语言变量名的序列有D种。A．4B．5C．6D．75．一个队列的入队序列为a，b，c，d，则该队列的输出序列是B。A．dcbaB．abcdC．adcbD．cbda6．在一个链式队列中，假设f和r分别为队头和队尾指针，则插入s所指结点的运算是B。A.f->next=s;f=s;B.r->next=s;r=s;C.s->next=s;r=s;D.s->next=f;f=s;7．如果5个元素出栈的顺序是1、2、3、4、5，则进栈的
3、顺序可能是C。A．3、5、4、1、2B．1、4、5、3、2C．5、4、1、3、2D．2、4、3、1、58．已知一个栈的进栈序列为1，2，3，…，n，其出栈输出序列是p1，p2，p3，…，pn。若p1=3，则p2的值D。A．一定是2B．一定是1C．可能是1D．可能是29．以1，2，3，…，n的顺序进队列，则可能的出队序列有D种。A．1B．nC．n(n+1)/2D．10．在计算递归函数时，如不用递归过程，应借助于B这种数据结构。A.线性表B.栈C.队列D.双向队列二、填空题1．栈和队列是一种特殊的线性表，其特殊性体
4、现在是运算受限线性表。设现有元素e1,e2,e3,e4,e5和e6依次进栈，若出栈的序列是e2,e4,e3,e6,e5,e1，则栈S的容量至少是3。2．顺序循环队列中，设队头指针为front，队尾指针为rear，队中最多可有MAX个元素，采用少用一个存储单元的方法区分队满与队空问题，则元素入队列时队尾指针的变化为rear=(rear+1)%MAX；元素出队列时队头指针的变化为front=(front+1)%MAX；队列中的元素个数为(rear-fort+MAX)%MAX 。队满的判别条件为为(rear+1)%M
5、AX=front，队空的判别条件为rear==front。3．下列函数的功能是从首尾开始依次交换。voidconvert(char*s,intn){chart;if(n>0){t=*(s+n-1);*(s+n-1)=*s;*s=t;convert(++s,n-2);}elsereturn;}4．下列算法的功能判断回文。intfunc(){InitStack(S);//初始化栈InitQueue(Q);//初始化队列while((c=getchar())!=’’){Push(S,c);EnQueue(Q,c)
6、;}while(!StackEmpty(S)){Pop(S,a);DeQueue(Q,b);if(a!=b)return0;}return1;}三、解答题1．用一维数组a[7]顺序存储一个循环队列，队首和队尾指针分别用front和rear表示，当前队列中已有5个元素：22，30，16，36，58，其中22是队首，front值为5，请画出对应的存储状态图，当连续做两次出队运算后，再做两次入队运算，让元素80，55依次进队，请再画出对应的存储状态图。225836163055805836162.用一个带头结点的循环链
7、表来表示循环队列，且该队列只设尾指针。编写初始化、入队、出队操作算法。StructLNode{ElemTypedata;LNode*next;}LinkQueue;LinkQueue*rear;VoidEnQueue(LinkQueue*&rear,ElemTypeitem){LNode*newPtr=newLNode;newptr->data=item;newptr->next=NULL；if(rear==NULL)rear=newptr;newptr->next=Newptr;}Else{newptr->n
8、ext=rear->next;rear->next=newptr;rear=newptr;}}ElemTypeoutQueue(LinkQueue&&rear){if(rear==NULL)cout<<错误<next;if(p==rear)rear=NULL;else{rear->neat=p->nex
