考生注意事项：
1、试题纸共有9页，答题纸共有1页，满分100分。请在答题纸上作答，写在试题纸上的一律无效
2、不得使用任何电子设备（如计算器、手机、电子词典等）或查阅任何书籍资料。
一、单项选择题（共15题，每题2分，共计30分；每题有且仅有一个正确选项）
1.中国的国家顶级域名是()
A. .cn B. .ch C. .chn D. .China
试题分析：常识，详情见普及组课程105课时。
2.二进制数11 1011 1001 0111和01 0110 1110 1011进行逻辑与运算的结果
A.01 0010 1000 1011 B.01 0010 1001 0011
C.0l 0010 1000 0001 D.01 0010 1000 0011
试题分析：逻辑与，当且仅当2个数对应位都为1的，答案才为1，详情见普及组课程63课时。
3.一个32位整型变量占用()个字节。
A. 32 B.128 C. 4 D.8
试题分析：1Byte(字节) = 8 bit(位) 32/8=4 详情见普及组课程103课时。
4.若有如下程序段,其中s、a、b、c均已定义为整型变量,且a、c均已赋值(c
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;
试题分析：s初始化为a; for循环执行c次，每次s减1，共减c，所以s=a-c
考察for循环的应用，详情见普及组课程16课时。
5.设有100个已排好序的数据元素,采用折半查找时,最大比较次数为()
A.7 B.10 C.6 D.8
试题分析：折半查找，首先将待查记录所在范围缩小一半，然后再缩小一半，即对100个元素进行折半查找，第一次比较范围缩小到50，第二次缩小到25，第三次缩小到17，第四次缩小到7，第五次缩小到4，第六次缩小到2，最多七次就可以查找到所要元素。详情见普及组课程第106课时。
6.链表不具有的特点是()
A.插入删除不需要移动元素 B.不必事先估计存储空间
C.所需空间与线性表长度成正比 D.可随机访问任一元素
试题分析：链表没有下标，不可随机访问详情见普及组第108课时。
7.把8个同样的球放在5个同样的袋子里,允许有的袋子空着不放,问共有多少种不同的分法?()提示:如果8个球都放在一个袋子里,无论是哪个袋子,都只算同一种分法。
A.22 B.24 C.18 D.20
试题分析：把整数8拆分成5个数字之和，允许有0，我们可以按照非零数字个数进行枚举，1个：1种，2个：4种，3个：5种，4个：5种，5个：3种，累加起来一共18种。详情见普及组课 程109课时。
8.一棵二叉树如右图所示,若采用顺序存储结构,即用一维数组元素存储该二叉树中的结点(根结点的下标为1,若某结点的下标为i,则其左孩子位于下标2i处、右孩子位于下标2i+1处),则该数组的最大下标至少为()
A.6 B.10 C.15 D.12
试题分析：根据题目描述直接计算就可以了，（（1*2+1）*2+1）*2+1=15
详情见普及 组课程99课时。
9.100以内最大的素数是()。
A.89 B.97 C.91 D.93
试题分析：97最大且为素数，详情见普及组课程123课时。
10.319和377的最大公约数是()。
A.27 B.33 C.29 D.31
试题分析：使用辗转相除法计算(319,377)=(319,58)=(58,29) = 29
详 情见普及组课程第121课时。
11.新学期开学了,小胖想减肥,健身教练给小胖制定了两个训练方案。方案一：
每次连续跑3公里可以消耗300千卡(耗时半小时):方案二:每次连续跑5公里可以消耗600千卡(耗时1小时)。小胖每周周一到周四能抽出半小时跑步,周五到周日能抽出一小时跑步。另外,教练建议小胖每周最多跑21公里,否则会损伤膝盖。请问如果小胖想严格执行教练的训练方案,并且不想损伤膝盖,每周最多通过跑步消耗多少千卡?()
A.3000 B.2500 C.2400 D.2520
试题分析：设方案1,2各i,j天，由题意，3*i+5*j<=21,i+j<=7,i<=3.求300*i+600*j的最大值。枚举所有情况当i=2,j=3时，最大值2400。
12.一副纸牌除掉大小王有52张牌,四种花色,每种花色13张。假设从这52张
牌中随机抽取13张纸牌,则至少()张牌的花色一致
A.4 B.2 C.3 D.5
试题分析：抽屉原理，13张牌最坏情况就是4种花色分别为3,3,3,4张，也就是至少4张一样花色。
13.一些数字可以颠倒过来看,例如0、1、8颠倒过来还是本身,6颠倒过来是9,9颠倒过来看还是6,其他数字颠倒过来都不构成数字。类似的,一些多位数也可以颠倒过来看,比如106颠倒过来是901。假设某个城市的车牌只由5位数字组成,每一位都可以取0到9。请问这个城市最多有多少个车牌倒过来恰好还是原来的车牌?()
A.60 B.125 C.75 D.100
试题分析：考察乘法原理，第1，2位有5种选法（0，1，6，8，9），第三位有三种0，1，8，第4，5位由前两位决定，所以答案位5*5*3=75。
14.假设一棵二叉树的后序遍历序列为 DGJHEBIFCA，中序遍历序列为 DBGEHJACIF，则其前序遍历序列为( )。
A. ABCDEFGHIJ B. ABDEGHJCFI
C. ABDEGJHCFI D. ABDEGHJFIC
试题分析：考察二叉树的遍历，后序遍历决定根是A，中序遍历中看A的左边DBGEH是左子树，右边CIF是右子树，依次类推可画出完整的树，再求先序遍历，详情见普及组课程100课时。
15.以下哪个奖项是计算机科学领域的最高奖?()
A.图灵奖 B.鲁班奖 C.诺贝尔奖D.普利策奖
试题分析：考察常识问题，并且是一道原题。详情见普及组课程102课时。
二、阅读程序(程序输入不超过数组或字符串定义的范围:判断题正确填√,错误填×:除特殊说明外,判断题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)输入的字符串只能由小写字母或大写字母组成。()
试题分析：题目没说，可以输入包含其他字符的字符串。
2)若将第8行的“i=1”改为“i=0”,程序运行时会发生错误()
试题分析：不能对0取余操作，错误。
3)若将第8行的“i<=n”改为“i*i<=n”,程序运行结果不会改变()
试题分析：求约数不是判断质数，i*i<=n只能取到n的前半部分约数。
4)若输入的字符串全部由大写字母组成,那么输出的字符串就跟输入的字符串一样。()
试题分析：按题意说明即可判断。
5)若输入的字符串长度为18,那么输入的字符串跟输出的字符串相比至多有()个字符不同。
A.18 B.6 C.10 D.1
试题分析：约数个数定理求约数个数。18的约数是：1，2，3，6，9，18。所以最多判定6次。
6)若输入的字符串长度为(),那么输入的字符串跟输出的字符申相比,至多有36个字符不同。
A.36 B.100000 C.1 D.128
试题分析：和上题同理。枚举4个选项。36有9个约数，1有1个约数，128有8个约数。选B。100000有36个约数。
#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，a[x] < y && b[y] < x成立，累计计算求和，最终结果肯定小于2n。
2)执行完第27行的“++ans”时,ans一定是偶数。()
试题分析：不一定，可以举例求出ans不是偶数的情况。
3) a[i]和b[i]不可能同时大于0。()
试题分析：举例即可找到反例。
4)若程序执行到第13行时,x总是小于y,那么第15行不会被执行。()
试题分析：同样举例可以实现。
5)若m个x两两不同,且m个y两两不同,则输出的值为()
A. 2n-2m B.2n+2 C.2n-2 D.2n
试题分析：根据题意，m次循环中会有2m个位置的值会变化，ans=2n-2m。
6)若m个x两两不同,且m个y都相等,则输出的值为()
A.2n-2 B.2n C.2m D.2n-2m
试题分析：如果m个x各不相同，循环里面的if都不会执行。对数组a，b赋值，只修改了2个位置。也可举例
答案是4。
#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数组有重复的数字,则程序运行时会发生错误。()
试题分析：分析代码，有重复的数字不会导致程序运行出错。
2)如果b数组全为0,则输出为0.()
试题分析：如果b数组是0，递归推出条件l>r返回0，根据return lres + rres + depth * b[mink];返回结果总是0。
3)当n=100时,最坏情况下,与第12行的比较运算执行的次数最接近的是（）
A.5000 B.6000 C.6 D.100
试题分析：最坏情况下a有序，总是求mink和min最小值，需要判断100+99+98+...+2+1 =5050，选A。
4)当n=100时,最好情况下,与第12行的比较运算执行的次数最接近的是（）
A.100 B.6 C.5000 D.600
试题分析：最好情况每次都二分，总次数为100，层数为 6<log2100<7，总次数约为[6*100,7*100]，选D。
5)当n=10时,若b数组满足,对任意0≤i<n,都有b[i]=i+1,那么输出最大为()
A.386 B.383 C.384 D.385
试题分析：n=10，深度最大是10，根据代码：1*b[0]+2*b[1]+...+10*b[9]=1*1+2*2+3*3+...+10*10=385。
6)(4分)当n=100时,若b数组满足,对任意0≤i<n,都有b[i]=1, 那么输出最小为()
A.582 B.580 C.579 D.581
试题分析：b[i]=1,即求一个100节点的完全二叉树，节点深度之和最小为多少。画图后，计算为
1*1+2*2+4*3+8*4+16*5+32*6+37*7=580
三、完善程序(单选题,每小题3分,共计30分)
#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;
① 处应填（ ）
A.n%2 B.0 C.t D.1
试题分析：（猜的话，变量t没有用过。）递归退出判断，参数t的赋值能发现是经常做取反操作。赋值和n没有必然联系，错误。选C。
② 处应填（ ）
A.x-step,y-step B.x,y-step
C.x-step,y D.x,y
试题分析：四个方向，x，y是当前坐标。根据下面参数，参数分别是x,y;x,y+step;x+step,y;x+step,y+step。
③ 处应填（ ）
A. x-step,y-step B. x+step,y+step
C. x-step,y D. x,y-step
④ 处应填（ ）
A.n-1,n%2 B.n,0 C.n,n%2 D.n-1,0
试题分析：第一次调用recursive函数，n是矩阵规模，初始为n，t是取反次数，所以t初始为0或者1。
1)⑤ 处应填（ ）
A.i<<(n+1) B.1<<n C.n+1 D.1<<(n-1)
试题分析：size是输出矩阵的边长，2^n,位运算是1<<n。
2. (计数排序）计数排序是一个广泛使用的排序方法。下面的程序使用双关键字计数排序，对 n 对 10000 以内的整数，从小达到排序。
例如有三对整数（3，4）、（2，4）、（3，3），那么排序之后应该是（2，4）、（3，3）、（3，4）。
输入第一行为 n，接下来 n 行，第 i 行有两个数 a[i] 和 b[i]，分别表示第 i 对整数的第一关键字和第二关关键字。
从小到大排序后输出。
提示：应先对第二关键字排序，再对第一关键字排序。数组 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 < maxs; ++i)
①; // 利用 cnt 数组统计数量
for (int i = 0; i < n; ++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;
1)①处应填()
A. ++cnt[1]
B. ++cnt[b[1]]
C, ++cnt[a[i]*maxs+b[i]]
D, ++cnt[a[i]]
试题分析：提示：应先对第二关键字排序，再对第一关键字排序。排序的题做了很多，认真读题，不是特别难的事。先对第二关键字进行排序，选B。
2)②处应填()
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
试题分析：cnt[b[i]]表示第i个数按第二关键字排的位。ord[i]表示第i个数在原位置。
3)③处应填()
A. ++cnt[b[i]]
B. ++cnt[a[i]*maxs+ b[i]]
C, ++cnt[a[il]
D. ++cnt[i]
试题分析：对第一关键字进行计数。
4)④处应填()
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]
试题分析：对应填空②，此处res[i]记录第一关键字第i的数的原位置。
5) ⑤处应填()
A. a[i],b[i]
B. a[res[i]], b[res[i]]
C. a[ord[res[i]]], b[ord[res[i]]]
D. a[res[ord[i]]], b[res[ord[i]]]
试题分析：res[i]记录第i个数的原位置。
以上是2019CSP-J（入门级）C++语言试题的解题分析，参加此次考试的学员们，你们都答对了吗？另，在后台回复【真题】即可免费领取“信息学奥赛历年真题资料包”哦~
CSP-J/S是CCF创办的CSP（软件能力认证）中面向非专业级的软件能力认证，也就是我们熟知的信息学奥赛，不仅含金量高，而且对孩子升学有很大的帮助。
童程童美信息学奥赛课程是由专业教研团队与北京知名学府联合研发，课程内容循序渐进，指导学员围绕每个考试阶段的重点知识进行学习；教研团队强大专业，授课老师经验充足，确保准确把握竞赛方向和特点，保证学员学习进度和质量，助力学员在考试中取得优异成绩！
了解更多关于
信息学奥赛
详情，添加
小童老师（tctm-xiaoxiaotong）
返回搜狐，查看更多
责任编辑：
