【单选题】【 3-1-8 】 已知一个栈的进栈序列为 p1,p2,p3,...,pn ,其输出序列是 1,2,3,...,n 。若 p3=1 ,则 p1 的值( )。 A .一定是 2 B .可能是 2 C .不可能是 2 D .一定是 3
C.
选 C 。当 p3=1 时,输入序列为 p1,p2,1,p4,… ,因为输出的第一个元素是 1 ,则 p1,p2 一定在栈内。如果下一个出栈的是 p2 ,可以断定 p2=2 ,则 p1 不可能是 2 。当然可能是 3 ,但不一定是 3 :也许 p1 暂不出栈, p4,p5,…,pi=3 进栈, pi 再出栈。