![](https://static.youtibao.com/asksite/comm/h5/images/m_q_title.png)
[主观题]
试证明:若借助栈可输入序列1,2,3,…,n得到一个输出序列p1,p2,p3,…,pn,(它是输
试证明:若借助栈可输入序列1,2,3,…,n得到一个输出序列p1,p2,p3,…,pn,(它是输
人序列的某一种排列),则在输出序列中不可能出现以下情况,即存在i<j<K,使得Pj<Pk<Pi。
查看答案
![](https://static.youtibao.com/asksite/comm/h5/images/solist_ts.png)
人序列的某一种排列),则在输出序列中不可能出现以下情况,即存在i<j<K,使得Pj<Pk<Pi。
设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)。