![](https://static.youtibao.com/asksite/comm/h5/images/m_q_title.png)
[主观题]
考查教材37页代码2.7中的permute()算法,假设rand()为理想的随机数发生器,试证明:a)通过反复调用permute()算法,可以生成向量V[0,n)的所有n!种排列:b)由该算法生成的排列中,各元素处于任一位置的概率均为1/n;c)该算法生成各排列的概率均为1/n!。
查看答案
![](https://static.youtibao.com/asksite/comm/h5/images/solist_ts.png)
序列中元素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)。
A.班级授课制
B.道尔顿制
C.文纳特卡制
D.分组教学制