中国电子学会（CEIT）考评中心历届真题（含解析答案）
C语言软件编程等级考试三级 2021年03月
编程题五道 总分:100分
一、找和为K的两个元素（20分）
在一个长度为n(n < 1000)的整数序列中，判断是否存在某两个元素之和为k。
时间限制: 1000ms
内存限制: 65536kb
输入
第一行输入序列的长度n和k，用空格分开。第二 行输入序列中的n个整数,用空格分开。
输出
如果存在某两个元素的和为k，则输出yes,否则输出no。
样例输入
9 10
1 2 3 4 5 6 7 8 9
样例输出
yes
#include <stdio.h> // 引入标准输入输出库
int a[1000]; // 定义一个整型数组a，可以存储1000个整数
int main() { // 主函数入口
int i,j,n,k; // 定义整型变量i, j, n, k
scanf("%d %d",&n,&k); // 从标准输入读取两个整数n和k，其中n表示接下来要输入的整数的数量，k表示要检查的和
for(i=0; i<n; i++){ // 循环n次，用于读取n个整数
scanf("%d",&a[i]); // 从标准输入读取一个整数，并存储在数组a的第i个位置
}
// 枚举两个数的和
for(i=0; i<n-1; i++){ // 外层循环，从数组的第一个元素开始，到倒数第二个元素结束
for(j=i+1; j<n; j++){ // 内层循环，从外层循环变量的下一个位置开始，到数组的最后一个元素结束
if(a[i]+a[j]==k){ // 如果数组a的第i个元素和第j个元素的和等于k
printf("yes"); // 则输出"yes"并立即结束程序
return 0; // 结束主函数，返回0
}
}
}
printf("no"); // 如果在数组中找不到两个数的和等于k，则输出"no"
return 0; // 结束主函数，返回0
}
/*
此代码的时间复杂度为O(n^2)，因为使用了双重循环来枚举所有可能的数对。
如果n很大，这可能会导致性能问题。但对于较小的n，这是一个简单且有效的方法。
*/
二、Minecraft（20分）
Minecraft是一个几乎无所不能的沙盒游戏，玩家可以利用游戏内的各种资源进行创造，搭建自己的世界。
在Minecraft中，基本的建筑元素是边长为1个单位的立方体，Tony想用N个这种小立方体搭建一个长方体，并用他珍藏已久的贴纸对其进行装饰。如果一张贴纸可以贴满小立方体的一个面。那么，他需要用掉多少张贴纸呢?
时间限制: 1000ms
内存限制: 65536kb
输入
一个整数N，表示小明所拥有的小立方体的个数。N不会超过1000。输出
一个整数，即小明最少用掉的贴纸有多少张。
样例输入
9
样例输出
30
#include<stdio.h> // 包含标准输入输出头文件，以使用printf和scanf函数
int main() {
int n, h, i, j; // 定义变量n（代表立方体的体积），h（代表立方体的高），i和j（分别代表立方体的长和宽）
int min = 999999, now; // 初始化min为很大的值（这里为999999），用于存储最小的表面积；now用于存储当前计算的表面积
scanf("%d", &n); // 从标准输入读取一个整数，并赋值给变量n
// 开始两层循环，i和j分别代表立方体的长和宽
for(i = 1; i <= n; i++){
for(j = i; j <= n ; j++){ // j从i开始是为了避免重复计算，例如i=2, j=1和i=1, j=2实际上是同一个立方体
if(n % (i * j) == 0){ // 检查n是否能被i和j整除，即是否能构成一个立方体
// 如果能，计算立方体的高
h = n / (i * j);
// 计算当前立方体的表面积
now = i * j * 2 + i * h * 2 + j * h * 2; // 立方体有6个面，每个面的面积是长乘宽或长高或宽高
if(now < min) // 如果当前计算的表面积小于之前的最小值
min = now; // 更新最小值
}
}
}
printf("%d", min); // 输出最小的表面积
return 0; // 程序结束，返回0
}
/*
这段代码的目的是找到给定体积n的立方体中，具有最小表面积的那个立方体的表面积。
它通过遍历所有可能的长和宽（i和j）来实现这一目标，其中高（h）由体积n除以i和j
的乘积得到。然后，它计算这个立方体的表面积，并与之前找到的最小值进行比较，以
更新最小值。最后，它输出找到的最小表面积。
*/
三、踩方格（20分）
有一个方格矩阵，矩阵边界在无穷远处。我们做如下假设:
(a)每走一步时，只能从当前方格移动一格，走到某个相邻的方格上;
(b）走过的格子立即塌陷无法再走第二次;
©只能向北、东、西三个方向走;
请问:如果允许在方格矩阵上走n步，共有多少种不同的方案。2种走法只要有一步不一样，即被认为是不同的方案。
时间限制: 1000ms
内存限制: 65536kb
输入
允许在方格上行走的步数n(n <= 20)
输出
计算出的方案数量
样例输入
2
样例输出
7
#include<iostream> // 引入输入输出流库，用于cin和cout操作
using namespace std; // 使用标准命名空间，使得可以直接使用如cin, cout等而不需要std::前缀
int main() // 主函数入口
{
int n, f[21]; // 定义一个整数n和一个大小为21的整数数组f
cin >> n; // 从标准输入读取一个整数赋值给n
f[0] = 1; // 初始化数组的第0项为1
f[1] = 3; // 初始化数组的第1项为3
for(int i = 2; i <= n; i++) // 从第2项开始，遍历到第n项
{
f[i] = f[i-1] * 2 + f[i-2]; // 根据数列的定义，计算第i项的值
}
cout << f[n]; // 输出数组的第n项的值到标准输出
return 0; // 主函数返回0，表示程序正常结束
}
/*
第0项 (f[0] = 1)
第1项 (f[1] = 3)
从第2项开始，每一项 (f[i]) 是前两项的和的两倍：
(f[i] = 2 \times (f[i-1] + f[i-2]))
*/
四、苹果消消乐（20分）
有100个苹果和香蕉排成一条直线，其中有N个香蕉，你可以使用至多M次魔法道具将香蕉变成苹果，最后“最长的连续苹果数量”即为你本次苹果消消乐的得分，给定苹果和香蕉的排列，求你能获得的最大得分。
时间限制: 1000ms
内存限制: 65536kb
输入
第一行是一个整数T(1<=T<= 10)，代表测试数据的组数。每个测试数据第一行是2个整数N和M(0<= N, M <=100)。第二行包含N个整数a1, a2… aN(1 <= a1< a2 < … < aN<= 100)，表示第a1,a2, … aN个位置上摆放的是香蕉。
输出
对于每组数据，输出通过使用魔法道具后你能获得的最大得分。
样例输入
3
5 1
34 77 82 83 84
5 2
10 30 55 56 90
5 10
10 30 55 56 90
样例输出
76
59
100
提示
这是个枚举题
// 引入标准输入输出库
#include <stdio.h>
// 引入字符串处理库
#include <string.h>
// 定义函数func，接收一个整数数组data和一个整数num作为参数
int func(int *data, int num) {
int i, n=0, t, mx=0; // 定义循环变量i，非零元素数量n，临时变量t和最大值mx
int temp[100] = {0}; // 定义一个临时数组temp，用于存放非零元素
// 遍历数组data，将非零元素放入temp数组中
for(i=0; i<num; i++){
if(data[i]!=0){
temp[n++] = data[i];
}
}
// 如果temp数组为空（即所有元素都被替换），则返回100
if(n==0)
return 100;
// 计算temp数组中连续非零元素的数量，并找到最大值
for(i=0; i<n; i++){
if(i==0)
t = temp[i] - 1;
else
t = temp[i] - temp[i-1] - 1;
if(t > mx)
mx = t;
}
// 返回最大值mx
return mx;
}
// 主函数
int main(){
int i, j, k, n[10], m[10], T; // 定义循环变量和一些数组
int data[10][100] = {0}; // 定义一个二维数组data，用于存放输入的数据
int app[100]; // 定义一个数组app，用于存放每组数据的副本
int mx = 0, t; // 定义最大值mx和临时变量t
// 读取测试用例的数量T
scanf("%d", &T);
// 对每组数据进行处理
for(i=0; i<T; i++){
scanf("%d %d", &n[i], &m[i]); // 读取每组数据的数量和要替换的数量
if(m[i] > n[i]) // 如果要替换的数量大于数据的数量，则替换数量为数据的数量
m[i] = n[i];
// 读取每组数据的具体数值
for(j=0; j<n[i]; j++){
scanf("%d", &data[i][j]);
}
}
// 对每组数据进行处理
for(i=0; i<T; i++){
mx = 0; // 每组的最大值赋初值0
// 枚举每组数据中的每个可能的替换位置
for(k=0; k<n[i]-m[i]+1; k++){
// 拷贝一组数据的副本到app数组
memcpy(app, data[i], sizeof(app));
// 在app数组中替换连续的m[i]个元素为0
for(j=0; j<m[i]; j++){
app[k+j] = 0;
}
// 调用func函数，计算替换后能够获得的最大连续非零元素数量
t = func(app, n[i]);
// 如果当前的最大值小于t，则更新最大值
if(t > mx)
mx = t;
}
// 输出每组数据的最大连续非零元素数量
printf("%d\n", mx);
}
return 0; // 程序结束
}
/*
这个程序的核心思想是，对于每组数据，枚举所有可能的替换位置，
然后计算替换后能够获得的最大连续非零元素数量。通过这种方式，
可以找到每组数据的最大连续非零元素数量。
*/
五、流感传染（20分）
有一批易感人群住在网格状的宿舍区内，宿舍区为n*n的矩阵，每个格点为一个房间，房间里可能住人，也可能空着。
在第一天，有些房间里的人得了流感，以后每天，得流感的人会使其邻居传染上流感，(已经得病的不变)，空房间不会传染。请输出第m天得流感的人数。
时间限制: 1000ms
内存限制: 65536kb
输入
第一行一个数字n,n不超过100，表示有n*n的宿舍房间。
接下来的n行，每行n个字符，'.‘表示第一天该房间住着健康的人，’#‘表示该房间空着，’@'表示第一天该房间住着得流感的人。
接下来的一行是一个整数m,m不超过100。输出
输出第m天，得流感的人数。
样例输入
5
....#
.#.@.
.#@..
#....
.....
4
样例输出
16
#include<cstring> // 引入C标准库中的字符串处理函数，这里可能并没有用到
#include<iostream> // 引入C++标准库中的输入输出流
using namespace std; // 使用标准命名空间std
char a[101][101],b[101][101]; // 定义两个101x101的字符数组a和b，用于存储地图状态
int main() { // 主函数入口
int n,m,ans=0; // 定义三个整数变量n, m和ans，并初始化ans为0
cin >> n; // 从标准输入读取一个整数n，表示地图的尺寸
// 读取地图的初始状态
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
cin >> a[i][j];
cin >> m; // 从标准输入读取一个整数m，表示传染的天数
// 开始模拟传染过程
for(int k=2; k<=m; k++){ // 对于每一天（从第二天开始）
// 将a数组的内容复制到b数组
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
b[i][j] = a[i][j];
// 检查每个位置，判断是否满足传染条件
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
if(a[i][j] == '.' && (b[i-1][j] == '@' || b[i+1][j] == '@' || b[i][j-1] == '@' || b[i][j+1] == '@'))
a[i][j] = '@'; // 如果满足条件，则更新a数组的状态
}
// 统计最终地图上'@'的数量
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
if(a[i][j] == '@')
ans++;
cout << ans << endl; // 输出结果
return 0; // 程序结束
}
/*
这个程序的主要逻辑是：
读取一个n*n的字符矩阵，表示地图的初始状态。其中'.'表示空白位置，
'@'可能表示已经被“传染”或占据的位置。
读取一个整数m，表示传染的天数。
对于每一天，检查每个'.'位置，如果它的上下左右有'@'位置，
则将该'.'位置更新为'@'。
在m天的传染过程结束后，统计地图上'@'的总数，并输出。
*/