2022年CCF非专业级别软件能力认证第一轮CSP_S/提高级
2022
第一轮
2023-09-02 20:01:50
36次
一、单选题
计算机系统用小端（Little Endian）和大端（Big Endian）来描述多字节数据的存储地址顺序模式，其中小端表示将低位字节数据存储在低地址的模式、大端表示将高位字节数据存储在低地址的模式。在小端模式的系统和大端模式的系统分别编译和运行以下 C++代码段表示的程序，将分别输出什么结果？（ ）
unsigned x = 0xDEADBEEF;
unsigned char *p = (unsigned char *)&x;
printf("%X", *p);
| A． EF、EF |
B． EF、DE |
| C． DE、EF |
D． DE、DE |
【知识点】 CCF非专业级别软件能力认证CSP-S/提高级
二、判断题
三、组合题
（归并第 k 小）已知两个长度均为 n 的有序数组 a1 和 a2（均为递增序，但不保证严格单调递增），并且给定正整数 k（1≤k≤2n），求数组 a1 和 a2 归并排序后的数组里第 k 小的数值。
试补全程序。
#include <bits/stdc++.h>
using namespace std;
int solve(int *a1, int *a2, int n, int k) {
int left1 = 0, right1 = n - 1;
int left2 = 0, right2 = n - 1;
while (left1 <= right1 && left2 <= right2) {
int m1 = (left1 + right1) >> 1;
int m2 = (left2 + right2) >> 1;
int cnt = ① ;
if ( ② ) {
if (cnt < k) left1 = m1 + 1;
else right2 = m2 - 1;
} else {
if (cnt < k) left2 = m2 + 1;
else right1 = m1 - 1;
}
}
if ( ③ ) {
if (left1 == 0) {
return a2[k - 1];
} else {
int x = a1[left1 - 1], ④ ;
return std::max(x, y);
}
} else {
if (left2 == 0) {
return a1[k - 1];
} else {
int x = a2[left2 - 1], ⑤ ;
return std::max(x, y);
}
}
}
(1)．④处应填（ ）
| A． y = a1[k - left2 - 1] |
B． y = a1[k - left2] |
| C． y = a2[k - left1 - 1] |
D． y = a2[k - left1] |
③处应填（ ）
| A． left1 == right1 |
B． left1 < right1 |
| C． left1 > right1 |
D． left1 != right1 |
①处应填（ ）
| A． (m1 + m2) * 2 |
B． (m1 - 1) + (m2 - 1) |
| C． m1 + m2 |
D． (m1 + 1) + (m2 + 1) |
⑤处应填（ ）
| A． y = a1[k - left2 - 1] |
B． y = a1[k - left2] |
| C． y = a2[k - left1 - 1] |
D． y = a2[k - left1] |
②处应填（ ）
| A． a1[m1] == a2[m2] |
B． a1[m1] <= a2[m2] |
| C． a1[m1] >= a2[m2] |
D． a1[m1] != a2[m2] |
【知识点】 CCF非专业级别软件能力认证CSP-S/提高级
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int f(const string &s, const string &t)
{
int n = s.length(), m = t.length();
vector<int> shift(128, m + 1);
int i, j;
for (j = 0; j < m; j++)
shift[t[j]] = m - j;
for (i = 0; i <= n - m; i += shift[s[i + m]]) {
j = 0;
while (j < m && s[i + j] == t[j]) j++;
if (j == m) return i;
}
return -1;
}
int main()
{
string a, b;
cin >> a >> b;
cout << f(a, b) << endl;
return 0;
}假设输入字符串由 ASCII 可见字符组成，完成下面的判断题和单选题：
(1)．该算法最坏情况下的时间复杂度为（ ）。
| A． O(n + m) |
B． O(n log m) |
| C． O(m log n) |
D． O(nm) |
当输入为“GoodLuckCsp2022 22”时，第 20 行的“j++”语句执行次数为 2。（ ）
| A．正确 | B．错误 |
f(a, b)与下列（ ）语句的功能最类似。
| A． a.find(b) |
B． a.rfind(b) |
| C． a.substr(b) |
D． a.compare(b) |
当输入为“abbababbbab abab”时，输出为 4。（ ）
| A．正确 | B．错误 |
当输入为“baaabaaabaaabaaaa aaaa”，第 20 行的“j++”语句执行次数为（ ）。
| A． 9 |
B． 10 |
| C． 11 |
D． 12 |
（1 分）当输入为“abcde fg”时，输出为-1。（ ）
| A．正确 | B．错误 |
【知识点】 CCF非专业级别软件能力认证CSP-S/提高级
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXL = 1000;
int n, k, ans[MAXL];
int main(void)
{
cin >> n >> k;
if (!n) cout << 0 << endl;
else
{
int m = 0;
while (n)
{
ans[m++] = (n % (-k) + k) % k; 20 n = (ans[m - 1] - n) / k;
}
for (int i = m - 1; i >= 0; i--)
cout << char(ans[i] >= 10 ?
ans[i] + 'A' - 10 :
ans[i] + '0');
cout << endl;
}
return 0;
}假设输入的 n 在 int 范围内，k 为不小于 2 且不大于 36 的正整数，完成下面的判断题和单选题：
(1)．当输入为“-255 8”时，输出为“（ ）”。
| A． 1400 |
B． 1401 |
| C． 417 |
D． 400 |
该算法的时间复杂度为 O(logk n)。（ ）
| A．正确 | B．错误 |
当输入为“1000000 19”时，输出为“（ ）”。
| A． BG939 |
B． 87GIB |
| C． 1CD428 |
D． 7CF1B |
当输入为“100 7”时，输出为（ ）。
| A． 202 |
B． 1515 |
| C． 244 |
D． 1754 |
删除第 23 行的强制类型转换，程序的行为不变。（ ）
| A．正确 | B．错误 |
除非输入的 n 为 0，否则程序输出的字符数为
| A．正确 | B．错误 |
【知识点】 CCF非专业级别软件能力认证CSP-S/提高级
#include <iostream>
using namespace std;
const int MAXN = 105;
int n, m, k, val[MAXN];
int temp[MAXN], cnt[MAXN];
void init()
{
cin >> n >> k;
for (int i = 0; i < n; i++) cin >> val[i];
int maximum = val[0];
for (int i = 1; i < n; i++)
if (val[i] > maximum) maximum = val[i];
m = 1;
while (maximum >= k) {
maximum /= k;
m++;
}
}
void solve()
{
int base = 1;
for (int i = 0; i < m; i++) {
for (int j = 0; j < k; j++) cnt[j] = 0;
for (int j = 0; j < n; j++) cnt[val[j] / base % k]++; 30 for (int j = 1; j < k; j++) cnt[j] += cnt[j - 1];
for (int j = n - 1; j >= 0; j--) {
temp[cnt[val[j] / base % k] - 1] = val[j];
cnt[val[j] / base % k]--;
}
for (int j = 0; j < n; j++) val[j] = temp[j];
base *= k;
}
}
int main()
{
init();
solve();
for (int i = 0; i < n; i++) cout << val[i] << ' ';
cout << endl;
return 0;
}假设输入的 n 为不大于 100 的正整数，k 为不小于 2 且不大于 100 的正整数，val[i]在int 表示范围内，完成下面的判断题和单选题：
(1)．当输入为“5 3 98 26 91 37 46”时，程序第一次执行到第 36 行，val[]数组的内容依次为（ ）。
| A． 91 26 46 37 98 |
B． 91 46 37 26 98 |
| C． 98 26 46 91 37 |
D． 91 37 46 98 26 |
这是一个不稳定的排序算法。（ ）
| A．正确 | B．错误 |
该算法的空间复杂度仅与 n 有关。（ ）
| A．正确 | B．错误 |
当输入的 k 比 val[i]的最大值还大时，该算法退化为（ ）算法。
| A． 选择排序 |
B． 冒泡排序 |
| C． 计数排序 |
D． 桶排序 |
若 val[i]的最大值为 100，k 取（ ）时算法运算次数最少。
| A． 2 |
B． 3 |
| C． 10 |
D． 不确定 |
该算法的时间复杂度为 O(m(n + k))。（ ）
| A．正确 | B．错误 |
【知识点】 CCF非专业级别软件能力认证CSP-S/提高级
（容器分水）有两个容器，容器 1 的容量为为 a 升，容器 2 的容量为 b 升；同时允许下列的三种操作，分别为：
1）FILL(i)：用水龙头将容器 i（i∈{1,2}）灌满水；
2）DROP(i)：将容器 i 的水倒进下水道；
3）POUR(i,j)：将容器 i 的水倒进容器 j（完成此操作后，要么容器 j 被灌满，要么容器 i 被清空）。
求只使用上述的两个容器和三种操作，获得恰好 c 升水的最少操作数和操作序列。上述 a、b、c 均为不超过 100 的正整数，且 c≤max{a,b}。
试补全程序。
#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int f[N][N];
int ans;
int a, b, c;
int init;
int dfs(int x, int y) {
if (f[x][y] != init)
return f[x][y];
if (x == c || y == c)
return f[x][y] = 0;
f[x][y] = init - 1;
f[x][y] = min(f[x][y], dfs(a, y) + 1);
f[x][y] = min(f[x][y], dfs(x, b) + 1);
f[x][y] = min(f[x][y], dfs(0, y) + 1);
f[x][y] = min(f[x][y], dfs(x, 0) + 1);
int t = min(a - x, y);
f[x][y] = min(f[x][y], ① );
t = min(x, b - y);
f[x][y] = min(f[x][y], ② );
return f[x][y];
}
void go(int x, int y) {
if ( ③ )
return;
if (f[x][y] == dfs(a, y) + 1) {
cout << "FILL(1)" << endl;
go(a, y);
} else if (f[x][y] == dfs(x, b) + 1) {
cout << "FILL(2)" << endl;
go(x, b);
} else if (f[x][y] == dfs(0, y) + 1) {
cout << "DROP(1)" << endl;
go(0, y);
} else if (f[x][y] == dfs(x, 0) + 1) {
cout << "DROP(2)" << endl;
go(x, 0);
} else {
int t = min(a - x, y);
if (f[x][y] == ④ ) {
cout << "POUR(2,1)" << endl;
go(x + t, y - t);
} else {
t = min(x, b - y);
if (f[x][y] == ⑤ ) {
cout << "POUR(1,2)" << endl;
go(x - t, y + t);
} else
assert(0);
}
}
}
int main() {
cin >> a >> b >> c;
ans = 1 << 30;
memset(f, 127, sizeof f);
init = **f;
if ((ans = dfs(0, 0)) == init - 1)
cout << "impossible";
else {
cout << ans << endl;
go(0, 0);
}
}
(1)．①处应填（ ）
| A． dfs(x + t, y - t) + 1 |
B． dfs(x + t, y - t) - 1 |
| C． dfs(x - t, y + t) + 1 |
D． dfs(x - t, y + t) - 1 |
④处应填（ ）
| A． dfs(x + t, y - t) + 1 |
B． dfs(x + t, y - t) - 1 |
| C． dfs(x - t, y + t) + 1 |
D． dfs(x - t, y + t) - 1 |
②处应填（ ）
| A． dfs(x + t, y - t) + 1 |
B． dfs(x + t, y - t) - 1 |
| C． dfs(x - t, y + t) + 1 |
D． dfs(x - t, y + t) - 1 |
③处应填（ ）
| A． x == c || y == c |
B． x == c && y == c |
| C． x >= c || y >= c |
D． x >= c && y >= c |
⑤处应填（ ）
| A． dfs(x + t, y - t) + 1 |
B． dfs(x + t, y - t) - 1 |
| C． dfs(x - t, y + t) + 1 |
D． dfs(x - t, y + t) - 1 |
【知识点】 CCF非专业级别软件能力认证CSP-S/提高级
