2019年CSP-J-初赛试卷及解析

2024年8月11日 | 分类: 【编程】

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]]]