#include <iostream>
#include <cstdlib>
using namespace std;
int n;
int d[10000];
int find(int L, int R, int k) {
int x = rand() % (R-L+1) + L;
swap(d[L], d[x]);
int a=L+1,b=R;
while(a<b) {
while (a < b && d[a] < d[L])
++a ;
while (a < b && d[b] >= d[L])
--b;
cout<<"*"<<endl;
swap(d[a], d[b]);
}
if (d[a] < d[L])
++a;
if(a-L==k)
return d[L];
if (a-L <k)
return find(a, R, k - (a - L));
return find(L + 1, a - 1, k);
}
int main() {
int k;
cin >> n;
cin >> k;
for(int i=0; i<n; ++i)
cin >> d[i];
cout << find(0, n - 1, k);
return 0;
}
假设输入的n, k和d[i]都是不超过10000的正整数，且k不超过n,并
假设rand( )函数产生的是均匀的随机数，完成下面的判断题和单选题:
判断题
1) 第9行的“x" 的数值范围是L+1到R，即[L+1, R]。( )
2) 将第19行的“d[a]"改为“d[b]”， 程序不会发生运行错误。 ( )
选择题
3) (2.5 分)当输入的d[i]是严格单调递增序列时，第17行的“swap"平均执行次数是( ) 。
4) (2.5 分)当输入的d[i]是严格单调递减序列时，第17行的“swap”平均执行次数是( ) 。
5) (2.5分) 若输入的d[i]为i,此程序①平均的时间复杂度和②最坏情况下的时间复杂度分别是( ) 。
6) (2.5分)若输入的d[i]都为同一个数，此程序平均的时间复杂度是()。