2020年CSP-S提高组初赛阅读程序：
#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;
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() 函数产生的是均匀的随机数，完成下面的判断题和单选题：
第 9 行的“x”的数值范围是 L+1 到 R，即 [L+l,R]。（ ）
将第 19 行的“d[a]”改为“d[b]”，程序不会发生运行错误。（ ）
当输入的 d[i] 是严格单调递增序列时，第 17 行的“swap”平均执行次数是( )。
O（n log n）
O（n）
O（log n）
O（n^2）
当输入的 d[i] 是严格单调递减序列时，第 17 行的“swap”平均执行次数是( )。
O（n^2）
O（n）
O（n log n）
O（log n）
若输入的 d[i] 为 i，此程序①平均的时间复杂度和②最坏情况下的时间复杂度分别是( )。
O（n）,O（n2）
O（n）,O（n log n）
O（n log n）,O（n2）
O（n log n）,O（n log n）
若输入的 d[i] 都为同一个数，此程序平均的时间复杂度是( )。
O（n ）
O（ log n）
O（n log n）
O（n2）