1716: CSP-S19阅读程序
Description
第一题
#include <cstdio>
using namespace std;
int n;
int a[100];
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i)
scanf("%d", &a[i]);
int ans = 1;
for (int i = 1; i <= n; ++i) {
if (i > 1 && a[i] < a[i - 1])
ans = i;
while (ans < n && a[i] >= a[ans + 1])
++ans;
printf("%d\n", ans);
}
return 0;
}
判断题
1.（1 分）第 16 行输出 ans 时，ans 的值一定大于 i。（）
A. 正确
B. 错误
2.（1 分）程序输出的 ans 小于等于 n。（）
A. 正确
B. 错误
3.若将第 12 行的 < 改为 !=，程序输出的结果不会改变。（）
A. 正确
B. 错误
4.当程序执行到第 16 行时，若 ans−i>2，则a[i+1]≤a[i]。 （）
A. 正确
B. 错误
选择题
5.（3 分）若输入的 a 数组是一个严格单调递增的数列, 此程序的时间复杂度（）
A. O(logn)
B. O(n^2)
C. O(nlogn)
D. O(n)
6.最坏情况下，此程序的时间复杂度是（）。
A. O(n^2)
B. O(logn)
C. O(n)
D. O(nlogn)
第二题
#include <iostream>
using namespace std;
const int maxn = 1000;
int n;
int fa[maxn], cnt[maxn];
int getRoot(int v) {
if (fa[v] == v) return v;
return getRoot(fa[v]);
}
int main() {
cin >> n;
for (int i = 0; i < n; ++i) {
fa[i] = i;
cnt[i] = 1;
}
int ans = 0;
for (int i = 0; i < n - 1; ++i) {
int a, b, x, y;
cin >> a >> b;
x = getRoot(a);
y = getRoot(b);
ans += cnt[x] * cnt[y];
fa[x] = y;
cnt[y] += cnt[x];
}
cout << ans << endl;
return 0;
}
判断题
7.（1 分）输入的 a 和 b 值应在 [0,n−1]的范围内。（）
A. 正确
B. 错误
8.（1 分）第 16 行改成 fa[i] = 0;，不影响程序运行结果。（）
A. 正确
B. 错误
9.若输入的 a 和 b 值均在 [0,n−1] 的范围内，则对于任意 0≤i<n 都有 0≤fa[i]<n （）
A. 正确
B. 错误
10.若输入的 a 和 b 值均在 [0,n−1] 的范围内，则对于任意 0≤i<n 都有 1≤cnt[i]≤n （）
A. 正确
B. 错误
选择题
11.当 n 等于50时，若 a,b 的值都在 [0,49] 的范围内，且在第 25 行时 x 总是不等于 y，那么输出为（）。
A. 1276
B. 1176
C. 1225
D. 1250
12.此程序的时间复杂度是（）。
A. O(n)
B. O(logn)
C. O(n^2)
D. O(nlogn)
第三题
t 是 s 的子序列的意思是：从 s 中删去若干个字符，可以得到 t；特别的，如果 s=t，那么 t 也是 s 的子序列；空串是任何串的子序列。例如：acd 是 abcde 的子序列，acd 是 acd 的子序列，但 adc 不是 abcde 的子序列。
s[x..y] 表示 s[x]⋯s[y] 共 y−x+l 个字符构成的字符串，若 x>y 则 s[x..y] 是空串。t[x..y] 同理。
#include <iostream>
#include <string>
using namespace std;
const int max1 = 202;
string s, t;
int pre[max1], suf[max1];
int main() {
cin >> s >> t;
int slen = s.length(), tlen = t.length();
for (int i = 0, j = 0; i < slen; ++i) {
if (j < tlen && s[i] == t[j]) ++j;
pre[i] = j; // t[0..j-1] 是 s[0..i] 的子序列
}
for (int i = slen - 1 , j = tlen - 1; i >= 0; --i) {
if(j >= 0 && s[i] == t [j]) --j;
suf[i]= j; // t[j+1..tlen-1] 是 s[i..slen-1] 的子序列
}
suf[slen] = tlen -1;
int ans = 0;
for (int i = 0, j = 0, tmp = 0; i <= slen; ++i){
while(j <= slen && tmp >= suf[j] + 1) ++j;
ans = max(ans, j - i - 1);
tmp = pre[i];
}
cout << ans << endl;
return 0;
}
提示：
t[0…pre[i]−1] 是 s[0…i] 的子序列；
t[suf[i]+1…tlen−1] 是 s[i…slen−1] 的子序列。
判断题
13.（1分）程序输出时，suf 数组满足：对任意 0≤i<slen,suf[i]≤suf[i+1]。 （）
A. 正确
B. 错误
14.（2分）当 t 是 s 的子序列时，输出一定不为 0。（）
A. 正确
B. 错误
15.（2分）程序运行到第 23 行时，j−i−1 一定不小于 0。（）
A. 正确
B. 错误
16.（2分）当 t 是 s 的子序列时，pre 数组和 suf 数组满足：对任意 0≤i<slen,pre[i]>suf[i+1]+1。 （）
A. 正确
B. 错误
选择题
17.若 tlen=10，输出为 0，则 slen 最小为（）。
A. 10
B. 12
C. 0
D. 1
18.若 tlen=10，输出为 2，则 slen 最小为（）。
A. 0
B. 10
C. 12
D. 1