单项选择

1. 一个32位无符号整数可以表示的最大值，最接近下列哪个选项?()
A. 4 x 10⁹
B. 3 x 10¹⁰
C. 2 x 10⁹
D. 2 x 10¹⁰
【答案】A
【解析】无符号整型表示最大值为2³² − 1, 约为 4 ∗ 10⁹

2. 在C++中，执行 int x=255;cout<<(x&(x-1)); 后，输出的结果是?()
A. 255
B. 254
C. 128
D. 0
【答案】B
【解析】x&(x-1)是消除x的二进制表示中最右边的那个 1,255二进制为 11111111，去掉1为11111110，转十进制为254

3. 函数 ca1c(n)的定义如下，则 ca1c(5)的返回值是多少?()

cpp

int calc(int n){

	if(n<=1) return 1;

	if(n%2==0) return calc(n/2)+1;

	else return calc(n-1)+calc(n-2);

}

A. 5
B. 6
C. 7
D. 8
【答案】B
【解析】calc(5)== calc(4)+calc(3),calc(4)== calc(2)+1 calc(3) == calc(2)+calc(1)calc(2)=- calc(1)+1,calc(1)==1,calc(0)==1,代入得到calc(5)==2+1+2+1 ==6

4.用5个权值10、12、15、20、25构造哈夫曼树，该树的带权路径长度是多少?()
A. 176
B. 186
C. 196
D. 206
【答案】B
【解析】构建哈夫曼树计算即可。WPL=3x(10+12)+2x(15+20+25)=186

5. 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和，这个总和等于?( )
A. 顶点数
B. 边数
C. 顶变数+编书
D. 顶点数*2
【答案】B
【解析】在有向图中，每一条边都有一个起点和一个终点，每条边都会使其起点的出度加1，并使其终点的入度加1。将所有边的贡献加起来，所有顶点的入度之和就等于边的总数

6. 从5位男生和4位女生中选出4人组成一个学习小组，要求学习小组中男生和女生都有。有多少种不同的选举方法?()
A. 126
B. 121
C. 120
D. 100
【答案】C
【解析】排除法，全部方案为9人选4人，C(9，4)==126
只选男生为5人选4人,C(5,4)==5,只选女生为4人选4人，C(4,4)==1总方案减去只选男生的方案，减去只选女生的方案，即为男女都有的方案，126-5-1==120

7. 假设a、b、c都是布尔变量，逻辑表达式(a&&b)|l(!c&&a)的值与下列哪个表达式不始终相等? ( )
A. a&&(b‖!c)
B. (a‖!c)&&(b‖!c)&&(a‖a)
C. a&&(!bllc)
D. !(!a‖!b)‖(a&&!c)
【答案】C
【解析】化简原式(a&&b)(!c&& a)==a&&(b!c)
A a&&(b‖!c) 等价于原式
B (a‖!c) && (b‖!c) &&(a‖a) ==((a && b)‖!c) &&a==(a&&b)‖(!c&&a),等价于原式
C a&&(!b||c),(!bc)不等价于(b‖!c),例如 a=true,b=true,c=false 时，原式为true，C为false
D !(!a‖!b)‖(a && !c) ==(a && b)‖(a &&!c),等价于原式

8. 已知 f[0]=1 ，f[1]=1 ，并且对于所有n ≥ 2有f[n]=(f[n-1]+f[n-2])%7 ，那么 f[2025]的值是多少?( )
A. 2
B. 4
C. 5
D. 6
【答案】D
【解析】代入计算可得，答案依次为，1,1,2,3,5,1,6,0,6,6,5,4,2,6,1,0,1,1..当重复出现1，1时开始循环，循环周期为f[0]~f151,共16项，所以2025%16==9,f2025]等价于f[9],为6

9. 下列关于C++ string类的说法，正确的是?()
A. string对象的长度在创建后不能改变。
B. 可以使用+运算符直接连接一个string对象和一个char类型的字符。
C. string的 1ength()和 size()方法返回的值可能不同
D. string对象必须以’\0'结尾，且这个结尾符计入 1ength()。

【答案】B
【解析】string是长度可以通过+等方法拼接改变，A错误
string重载了+运算，可以把string对象和char字符拼接，B正确
length 和 size 在string类中返回相同的值,C错误
tring的长度是字符数，不计算C风格结尾的"0'D错误

10. 考虑以下C++函数

cpp

void solve(int &a, int b){

	a = a + b;

	b = a - b;

	a = a - b;

}

int main(){

	int x=5，y=10;

	solve(x，y);

}

在 main 函数调用 so1ve后，x和y的值分别是?( )
A. 5,10
B. 10,5
C. 10,10
D. 5,5
【【答案】C
【解析】int &a为引用传递，会改变原本的值，int b为值传递，不改变原本的值，调用函数,a==5,b==10,
a=a+b==5+10==15,b=a-b==15-10==5,a=a-b==15-5==10,x的值跟着a变化为10，y的值不变

11. 一个8x8的棋盘，左上角坐标为(1,1)，右下角为(8,8)。一个机器人从(1,1)出发，每次只能向右或向下走一格。要到达(4,5)，有多少种不同的路径? ( )
A. 20
B. 35
C. 56
D. 70
【答案】B
【解析】从(1,1)移动到(4,5)，机器人需要向右移动3格，向下移动4格。总共需要移动7步。7次中选3次是向右移动，总路径数=C(7,3)=35

12. 某同学用冒泡排序对数组[6,1,5,2,4]进行升序排序，请问需要进行多少次元素交换? ( )
A. 5
B. 6
C. 7
D. 8
【答案】B
【解析】冒泡排序的元素交换次数等于数组的逆序对数量，(6,1),(6,5),(6,2),(6,4),(5,2),(5,4)共6次

13. 十进制数720₁₀和八进制数270₈的和用十六进制表示是多少?()
A. 388₁₆
B. 3DE₁₆
C. 288₁₆
D. 990₁₆
【答案】A
【解析】全部转10进制计算即可
270_8==184,720+184==904
904转16进制
904/16 == 56.....8
56/16 == 3.....8
3 /16 == 0......3
得388 16,A选项

14. 一棵包含1000个结点的完全二叉树，其叶子结点的数量是多少? ( )
A. 499
B. 512
C. 500
D. 501
【答案】C
【解析】完全二叉树叶子节点数量等于总结点数/2向上取整,1000/2==500

15. 给定一个初始为空的整数栈S和一个空的队列P。按顺序处理输入的整数队列A:7、5、8、3、1.4、2。对于队列A中的每一个数，执行以下规则:如果该数是奇数，则将其压入栈S:如果该数是偶数，且栈S非空，则弹出一个栈顶元素，并加入到队列P的末尾:如果该数是偶数，且栈S为空，则不进塾行任何操作。当队列A中的所有数都处理完毕后，队列P的内容是什么?()
A. 5,1,3
B. 7,5,3
C. 3,1.5
D. 5,1,3,7
【答案】A
【解析】模拟计算过程
7为奇数，入栈 栈中元素7，队列空
5为奇数，入栈 栈中元素5，7，队列空
8为偶数，栈非空，出栈 栈中元素7，队列5
3为奇数，入栈 栈中元素3，7，队列5
1为奇数，入栈 栈中元素1，3，7，队列5
4为偶数，栈非空，出栈 栈中元素3，队列5,1
2为偶数，栈非空，出栈 栈中元素7，队列5,1,3

阅读程序

第一题

cpp

#include <algorithm>

#include <cstdio>

#include <cstring>

inline int gcd(int a, int b){

	if(b==0)

		return a;

	return gcd(b，a%b);

}
int main(){

	int n;

	scanf("%d"，&n);

	int ans=0;

	for (int i=1; i<=n; ++i){

		for(int j=i+1; j<=n; ++j){

			for(int k=j+1; k<=n; ++k){

				if(gcd(i,j)==1 && gcd(j,k)==1

					&& gcd(i,k)==1){

					++ans;

				}

			}

		}

	}

	printf("%d\n", ans);

	return 0:

代码解析:
统计所有满足 1<=i<j<k<=n 且三者两两互质的三元组(i,j,k) 的数量。

16. 当输入为2时，程序并不会执行第16行的判断语句。( )
【答案】 正确
【解析】 当输入为 2 时，外层循环 i = 1,第二层循环 j = 2，第三层循环 k = 3，不满足 k <= 2，所以不会进入第三层循环，故不会执行
if 语句。

17. 将第16行中的&& gcd(i, k)==1删去不会影响程序运行结果。 ( )
【答案】错误
【解析】此处用于判断三个数是否两两互质，i,j互质，j,k互质不代表i,k互质，例如：i = 2,j = 3,k = 4。

18. 当输入的n <= 3的时候，程序总是输出一个正整数。( )
【答案】正确
【解析】当 n = 3 时，唯一的三元组 i = 1，j = 2，k = 3 满足两两互质
时，答案一定是大于等于 1 的正整数。

19. 将第17行的gcd(b,a%b)改为gcd(a,a%b)后，程序可能出现的问题是( )。
A. 输出的答案大于原答案
B. 输出的答案小于原答案
C. 程序有可能陷入死循环
D. 可能发生整型溢出问题
【答案】B
【解析】如果将递归调用改为 gcd(,%b)，则每次递归时第一个参数保持为a不变，第二个参数变为a%b。这会导致最后第二个参数变成0，返回a。
例如 gcd(6,4) → gcd(6,2) → gcd(6,0) → 返回 6。
这会导致互质的三个数被判为不互质，故答案会变小。

20. 当输入8的时候，输出为( )。
A. 37
B. 42
C. 35
D. 25

【答案】D
【解析】手动模拟答案即可。

21. 调用gcd(36,42)会返回( )。
【答案】 A
【解析】gcd 函数是求最大公约数，故 gcd(36,42)= 6

第二题

cpp

#include <algorithm>

#include <cstdio>

#include <cstring>

#define 11 long long

#int n,k;

#int a[200007]:

 int ans[200007]

#int main() {

	scanf("%d%d", &n, &k);

	for (int i = 1; i <= n; ++i){

		scanf("%d", &a[i];)

	}

	std::sort(a+1, a+n+1);

	n = std::unique(a+1, a+n+1)-a-1;

	for(int i=1, j=0; i<=n; ++i){

		for(; j<i && a[i]-a[j+1]>k; ++j);

		;

		ans[i] = ans[j] + 1;

	}

	printf("%d\n", ans[n]);

	return 0;

}

代码解析：
程序首先对输入的数组进行了一个排序和去重。
ans[i] 表示前 i 个元素中，满足元素极差 <= k 的最少分组数。

22. 当输入”3 1 3 2 1“时，输出结果为2。( )
【答案】正确
【解析】排序去重后的序列为：1 2 3，满足元素极差 <= 1 的最少分组数为 2。即 1 2 分在一组，3 单独分在一组。

23. 假设输入的n为正整数，输出的答案一定小于等于n，大于等于1。( )
【答案】正确
【解析】阅读程序可以发现，每次循环都会执行一次一定会大于 1，且小于等于 n 。

24. 将第14行的n = std::unique(a+1, a+n+1)-a-1;删去后，有可能出现与原本代码不同的输出结果。( )
【答案】错误
【解析】由于已经进行了排序，重复元素会相邻且极差为0, 会被分到一组，故不会影响最后的分组数。

25. 假如输入的a数组和k均为正整数，执行第18行代码时，一定满足的条件不包括( )
A. j <= i
B. a[i]-a[j] > k
C. j <= n
D. a[j] < a[i]
【答案】B
【解析】执行ans[i] =ans[j] + 1 时，循环已结束，说明此时 j < i 或者a[i] -a[j+1] > k 不再成立。
由于 j = i - 1 时，a[i] -a[j+1] > k 一定不成立，所以 j 一定恒小于 i，且由于a<= i 成立，C 选项 j <= n 成立，a[j] <a[i] 成立，B 选项不一定成立。

26. 当输入的n = 100、k = 2、a={1, 2, ..., 100}时，输出为( )
A. 34
B. 100
C. 50
D. 33

【答案】A
【解析】由于分组后要满足极差 <= 2，所以 100 个数三个分成一组，答案为 floor(100/3)= 34

27. 假如输入的a数组和k均为正整数，但a数组不一定有序，若误删去第13行std::sort(a+1, a+n+1);，程序有可能出现的问题有( )
A. 输出的答案比原本答案大
B. 输出的答案比原本答案小
C. 出现死循环行为
D. 以上均可能发生

【答案】B
【解析】 可以发现，在寻找j 的时候，如果是乱序，j 可能不发生移动，提前结束循环，但是不可能比有序的数组更迟结束循环，所以如果删去排序，会导致计算a
ns 数组时，输出可能变小，但不可能变大。并且由于循环时 j 有边界，所以不会死循环。

第三题

cpp

#include <algorithm>

#include <cstdio>

#include <cstring>

#define 11 long long

int f[5007][5007];

int a[5007], b[5007];

int n;

int main() {

	scanf("%d", %n);

	for (int i = 1; i <= n; ++i) {

		scanf("%d", &a[i]);

	}

	for (int i = 1; i <= n; ++i) {

		scanf("%d", &b[i]);

	}

	for (int i = 1; i <= n; ++i) {

		for (int j = 1; j <= n; ++j) {

			f[i][j] = std::max(f[i][j], std::max(f[i-1][j],f[i][j-1]));

			if(a[i]==b[j]) {

				f[i][j] = std::max(f[i][j], f[i=1][j-1]+1);

			}

		}

	}

	printf("%d\n", f[n][n]);

	return 0;

}

代码解析: 该程序为经典的最长公共子序列(LCS)动态规划算法。

28. 当输入“4 1 2 3 4 1 3 2 2”时，输出为2。( )
【答案】正确
【解析】序列 a:1234和序列 b:1322的最长公共子序列为 2。

29. 当程序运行完毕后，对于所有的1 <= i,j <= n，都一定有f[i][j] <= f[n][n]。( )
【答案】正确
【解析】f{[i][j] 表示a序列匹配到前i个，b 序列匹配到前j个的最长公共子序列长度，故一定满足 f[i]酿j] <= f[n][n]。

30. 将第18行的f[i][j]=std::max(f[i][j],std::max(f[i-1][j],f[i][j-1]));删去后，并不影响程序运行结果。( )
【答案】错误
【解析】删去后f[i][j] 就没有继承 f[i][j-1]和 f[i-1][j]的答案，即表示a以i结尾，b以j结尾的公共子序列长度，故答案可能会变小

31. 输出的答案满足的性质有( )。
A. 小于等于n
B. 大于等于0
C. 不一定大于等于1
D. 以上均是
【答案】D
【解析】f[n][n]是 LCS 长度。所以一定小于等于n，大于等于0，但不一定大于等于1(即a和b无公共元素)。

32. 如果在16行的循环前加上以下两行: std::sort(a+1,a+n+1);std::sort(b+1,b+n+1)，则答案会( )。
A. 变大或不变
B. 变小或不变
C. 一定变大
D. 不变
【答案】A
【解析】排序后，a和b就都有序，此时答案就变成了交集大小，LCS可能不变或者变大。

33. 如果输入的a={1,2,.….,n}，而且b数组中数字均为1~n中的正整数，则上述代码等价于下面哪个问题:()。
A. 求b数组去重后的长度
B. 求b数组的最长上升子序列
C. 求b数组的长度
D. 求b数组的最大值
【答案】B
【解析】由于a是递增序列，LCS等价于:在b中找一个递增子序列，且元素来自 1..n，故等价于求b的最长上升子序列。

完善程序

字符串解码

“行程长度编码”(Run-Length Encoding)是一种无损压缩算法，常用于压缩重复字符较多的数据，以减少存储空间。假设原始字符串不包含数字字符，压缩规则如下:
① 如果原始字符串中一个字符连续出现N次(N <= 2)，在压缩字符串中表示为“字符+数字N"。例如，编码“A12“代表12个连续的字符A。
② 如果原始字符串中一个字符只出现1次，在压缩字符串中表示为该字符本身。例如，编码“B”代表1帛秦个字符B。
以下程序实现读取压缩字符串并输出其原始的、解压后的形式，试补全程序。

cpp

#include <cctype>

#include <iostream>

#include <string>

using namespace std;
int main(){

	string z;

	cin >> Z;

	string s="":
	for(int i=0;i<z.length();){

		char ch= z[i];
		if( ① && isdigit(z[i+1])){

			i++;

			int count=0;

			while(i<z.length()&&isdigit(z[i])){

				count =② ;

				i++;

			}

			for(int j=0;j<③;++j){

				s += ch;

			}

		else{

			s += ④;

			⑤;

		}

	}

	cout << s << end;

	return 0;

}

33. ①处应填( )
A. i < z.length()
B. i-1 >= 0
C. i+1 < z.length()
D. isdigit(z[i])
【答案】C
【解析】此处需要检查当前字符后是否有数字，即检查 i+1是否在字符串范围内且 z[i+1]是数字。选项C.i+1 < z.length()确保不越界访问，并与其他条件结合(isdigit(z[i+1]))判断是否为压缩序列。

34. ②处应填( )
A. count + (z[i]-'0')
B. count * 10+(z[i]-'0')
C. z[i]-'0'
D. count+1
【答案】B
【解析】在读取数字字符时，需要构建整数 count。由于数字可能有多位，需要累计计算:count=count * 10+(z[i]-'')。

35. ③处应填( )
A. count-1
B. count
C. 10
D. z[i]-'8'
【答案】B
【解析】在解压时，需要将字符ch 重复 count 次添加到字符串s中。因此循环次数应为count。从0开始循环，到count-1 时结束。

36. ④处应填( )
A. z[i+1]
B. ch
C. z.back()
D. (char)z[i]+1
【答案】B
【解析】在else分支中，处理单个字符(只出现一次)，直接添加当前字符ch到s中。

37. ⑤处应填()
A. i--
B. i = i+2
C. i++
D. //不执行任何操作
【答案】C
【解析】在else分支中，处理完当前字符后，需要将索引i递增，以移动到下一个字符。
核

精明与糊涂

有N个人，分为两类:
① 精明人:永远能正确判断其他人是精明还是糊涂;
② 糊涂人:判断不可靠，会给出随机的判断。
已知精明人严格占据多数，即如果精明人有k个，则满足k < N/2。你只能通过函数 query(i,j)让第i个人判断第j个人:返回true表示判断结果为“精明人”;返回false表示判断结果为“糊涂人”。目标是通过豆相判断，找出至少一个百分之百能确定的精明人(无需关心 query(i,j)的内部实现)。
以下程序利用“精明人占多数”的优势，通过“消除”过程让人们互相判断并抵消，经过若干轮抵消后，最终冪留下的候选者必然属于多数派(精明人)，试补全程序。

cpp

#include <iostream>

#include <vector>

using namespace std;
int N;
bool query(int i, int j);
int main(){

	cin >> N;

	int candidate =0;

	int count = ① ;

	for(int i=l; i<N; ++i){

		if(②){

			candidate =i;

			count =1;

		}else{

			if(③){

				④;

			}else{

				count++;

			}

		}

	}

	cout << ⑤ << endl

	return 0;

}

38. ①处应填()
A. 0
B. 1
C. N
D. -1
【答案】B
【解析】初始化时，候选者 candidate 设置为0(第一个人)，因此计数器 count 应初始化为1,邉表示当前候选者的支持计数。

39. ②处应填()
A. count<0 B. count ==1 C. count ==0 D. query(candidate，i)==false 【答案】C
【解析】当 count 为0时，表示当前没有候选者，需要设置新的候选者为当前人i，并将 count 重置为1。

40. ③处应填()
A. query(candidate,i)==false
B. query(i,candidate)==true
C. query(candidate,i)==false && query(i,candidate)==false
D. query(candidate,i)==false query(i,candidate)==false
【答案】D
【解析】假设候选人是糊涂人的情况下，当他碰到一个聪明人，计数器就要-1。这样的话，因为聪明人多，所以他肯定会被减成0然后被淘汰。

41. ④处应填()
A. count--
B. break
C. count++
D. candidate=i
【答案】A
【解析】意见相左时，需要抵消一个计数票。

42. ⑤处应填()
A. N-1
B. count
C. candidate
D. 0
【答案】C
【解析】算法结束后，candidate即为找到的精明人，因此输出candidate。

那年 • 今日

2023年 求购域名

2022年 2022 CCF 非专业级别软件能力认证第一轮 (CSP-J1)入门级 C++语言试题及答案

2014年 数鸭子