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

C++语言试题

模拟时间：2023 年 9 月 10 日

考生注意事项：

• 试题纸共有 16 页，答题纸共有 1 页，满分 100 分。请在答题纸上作答，写在试题纸上的 一律无效。
• 不得使用任何电子设备（如计算器、手机、电子词典等）或查阅任何书籍资料。#### 一、单项选择题（共 15 题，每题 2 分，共计 30 分；每题有且仅有一个正确选项选择题

1. 在 Linux 系统终端中，用于列出当前目录下所含的文件和子目录的命令为（ ）。

{{ select(1) }}

• ls
• cd
• cp
• all

2. 有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

3. 设 x=true,y=true,z=false，以下逻辑运算表达式值为真的是 ()。

   {{ select(3) }}

• (y∨z)∧x∧z
• x^(z∨y) ∧Z
• (x∧y) ∧z
• (x∧y)∨(z∨x)

4. 以比较作为基本运算，在 N个数中找出最大数，最坏情况下所需要的最少的比较次数为 ()。 {{ select(4) }}

• N2
• N
• N -1
• N +1

5. 对于有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

7. 排序的算法很多，若按排序的稳定性和不稳定性分类，则()是不稳定排序 {{ select(7) }}

• 冒泡排序
• 直接插入排序
• 快速排序
• .归并排序

8. 二进制数 101.01 对应的十进制数是 () {{ select(8) }}

• 5.25
• 5.75
• 5.625
• 6.5

9. 令根结点的高度为 1，则一棵含有 2021 个结点的二又树的高度至少为 () {{ select(9) }}

• 2021
• 10
• 11
• 12

10. 一些数字可以颠倒过来看，例如 0,1,8 颠倒过来还是本身，6 颠倒过来是 99 倒过来看还是 6其他数字颠倒过来都不构成数字。类似的，，一些多位数也可以颠倒过来看，比如 106 颠倒过来是901。假设某个城市的车牌只有 5 位数字，每一位都可以取 0到9。请问这个城市有多少个车牌倒过来恰好还是原来的车牌，并且车牌上的 5位数能被 3整除? () {{ select(10) }}

• 40
• 25
• 30
• 20

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

{{ select(11) }}

• 18
• 15
• 12
• 24

12. 考虑如下递归算法

    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

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

• 12
• 13
• 14
• 15

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

• 14
• 15
• 16
• 17

15. 有如下的有向图，节点为 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) }}

• 正确
• 错误

单选题

21. 当输入为 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 是不超过 $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 行的比较运算执行的次数最接近的是:

{{ 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数组满足，对任意$0 \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个区间的左右端点是$[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++