数据结构练习(含答案):第三章栈和队列
《数据结构练习(含答案):第三章栈和队列》由会员分享,可在线阅读,更多相关《数据结构练习(含答案):第三章栈和队列(5页珍藏版)》请在装配图网上搜索。
1、第三章 栈和队列 一、选择题 1. 一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是( )。 (A) edcba(B)decba(C)dceab (D)abcde 参考答案:C 2.栈结构通常采用的两种存储结构是( )。 (A) 线性存储结构和链表存储结构(B)散列方式和索引方式 (C)链表存储结构和数组 (D)线性存储结构和非线性存储结构 参考答案:A 3.判定一个栈ST(最多元素为m0)为空的条件是( )。 (A) ST-〉top!=0 (B)ST-〉top==0 (C)ST-〉top!=m0 (D)ST-〉top=m0 参考答案:B 4.判
2、定一个栈ST(最多元素为m0)为栈满的条件是( )。 (A)ST->top!=0 (B)ST->top==0 (C)ST->top!=m0-1(D)ST->top==m0 参考答案:D 5.一个队列的入列序列是1,2,3,4,则队列的输出序列是( )。 (A)4,3,2,1(B)1,2,3,4(C)1,4,3,2(D)3,2,4,1 参考答案:B 6.循环队列用数组A[0,m-1]存放其元素值,已知其头尾指针分别是front和rear则当前队列中的元素个数是( ) (A)(rear-front+m)%m (B) rear-front+1 (C)rear-front-1(D)r
3、ear-front 参考答案:B 7.栈和队列的共同点是( ) (A) 都是先进后出 (B)都是先进先出 (C)只允许在端点处插入和删除元素(D)没有共同点 参考答案:C 8.表达式a*(b+c)-d的后缀表达式是( )。 (A)abcd*+-(B)abc+*d- (C)abc*+d-(D)-+*abcd 参考答案:B 9.4个元素a1,a2,a3和a4依次通过一个栈,在a4进栈前,栈的状态,则不可能的出栈序是( ) (A)a4,a3,a2,a1 (B)a3,a2,a4,a1 (C)a3,a1,a4,a2 (D)a3,a4,a2,a1 参
4、考答案:C 10.以数组Q[0..m-1]存放循环队列中的元素,变量rear和qulen分别指示循环队列中队尾元素的实际位置和当前队列中元素的个数,队列第一个元素的实际位置是( ) (A)rear-qulen (B)rear-qulen+m (C)m-qulen (D)1+(rear+m-qulen)% m 参考答案:D 二、填空题1、 1.栈的特点是_______________________,队列的特点是__________________________。 先进后出; 先进先出; 2.线性表、栈和队列都是_____________________结构,可以在线
5、性表的______________位置插入和删除元素,对于栈只能在________插入和删除元素,对于队列只能在_______插入元素和_________删除元素。 线性 ; 任何 ;栈顶;队尾;对头 3.一个栈的输入序列是12345,则栈有输出序列12345是____________。(正确/错误) 正确的 4.设栈S和队列Q的初始状态皆为空,元素a1,a2,a3,a4,a5和a6依次通过一个栈,一个元素出栈后即进入队列Q,若6个元素出队列的顺序是a3,a5,a4,a6,a2,a1则栈S至少应该容纳_____个元素。 4 三、算法设计题 1.假设有两个栈s1和s2共享一
6、个数组stack[M],其中一个栈底设在stack[0]处,另一个栈底设在stack[M-1]处。试编写对任一栈作进栈和出栈运算的C函数push(x,i)和pop(i),i=l,2。其中i=1表示左边的栈,,i=2表示右边的栈。要求在整个数组元素都被占用时才产生溢出。 #define M 100 elemtype stack[M]; int top1=0,top2=m-1; int push(elemtype x,int i) { if(top1-top2==1) return(1); /*上溢处理*/ else if(i==1) stack[top1++]=x; if(i=
7、=2)stack[top2--]=x; return(0); } int pop(elemtype *px,int i) { if(i==1) if(top1==0) return(1); else { top1--; *px=stack[top1]; return(0); } else if(i==2) if(top2==M-1) return(1); else { top2++; *px=stack[top2]; return(0); } } 2.利用两个栈s1,s2模拟一个队列时,如何用栈的运算来实现该队列的运算?写出模拟队列的插入
8、和删除的C函数。 一个栈s1用于插入元素,另一个栈s2用于删除元素. elemtype s1[MAXSIZE],s2[MAZSIZE]; int top1,top2; void enqueue(elemtype x) { if(top1==MAXSIZE) return(1); else { push(s1,x); return(0); }} void dequeue(elemtype *px) { elemtype x; top2=0; while(!empty(s1)) { pop(s1,&x); push(s2,x); } pop(s2,&x); while(!empty(s2)) { pop(s2,&x); push(s1,x); } }
- 温馨提示:
1: 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
2: 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
3.本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
5. 装配图网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。