首页 > 试题广场 >

一个栈的入栈序列为1,2,3,...,n ，其出栈序列是 p

[单选题]

一个栈的入栈序列为1,2,3,...,n ，其出栈序列是 p 1 ,p 2 ,p 3 ,...p n 。若p 2 = 3，则 p 3 可能取值的个数是（） 

  • n-3
  • n-2
  • n-1
  • 无法确定
查看正确选项
添加回答
zhisheng_blog头像 zhisheng_blog

答案：C （ n - 1）个

看了别人的一些解析，觉得不够完善，下面给出自己的见解。

首先，栈的先进后出原则大家应该是知道的。

根据题意 p 2 = 3，可以知道 p 1 的可能情况有三种：1，2 或 4 。（看到有些人只想到了 1，2）

为啥这样想呢？这里估计还有一个关键是要考虑到 n 的大小。

当 n = 3 时， p 2 = 3 的话，那么 p 1 有两种情况 1 和 2 。

  • 如果 p 1 = 1 ， 那么 p 3 = 2 ；
  • 如果 p 1 = 2 ，那么 p 3 = 1 ；

此时的话我们就可以看到 p 3 只有两种可能 1 或者 2 （n - 1）个。

当 n > 3 时： p 2 = 3 的话，那么 p 1 有三种情况 1 ， 2 和 4 。

  • 如果 p 1 = 1 ， 那么 p 3 = 2，4，5，... n （n - 2）个
  • 如果 p 1 = 2 ，那么 p 3 = 1，4，5，... n （n - 2）个
  • 如果 p 1 = 4 ，那么 p 3 = 2，5，6，... n （n - 3）个

此时的话我们就可以看到 p 3 的情况有 1，2，4，5，... n （n - 1）个。

综上所述就是 p 3 可能取值的个数是 （n - 1）个。

发表于 2017-03-08 19:21:54 回复(11)
更多回答
羽落长安头像 羽落长安
最简单的举例子:
n=3
-->1,2,3
-->p1,p2,p3         p2=3
所有可能情况:
1 2 3
1 3 2
2 1 3
2 3 1
3 2 1
==>n=3时答案为2
发表于 2017-02-01 12:12:56 回复(0)
福娃头像 福娃
第二个出栈的是3,根据栈先进后出的规律，可知第一个可能是1也有可能是2。假设第一个出栈的是1,则留在栈里边的是2,等3出栈后2接着出栈。对于第一个出栈的是2情况也可以推出，3后面可能是1,其他的数字可以进栈接着出栈得到。因此，唯一能排除的数字就是3,其他数字都有可能！故为n-1
发表于 2016-12-03 13:34:21 回复(5)
用代碼將夢想照進現實头像 用代碼將夢想照進現實
说说我自己的想法。首先3后面的都可以取到，那么就有n-3种取法。p2=3弹出后，可以接着弹出p3=2，再加一种；p3能不能取到1呢？可以。假如我们在p2=3弹出前先让p1=2弹出，那么p3就可以取到1。因此，综上所述，共有n-3+1+1=n-1种取法。
发表于 2018-10-24 16:12:26 回复(0)
牛客985409号头像 牛客985409号
如果第一个出栈的是2则p3可能的取值为1、4、5、...、n，如果第一个出栈的是4则p3可能的取值为2、5、...、n，综上p3可能的取值为1、2、4、5、...、n，即p3可能的取值有n-1个
编辑于 2016-11-29 21:50:21 回复(7)
背、驰头像 背、驰
考虑不全，除3外其他都可能是p3；
发表于 2018-08-09 11:51:48 回复(0)
牛客476474541号头像 牛客476474541号
由栈先进后出的性质，知p1只能是1或者2，当p1=1时，p2可以取3，即p2= 3, 那么此时p3可以取的数是2,4,5,6........n(没有1和3)，
当p1=2时，p2=3,那门此时p3= 1,4,5,6.......n.
故综上所述，p3的取值可以是1,2,4,5,6，.......n(就是没有3)，故p3的取值可能有n-1个

发表于 2021-10-19 23:07:56 回复(0)
字节内推dd头像 字节内推dd
这题不选 n-2 而是选 n-1 的原因是：你并不知道 p1 出来的是谁。
也就意味着：
p1出来的是1 时 ，能取到除了 1、3 的其他，共计 n-2 个
p1出来的是2 时 ，能取到除了 2、3 的其他，共计 n-2个
p1出来的是3 时 ，能取到除了 4、3 的其他，共计 n-2个
但是因为你不知道 p1 到底是谁，所以综上所述：其实能取到除了 3 之外的 n-1 个数。

ps：个人觉得这个题出的有病，不太好（也可能是我自己的问题，没有和出题老师同频率）。
发表于 2022-03-04 19:44:36 回复(0)
牛客726231979号头像 牛客726231979号
这里问的有多少种可能不是有多少个，所以除了3，其他的都有可能
发表于 2023-11-30 18:14:55 回复(0)
黄奕强头像 黄奕强
搞活经济
发表于 2023-04-09 12:07:20 回复(1)
摩托圆头像 摩托圆
我就奇怪p1和p2都出栈了，一共也就n个数，出了2个，不应该是n-2么？p3取值为什么还有n-1个？
发表于 2022-08-05 12:48:34 回复(2)
牛客768117412号头像 牛客768117412号
入栈序列不代表次序
发表于 2022-04-05 16:43:17 回复(0)
意会。头像 意会。
除了3，其他的都有可能。
发表于 2021-11-02 11:44:57 回复(0)
先胖三斤做个预实验头像 先胖三斤做个预实验
其实问题的关键在于能不能取到1，可以就是n-1
发表于 2021-08-29 09:13:52 回复(0)
禾离拼了头像 禾离拼了
两种情况：
①1,2,3,4进栈，出栈序列为4,3,,p3 。那么p3的值可能是2∪[5,n]
②1,2进栈，2出栈，3进栈，3出栈，出栈序列为2,3,p3。那么p3的值可能是1∪[4,n]
综上取并集，得到[1,2]∪[4,n] 
发表于 2021-03-19 18:52:06 回复(0)
Kevin11111头像 Kevin11111
本题其实和栈的先进后出没什么关系吧;
当n=3时,p2=3,p1,p3只剩俩个值,所以p3只能是其中之一,也就是n-1
当n>3时,p2=3,p3可能是除了3以外任意一个,也就是n-1
编辑于 2019-12-17 17:45:10 回复(0)
橘子橘子橘子头像 橘子橘子橘子
除了3都有可能，所以是n-1
发表于 2019-08-21 19:41:57 回复(0)
门头沟落魄打工人头像 门头沟落魄打工人

少考虑的一种情况。。。。

第二个出栈的是3的话，可能有几种情况：

  • 先2后3，则下一个可能是除了2和3外的所有数
  • 先4后3，则下一个可能是除了4和3外的所有数
  • 先1后3，则下一个可能是除了1和3外的所有数

综上，除了3以外的所有数都可能取到，是n-1

发表于 2019-08-06 08:54:31 回复(0)
wxl_1605头像 wxl_1605
题目的意思是p3的可能取值，并没有说在一种情况的时候的可能取值。
发表于 2018-09-17 20:42:06 回复(0)
krystal-2018头像 krystal-2018
代入法，当n=3时。
所有的可能情况为
1,2,3
1,3,2
2,3,1
2,1,3
3,2,1
发表于 2018-09-16 20:57:52 回复(0)
提交观点

问题信息

栈
上传者：城市里的养猫者
难度：
25条回答 15669浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号