设有一个栈,元素依次进栈的顺序为a,b,c,d,e。下列( )是不可能的出栈序列。(2.0) A.d,c,a,b,e B.c,b,e,d,a C.a,b,c,d,e D.a,c,b,d,e
时间: 2023-10-13 10:07:22 浏览: 142
栈的出栈序列必须满足后进先出的原则。对于这个栈,元素进栈顺序为a,b,c,d,e。因此,栈的底部元素是a,栈的顶部元素是e。则:
A. d,c,a,b,e 不可能出现,因为元素e必须在d,c,a,b之后出栈;
B. c,b,e,d,a 不可能出现,因为元素a必须在c,b,e,d之后出栈;
C. a,b,c,d,e 可能出现,因为栈的出栈顺序与元素进栈顺序相同;
D. a,c,b,d,e 可能出现,因为元素c可以在a,b之前或之后出栈。
因此,不可能的出栈序列是A和B。答案为A、B不可能。
相关问题
设有A、B、C、D四个元素顺序进栈,在进栈过程可以出栈,出栈次序错误的排列是
四个元素顺序进栈,共有 4! = 24 种出栈次序,其中有且仅有一种是正确的出栈次序。错误的排列包括:
1. A B C D
2. A B D C
3. A C B D
4. A D B C
5. B A C D
6. B A D C
7. B C A D
8. B D A C
9. C A B D
10. C B A D
11. C D A B
12. D A B C
13. D B A C
14. D C B A
正确的出栈次序是:D C B A。
设有一顺序栈S,元素a,b,c,d,e,f,g,h依次进栈,如果8个元素出栈的顺序是d,f,e,c,h,g,b,a,则栈的容量至少应该是多少
个?
根据出栈顺序可以得到,a和b在栈中的顺序是相邻的,c在a之前,d在b之前,e在f之前,g在h之前,因此可以分为两个子序列:
1. b,a,c,d
2. e,f,g,h
出栈的顺序也可以看作是两个子序列的拼接,因此反过来入栈时应该执行以下操作:
1. 先将d入栈,再将c入栈,然后将a和b按顺序入栈
2. 再将h入栈,再将g入栈,然后将e和f按顺序入栈
容量至少应该是8个。