题目内容
（请给出正确答案）
[主观题]
试证明：若借助栈可输入序列1，2，3，…，n得到一个输出序列p1,p2,p3,…，pn，(它是输
试证明：若借助栈可输入序列1，2，3，…，n得到一个输出序列p1,p2,p3,…，pn，（它是输
人序列的某一种排列)，则在输出序列中不可能出现以下情况，即存在i<j<K,使得Pj<Pk<Pi。
查看答案
如果结果不匹配，请 联系老师 获取答案
题目内容
（请给出正确答案）
如果结果不匹配，请 联系老师 获取答案
题目内容
（请给出正确答案）
人序列的某一种排列)，则在输出序列中不可能出现以下情况，即存在i<j<K,使得Pj<Pk<Pi。
如果结果不匹配，请 联系老师 获取答案
更多“试证明：若借助栈可输入序列1，2，3，…，n得到一个输出序列…”相关的问题
设B为A=(1，2，3，...，n)的任一排列。
a)试证明，B是A的一个栈混洗，当且仅当对于任意1≤i＜j＜k≤n，P中都不含如下模式：{...，k，...，i，...，j，...}
b)若对任意1≤i＜j＜k＜n，B中都不含模式{...，j+1，...，i，...，j，...}，则B是否必为A的一个栈混洗？若是，试给出证明;否则，试举一反例。
c)若对任意1＜i＜j＜k≤n，B中都不含模式{...，k，...，j-1，...，j，...}，则B是否必为A的一个栈混洗？若是，试给出证明;否则，试举一反例。
A、j-i
B、n-I
C、j-i+1
D、不确定
a)试给出在算法退出之前，操作数栈和操作符栈的演化过程：
b)该算法是否能够正常终止？若异常退出，试解释原因;否则，试给出算法的输出;
c)试改进该evaluate()算法，使之能够判别表达式的语法是否正确。
若x(n)为纯虚序列,DFT[x(n)]=X[k),分解为实部与虚部写作X(k)=
试证明
是k的奇函数,X1(k)是k的偶函数.
设使用Pratt序列：
对长度为n的任一向量S做希尔排序。
试证明：
a)若S已是(2，3)-有序，则只需o(n)时间即可使之完全有序;
b)对任何
，若S已是(2hk，3hk)-有序，则只需o(n)时间即可使之hk-有序;
c)针对
序列中的前o(logtn)项，希尔排序算法需要分别迭代一轮;
d)总体的时间复杂度为o(log2n)。
