资源描述：
《03：栈与队列习题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、【基础知识题】1．若按3.1.1节中所示铁道进行车厢调度(注意：两侧铁道均为单向行驶道)，则请回答： (1)如果进站的车厢序列为123，则可能得到的出站车厢序列是什么? (2)如果进站的车厢序列为123456，则能否得到435612和135426的出站序列，并请说明为什么不能得到或者如何得到(即写出以'S'表示进栈和以'X'表示出栈的栈操作序列)。 2．简述栈和线性表的差别。 3．写出下列程序段的输出结果（栈的元素类型SElemType为char）。 voidmain(){ StackS; charx,y; InitStack(S); x='c';y='k'; Push(
2、S,x);Push(S,'a');Push(S,y); Pop(S,x);Push(S,'t');Push(S,x); Pop(S,x);Push(S,'s'); while(!StackEmpty(S)){Pop(S,y);printf(y);}; printf(x); } 4．简述以下算法的功能（栈的元素类型SElemType为int）。 (1)statusalgo1(StackS){ inti,n,A[255]; n=0; while(!StackEmpty(S)){n++;Pop(S,A[n]);}; for(i=1;i<=n;i++)Push
3、(S,A[i]); } (2)statusalgo2(StackS,inte){ StackT;intd; InitStack(T); while(!StackEmpty(S)){ Pop(S,d); if(d!=e)Push(T,d); } while(!StackEmpty(T)){ Pop(T,d); Push(S,d); } } 11．简述队列和栈这两种数据类型的相同点和差异处。 13．简述以下算法的功能（栈和队列的元素类型均为int）。 voidalgo3(Queue&Q) { StackS;intd
4、; InitStack(S); while(!QueueEmpty(Q)) { DeQueue(Q,d);Push(S,d); } while(!StackEmpty(S)) { Pop(S,d);EnQueue(Q,d); } } 【编程练习题】 本章编程练习题中可以利用的栈和队列的类型定义如下： //stack类型 voidInitStack(stack&s); //初始化s为空栈 voidPush(stack&s,charx);//将元素x插入s的栈顶 voidPop(stack&s); //删除s中的栈顶元素 boolSEmpty(st
5、ack&s); //若栈s为空则返回TRUE,否则返回FALSE charGetTop(stack&s); //返回s中的栈顶元素 voidClearStack(stack&s); //将栈s清空 intStackLength(stack&s); //返回栈s中元素个数 voidDestroyStack(stack&s);//销毁栈s结构 //queue类型 voidInitQueue(queue&q); //初始化q为空栈 voidEnQueue(queue&q,charx);//将元素x插入q的队尾 voidDequeue(queue&q); //删除q中队头元素 cha
6、rGetHead(queue&q); //返回q中队头元素 boolQEmpty(queue&q); //若队列q为空则返回TRUE,否则返回FALSE voidClearQueue(queue&q); //将队列q清空 intQueueLength(queue&q); //返回队列q中元素个数 voidDestroyQueue(queue&q); //销毁队列q结构 17.试写一个算法，识别依次读入的一个以@为结束符的字符序列是否为形如'序列1&序列2'模式的字符序列。其中序列1和序列2中都不含字符'&'，且序列2是序列1的逆序列。例如，'a+b&b+a'是属该模式的字符序列，而'
7、1+3&3-1'则不是。 boolmatching(char*str) //若给定字符串str为形如"序列1&序列2"的对称字符串 //(序列2是序列1的逆串)，则返回true，否则返回false 19.假设一个算术表达式中可以包含三种括号：圆括号"("和")"，方括号"["和"]"和花括号"{"和"}"，且这三种括号可按任意的次序嵌套使用（如：…[…{…}…[…]…]…[…]…(…)…）。编写
