计算机学科专业基础2026 真题档案

一个栈的入栈序列是 1,2,…,n（n≥ 3）。请回答下列问题。

（1）当 n=9 时，是否能得到出栈序列 2,3,1,6,4,7,5,9,8？是否能得到出栈序列 2,3,1,5,6,7,4,9,8？（2 分）

（2）对于由 1,2,…,n 组成的任意序列 P₁,P₂,…,P_n 中的元素 P_i、P_j、P_k（i<j<k），当 P_i、P_j、P_k 的大小满足什么关系时，序列 P₁,P₂,…,P_n 不是可以得到的出栈序列？（2 分）

（3）当 n=4 时，可以得到的以 2 开头的出栈序列的个数是多少？（2 分）

（4）若当 n=k-1 时可以得到的出栈序列个数为 M，则当 n=k 时可以得到的以 1 开头的出栈序列的个数是多少？可以得到的以 2 开头的出栈序列的个数是多少？可以得到的所有出栈序列的个数是多少？（4 分）