#A. csp_test

    Type: Objective

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 分;每题有且仅有一个正确选项选择题
  1. 在 Linux 系统终端中,用于列出当前目录下所含的文件和子目录的命令为( )。

{{ select(1) }}

  • ls
  • cd
  • cp
  • all
  1. 有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
  1. x=true,y=true,z=false,以下逻辑运算表达式值为真的是 ()。

    {{ select(3) }}

  • (y∨z)∧x∧z
  • x^(z∨y) ∧Z
  • (x∧y) ∧z
  • (x∧y)∨(z∨x)
  1. 以比较作为基本运算,在 N个数中找出最大数,最坏情况下所需要的最少的比较次数为 ()。 {{ select(4) }}
  • N2
  • N
  • N -1
  • N +1
  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
  1. 排序的算法很多,若按排序的稳定性和不稳定性分类,则()是不稳定排序 {{ select(7) }}
  • 冒泡排序
  • 直接插入排序
  • 快速排序
  • .归并排序
  1. 二进制数 101.01 对应的十进制数是 () {{ select(8) }}
  • 5.25
  • 5.75
  • 5.625
  • 6.5
  1. 令根结点的高度为 1,则一棵含有 2021 个结点的二又树的高度至少为 () {{ select(9) }}
  • 2021
  • 10
  • 11
  • 12
  1. 一些数字可以颠倒过来看,例如 0,1,8 颠倒过来还是本身,6 颠倒过来是 99 倒过来看还是 6其他数字颠倒过来都不构成数字。类似的,,一些多位数也可以颠倒过来看,比如 106 颠倒过来是901。假设某个城市的车牌只有 5 位数字,每一位都可以取 0到9。请问这个城市有多少个车牌倒过来恰好还是原来的车牌,并且车牌上的 5位数能被 3整除? () {{ select(10) }}
  • 40
  • 25
  • 30
  • 20
  1. 由 1,1,2,2,3 这五个数字组成不同的三位数有 ()种

{{ select(11) }}

  • 18
  • 15
  • 12
  • 24
  1. 考虑如下递归算法
    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
  1. 一个字符串中任意个连续的字符组成的子序列称为该字符串的子串,则字符串 abcab 有 () 个内容互不相同的子串。 {{ select(13) }}
  • 12
  • 13
  • 14
  • 15
  1. 有四个人要从 A 点坐一条船过河到 B 点,船一开始在 A 点。该船次最多可坐两个人。已知这四个人中每个人独自坐船的过河时间分别为 1,2,4,8,且两个人坐船的过河时间为两人独自过河时间的较大者。则最短 ()时间可以让四个人都过河到 B 点 (包括从 B 点把船开回 A 点的时间) {{ select(14) }}
  • 14
  • 15
  • 16
  • 17
  1. 有如下的有向图,节点为 A,B,··,J,其中每条边的长度都标在图中。则节点 A 到 J 节点了的最短路径长度为 ( )。 image

{{ select(15) }}

  • 20
  • 22
  • 16
  • 19

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

(1)

image

判断题

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

  • 正确
  • 错误
单选题
  1. 当输入为 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 是不超过 2622^{62}的正整数, kk都是不超过 10000 的正整数,完成下面的判断题和单选题:

判断题.

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

  • 正确
  • 错误

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

  • 正确
  • 错误

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

  • 正确
  • 错误
单选题

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

  • 1
  • (10301015)/2(10^{30}−10^{15})/2
  • (1030+1015)/2(10^{30}+10^{15})/2
  • 101510^{15}

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

  • 3303^{30}
  • (3301)/2(3^{30}−1)/2
  • 33013^{30}−1
  • (330+1)/2(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 行的比较运算执行的次数最接近的是:

{{ 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数组满足,对任意0i<n0 \le i <n,都有 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个区间的左右端点是[ai,bi][a_i,b_i]。现在要在这些区间中选出若干个,使得区间 [0,m] 被所选区间的并覆盖(即每一个 0≤i≤m 都在某个所选的区间中)。保证答案存在,求所选区间个数的最小值。

输入第一行包含两个整数n和 m1n5000,1m109(1≤n≤5000,1≤m≤10^9)

接下来 n 行,每行两个整数 ai,bi0ai,bima_i,b_i(0≤a_i​,b_i​≤m)

提示:使用贪心法解决这个问题。先用 O(n2)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 第一轮模拟测试

Not Attended
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