试证明：若借助栈由输入序列12...n得到的输出序列为（它是输入序列的一个排列)，则在输出序列中不

仅由S和X组成的序列。称可以操作的序列为合法序列(例如， SXS X为合法序列， S XXS为非法序列)。试给出区分给定序列为合法序列或非法序列的一般准则，并证明：两个不同的合法(栈操作)序列(对同一输入序列)不可能得到相同的输出元素(注意：在此指的是元素实体，而不是值)序列。

A.5 4 1 3 2

B.2 3 4 1 5

C.1 5 4 3 2

D.2 3 1 4 5

一个栈的输入序列为1，2，3，…，r1，若输出序列的第一个元素是n，则输出的第i(1≤i≤n)个元素是()。

A.不确定

B.n—i+1

C.i

D.n—i

A.不确定

B.n-i+l

C.i

D.n-i

一个栈的输入序列为1，2，3，…，n，若输出序列的第一个元素是n，输出第i(1≤i≤n)个元素是()。

A.不确定

B.n—i+1

C.i

D.n—i

首先对较短的子序列进行排序，试编写相应的算法，并说明在此做法下，快速排序所需要的栈的深度为O(log₂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的一个栈混洗？若是，试给出证明;否则，试举一反例。

若已知实数有限长序列x₁（n)、x₂（n),其长度都为N:试证明下列关系式成立:

若已知实数有限长序列x₁(n)、x₂(n),其长度都为N:

试证明下列关系式成立: