《第三章栈和队列习题-数据结构》由会员分享，可在线阅读，更多相关《第三章栈和队列习题-数据结构（11页珍藏版）》请在金锄头文库上搜索。
1、习题三 栈和队列一 单项选择题1. 在作进栈运算时,应先判别栈是否( ),在作退栈运算时应先判别栈是否( )。当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为( )。, : A. 空 B. 满 C. 上溢 D. 下溢 : A. n-1 B. n C. n+1 D. n/2 2若已知一个栈的进栈序列是1，2，3，n，其输出序列为p1，p2，p3，.，pn，若p13，则p2为( )。A 可能是2 B 一定是2 C 可能是1 D 一定是13. 有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（ ）A. 5 4 3 6 1 2 B. 4 5 3 1 2 6
2、C. 3 4 6 5 2 1 D. 2 3 4 1 5 6 4.设有一顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素出栈的顺序是s2,s3,s4, s6 , s5,s1,则栈的容量至少应该是 （ ）A.2 B. 3 C. 5 D.65. 若栈采用顺序存储方式存储，现两栈共享空间V1.m，topi代表第i个栈( i =1,2)栈顶，栈1的底在v1，栈2的底在Vm，则栈满的条件是（ ）。A. |top2-top1|=0 B. top1+1=top2 C. top1+top2=m D. top1=top26. 执行完下列语句段后，i值为：（ ） int f(int x) re
3、turn (x0) ? x* f(x-1):2); int i ; i =f(f(1);A2 B. 4 C. 8 D. 无限递归7. 表达式3* 2(4+2*2-6*3)-5求值过程中当扫描到6时，对象栈和算符栈为（ ），其中为乘幂 。A. 3,2,4,1,1；(*(+*- B. 3,2,8；(*- C. 3,2,4,2,2；(*(- D. 3,2,8；(*(-8. 用链接方式存储的队列，在进行删除运算时（ ）。A. 仅修改头指针 B. 仅修改尾指针 C. 头、尾指针都要修改 D. 头、尾指针可能都要修改9. 递归过程或函数调用时，处理参数及返回地址，要用一种称为（ ）的数据结构。A队列 B多
4、维数组 C栈 D. 线性表10设C语言数组Datam+1作为循环队列SQ的存储空间， front为队头指针，rear为队尾指针，则执行出队操作的语句为 （ ）A.front=front+1 B. front=（front+1）% mC.rear=(rear+1)%(m+1) D. front=(front+1)%(m+1)11.循环队列的队满条件为 ( )A. (sq.rear+1) % maxsize =(sq.front+1) % maxsize;B. (sq.front+1) % maxsize =sq.rearC. (sq.rear+1) % maxsize =sq.frontD.sq
5、.rear =sq.front12. 栈和队列的共同点是（ ）。A. 都是先进先出 B. 都是先进后出 C. 只允许在端点处插入和删除元素 D. 没有共同点二、填空题 1栈是_的线性表，其运算遵循_的原则。2. 一个栈的输入序列是：1，2，3则不可能的栈输出序列是_。3用S表示入栈操作，X表示出栈操作，若元素入栈的顺序为1234，为了得到1342出栈顺序，相应的S和X的操作串为_。4. 循环队列的引入，目的是为了克服_。 5队列是限制插入只能在表的一端，而删除在表的另一端进行的线性表，其特点是_。6. 已知链队列的头尾指针分别是f和r，则将值x入队的操作序列是_。7表达式求值是_应用的一个典型
6、例子。8循环队列用数组A0.m-1存放其元素值，已知其头尾指针分别是front和rear ，则当前队列的元素个数是_。9. 以下运算实现在链栈上的初始化，请在_处用请适当句子予以填充。Void InitStacl(LstackTp *ls) _;10. 以下运算实现在链栈上的进栈，请在处用请适当句子予以填充。Void Push（LStackTp *ls,DataType x） LstackTp *p;p=malloc(sizeof(LstackTp); _; p-next=ls; _; 11以下运算实现在链栈上的退栈，请在_处用请适当句子予以填充。Int Pop(LstackTp *ls,Da
7、taType *x) LstackTp *p; if(ls!=NULL) p=ls; *x=_; ls=ls-next; _; return(1)； else return(0); 12. 以下运算实现在链队上的入队列，请在_处用适当句子予以填充。Void EnQueue(QueptrTp *lq,DataType x) LqueueTp *p; p=(LqueueTp *)malloc(sizeof(LqueueTp); _=x; p-next=NULL; (lq-rear)-next=_; _; 三、应用题1给出栈的两种存储结构形式名称，在这两种栈的存储结构中如何判别栈空与栈满？2. 画出
8、对算术表达式A-B*C/D-EF求值时操作数栈和运算符栈的变化过程。3. 将两个栈存入数组V1.m应如何安排最好？这时栈空、栈满的条件是什么？ 4. 怎样判定循环队列的空和满？四、算法设计题1借助栈(可用栈的基本运算)来实现单链表的逆置运算。2. 设表达式以字符形式已存入数组En中，#为表达式的结束符，试写出判断表达式中括号（和）是否配对的C语言描述算法：EXYX(E); (注：算法中可调用栈操作的基本算法。) 3. 假设以I和O分别表示入栈和出栈操作。栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由I和O组成的序列，称可以操作的序列为合法序列，否则称为非法序列。 （1）下面所示的序列中
9、哪些是合法的？ A. IOIIOIOO B. IOOIOIIO C. IIIOIOIO D. IIIOOIOO （2）通过对（1）的分析，写出一个算法，判定所给的操作序列是否合法。若合法，返回true，否则返回false（假定被判定的操作序列已存入一维数组中）。4. 设有两个栈S1,S2都采用顺序栈方式，并且共享一个存储区O.maxsize-1,为了尽量利用空间，减少溢出的可能，可采用栈顶相向，迎面增长的存储方式。试设计S1,S2有关入栈和出栈的操作算法。5. 请利用两个栈S1和S2来模拟一个队列。已知栈的三个运算定义如下：PUSH(ST,x):元素x入ST栈；POP(ST,x)：ST栈顶元素
10、出栈，赋给变量x；Sempty(ST)：判ST栈是否为空。那么如何利用栈的运算来实现该队列的三个运算：enqueue:插入一个元素入队列； dequeue:删除一个元素出队列；queue_empty：判队列为空。（请写明算法的思想及必要的注释）6 要求循环队列不损失一个空间全部都能得到利用，设置一个标志tag,以tag为0或1来区分头尾指针相同时的队列状态的空与满，请编写与此相应的入队与出队算法。7. 已知Q是一个非空队列，S是一个空栈。仅用队列和栈的ADT函数和少量工作变量，编写一个算法，将队列Q中的所有元素逆置。栈的ADT函数有：makeEmpty(s:stack); 置空栈push(s:
11、stack;value:datatype); 新元素value进栈pop(s:stack):datatype; 出栈，返回栈顶值isEmpty(s:stack):Boolean; 判栈空否 队列的 ADT函数有：enqueue(q:queue:value:datatype); 元素value进队deQueue(q:queue):datatype; 出队列，返回队头值isEmpty(q:queue):boolean; 判队列空否 第3章 栈和队列一 单项选择题1. B A B2 A 3. C4.B5. B6. B7. D8. D9. C10D11.C12. C二、填空题 1操作受限（或限定仅在表
12、尾进行插入和删除操作） 后进先出2. 3 1 23SSSS 4. 假溢出时大量移动数据元素 5先进先出6. s=(LinkedList)malloc(sizeof(LNode)； s-data=x;s-next=r-next；r-next=s；r=s；7栈8（rear-front+m）% m；9ls=NULL10 p-data=x, ls=p11p-data, free(p)12 p-data, p, lq-rear=p三、应用题1【解答】（1）顺序栈 （top用来存放栈顶元素的下标）判断栈S空：如果S-top=-1表示栈空。判断栈S满：如果S-top=Stack_Size-1表示栈满。(2) 链栈（top为栈顶指针，指向当
