#A. csp_test

Type: Objective

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 系统终端中，用于列出当前目录下所含的文件和子目录的命令为（）。

有6个元素，按照 6,5,4,3,2,1的顺序进入栈 S，请问下列哪个出栈序列是非法的 ()。

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) }}

由 1,1,2,2,3 这五个数字组成不同的三位数有 ()种

考虑如下递归算法

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) }}

一个字符串中任意个连续的字符组成的子序列称为该字符串的子串，则字符串 abcab 有 () 个内容互不相同的子串。 {{ select(13) }}

有四个人要从 A 点坐一条船过河到 B 点，船一开始在 A 点。该船次最多可坐两个人。已知这四个人中每个人独自坐船的过河时间分别为 1,2,4,8，且两个人坐船的过河时间为两人独自过河时间的较大者。则最短 ()时间可以让四个人都过河到 B 点 (包括从 B 点把船开回 A 点的时间) {{ select(14) }}

有如下的有向图，节点为 A,B，··,J,其中每条边的长度都标在图中。则节点 A 到 J 节点了的最短路径长度为 ( )。

二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填√，错误填×；除特殊说明外，判断题 1.5 分，选择题 3 分，共计 40 分）

(1)

判断题

16.输入的 n 等于 1001 时，程序不会发生下标越界。 {{ select(16) }}

正确
错误

17.输入的 a[i] 必须全为正整数，否则程序将陷入死循环。

正确
错误

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 函数的后面，程序可以正常编译运行。

正确
错误

单选题

当输入为 2 -65536 2147483647时，输出为（）。

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 是不超过 $2^{62}$ 的正整数， $k$ 都是不超过 10000 的正整数，完成下面的判断题和单选题:

判断题.

22.若k =1，则输出 ans 时，len = n。 ( ) {{ select(22) }}

正确
错误

23.若k>1，则输出 ans 时，len 一定小于n。 ( ) {{ select(23) }}

正确
错误

24.若k > 1，则输出 ans 时， $k^{len}$ 一定大于n。 () {{ select(24) }}

正确
错误

单选题

25.若输入的 n 等于: $10^{15}$ ，输入的 k 为 1，则输出等于 () {{ select(25) }}

1
$(10^{30}−10^{15})/2$
$(10^{30}+10^{15})/2$
$10^{15}$

26.若输入的n等于 205,891,132,094,649 (即 $3^{30}$ )，输入的 k 为 3，则输出等于() {{ select(26) }}

$3^{30}$
$(3^{30}−1)/2$
$3^{30}−1$
$(3^{30}+1)/2$

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 行的比较运算执行的次数最接近的是:

5000
600
6
100

31.当n =100 时，最好情况下，与第 12 行的比较运算执行的次数最接近的是:

100
6
5000
600

32.当n=10时，若b数组满足，对任意0<i<n，都有 b[i] = i + 1，那么输出最大为 ()。 {{ select(32) }}

33.(4分)当n =100 时，若b数组满足，对任意 $0 \le i <n$ ，都有 b[i]=1，那么输出最小为 () 。 {{ select(33) }}

三、完善程序（单选题，每小题 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.①处应填

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个区间的左右端点是 $[a_i,b_i]$ 。现在要在这些区间中选出若干个，使得区间 [0,m] 被所选区间的并覆盖（即每一个 0≤i≤m 都在某个所选的区间中）。保证答案存在，求所选区间个数的最小值。

输入第一行包含两个整数n和 m $（1≤n≤5000,1≤m≤10^9）$

接下来 n 行，每行两个整数 $a_i,b_i（0≤a_i,b_i≤m）$ 。

提示：使用贪心法解决这个问题。先用 $O(n^2)$ 的时间复杂度排序，然后贪心选择这些区间。

试补全程序。

#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-j1

Not Claimed

Status: Done
Problem: 9
Open Since: 2024-8-20 0:00
Deadline: 2024-9-20 23:59
Extension: 24 hour(s)

#A. csp_test

csp_test

2021 CCF 非专业级别软件能力认证第一轮模拟

C++语言试题

模拟时间：2023 年 9 月 10 日

考生注意事项：

二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填√，错误填×；除特殊说明外，判断题 1.5 分，选择题 3 分，共计 40 分）

(1)

判断题

单选题

(2)

判断题.

单选题

（3）

判断题

选择题

三、完善程序（单选题，每小题 3分，共计 30 分）

csp-j1

Status

Development

Support

#A. csp_test

csp_test

2021 CCF 非专业级别软件能力认证第一轮模拟

C++语言试题

模拟时间：2023 年 9 月 10 日

考生注意事项：

二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填√，错误填×；除特 殊说明外，判断题 1.5 分，选择题 3 分，共计 40 分）

(1)

判断题

单选题

(2)

判断题.

单选题

（3）

判断题

选择题

三、完善程序（单选题，每小题 3分，共计 30 分）

csp-j1

Status

Development

Support

Don't have an account?

SIGN IN

二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填√，错误填×；除特殊说明外，判断题 1.5 分，选择题 3 分，共计 40 分）