童程童美少儿编程教育

少儿编程 > 新闻活动 > 真题解析Ⅱ | CCF CSP-S 2019 提高级 C++语言真题及答案(附信奥真题库)

真题解析Ⅱ | CCF CSP-S 2019 提高级 C++语言真题及答案(附信奥真题库)

童程童美 2019-10-22

CSP-J/S是CCF创办的CSP(软件能力认证)中面向非专业级的软件能力认证,也就是我们熟知的信息学奥赛,含金量高。以下为2019CSP-S(提高级)C++语言试题的解题分析~

摘要

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

(CSP-S)提高级C++语言试题A卷

(B卷与A卷仅顺序不同)

认证时间:2019年10月19日

考生注意事项:

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

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

一、单项选择题(共15题,每题2分,共计30分;每题有且仅有一个正确选项)

1.若有定义:int a=7; float x=2.5,y=4.7;则表达式x+a%3*(int)(x+y)%2的值是:( )

A.0.000000          B.2.750000          C.2.500000          D.3.500000

答案:D

题目分析:基础题目,数据类型和运算符优先顺序。x+a%3*(int)(x+y)%2转化为式子为:

2.5+7%3*(int)(2.5+4.7)%2

= 2.5+7%3*(int)(7.2)%2

= 2.5+1*7%2

= 2.5+7%2

= 3.5

2.下列属于图像文件格式的有( )

A.WMV          B.MPEG          C.JPEG          D.AVI

答案:C

题目分析:计算机基础题目。考前准备的知识点中有,多注意一下电脑信息也能知道。WMV、MPEG、AVI是视频格式,JPEG是图像格式。

3. 二进制数11 1011 1001 0111 和 01 0110 1110 1011 进行逻辑或运算的结果是( )

A.11 1111 1111 1101          B.11 1111 1111 1101

C.10 1111 1111 1111          D.11 1111 1111 1111

答案:D

题目分析:考前单独强调总结的知识点中有位运算的内容。逐位做或运算,两个数字中有一个1即得1,选D。

11 1011 1001 0111

01 0110 1110 1011

11 1111 1111 1111

4.编译器的功能是( )

A.将源程序重新组合

B.将一种语言(通常是高级语言)翻译成另一种语言(通常是低级语言)

C.将低级语言翻译成高级语言

D.将一种编程语言翻译成自然语言

答案:B

题目分析:编译成计算机能够理解的语言,计算机识别二进制0和1。编译器的主要工作流程:源代码 → 编译 → 目标代码 → 链接(dll库等) → 生成可执行程序 。

5.设变量x为float型且已赋值,则以下语句中能将x中的数值保留到小数点后两位,并将第三位四舍五入的是( )

A.X=(x*100+0.5)/100.0          B.x=(int)(x*100+0.5)/100.0;

C.x=(x/100+0.5)*100.0          D.x=x*100+0.5/100.0;

答案:B

题目分析:类型转换题目,强制转换,比较简单,课堂练习过。B选项。

也可以假设x=3.141,然后带入计算:

(int)(3.141*100+0.5)/100.0

= (int)(314.1+0.5)/100.0

= (int)(314.6)/100.0

= 314/100

= 3.14

6. 由数字1,1,2,4,8,8所组成的不同的4位数的个数是( )

A.104          B.102          C.98          D.100

答案:B

题目分析:排列组合题,最后专项讲解中有类似的。

不能直接A(6,4),要分情况讨论:

(1)只有2个相同的数构成的4位数,1、1、2、4;1、1、2、8;1、1、4、8;1、2、8、8;1、4、8、8;2、4、8、8组成。

每种有A(4,4)/A(2,2)=4×3=12(种)

共有12×6=72种.

(2)4个不同的数构成,只有1、2、4、8组成,有A(4,4)=4×3×2×1=24(种)

(3)2个重复的数字构成,只有1、1、8、8,有C(4,2)=6(种)

所以,共有72+24+6=102(种)

7.排序的算法很多,若按排序的稳定性和不稳定性分类,则( )是不稳定排序。

A.冒泡排序          B.直接插入排序          C.快速排序          D.归并排序

答案:C

题目分析:上课和复习时讲过。选择排序、快速排序、希尔排序、堆排序不是稳定的排序算法,而冒泡排序、插入排序、归并排序和基数排序是稳定的排序算法。

8. G是一个非连通无向图(没有重边和自环),共有28条边,则该图至少有( )个顶点

A.10          B.9          C.11          D.8

答案:B

题目分析:图的知识点。前几天练习的题有相似的。也可以验证答案。题目要求:没有自环,而且是非连通图。一个n 阶的完全无向图含有n*(n-1)/2 条边,n=8的时候是8*7/2=28,意味着8个顶点最多有28条边,第9个点可以单独存在,不连通,可满足条件。

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

A.40          B.25          C.30          D.20

答案:B

题目分析:排列组合题。枚举每位数字的可能性。颠倒后还得是个数字,因此前2位有0,1,8,6,9,5种选择,第3位只能放0,1,8,后2位由前2位决定。而0,1,8模3正好余0,1,2,所以给定其他4位,第3位有且仅有1种选择,总数=5*5*1*1*1=25。

10.一次期末考试,某班有15人数学得满分,有12人语文得满分,并且有4人语、数都是满分,那么这个班至少有一门得满分的同学有多少人?( )

A.23          B.21          C.20          D.22

答案:A

题目分析:容斥原理,初赛课和冲刺课都讲过。总满分人数=数学满分+语文满分-语文数学满分=15+12-4=23。

11.设A和B是两个长为n的有序数组,现在需要将A和B合并成一个排好序的数组,请问任何以元素比较作为基本运算的归并算法,在最坏情况下至少要做多少次比较?( )

A.n²           B.n㏒n          C.2n          D.2n-1

答案:D

题目分析:往年考过。也可枚举n=1,一共2个数字,只需要比较1次,AD中选,n=2再验证……

12.以下哪个结构可以用来存储图( )

A.栈          B.二叉树          C.队列          D.邻接矩阵

答案:D

题目分析:可用排除法,讲过数据结构的分类。

13.以下哪些算法不属于贪心算法?( )

A.Di.jkstra算法          B.Floyd算法

C.Prim算法          D.Kruskal算法

答案:B

题目分析:提高组课上讲过。Floyd是枚举所有情况。

14.有一个等比数列,共有奇数项,其中第一项和最后一项分别是2和118098,中间一项是486,请问一下哪个数是可能的公比?( )

A.5          B.3          C.4          D.2

答案:B

题目分析:可以枚举答案。等比数列,首项是2,公比是5,末项不可能是118098;

公比是4,486%4!=0;公比是2,可演算2的n次方不是118098。排除法,选B。

15.有正实数构成的数字三角形排列形式如图所示。第一行的数为a1,1,第二行a2,1,a2,2,第n行的数为an,1,an,2,…,an,n。从a1,1开始,每一行的数ai,j只有两条边可以分别通向下一行的两个数ai+1,j和ai+1,j+1。用动态规划算法找出一条从a1,1向下通道an,1,an,2,…,an,n中某个数的路径,使得该路径上的数之和最大。

真题解析Ⅱ | CCF CSP-S 2019 提高级 C++语言真题及答案

令C[i][j]是从a1,1到ai,j的路径上的数的最大和,并且C[i][0]= C[0][j]=0,则C[i][j]=( )

A.max{C[i-1][j-1],C[i-1][j]}+ ai,j

B.C[i-1][j-1]+C[i-1][j]

C.max{C[i-1][j-1],c[i-1][j]}+1

D.max{C[i][j-1],C[i-1][j]}+ ai,j

答案:A

题目分析:dp基础题:数塔,基础讲过,路径只能从左上方和上方过来。

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

1.

真题解析Ⅱ | CCF CSP-S 2019 提高级 C++语言真题及答案

概述:基础题,大家模拟即可,可以带入几组数据执行。例如:

5

1 2 3 4 5

判断题

1)(1分)第16行输出ans时,ans的值一定大于i。( )

答案:×

题目分析:第一次输出,ans=i。(猜题小技巧:说“一定”的,很可能错。)

2) 1分)程序输出的ans小于等于n。( )

答案:√

题目分析:13行i<=n,15行ans<n才会自增,所以不会超过n。

3)若将第12行的“<”改为“!=”,程序输出的结果不会改变。( )

答案:√

题目分析:最后结果不变。

4)当程序执行到第16行时,若ans-i>2,则a[i+1]≦a[i]。( )

答案:√

题目分析:14行,由于ans是第一个大于a[i]的,所以a[i+1]..a[ans-1]都不超过a[i],结论成立。

5)(3分)若输入的a数组是一个严格单调递增的数列,此程序的时间复杂度是( )。

A.0(logn)          B.0(n2)

C.0(nlog n)          D. 0(n)

答案:D

题目分析:根据举例,单调增,复杂度为O(n)

6)最坏情况下,此程序的时间复杂度是( )。

A. 0(n2)          B. 0(logn)

C. 0(n)            D. 0(nlog n)

答案:A

题目分析:最坏情况下,while循环会一直执行n,复杂度为1+2+..+n=O(n^2)

2.

真题解析Ⅱ | CCF CSP-S 2019 提高级 C++语言真题及答案

分析:getroot函数是并查集中的find函数啊。下面就好办了。

判断题

1)(1分)输入的a和b值应在[0,n-1]的范围内。( )

答案:√

题目分析:找a、b的根结点,下标范围为0到n-1,所以a、b范围也在0到n-1。

2) (1分)第16行改成“fa[i]=0;”, 不影响程序运行结果。( )

答案:×

题目分析:初始化,标准写法。

3) 若输入的a和b值均在[0, n-1]的范围内,则对于任意0≤i<n,都有0≤fa[i]<n。( )

答案:√

题目分析:并查集知识。

4) 若输入的a和b值均在[0,n-1]的范围内,则对于任意≤i<n,都有≤cnt[i] ≤n。( )

答案:×

题目分析:cnt表示集合数量。

选择题

5)当n等于50时,若a、b的值都在[0,49]的范围内,且在第25行时总是不等于y,那么输出为( )

A.1276          B.1176          C.1225          D.1250

答案:C

题目分析:x和y都不同,每次都是单独一个去和整体合并。此时cnt[y]增加cnt[x]的值,也就是加1。1*1+1*2+...1*49=50*49/2=1225。

6)此程序的时间复杂度是( )

A. O(n)          B. O(logn)          C. O(n)          D. O(nlogn)

答案:C

题目分析:并查集getroot函数没有路径压缩,单次查找最坏为O(n)。总效率为O(n^2)。

3.本题t是s的子序列的意思是:从s中删去若干个字符,可以得到t;特别的,如果s=t,那么t也是s的子序列;空串是任何串的子序列。例如“acd”是“abcde”的子序列,“acd”是“acd”的子序列,但“acd”不是“abcde”的子序列。

s[x..y]表示s[x]…s[y]共y-x+1个字符构成的字符串,若x>y则s[x..y]是空串。t[x..y]同理。

真题解析Ⅱ | CCF CSP-S 2019 提高级 C++语言真题及答案

注意:是子序列,而不是子串。可以举例输入两个字符串,进行验证,即可模拟出pre数组和suf数组的内容。Pre数组保存的是前面匹配了多少个字符,suf保存的是从后面比较匹配了多少个字符。ans是匹配字符之间的距离最大值。

例如 abca ac

判断题

1.(1分)程序输出时,suf数组满足:对任意0≤i<slen,suf[i] ≤suf[i+1].( )

答案:√

题目分析:15到19行程序中,循环变量初值是从大到小,从最后一个位置开始判断,可以得出该结论。

2. (2分) 当t是s的子序列时,输出一定不为0.( )

答案:×

题目分析:如果s==t时,结果是0。

3.(2分)程序运行到第23行时,“j-i-1”一定不小于0.( )

答案:×

题目分析:这个不一定,如果22行条件不成立,j=i=0,j-i-1就可能是负数。

4 (2分)当t时s的子序列时,pre数组和suf数组满足:对任意0≤i<slen,pre[i]>suf[i+1]+1.( )

答案:×

题目分析:这个不一定。如果t==s='cc'代入检验,有的i可以pre[i]==suf[i+1]+1。

选择题

5.若tlen=10,输出为0,则slen最小为( )

A. 10          B. 12          C.0          D.1

答案:D

题目分析:求的是最小可能的长度。s的长度为1的时候,t=10,是空串,输出是0。

6.若tlen=10,输出为2,则slen最小为( )

A. 0          B.10          C.12          D.1

答案:C

题目分析:输出是2说明存在子序列。s串删去两个元素后至少为10,因此删前至少为12。

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

1.(匠人的自我修养)一个匠人决定要学习n个新技术,要想成功学习一个新技术,他不仅要拥有一定的经验值,而且还必须要先学会若干个相关的技术。学会一个新技术之后,他的经验值会增加一个对应的值。给定每个技术的学习条件和习得后获得的经验值,给定他已有的经验值,请问他最多能学会多少个新技术。

输入第一行有两个数,分别为新技术个数n(1≤n≤10³),以及已有经验值(≤10^7)。

接下来n行。第i行的两个整数,分别表示学习第i个技术所需的最低经验值(≤10^7),以及学会第i个技术后可获得的经验值(≤10^4)。

接下来n行。第i行的第一个数mi(0≤mi<n),表示第i个技术的相关技术数量。紧跟着m个两两不同的数,表示第i个技术的相关技术编号,输出最多能学会的新技术个数。

下面的程序已O(n^2)的时间复杂完成这个问题,试补全程序。

真题解析Ⅱ | CCF CSP-S 2019 提高级 C++语言真题及答案

分析:学技术有先后,经验值还得够,根据已有的经验值选择新技术,也可以用有向图分析理解。可以用二维数组实现。n小于1000。

1) ①处应填( )

A. unlock[i]<=0

B. unlock[i]>=0

C. unlock[i]==0

D. unlock[i]==-1

答案:C

试题分析:学习新技术的条件之一。unlock判断是否能解锁任务。解锁条件是需要0个前提任务。

2) ②处应填( )

A. threshold[i]>points

B. threshold[i]>=points

C. points>threshold[i]

D. points>=threshold[i]

答案:D

试题分析:学习新技术的条件之一。,经验点要够,大于等于任务的需求点。

3) ③处应填( )

A. target = -1

B. --cnt[target]

C. bbonus[target]

D. points += bonus[target]

答案:D

题目分析:经验点增加。条件都满足,可以学习新技术了。

4) ④处应填( )

A. cnt [child[target][i]] -=1

B. cnt [child[target][i]] =0

C. unlock[child[target][i]] -= 1

D. unlock[child[target][i]] =0

答案:C

题目分析:学习下一个技术需要解锁的任务数,解锁一个任务,unlock值都要减1。

5) ⑤处应填( )

A. unlock[i] = cnt[i]

B. unlock[i] =m

C. unlock[i] = 0

D. unlock[i] =-1

答案:B

题目分析:“开门”阶段,读入信息,由题意可知,m是任务依赖的任务数,当unlock[i]为-1时表示解锁成功。其他选项没有意义。

2.(取石子) Alice和Bob两个人在玩取石子游戏,他们制定了n条取石子的规则,第i条规则为:如果剩余的石子个数大于等于a[i]且大于等于b[i],那么她们可以取走b[i]个石子。他们轮流取石子。如果轮到某个人取石子,而她们无法按照任何规则取走石子,那么他就输了,一开始石子有m个。请问先取石子的人是否有必胜的方法?

输入第一行有两个正整数,分别为规则个数n(1≤n≤64),以及石子个数m(≤10^7)。

接下来n行。第i行有两个正整数a[i]和b[i]。(1≤a[i]≤10^7,1b[i]≤64)

如果先取石子的人必胜,那么输出“Win”,否则输出“Loss”。

提示:

可以使用动态规划解决这个问题。由于b[i]不超过64,所以可以使用位无符号整数去压缩必要的状态。

status是胜负状态的二进制压缩,trans是状态转移的二进制压缩。

试补全程序。

代码说明:

“~”表示二进制补码运算符,它将每个二进制位的0变成1、1变为0;

而“^”表示二进制异或运算符,它将两个参与运算的数重的每个对应的二进制位一一进行比较,若两个二进制位相同,则运算结果的对应二进制位为0,反之为1。

U11标识符表示它前面的数字是unsigned long long 类型。

真题解析Ⅱ | CCF CSP-S 2019 提高级 C++语言真题及答案

题目分析:博弈论类的问题,讲过。位运算,考前专门复习过。题目里说了,用动态规划实现,并且用位运算代替数组实现。

1)①处应填( )

A.0

B .~0ull

C.~0ull^1

D.1

答案:C

题目分析:根据题目要求,状态压缩到64位,A和D默认是32位整数,所以B或者C。最开始石子是0个,应该是输的状态,所以最低位不能是1,选C。

2)处应填( )

A.a[j]< i

B.a[j]==i

C.a[j] !=i

D.a[j] >i

答案:B

题目分析:n个条件范围内,符合题目要求的石子个数,即可发生状态转移,选B。并且根据代码,状态转移到trans变量。增加状态,位运算|实现加的功能,下一个选A。

3)③处应填( )

A. trans |= 1ull <<(b[j] - 1)

B. status |= 1ull << (b[j]- 1)

C. status += 1ull << (b[j]-1)

D. trans += 1ull<< (b[j]-1)

答案:A

4)④处应填( )

A. ~status|trans

B. status&trans

B. status|trans

D. ~status&trans

答案:D

题目分析:判断win的值。先手必胜,对当前状态和以前状态做判断。

5)⑤处应填( )

A. trans = status | trans ^win

B. status = trans >> 1^win

C. trans = status ^trans |win

D. status =status <<1^win

答案:D

更新status状态值,将当前win值记录到status中。

以上是2019CSP-S(提高级)C++语言题目的解题分析,参加此次考试的学员们,你们都答对了吗?另,关注童程童美微信公众号,后台回复【真题】即可免费领取“信息学奥赛历年真题资料包”哦~

童程童美微信公众号

CSP-J/S是CCF创办的CSP(软件能力认证)中面向非专业级的软件能力认证,也就是我们熟知的信息学奥赛,含金量高。

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