设a是群＜ G,*＞的一个元素，试用归纳法证明，对于i,j∈I有

序列中元素A[i]和A[j]若满足i<j且A[i]>A[j]，则称之为一个逆序对(inversion)。考查如教材80页代码3.19所示的插入排序算法List::insertionSort()，试证明：

a)若所有逆序对的间距均不超过k，则运行时间为o(kn);

b)特别地，当k为常数时，插入排序可在线性时间内完成;

c)若共有I个逆序对，则关键码比较的次数不超过o(I);

d)若共有I个逆序对，则运行时间为o(n+I)。

设是一个实矩阵且ad-bc=1。证明：

(i)如果|trA|>2，那么存在可逆实矩阵T，使得这里λ∈R且λ≠0，1，-1;

(ii)如果|trA|=2且A≠±1，那么存在可逆实矩阵T，使得

(iii)如果|trA|<2，则存在可逆实矩阵T及θ∈R，使得

设代数A=< I,+,X>,I是整数集合。+,×是一般加法和乘法，定义J上的关系为运算+,~是同余关系吗?对运算×,~是同余关系吗?

设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的一个栈混洗?若是，试给出证明;否则，试举一反例。

设文法G(<表达式>)为 <表达式>→i｜(<表达式>)｜<表达式><运算符><表达式> <运算符>→＋｜—｜*｜／｜↑ 试证明该文法具有二义性。

一个栈的输入序列为123…n，若输出的序列的第一个元素是n，输出的第i（1<=i<=n）个元素是【】

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