#A. csp_test
csp_test
You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.
2021 CCF 非专业级别软件能力认证第一轮模拟
C++语言试题
模拟时间:2023 年 9 月 10 日
考生注意事项:
- 试题纸共有 16 页,答题纸共有 1 页,满分 100 分。请在答题纸上作答,写在试题纸上的 一律无效。
- 不得使用任何电子设备(如计算器、手机、电子词典等)或查阅任何书籍资料。#### 一、单项选择题(共 15 题,每题 2 分,共计 30 分;每题有且仅有一个正确选项选择题
- 在 Linux 系统终端中,用于列出当前目录下所含的文件和子目录的命令为( )。
{{ select(1) }}
- ls
- cd
- cp
- all
- 有6个元素,按照 6,5,4,3,2,1的顺序进入栈 S,请问下列哪个出栈序列是非法的 ()。
{{ select(2) }}
- 5,4,3,6,1,2
- 4,5,3,1,2,6
- 3,4,6,5,2,1
- 2,3,4,1,5,6
-
设
x=true,y=true,z=false
,以下逻辑运算表达式值为真的是 ()。{{ select(3) }}
- (y∨z)∧x∧z
- x^(z∨y) ∧Z
- (x∧y) ∧z
- (x∧y)∨(z∨x)
- 以比较作为基本运算,在 N个数中找出最大数,最坏情况下所需要的最少的比较次数为 ()。 {{ select(4) }}
- N2
- N
- N -1
- N +1
- 对于有n个顶点、m 条边的无向连通图(m>n),需要删掉 ()条边才能使其成为一棵树。 {{ select(5) }}
- n-1
- m -n
- m-n-1
- m-n+1
6.对表达式 a+(b-c)*d
的前缀表达式为 ( ) ,其中 +、-、*
是运算符
{{ select(6) }}
*+a-bcd
+a*-bcd
abc-d*+
abc-+d
- 排序的算法很多,若按排序的稳定性和不稳定性分类,则()是不稳定排序 {{ select(7) }}
- 冒泡排序
- 直接插入排序
- 快速排序
- .归并排序
- 二进制数 101.01 对应的十进制数是 () {{ select(8) }}
- 5.25
- 5.75
- 5.625
- 6.5
- 令根结点的高度为 1,则一棵含有 2021 个结点的二又树的高度至少为 () {{ select(9) }}
- 2021
- 10
- 11
- 12
- 一些数字可以颠倒过来看,例如 0,1,8 颠倒过来还是本身,6 颠倒过来是 99 倒过来看还是 6其他数字颠倒过来都不构成数字。类似的,,一些多位数也可以颠倒过来看,比如 106 颠倒过来是901。假设某个城市的车牌只有 5 位数字,每一位都可以取 0到9。请问这个城市有多少个车牌倒过来恰好还是原来的车牌,并且车牌上的 5位数能被 3整除? () {{ select(10) }}
- 40
- 25
- 30
- 20
- 由 1,1,2,2,3 这五个数字组成不同的三位数有 ()种
{{ select(11) }}
- 18
- 15
- 12
- 24
- 考虑如下递归算法
solve(n) if n<=1 return 1 else if n>=5 return n*solve(n-2) else return n*solve(n-1)
则调用solve(7)得到的返回结果为 ()。 {{ select(12) }}
- 105
- 210
- 420
- 840
- 一个字符串中任意个连续的字符组成的子序列称为该字符串的子串,则字符串 abcab 有 () 个内容互不相同的子串。 {{ select(13) }}
- 12
- 13
- 14
- 15
- 有四个人要从 A 点坐一条船过河到 B 点,船一开始在 A 点。该船次最多可坐两个人。已知这四个人中每个人独自坐船的过河时间分别为 1,2,4,8,且两个人坐船的过河时间为两人独自过河时间的较大者。则最短 ()时间可以让四个人都过河到 B 点 (包括从 B 点把船开回 A 点的时间) {{ select(14) }}
- 14
- 15
- 16
- 17
- 有如下的有向图,节点为 A,B,··,J,其中每条边的长度都标在图中。则节点 A 到 J 节点了的最短路径长度为 ( )。
{{ select(15) }}
- 20
- 22
- 16
- 19
二、阅读程序(程序输入不超过数组或字符串定义的范围;判断题正确填√,错误填×;除特 殊说明外,判断题 1.5 分,选择题 3 分,共计 40 分)
(1)
判断题
16.输入的 n 等于 1001 时,程序不会发生下标越界。 {{ select(16) }}
- 正确
- 错误
17.输入的 a[i]
必须全为正整数,否则程序将陷入死循环。
{{ select(17) }}
- 正确
- 错误
18.当输入为 5 2 11 9 16 10
时,输出为 3 4 3 17 5
。
{{ select(18) }}
- 正确
- 错误
19.当输入为 1 511998
时,输出为 18
。
{{ select(19) }}
- 正确
- 错误
20.将源代码中 g
函数的定义 (14~17行)移到 main 函数的后面,程序可以正常编译运行。
{{ select(20) }}
- 正确
- 错误
单选题
- 当输入为
2 -65536 2147483647
时,输出为()。
{{ select(21) }}
65532 33
65552 32
65535 34
65554 33
(2)
#include <iostream>
using namespace std;
long long n, ans;
int k, len;
long long d[1000000];
int main() {
cin >> n >> k;
d[0] = 0;
len= 1;
ans = 0;
for (long long i = 0; i <n; ++i) {
++d[0];
for (int j = 0; j + 1<len; ++j) {
if (d[j] == k) {
d[j] = 0;
d[j + 1] += 1;
++ans;
}
}
if (d[len- 1] == k) {
d[len - 1] = 0;
d[len] =1;
++len;
++ans;
}
}
cout << ans << endl;
return 0;
}
假设输入的 n 是不超过 的正整数, 都是不超过 10000 的正整数,完成下面的判断题和单选题:
判断题.
22.若k =1,则输出 ans 时,len = n。 ( ) {{ select(22) }}
- 正确
- 错误
23.若k>1,则输出 ans 时,len 一定小于n。 ( ) {{ select(23) }}
- 正确
- 错误
24.若k > 1,则输出 ans 时, 一定大于n。 () {{ select(24) }}
- 正确
- 错误
单选题
25.若输入的 n 等于: ,输入的 k 为 1,则输出等于 () {{ select(25) }}
- 1
26.若输入的n等于 205,891,132,094,649
(即 ),输入的 k 为 3,则输出等于()
{{ select(26) }}
27.若输入的n等于 100,010,002,000,090
,输入的 k 为 10,则输出等于 ()。
{{ select(27) }}
11,112,222,444,543
11,122,222,444,453
11,122,222,444,543
11,112,222,444,453
(3)
#include <iostream>
using namespace std;
const int maxn = 10000;
int n;
int a[maxn];
int b[maxn];
int f(int l, int r, int depth) {
if (l > r)
return 0;
int min = maxn, mink;
for (int i = l; i <= r; ++i) {
if (min > a[i]) {
min = a[i];
mink = i;
}
}
int lres = f(l, mink - 1, depth + 1);
int rres = f(mink + 1, r, depth + 1);
return lres + rres + depth * b[mink];
}
int main() {
cin >> n;
for (int i = 0; i < n; ++i)
cin >> a[i];
for (int i = 0; i < n; ++i)
cin >> b[i];
cout << f(0, n - 1, 1) << endl;
return 0;
}
判断题
28.如果 a 数组有重复的数字,则程序运行时会发生错误。 {{ select(28) }}
- 正确
- 错误
29.如果b数组全为 0,则输出为 0。 {{ select(29) }}
- 正确
- 错误
选择题
30.当n =100 时,最坏情况下,与第 12 行的比较运算执行的次数最接近的是:
{{ select(30) }}
- 5000
- 600
- 6
- 100
31.当n =100 时,最好情况下,与第 12 行的比较运算执行的次数最接近的是:
{{ select(31) }}
- 100
- 6
- 5000
- 600
32.当n=10时,若b数组满足,对任意0<i<n,都有 b[i] = i + 1
,那么输
出最大为 ()。
{{ select(32) }}
- 386
- 383
- 384
- 385
33.(4分)当n =100 时,若b数组满足,对任意,都有 b[i]=1
,那么输出最小为 () 。
{{ select(33) }}
- 582
- 580
- 579
- 581
三、完善程序(单选题,每小题 3分,共计 30 分)
1.(质因数分解)给出正整数 n,请输出将 n 质因数分解的结果,结果从小到大输出。
例如:输入 n=120,程序应该输出 2 2 2 3 5
,表示:120=2×2×2×3×5。输入保证 2≤n≤109。
提示:先从小到大枚举变量 i,然后用 i 不停试除 n 来寻找所有的质因子。
试补全程序。
#include <cstdio>
using namespace std;
int n, i;
int main() {
scanf("%d", &n);
for(i = ①; ② <=n; i ++) {
③ {
printf("%d ", i);
n = n / i;
}
}
if(④)
printf("%d ", ⑤);
return 0;
}
34.①处应填
{{ select(34) }}
1
n-1
2
0
35.②处应填 {{ select(35) }}
n/i
n/(i*i)
i*i
i*i*i
36.③处应填 {{ select(36) }}
if(n%i==0)
if(i*i<=n)
while(n%i==0)
while(i*i<=n)
37.④处应填 {{ select(37) }}
n>1
n<=1
i<n/i
i+i<=n
38.⑤处应填 {{ select(38) }}
2
n/i
n
i
2.(最小区间覆盖)给出n个区间,第i个区间的左右端点是。现在要在这些区间中选出若干个,使得区间 [0,m] 被所选区间的并覆盖(即每一个 0≤i≤m 都在某个所选的区间中)。保证答案存在,求所选区间个数的最小值。
输入第一行包含两个整数n和 m
接下来 n 行,每行两个整数 。
提示:使用贪心法解决这个问题。先用 的时间复杂度排序,然后贪心选择这些区间。
试补全程序。
#include <iostream>
using namespace std;
const int MAXN = 5000;
int n, m;
struct segment { int a, b; } A[MAXN];
void sort() // 排序
{
for (int i = 0; i < n; i++)
for (int j = 1; j < n; j++)
if (①)
{
segment t = A[j];
②
}
}
int main()
{
cin >> n >> m;
for (int i = 0; i < n; i++)
cin >> A[i].a >> A[i]?b;
sort();
int p = 1;
for (int i = 1; i < n; i++)
if (③)
A[p++] = A[i];
n = p;
int ans =0, r = 0;
int q = 0;
while (r < m)
{
while (④)
q++;
⑤;
ans++;
}
cout << ans << endl;
return 0;
}
39①处应填 {{ select(39) }}
A[j].b>A[j-1].b
A[j].a<A[j-1].a
A[j].a>A[j-1].a
A[j].b<A[j-1].b
40②处应填 {{ select(40) }}
A[j+1]=A[j];A[j]=t;
A[j-1]=A[j];A[j]=t;
A[j]=A[j+1];A[j+1]=t;
A[j]=A[j-1];A[j-1]=t;
41③处应填 {{ select(41) }}
A[i].b>A[p-1].b
A[i].b<A[i-1].b
A[i].b>A[i-1].b
A[i].b<A[p-1].b
42④处应填 {{ select(42) }}
q+1<n&&A[q+1].a<=r
q+1<n&&A[q+1].b<=r
q<n&&A[q].a<=r
q<n&&A[q].b<=r
43⑤处应填 {{ select(43) }}
r=max(r,A[q+1].b)
r=max(r,A[q].b)
r=max(r,A[q+1].a)
q++
CSP 第一轮模拟测试
- Status
- Done
- Rule
- ACM/ICPC
- Problem
- 1
- Start at
- 2023-9-15 19:00
- End at
- 2023-9-15 20:00
- Duration
- 1 hour(s)
- Host
- Partic.
- 14