数据结构及应用算法教程习题第四章栈和队列.doc

第四章 栈和队列一、选择题1对于栈操作数据的原则是（B ）。A先进先出 B后进先出 C后进后出 D不分顺序2一个栈的输入序列为123n，若输出序列的第一个元素是n，输出第i（1=i0) ? x* f(x-1):2); int i ; i =f(f(1);A2 B4 C8 D无限递归13表达式a*(b+c)-d的后缀表达式是( B )。Aabcd*+- Babc+*d- Cabc*+d- D-+*abcd14设计一个判别表达式中左，右括号是否配对出现的算法，采用（ D ）数据结构最佳。A线性表的顺序存储结构 B队列 C线性表的链式存储结构 D栈15用不带头结点的单链表存储队列时,其队头指针指向队头结点,其队尾指针指向队尾结点，则在进行删除操作时( A )。A仅修改队头指针 B仅修改队尾指针 C队头、队尾指针都要修改 D队头,队尾指针都可能要修改16假设以数组Am存放循环队列的元素,其头尾指针分别为front和rear，则当前队列中的元素个数为（ A ）。A(rear-front+m)%m Brear-front+1 C(front-rear+m)%m D(rear-front)%m17循环队列A0m-1存放其元素值，用front和rear分别表示队头和队尾，则当前队列中的元素数是( A )。A(rear-front+m)%m Brear-front+1 Crear-front-1 Drear-front18循环队列存储在数组A0m中，则入队时的操作为（ C ）。Arear=rear+1 Brear=(rear+1) mod (m-1)Crear=(rear+1) mod m Drear=(rear+1)mod(m+1) 19若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？( B ) A1和 5 B2和4 C4和2 D5和1 21最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是 （ B ）。A(rear+1) MOD n=front Brear=front Crear+1=front D(rear-l) MOD n=front22栈和队列的共同点是（ C ）。A都是先进先出 B都是先进后出 C只允许在端点处插入和删除元素 D没有共同点23栈和队都是（ C ）A顺序存储的线性结构 B链式存储的非线性结构C限制存取点的线性结构 D限制存取点的非线性结构24设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4,e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3,e6,e5,e1则栈S的容量至少应该是( )。A6 B4 C3 D2二、填空题 1_是限定仅在表尾进行插入或删除操作的线性表。2设有一个空栈，栈顶指针为1000H(十六进制)，现有输入序列为1，2，3，4，5，经过PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH之后，输出序列是_，而栈顶指针值是_H。设栈为顺序栈，每个元素占4个字节。4在作进栈运算时应先判别栈是否_(1)_;在作退栈运算时应先判别栈是否_(2)_；当栈中元素为n个，作进栈运算时发生上溢，则说明该栈的最大容量为_(3)_。6用S表示入栈操作，X表示出栈操作，若元素入栈的顺序为1234，为了得到1342出栈顺序，相应的S和X的操作串为_。7循环队列的引入，目的是为了克服_。 8_又称作先进先出表。9已知链队列的头尾指针分别是f和r，则将值x入队的操作序列是_。10区分循环队列的满与空，只有两种方法，它们是_和_。 11设循环队列用数组A1M表示，队首、队尾指针分别是FRONT和TAIL，判定队满的条件为_。12表达式求值是_应用的一个典型例子。13循环队列用数组A0m-1存放其元素值，已知其头尾指针分别是front和rear ，则当前队列的元素个数是_。14设Q0N-1为循环队列，其头、尾指针分别为P和R，则队Q中当前所含元素个数为_。三、应用题1有5 个元素，其入栈次序为：A，B，C，D，E，在各种可能的出栈次序中，以元素C，D最先出栈（即C第一个且D第二个出栈）的次序有哪几个？5如果用一个循环数组q0m-1表示队列时，该队列只有一个队列头指针front，不设队列尾指针rear，而改置计数器count用以记录队列中结点的个数。（1）编写实现队列的三个基本运算：判空、入队、出队（2）队列中能容纳元素的最多个数是多少？ 参考答案一、选择题 1.B2.B 3.C 4.D5.D 6.C 7.B 8.C 9.B 10.D 11.B 12.B 13.B 14.D 15.D 16.A 17.A 18.D 19.B 20.C 21.B 22.C 23.C 24.C二、填空题 1、栈 2、23 100CH 3、0 n+1 top1+1=top24、(1)满 (2)空 (3)n (4)栈底 (5)两栈顶指针相邻（即值之差的绝对值为1）5、链式存储结构 6、SSSS 7、假溢出时大量移动数据元素。 8、队列 9、s=(LinkedList)malloc(sizeof(LNode)； s-data=x;s-next=r-next；r-next=s；r=s； 10、牺牲一个存储单元 设标记 11、（TAIL+1）MOD M=FRONT (数组下标0到M-1，若一定使用1到M，则取模为0者，值改取M 12、栈 13、（rear-front+m）% m； 14、（R-P+N）% N；三、应用题1、三个：CDEBA，CDBEA，CDBAE2、借助栈结构，n个入栈元素可得到1/(n+1)(2n）！/（n!*n!）)种出栈序列。本题4个元素，可有14种出栈序列，abcd和dcba就是其中两种。但dabc和adbc是不可能得到的两种。5、typedef structelemtp qm; int front,count; /front是队首指针，count是队列中元素个数。cqnode; /定义类型标识符。(1)判空：int Empty(cqnode cq) /cq是cqnode类型的变量 if(cq.count=0) return(1)；else return(0); /空队列入队: int EnQueue(cqnode cq，elemtp x)if(count=m)printf(“队满n”)；exit(0); cq.q(cq.front+count)%m=x; /x入队 count+; return(1); /队列中元素个数增加1,入队成功。出队: int DelQueue(cqnode cq)if (count=0)printf(“队空n”)；return(0); printf(“出队元素”，cq.qcq.front); x=cq.qcq.front;cq.front=(cq.front+1)%m; /计算新的队头指针。return(x)(2) 队列中能容纳的元素的个数为m。队头指针front指向队头元素。8、题目分析表达式中的括号有以下三对：（、）、，使用栈，当为左括号时入栈，右括号时，若栈顶是其对应的左括号，则退栈，若不是其对应的左括号，则结论为括号不配对。当表达式结束，若栈为空，则结论表达式括号配对，否则，结论表达式括号不配对。int Match(LinkedList la)/算术表达式存储在以la为头结点的单循环链表中，本算法判断括号是否正确配对char s; /s为字符栈，容量足够大p=la-link; /p为工作指针，指向待处理结点StackInit(s); /初始化栈s while (p!=la) /循环到头结点为止 switch (p-ch) case (:push(s,p-ch); break; case ):if(StackEmpty(s)|StackGetTop(s)!=()printf(“括号不配对n”); return(0); else pop(s);break;case :push(s,p-ch); break; case : if(StackEmpty(s)|StackGetTop(s)!=)printf(“括号不配对n”); return(0); else pop(s);break;case :push(s,p-ch); break; case : if(StackEmpty(s)|StackGetTop(s)!=)printf(“括号不配对n”); return(0); else pop(s);break; p=p