资源描述:
《数据结构练习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