栈的典型题目.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,关于栈的考题,1.有,A B C,三辆列车顺序进入栈式结构的站台，问这三辆车开出站台的序列有多少种，并写出具体序列。,2.某堆栈的输入序列是,a、b、c、d，,则下列序列中,不可能,是它的输出序列的是（）,A.a,c,b,d B.b,c,d,a C.c,d,b,a D.d,c,a,b,D,3.一个栈的输入序列为123,n，,若输出序列的第一个元素是,n，,则输出的第,i,个元素是（）,A.,不确定,B.n-i+1 C.i D.n-i,B,关于栈的考题,4.一个栈的输入序列为123,n，,若输出序列的第一个元素是,i，,则输出的第,j,个元素是（）,A.i-j-1 B.i-j C.i-j+1 D.,不确定,D,5.一个栈的输入序列为123,n，,若输出序列为,P,1,，P,2,，P,3,，.，P,N,，,若,P,N,是,n，,则,P,i,是（）,A.i B.n-i C.n-i+1 D.,不确定,D,6.输入序列为,ABC，,要变为,CBA，,经过的栈操作为（）,A.push,pop,push,pop,push,pop,B.push,push,push,pop,pop,pop,C.push,push,pop,pop,push,pop,D.push,pop,push,push,pop,pop,B,关于栈的考题,7.,在一个算法中需要建立多个堆栈时可以选用下列三种方案之一，试问：这三中方案之间相比较各有什么优缺点？（1）分别用多个顺序存储空间建立多个独立的堆栈。（2）多个堆栈共享一个顺序存储空间。（3）分别建立多个独立的链接堆栈。,1）每个栈各用一个顺序存储空间时，操作简便，但分配空间小了容易产生溢出，分配空间大了容易浪费，各栈不能共享空间。,2）多个栈共享一个顺序存储空间，充分利用了存储空间，只有在整个存储空间都用完时才会产生溢出，其缺点是当一个栈满时要向左右栈查询有无空闲单元，如果有则要移动元素和修改相关的栈底和栈顶指针。当接近栈满时，查询空闲单元、移动元素和修改栈底栈顶指针的操作频繁，计算复杂并且耗费时间。,3）多个链栈一般不考虑栈的溢出（仅受用户内存空间限制），缺点是栈中元素要以指针相连接，比顺序存储多占了存储空间。,关于栈的考题,8.,试证明：若借助栈由输入序列123,n,得到的输出序列,P1P2,Pn,(,它是输入序列的一个排列)，则在输出序列中不可能出现这样的情形：存在着,ijk,使,Pk,Pi,Pj,。,举例说，对于输入序列1、2、3，不可能出现3、1、2的输出序列。,证明：假设成立，这意味着在,Pk,出栈之前,Pi,和,Pj,都已入栈，且留在栈中。但在,Pk,出栈后，要满足,Pi,Pj,的出栈顺序式不可能的，因为按照输入顺序，当,Pi,与,Pj,同时在栈中时，必然,Pi,被,Pj,封盖，所以根据栈后进先出的性质，当,ijk,时必有,Pk,Pj,Pi，,与假设矛盾，所以命题不成立。,