2.
#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]都为同一个数，此程序平均的时间复杂度是()。
3.
#include <iostream>
#include <queue>
using namespace std;
const int maxl = 2000000000;
class Map {
struct item {
string key; int value;
} d[maxl];
int cnt;
public:
int find(string x) {
for(int i=0; i<cnt; ++i)
if (d[i].key == x)
return d[i].value;
return -1;
}
static int end() {return -1;}
void insert(string k, int v) {
d[cnt].key = k; d[cnt++].value = v;
}
} s[2];
class Queue {
string q[maxl];
int head, tail;
public:
void pop() {++head;}
string front() {return q[head + 1];}
bool empty() {return head == tail;}
void push(string x) {q[++tail] = x;}
} q[2];
string st0, st1;
int m;
string LtoR(string s, int L, int R) {
string t = s;
char tmp = t[L];
for(int i=L; i<R; ++i)
t[i] = t[i + 1];
t[R] = tmp;
return t;
}
string RtoL(string s, int L, int R) {
string t = s;
char tmp = t[R];
for(int i=R; i>L; --i)
t[i] = t[i - 1];
t[L] = tmp;
return t;
}
bool check(string st, int p, int step) {
if (s[p].find(st) != s[p].end())
return false;
++step;
if (s[p ^ 1].find(st) == s[p].end()) {
s[p].insert(st, step);
q[p].push(st);
return false;
}
cout << s[p ^ 1].find(st) + step << endl;
return true ;
}
int main() {
cin>> st0>> st1;
int len = st0.length();
if (len != st1.length()) {
cout << -1 << endl;
return 0;
}
if (st0 == st1) {
cout << 0 << endl;
return 0;
}
cin>> m;
s[0].insert(st0, 0);s[1].insert(st1, 0);
q[0].push(st0); q[1].push(st1);
for(int p=0;
!(q[0]. empty() && q[1]. empty());
p^=1) {
string st = q[p]. front();q[p].pop();
int step = s[p].find(st);
if((p==0&&
(check(LtoR(st, m, len - 1), p, step) ||
check(RtoL(st, 0, m), p, step)))
||
(p==1&&
(check(LtoR(st, 0, m), p, step)||
check(RtoL(st, m, len - 1), p, step))))
return 0;
}
cout << -1 << endl;
return 0;
}
判断题
1) 输出可能为0。( )
2) 若输入的两个字符串长度均为101时，则m=0时的输出与m=100时的输出是一样的。( )
3) 若两个字符串的长度均为n，则最坏情况下，此程序的时间复杂度为θ(n!)。( )
选择题
4) (2.5 分)若输入的第一个字符串长度由100个不同的字符构成，第二个字符串是第一个字符串的倒序，输入的m为0，则输出为( ) 。
5) (4 分)已知当输入为“0123)n3210\n1”时输出为4，当输入为“0123451543210\n1”时输出为14，当输入为“012345671n76543210\n1”时输出为28，则当输入为“0123456789ab\nba9876543210\n1"输出为( ) 。其中“\n”为换行符。
6) (4分) 若两个字符串的长度均为n,且0<m<n-1，且两个字符串的构成相同(即任何一个字符在两个字符串中出现的次数均相同)，则下列说法正确的是( ) 。提示:考虑输入与输出有多少对字符前后顺序不一样。