数据结构考研分类复习真题 第三章 答案[5]

输入序列为不能得出其理由是输出序列最后两元素是前面个元素（）得到后栈中元素剩且在栈顶不可能栈底元素在栈顶元素之前出栈

得到的过程如下入栈并出栈得到部分输出序列然后和入栈出栈部分输出序列变为接着和入栈和依次出栈部分输出序列变为最后入栈并退栈得最终结果

能得到出栈序列BCAED不能得到出栈序列DBACE其理由为若出栈序列以D开头说明在D之前的入栈元素是AB和C三个元素中C是栈顶元素B和A不可能早于C出栈故不可能得到DBACE出栈序列

借助栈结构n个入栈元素可得到/(n+)((n）！/（n!*n!）)种出栈序列本题个元素可有种出栈序列abcd和dcba就是其中两种但dabc和adbc是不可能得到的两种

不能得到序列栈可以用单链表实现这就是链栈由于栈只在栈顶操作所以链栈通常不设头结点

如果i<j则对于pi<pj情况说明pi在pj入栈前先出栈而对于pi>pj的情况则说明要将pj压到pi之上也就是在pj出栈之后pi才能出栈这就说明对于i<j<k不可能出现pj<pk<pi的输出序列换句话说对于输入序列不可能出现的输出序列

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []