（简答题）
试证明：若借助栈由输入序列12…n得到的输出序列为p1p2…pn（它是输入序列的一个排列），则在输出序列中不可能出现这样的情形：存在着i＜j＜k使pj＜pk＜pi。
正确答案
因为输入序列是从小到大排列的，所以若pj＜pk＜pi，则可以理解为通过输入序列pjpkpi可以得到输出序列pipjpk，显然通过序列123是无法得到312的，所以不可能存在着i＜j＜k使pj＜pk＜pi。
答案解析
略
相似试题
（单选题）
若一个栈的输入序列是1，2，3，…，n，输出序列的第一个元素是n，则第i个输出元素是（）。
（单选题）
若一个栈的输入序列是1，2，3……n，则输出序列的第一个元素是n，则第i个输出元素是（）
（简答题）
假设以S和X分别表示入栈和出栈的操作，则初态和终态均为空栈的入栈和出栈的操作序列可以表示为仅由S和X组成的序列。称可以操作的序列为合法序列（例如，SXSX为合法序列，SXXS为非法序列）。试给出区分给定序列为合法序列或非法序列的一般准则，并证明：两个不同的合法（栈操作）序列（对同一输入序列）不可能得到相同的输出元素（注意：在此指的是元素实体，而不是值）序列。
（单选题）
有数据{53，30，37，12，45，24，96}，从空二叉树开始逐个插入数据来开成二叉排序树，若希望高度最小，则应选择下面哪个序列输入（）。
（简答题）
设信道输入是连续型随机序列X1X2...XN，输出也是连续型随机序列Y1Y2...YN，信道传递概率密度为p（y|x）。试证明： （1）当信源是无记忆时，有 （1）当信源是无记忆时，有
（填空题）
已知一个栈的输入序列为1，2，3，...，n，则其输出序列的第2个元素为n的输出序列的种数是（）。
（单选题）
设输入序列是1、2、3、……、n，经过栈的作用后输出序列的第一个元素是n，则输出序列中第i个输出元素是（）。
（简答题）
给定n个记录的有序序列A[n]和m个记录的有序序列B[m]，将它们归并为一个有序序列，存放在C[m+n]中，试写出这一算法。
（简答题）
一个栈的输入序列为1、2、3，试给出全部可能的出栈序列。
