CSP-J2019普及组初赛(第一轮)
分数及形式:满分100分,形式为笔试(今年可能上机)
1.单项选择题,共15题,每题2分,共30分
2.阅读程序题,共3题,前两题12分,第三题16分,共40分(考试形式为选择判断形式,其中判断题1.5分,选择题3分)
3.完善程序,共2题,每题15分,共30分(选择题形式,每空3分)
参考:https://www.cnblogs.com/bigbigli/p/13530212.html
参考:https://cloud.tencent.com/developer/article/2320722
参考:https://blog.csdn.net/weixin_39104847/article/details/108671116
一. 单项选择题(共15题,每题2分,共计30分;每题有且仅有一个正确选项)
1.中国的国家顶级域名是()
A. .cn B. .ch C. .chn D. .china
答案:A
解析:.cn是中国国家顶级域名;.ch是瑞士国家顶级域名;.chn是中国拥有自主产权的网络域名,非国家顶级域名;暂无.china域名
2.二进制数11 1011 1001 0111和01 0110 1110 1011进行逻辑与运算的结果是()。
A. 01 0010 1000 1011
B. 01 0010 1001 0011
C. 01 0010 1000 0001
D. 01 0010 1000 0011
答案:D
解析:
逻辑运算是按位进行的,位与位之间不像加减运算那样有进位或借位的联系。
逻辑与(即逻辑乘法)有以下规则:0*0=0 0*1=1 1*1=1
3.一个32位整型变量占用()个字节。
A. 32 B. 128 C. 4 D. 8
答案:C
解析:1字节(byte)等于8位(bit),32位及32/8=4字节,所以选C
4.若有如下程序段,其中s、a、b、c均已定义为整型变量,且a、c均已赋值(c大于0)
s = a; for (b = 1; b <= c; b++) s = s - 1;
则与上述程序段功能等价的赋值语句是()
A. s = a – c;
B. s = a – b;
C. s = s – c;
D. s = b – c;
答案:A
解析:循环执行c次,每次s-1,s一共减去了c个1,即s=a-c
5.设有100个已排好序的数据元素,采用折半查找时,最大比较次数为()
A. 7 B. 10 C. 6 D. 8
答案:A
解析:对折半查找。
首先将待查记录所在范围缩小一半,然后逐步缩小,对100个元素的顺序表,第一次比较范围缩小到50,第二次缩小到25,第三次缩小到13,第四次缩小到7,第五次缩小到4,第六次缩小到2,第七次就可以找到查找的元素。
6.链表不具有的特点是()
A. 插入删除不需要移动元素
B. 不必事先估计存储空间
C. 所需空间与线性表长度成正比
D. 可随机访问任一元素
答案:D
解析:
链表采用的是链式存储结构,它克服了顺序存储结构的缺点,具有以下优点:
1. 它的结点空间可以动态申请和释放;
2. 它的数据元素的逻辑次序靠结点的指针来指示,不需要移动数据元素。
但是链式存储结构也有不足之处:
1. 每个结点中的指针域需额外占用存储空间;
2. 链式存储结构是一种非随机存储结构。
7.把8个同样的球放在5个同样的袋子里,允许有的袋子空着不放,问共有多少种不同的分法?()
提示:如果8个球都放在一个袋子里,无论是哪个袋子,都只算同一种分法。
A. 22 B. 24 C. 18 D. 20
答案:C
【解析1】
运用5个袋子装8个球有3种:1+1+1+1+4 = 8,1+1+1+2+3 = 8,1+1+2+2+2 = 8;
运用4个袋子分8个球有5种:1+1+1+5=8,1+1+2+4=8,1+1+3+3=8,1+2+2+3=8,2+2+2+2=8;
运用3个袋子分8个球有5种:1+1+6=8,1+2+5=8,1+3+4=8,2+2+4=8,2+3+3=8;
运用2个袋子分8个球则有4种:1+7=8,2+6=8,3+5=8,4+4=8;
运用1个袋子装8个球则有1种:8=8。
所以一共有3+5+5+4+1 = 18种。
【解析2】
把问题合成,先思索5个袋子都不空的状况,再思索4个袋子不空的状况,以此类推,最后思索只运用一个袋子的状况(这种分法只要1种),把一切子状况的分法数相加求出总分法。
进一步剖析,运用k个袋子装n个球(袋子不空),一共有几种分法的问题能够转化为k个数相加等于n的种数问题。
运用5个袋子装8个球则有3种:
1+1+1+1+4 = 8
1+1+1+2+3 = 8
1+1+2+2+2 = 8
运用4个袋子分8个球则有5种:
1+1+1+5=8
1+1+2+4=8
1+1+3+3=8
1+2+2+3=8
2+2+2+2=8
运用3个袋子分8个球则有5种:
1+1+6=8
1+2+5=8
1+3+4=8
2+2+4=8
2+3+3=8
运用2个袋子分8个球则有4种:
1+7=8
2+6=8
3+5=8
4+4=8
运用1个袋子装8个球则有1种:
8=8
因而,该问题的答案即为一切子状况下的和,3+5+5+4+1 = 18。
扩展局部:
关于将一个整数 N 合成成 K 个不为0的数之和,能够应用递归加动态规划来停止快速运算。
递推公式为:
f(n, k) = f(n-1, k-1) + f(n-k, k)
递归出口为:
f(n, k) = 1, 当 k == 1 或 n == k;(很明显,只要一个袋子,或者袋子数和球数相同时只要一种分法)
f(n, k) = 0, 当 n < k;(球数比袋子数少,则必然存在尚未应用的袋子,无解)
接下来停止剖析:
f(n-1, k-1)怎样了解呢,就是把第 1 个数放成 1,然后把剩下的 n-1 这个数分红 k-1 份。f(n-1, k-1)就是原n,k问题中第一个数是 1 的一切分的办法数;
f(n-k, k) 就是原n,k问题中第一个数不是 1(大于1),能够分的办法数。这是一个关键点。认真剖析,相当于给 k 个位置,每个位置先放一个 1,(相当于每个袋子都有1个球)。接下来剩下的 n-k ,这个数字再往这 k 个位置上分,(相当于把剩下的球分给袋子,仍保证应用一切袋子)这能够保证第一个位置至少比1大(第一个袋子的球数大于1)。
8.一棵二叉树如右图所示,若采用顺序存储结构,即用一维数组元素存储该二叉树中的结点(根结点的下标为1,若某结点的下标为i ,则其左孩子位于下标2i处、右孩子位于下标2i+l处),则该数组的最大下标至少为()。
A. 6 B. 10 C. 15 D. 12
答案:C
解析:根据题目给定的规则可知,下标最大的结点为树中深度最大且最靠右的结点,其下标为((12+1)2+1)*2+1=15
9.100以内最大的素数是()。
A. 89 B. 97 C. 91 D. 93
答案:B
解析:98~100均为合数,97为素数
10.319和377的最大公约数是()。
A. 27 B. 33 C. 29 D. 31
答案:C
解析:使用辗转相除法可得GCD(319,377)=GCD(319,58)=GCD(58,29)=29。或者将两数分解质因数后,提取公共部分亦可求解
11.新学期开学了,小胖想减肥,健身教练给小胖制定了两个训练方案。
方案一:每次连续跑3公里可以消耗300千卡(耗时半小时);
方案二:每次连续跑5公里可以消耗600千卡(耗时1小时)。
小胖每周周一到周四能抽出半小时跑步,周五到周日能抽出一小时跑步。
另外,教练建议小胖每周最多跑21公里,否则会损伤膝盖。
请问如果小胖想严格执行教练的训练方案,并且不想损伤膝盖,每周最多通过跑步消耗多少千卡?()
A. 3000 B. 2500 C. 2400 D. 2520
答案:C
解析:设方案1执行x天,方案2执行y天,则有3x+5y<=21、x+y<=7、y<=3。要求300x+600y的最大值,枚举可得最优方案为x=2、y=3,此时300x+600y为2400。
12.—副纸牌除掉大小王有52张牌,四种花色,每种花色13张。假设从这52张牌中随机抽取13张纸牌,则至少()张牌的花色一致。
A. 4 B. 2 C. 3 D. 5
答案:A
解析:抽屉原理,最坏情况,13张牌对应四种花色的牌数为3、3、3、4
13.一些数字可以颠倒过来看,例如0、1、8颠倒过来还是本身,6颠倒过来是9, 9颠倒过来看还是6,其他数字颠倒过来都不构成数字。
类似的,一些多位数也可以颠倒过来看,比如106颠倒过来是901。假设某个城市的车牌只由5位数字组成,每一位都可以取0到9。
请问这个城市最多有多少个车牌倒过来恰好还是原来的车牌?()
A. 60 B. 125 C. 75 D. 100
答案:C
解析:乘法原理,前2位有0,1,8,6,9共5种选择,第3位只能放0,1,8、后2位由前2位决定,因此总方案数为55311=75。
14.假设一棵二叉树的后序遍历序列为DGJHEBIFCA,中序遍历序列为DBGEHJACIF,则其前序遍历序列为()。
A. ABCDEFGHIJ
B. ABDEGHJCFI
C. ABDEGJHCFI
D. ABDEGHJFIC
答案:B
解析:后序遍历的规则是“左右根”、中序遍历的规则是“左根右”,因此可知,A是树根、DBGEHJ是A左子树的中序遍历(对应后序遍历DGJHEB)、CIF是A右子数的中序遍历(对应后序遍历IFC),递归画出对应的二叉树,再根据前序遍历规则“根左右”即可求出答案
15.以下哪个奖项是计算机科学领域的最高奖?()
A. 图灵奖 B. 鲁班奖 C. 诺贝尔奖 D. 普利策奖
答案:A
解析:图灵奖由美国计算机协会于1966年设立,其名称取自计算机科学之父图灵,专门奖励对计算机事业作出重要贡献的个人,被誉为“计算机界的诺贝尔奖”。
第 16 题
二、阅读程序(程序输入不超过数组或字符串定义的范围;判断题正确填√,错误填×;除特殊说明外,判断题1.5分,选择题3分,共计40分)
#include <cstdio> #include <cstring> using namespace std; char st[100]; int main() { scanf("%s", st); int n = strlen(st); for (int i = 1; i <= n; ++i) { if (n % i == 0) { char c = st[i - 1]; if (c >= 'a') st[i - 1] = c - 'a' + 'A'; } } printf("%s", st); return 0; }
•判断题
1. 输入的字符串只能由小写字母或大写字母组成。()
A. 正确
B. 错误
答案:错
解析:输入的字符串也可以包含数字等其他字符
2. 若将第8行的 i = 1 改为 i = 0,程序运行时会发生错误。()
A. 正确
B. 错误
答案:对
解析:若i可以为0,则第9行的if语句条件 “n%i==0” 将发生运行时错误RE。
3. 若将第8行的i <= n改为i * i <= n,程序运行结果不会改变。()
A. 正确
B. 错误
答案:错
解析:当第8行的循环条件为“i<=n”时,字符串的末尾字符会被程序加工,但若改为“i*i<=n”,字符串的末尾字符将不会被程序加工(除非字符串长度为1)。
4. 若输入的字符串全部由大写字母组成,那么输出的字符串就跟输入的字符串一样。()
A. 正确
B. 错误
答案:对
解析:大写字母的ASCLL编码值小于小写字母的。若输入的字符串全部由大写字母组成,则程序不会对其进行加工。
•选择题
1. 若输入的字符串长度为18,那么输入的字符串跟输出的字符串相比,至多有()个字符不同。
A. 18 B. 6 C. 10 D. 1
答案:B
解析:18的正约数共有6个,因此程序最多修改输入字符串中的6个字符,即输出字符串与输入字符串最多有6个字符不同。
2. 若输入的字符串长度为(),那么输入的字符串跟输出的字符串相比,至多有36个字符不同。
A. 36 B. 100000 C. 1 D. 128
答案:B
解析:要使输出字符串和输入字符串之间最多有36个字符不同,36应当是字符串长度n的约数个数。本题选项中,仅有100000满足要求,分解质因数得25*55,正约数共有(5+1)*(5+1)=36个
第 17 题
#include<cstdio> using namespace std; int n, m; int a[100], b[100]; int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= n; ++i) a[i] = b[i] = 0; for (int i = 1; i <= m; ++i) { int x, y; scanf("%d%d", &x, &y); if (a[x] < y && b[y] < x) { if (a[x] > 0) b[a[x]] = 0; if (b[y] > 0) a[b[y]] = 0; a[x] = y; b[y] = x; } } int ans = 0; for (int i = 1; i <= n; ++i) { if (a[i] == 0) ++ans; if (b[i] == 0) ++ans; } printf("%d", ans); return 0; }
假设输入的n和m都是正整数,x和y都是在[1, n]的范围内的整数,完成下面的判断题和单选题: •
•判断题
1. 当m>0时,输出的值一定小于2n。()
A. 正确
B. 错误
答案:对
解析:由限定条件0<x,y<=n可知,当m>0时,一定存在某个数对被我们选中,此时ans<2n
2. 执行完第27行的++ans时,ans —定是偶数。()
A. 正确
B. 错误
答案:错
解析:由于数对是一个左值与一个由值相匹配,因此ans最终一定是偶数。但第27行的“++ans”在第23行的for循环内部,其中间结果可能为奇数。
3. a[i]和b[i]不可能同时大于0。()
A. 正确
B. 错误
答案:错
解析:a[i]用于记录与左值i相匹配的右值,不存在则为0;b[i]用于记录与右值i相匹配的左值,不存在则为0.当存在数对(i,y)和(x,i)都被我们选中时,a[i]和b[i]就会同时大于0。
4. 右程序执行到第13行时,x总是小于y,那么第15行不会被执行。()
A. 正确
B. 错误
答案:错
解析:存在反例,依次考虑数对(1,2)(1,3)时,第15行程序会被执行。
•选择题
1. 若m个x两两不同,且m个y两两不同,则输出的值为()
A. 2n-2m
B. 2n+2
C. 2n-2
D. 2n
答案:A
解析:此时,输入的数对两两互不冲突,因此程序会将他们全部选中,根据上述ans的意义可知,其结果为2n-2m。
2. 若m个x两两不同,且m个y都相等,则输出的值为()
A. 2n-2
B. 2n
C. 2m
D. 2n-2m
答案:A
解析:此时,输入的数对两两存在冲突,因此程序最终只会选用一个数对,根据上述ans的意义可知,其结果为 2n-2 。
第 18 题
#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; }
•判断题
1. 如果a数组有重复的数字,则程序运行时会发生错误。()
A. 正确
B. 错误
答案:错
解析:若a数组有重复数字,则程序在根据a数组递归构造符合要求的二叉树时,对于相同结点值,会优先考虑位于左侧的。
2. 如果b数组全为0,则输出为0。()
A. 正确
B. 错误
答案:对
解析:程序最终输出的是各结点深度与b值得加权和,因此若b数组全为0,则加权和显然为0。
•选择题
1. 当n=100时,最坏情况下,与第12行的比较运算执行的次数最接近的是:()。
A. 5000
B. 600
C. 6
D. 100
答案:A
解析:最坏情况下,程序所构成的二叉树的每个结点最多有一个子结点,此时,程序将递归100层,其中第i层进行100-i+1次第12行的比较运算,总执行次数为100+99+98+…+1≈5000。
2. 当n=100时,最好情况下,与第12行的比较运算执行的次数最接近的是:()。
A. 100
B. 6
C. 5000
D. 600
答案:D
解析:最佳情况下,程序构造二叉树时,对于每个结点会尽可能均分其左右子树。定义根结点深度为1,则含n=100个结点的树的深度最小为logn≈7,此时每选定一层结点,程序都需要执行约n次的第12行的比较运算,因此总执行次数约为nlogn≈600。
3. 当n=10时,若b数组满足,对任意0<=i<n,都有b[i] = i + 1,那么输出最大为()。
A. 386
B. 383
C. 384
D. 385
答案:D
解析:此时,要使输出的ans值尽可能大,程序所构造的二叉树的深度应尽可能大。定义根结点深度为1,则含10个结点的二叉树的最大深度为10,因此ans的最大值为11+22+33+…+1010=385。
4.当n=100时,若b数组满足,对任意0 <= i < n,都有b[i]=1,那么输出最小为()。
A. 582
B. 580
C. 579
D. 581
答案:B
解析:此时,要使输出的ans值尽可能小,程序应参照完全二叉树构造此树,其中深度为1的结点共1个,深度为2的结点共2个,深度为3的结点共4个…深度为6的结点共32个,剩余37个结点的深度为7,因此ans的最小值为(11+22+33+…+632)+7*37=580。
第 19 题
1.(矩阵变幻)有一个奇幻的矩阵,在不停的变幻,其变幻方式为:
数字 0 变成矩阵
0 0
0 1
数字 1 变成矩阵
1 1
1 0
最初该矩阵只有一个元素 0,变幻 n 次后,矩阵会变成什么样?
例如,矩阵最初为:[0];
矩阵变幻 1 次后:
0 0
0 1
矩阵变幻 2 次后:
0 0 0 0
0 1 0 1
0 0 1 1
0 1 1 0
输入一行一个不超过 10 的正整数 n。输出变幻 n 次后的矩阵。
试补全程序。
提示:
<< 表示二进制左移运算符,例如(11)
2
<< 2 = (1100)
2
; 而 ^ 表示二进制异或运算符,它将两个参与运算的数中的每个对应的二进制位—进行比较,若两个二进制位相同,则运算结果的对应二进制位为 0 ,反之为 1。
#include <cstdio> using namespace std; int n; const int max_size = 1 << 10; int res[max_size][max_size]; void recursive(int x, int y, int n, int t) { if (n == 0) { res[x][y] = ①; return; } int step = 1 << (n - 1); recursive(②, n - 1, t); recursive(x, y + step, n - 1, t); recursive(x + step, y, n - 1, t); recursive(③, n - 1, !t); } int main() { scanf("%d", &n); recursive(0, 0, ④); int size = ⑤; for (int i = 0; i < size; i++) { for (int j = 0; j < size; j++) printf("%d", res[i][j]); puts(""); } return 0; }
①处应填(C)
A. n%2
B. 0
C. t
D. 1
②处应填(D)
A. x-step,y-step
B. x,y-step
C. x-step,y
D. x,y
③处应填(B)
A. x-step,y-step
B. x+step,y+step
C. x-step,y
D. x,y-step
④处应填(B)
A. n-1,n%2
B. n,0
C. n,n%2
D. n-1,0
⑤处应填(B)
A. 1<<(n+1)
B. 1<<n
C. n+1
D. 1<<(n-1)
第 20 题
2.(计数排序)计数排序是一个广泛使用的排序方法。下面的程序使用双关键字计数排序,将n对10000以内的整数,从小到大排序。
例如有三对整数(3,4)、(2,4)、(3,3),那么排序之后应该是(2,4)、(3,3)、(3,4) 。
输入第一行为n,接下来n行,第i行有两个数a[i]和b[i],分别表示第i对整数的第一关键字和第二关键字。
从小到大排序后输出。
数据范围 1 < n < 107, 1 < a[i], b[i] < 104
提示:应先对第二关键字排序,再对第一关键字排序。数组ord[]存储第二关键字排序的结果,数组res[]存储双关键字排序的结果。
试补全程序。
#include <cstdio> #include <cstring> using namespace std; const int maxn = 10000000; const int maxs = 10000; int n; unsigned a[maxn], b[maxn],res[maxn], ord[maxn]; unsigned cnt[maxs + 1]; int main() { scanf("%d", &n); for (int i = 0; i < n; ++i) scanf("%d%d", &a[i], &b[i]); memset(cnt, 0, sizeof(cnt)); for (int i = 0; i < n; ++i) ①; // 利用 cnt 数组统计数量 for (int i = 0; i < maxs; ++i) cnt[i + 1] += cnt[i]; for (int i = 0; i < n; ++i) ②; // 记录初步排序结果 memset(cnt, 0, sizeof(cnt)); for (int i = 0; i < n; ++i) ③; // 利用 cnt 数组统计数量 for (int i = 0; i < maxs; ++i) cnt[i + 1] += cnt[i]; for (int i = n - 1; i >= 0; --i) ④ // 记录最终排序结果 for (int i = 0; i < n; i++) printf("%d %d", ⑤); return 0; }
①处应填(B)
A. ++cnt [i]
B. ++cnt[b[i]]
C. ++cnt[a[i] * maxs + b[i]]
D. ++cnt[a[i]]
②处应填(D)
A. ord[–cnt[a[i]]] = i
B. ord[–cnt[b[i]]] = a[i]
C. ord[–cnt[a[i]]] = b[i]
D. ord[–cnt[b[i]]] = i
③处应填(C)
A. ++cnt[b[i]]
B. ++cnt[a[i] * maxs + b[i]]
C. ++cnt[a[i]]
D. ++cnt [i]
④处应填(A)
A. res[–cnt[a[ord[i]]]] = ord[i]
B. res[–cnt[b[ord[i]]]] = ord[i]
C. res[–cnt[b[i]]] = ord[i]
D. res[–cnt[a[i]]] = ord[i]
⑤处应填(B)
A. a[i], b[i]
B. a[res[i]], b[res[i]]
C. a[ord[res[i]]]j b[ord[res[i]]]
D. a[res[ord[i]]]j b[res[ord[i]]]