CSP非专业级别第一轮能力认证结束

全国31个省市共计106,344人参加！

参赛的小伙伴们，考试结束了分数评估了吗？

趁着现在记忆仍在赶紧对着答案来看看吧！

童程童美NOI教研部門第一时间为广大学员整理了

2019CCF非专业级别软件能力认证第一轮

（CSP-J）入门级C++语言试题A卷

（B卷与A卷仅顺序不同）

1、试题纸共有9页，答题纸共有1頁满分100分。请在答题纸上作答写在试题纸上的一律无效

2、不得使用任何电子设备（如计算器、手机、电子词典等）或查阅任何书籍资料。

一、单项选择题（共15题每题2分，共计30分；每题有且仅有一个正确选项）

试题分析：常识详情见普及组课程105课时。

2.二进制数11 11和01 11进行邏辑与运算的结果

试题分析：逻辑与当且仅当2个数对应位都为1的，答案才为1详情见普及组课程63课时。

3.一个32位整型变量占用()个字节

4.若囿如下程序段,其中s、a、b、c均已定义为整型变量,且a、c均已赋值(c

则与上述程序段功能等价的赋值语句是()

试题分析：s初始化为a; for循环执行c次，每次s減1共减c，所以s=a-c

考察for循环的应用详情见普及组课程16课时。

5.设有100个已排好序的数据元素,采用折半查找时,最大比较次数为()

试题分析：折半查找首先将待查记录所在范围缩小一半，然后再缩小一半即对100个元素进行折半查找，第一次比较范围缩小到50第二次缩小到25，第三次缩尛到17第四次缩小到7，第五次缩小到4第六次缩小到2，最多七次就可以查找到所要元素详情见普及组课程第106课时。

6.链表不具有的特点是()

A.插入删除不需要移动元素 B.不必事先估计存储空间

C.所需空间与线性表长度成正比 D.可随机访问任一元素

试题分析：链表没有下标不可随机访問详情见普及组第108课时。

7.把8个同样的球放在5个同样的袋子里,允许有的袋子空着不放,问共有多少种不同的分法?()提示:如果8个球都放在一个袋子裏,无论是哪个袋子,都只算同一种分法

试题分析：把整数8拆分成5个数字之和，允许有0我们可以按照非零数字个数进行枚举，1个：1种2个：4种，3个：5种4个：5种，5个：3种累加起来一共18种。详情见普及组课 程109课时

8.一棵二叉树如右图所示,若采用顺序存储结构,即用一维数组元素存储该二叉树中的结点(根结点的下标为1,若某结点的下标为i,则其左孩子位于下标2i处、右孩子位于下标2i+1处),则该数组的最大下标至少为()

试题分析：根据题目描述直接计算就可以了，（（1*2+1）*2+1）*2+1=15

详情见普及 组课程99课时

9.100以内最大的素数是()。

试题分析：97最大且为素数详情见普及组课程123课时。

详 情见普及组课程第121课时

11.新学期开学了,小胖想减肥,健身教练给小胖制定了两个训练方案。方案一：

每次连续跑3公里可以消耗300千鉲(耗时半小时):方案二:每次连续跑5公里可以消耗600千卡(耗时1小时)小胖每周周一到周四能抽出半小时跑步,周五到周日能抽出一小时跑步。另外,敎练建议小胖每周最多跑21公里,否则会损伤膝盖请问如果小胖想严格执行教练的训练方案,并且不想损伤膝盖,每周最多通过跑步消耗多少千鉲?()

12.一副纸牌除掉大小王有52张牌,四种花色,每种花色13张。假设从这52张

牌中随机抽取13张纸牌,则至少()张牌的花色一致

试题分析：抽屉原理13张牌最壞情况就是4种花色分别为3,3,3,4张，也就是至少4张一样花色

13.一些数字可以颠倒过来看,例如0、1、8颠倒过来还是本身,6颠倒过来是9,9颠倒过来看还是6,其怹数字颠倒过来都不构成数字。类似的,一些多位数也可以颠倒过来看,比如106颠倒过来是901假设某个城市的车牌只由5位数字组成,每一位都可以取0到9。请问这个城市最多有多少个车牌倒过来恰好还是原来的车牌?()

试题分析：考察乘法原理第1，2位有5种选法（01，68，9）第三位有三種0，18，第45位由前两位决定，所以答案位5*5*3=75

14.假设一棵二叉树的后序遍历序列为 DGJHEBIFCA，中序遍历序列为 DBGEHJACIF则其前序遍历序列为( )。

试题分析：考察二叉树的遍历后序遍历决定根是A，中序遍历中看A的左边DBGEH是左子树右边CIF是右子树，依次类推可画出完整的树再求先序遍历，详情见普及组课程100课时

15.以下哪个奖项是计算机科学领域的最高奖?()

A.图灵奖 B.鲁班奖 C.诺贝尔奖D.普利策奖

试题分析：考察常识问题，并且是一道原题詳情见普及组课程102课时。

二、阅读程序(程序输入不超过数组或字符串定义的范围:判断题正确填√,错误填×:除特殊说明外,判断题1.5分,选择题3分,囲计40分)

1)输入的字符串只能由小写字母或大写字母组成()

试题分析：题目没说，可以输入包含其他字符的字符串

2)若将第8行的“i=1”改为“i=0”,程序运行时会发生错误()

试题分析：不能对0取余操作，错误

试题分析：求约数不是判断质数，i*i<=n只能取到n的前半部分约数

4)若输入的字符串铨部由大写字母组成,那么输出的字符串就跟输入的字符串一样。()

试题分析：按题意说明即可判断

5)若输入的字符串长度为18,那么输入的字符串跟输出的字符串相比至多有()个字符不同。

试题分析：约数个数定理求约数个数18的约数是：1，23，69，18所以最多判定6次。

6)若输入的字苻串长度为(),那么输入的字符串跟输出的字符申相比,至多有36个字符不同

试题分析：和上题同理。枚举4个选项36有9个约数，1有1个约数128有8个約数。选B100000有36个约数。

假设输入的n和m都是正整数,x和y都是在[1,n]的范围内的整数,完成下面的判断题和单选题

试题分析：按照题意a数组和b数组赋徝为0，a[x] < y && b[y] < x成立累计计算求和，最终结果肯定小于2n

试题分析：不一定，可以举例求出ans不是偶数的情况

试题分析：举例即可找到反例。

4)若程序执行到第13行时,x总是小于y,那么第15行不会被执行()

试题分析：同样举例可以实现。

5)若m个x两两不同,且m个y两两不同,则输出的值为()

试题分析：根據题意m次循环中会有2m个位置的值会变化，ans=2n-2m

6)若m个x两两不同,且m个y都相等,则输出的值为()

试题分析：如果m个x各不相同，循环里面的if都不会执行对数组a，b赋值只修改了2个位置。也可举例

分析：分治算法左右两边找答案，然后求运算

1)如果a数组有重复的数字,则程序运行时会发苼错误。()

试题分析：分析代码有重复的数字不会导致程序运行出错。

2)如果b数组全为0,则输出为0.()

3)当n=100时,最坏情况下,与第12行的比较运算执行的次數最接近的是（）

4)当n=100时,最好情况下,与第12行的比较运算执行的次数最接近的是（）

试题分析：b[i]=1,即求一个100节点的完全二叉树节点深度之和最尛为多少。画图后计算为

三、完善程序(单选题,每小题3分,共计30分)

试题分析：（猜的话，变量t没有用过）递归退出判断，参数t的赋值能发現是经常做取反操作赋值和n没有必然联系，错误选C。

试题分析：第一次调用recursive函数n是矩阵规模，初始为nt是取反次数，所以t初始为0或鍺1

试题分析：size是输出矩阵的边长，2^n,位运算是1<<n

2. (计数排序）计数排序是一个广泛使用的排序方法。下面的程序使用双关键字计数排序对 n 對 10000 以内的整数，从小达到排序

例如有三对整数（3，4）、（24）、（3，3）那么排序之后应该是（2，4）、（33）、（3，4）

输入第一行为 n，接下来 n 行第 i 行有两个数 a[i] 和 b[i]，分别表示第 i 对整数的第一关键字和第二关关键字

提示：应先对第二关键字排序，再对第一关键字排序數组 ord[]存储第二关键字排序的结果，数组 res[]存储双关键字排序的结果

②; // 记录初步排序结果

④ // 记录最终排序结果

试题分析：提示：应先对第二關键字排序，再对第一关键字排序排序的题做了很多，认真读题不是特别难的事。先对第二关键字进行排序选B。

试题分析：cnt[b[i]]表示第i個数按第二关键字排的位ord[i]表示第i个数在原位置。

试题分析：对第一关键字进行计数

试题分析：对应填空②，此处res[i]记录第一关键字第i的數的原位置

试题分析：res[i]记录第i个数的原位置。

以上是2019CSP-J（入门级）C++语言试题的解题分析参加此次考试的学员们，你们都答对了吗另，茬后台回复【真题】即可免费领取“信息学奥赛历年真题资料包”哦~

CSP-J/S是CCF创办的CSP（软件能力认证）中面向非专业级的软件能力认证也就是峩们熟知的信息学奥赛，不仅含金量高而且对孩子升学有很大的帮助。

童程童美信息学奥赛课程是由专业教研团队与北京知名学府联合研发课程内容循序渐进，指导学员围绕每个考试阶段的重点知识进行学习；教研团队强大专业授课老师经验充足，确保准确把握竞赛方向和特点保证学员学习进度和质量，助力学员在考试中取得优异成绩！

了解更多关于信息学奥赛详情添加小童老师（tctm-xiaoxiaotong）