2019CCF非专业级别软件能力认证第一轮认证
入门级（CSP-J）参考答案
一、单项选择题（共15题，每题2分，共计30分）
12345678910
A D C A A D C C
B C
1112131415
C A C B A
二、阅读程序（共3题，除特殊说明外，判断题  1.5分，选择题3分，共计40分）
1.×，√，×，√，B，B
2.√，×，×，×，A，A
3.×，√，A，D，D，B
三、完善程序（共10题，每题3分，共计30分）
第1题第2题1234512345 C D B B B B D C A B
【解析】
一、单项选择题
1.常识题，中国国家顶级域名为。
2.考查二进制的基本运算。按位与的操作是对二进制每一位对应做与，两个数这一位都是1，结果才是1。
3.一个字节包含8位二进制数，故应该占4字节。
4.分析过程可以知道，s先被赋值成了a又减掉了c个1，所以就是a-c。
5.比100大的最小的二的次方是128，是27，所以需要7次。
6.链表只能顺序查元素，不能实现随机访问。
7.为了避免重复，我们可以设后边的袋子装的不比前边多，把所有情况列出来即可，共18种。
8.下标最大的一个结点是最右下方的结点，下标为2*(2*(2*1+1)+1)+1= 15。
9.可以通过从大到小枚举每个数验证得知100以内最大素数为97。
10.可以通过试除的方法算出这两个数的最大公约数是29。
11.连续跑5公里肯定是更好的，所以就在周五到周日3天跑5公里，周一到周四中选2天跑3公里即可。
12.根据鸽巢原理，最平均的分法就是每种花先有3张，此时最后一张无论是什么花都会导致有4张牌花一致。
13.只需要考虑前3位，后2位是必须根据前边对应过来的，前两位取这5个数都可以，中间那一位只能取0、1、8，所以总共5*5*3=75个。
14.根据后序遍历当前子树的根，根据中序遍历再把当前子树拆成左右子树，递归建树，然后进行前序遍历。
15.计算机科学领域的最高奖为图灵奖。
二、问题求解
1.分析程序过程可以发现，该程序将所有i为n的约数的位置的小写字母都转化为了大写字母。
判断题：
(1)错误，因为字符串包含的字符不仅仅可以是字母。
(2)正确，如果i的初值为0的话，在n%i==0和st[i-1]处都会出错。
(3)错误，n的约数是有可能大于sqrt(n)的。
(4)正确，大写字母的ASCII值都比小写字母小，因此不会发生任何改变。
选择题：
(5)18拥有6个因数：1，2，3，6，9，18。
(6)若想有36个不同，那么这个数字必须至少有36个因数。100000=25∗55,5+1∗5+1=36。
2.判断题：
(1)正确，此时一定至少有一个位置被赋值成了非0数。
(2)错误，如果m=1且输入“15”，当i=1时，++ans后值为1，是奇数。
(3)错误，如果m=1且输入了“11”后a[1]=b[1]=1>0。
(4)错误，第15行是否执行与x和y的大小关系无关。
反例：
32
12
13
选择题：
(5)每次操作一定会把两个0变成非负数，所以答案为2n-2m。
(6)除了第一次进入if后之后的进入就会发现因为x两两不同，所以a[x]肯定为0，但是b[y]记录的上一次进入时候的x的值，就相当于把上次的a[x]置零，然后再是修改，能够发现本质上非零的个数还是没变。
3.判断题：
(1)错误，有相等的数字是不会对程序有影响的。
(2)正确，每次函数返回值的时候都有depth*b[mink]但是因为b数组全为0所以返回的每一个值都是0。
选择题：
(3)最坏情况下，每次到的都恰好是最前边的或者每次到的都恰好是最后边的，那么总体复杂度会达到O(n2)级别。
(4)最好情况下，每次都能够二分整个区间，复杂度就会达到O(nlogn)级别。
(5)想要值最大，就应该让大数的深度尽可能大，最好的策略就是a按照递增顺序，这样每次分割都会只去掉最前面一个数字。
(6)每一次都是二分，可以算出从浅到深每层的数量是1,2,4,8,16,32,37，乘上深度加起来即可。
三、阅读程序写结果
1.递归到这一个位置的情况，那就直接赋值成应该的数。
2.左上部分的左上角坐标就是（x，y）。
3.右下部分的左上角坐标是（x+step，y+step）。
4.分析功能可知，后两个参数应该为递归深度以及左上角的数值，也就依次是n，0。
5.分析可知最终矩阵的大小应该为2n，也就是（1<<n）。
6.此处实现的功能应该为统计b[i]的数量。
7.此时实现的功能为按b排序，记录位置。
8.此处实现的功能应该为统计a[i]的数量。
9.此处实现的功能应该为按a排序放好记录好每个位置放的是原来的第几个数。
10.此处实现的功能应该为到排好序以后是对应的原来的第几个数。
2019CCF非专业级别软件能力认证第一轮认证
提高级（CSP-S）参考答案
一、单项选择题（共15题，每题2分，共计30分）
12345678910
D C D B B B C B B A
1112131415
D D B B A
二、阅读程序（共3题，除特殊说明外，判断题  1.5分，选择题3分，共计40分）
1.×，√，√，√，D，A
2.√，×，√，×，C，C
3.√，×，×，×，D，C
三、完善程序（共10题，每题3分，共计30分）
第1题第2题1234512345
C D D C B C B A D D
【解析】
一、单项选择题
1.(int)(x+y)=(int)7.2=7，式子等于
2.5+7%3*7%2，右式从左到右算，所以是答案
3.5。
2.考查计算机基础知识，WMV，MPEG，AVI均为视频文件格式，而JPEG是图像文件。
3.考查位运算的基本知识，按位依次做或运算即可。
4.编译器的作用是将一种语言（通常是高级语言）翻译成另一种语言（通常是低级语言），这是编译器的功能。
5.其它选项都没有强制转换类型操作，也就意味着数值不会发生变化。如果x小数点后三位大于5，加上0.5再截断取整，就会进1（五入），否则会舍掉小数部分（四舍）。
6.可以按照包含的数字分类讨论：包含1248的有P44=24种，1188的有P44P22∗P22=6种，
11xx和88xx(xx为2，4，8中任意两种)的有C32∗P44P22=36种。
7.考查排序算法的基本知识，冒泡排序，直接插入排序和归并排序都属于稳定排序，稳定排序的定义是排序后值相同的元素的相对位置不会发生变化，而快速排序属于不稳定排序。
8.考查图论的基本知识，8个点的完全图的边数为8*7/2=28条，而如果想让图不连通，至少还需要额外加一个点，故至少有9个点。
9.首先本题只需考虑由0，1，8，6，9构成的五位数，如果一个数是3的倍数，那么它的数位之和一定也是3的倍数。同时由于本题的特殊性质，只需确定前三位就能够确定这么一个数字。那么我们按照第三位的情况分类讨论：
如果第3位数是0，那么第一位+第二位对3取模的余数必须为0，合法的组合共有11种。(00,99,66,09,90,69,96,06,60,18,81)
如果第3位数是1，那么第一位+第二位对3取模的余数必须为1，合法的组合共有7种。(10,01,16,61,19,91,88)。
如果第3位数是8，那么第一位+第二位对3取模的余数必须为2，合法的组合共有7种。(80,08,86,68,89,98,11)。
综上所述，总共有25种。
10.由容斥原理可以得知，答案为15+12-4=23。
11.归并算法的原理是：比较当前的Ai和Bi，如果Ai更小，则放入Ai，否则放入Bi。如果某个数组为空的话，就把这个数组里的所有元素直接顺次放入新数组，而不需要进行任何比较。因此，如果想使得比较次数尽可能地大，就需要构造两个数组，使得算法运行到最后一个数组为空时另一个数组剩余的元素尽可能少，而最少可以为1。那么在这种情况下，除了最后一个元素没有被比较以外，其余每一个元素被放入新数组之前都进行了一次比较，故答案为2*n-1。
12.邻接矩阵和邻接表都是常用的表示图的数据结构。
13.Floyd算法属于动态规划。其它三个算法多多少少都有涉及到贪心的思想。
14.4862=243，118098486=243，243=35，所以选项只有3符合要求。
15.本题考查动态规划的基本知识，为了计算走到当前位置花费，需要枚举从哪里走到当前位置，也就是从两种走法中取一个最大的。随后需要加上当前位置的权值以表示走到当前位置用的代价。
二、问题求解
1.分析程序过程可以发现，该程序对于每一个下标i求出了一个ans，表示a[i]到a[ans]之间的数字都不大于a[i]并且a[ans+1]大于a[i]。
判断题：
(1)错误，考虑一个递增的数组，每一个ans都等于i。
(2)正确，因为有ans<n这一条件，所以一定会小于等于n。
(3)正确，事实上即使没有12行的条件判断，而每次都将ans的初值设置为i的话，答案不会发生变化。12行的判断实际上是一种优化：如果当前位置的值不小于上一个值的话，那么求出的ans一定不小于上一个求出的ans。所以只需要在当前值比上一个值小的时候再从i开始枚举。字符串长度1是什么意思
(4)正确，ans比i更大，说明从i到ans中间的每一个数都不大于a[i]。
选择题：
(5)如果严格单调递增，那么14行的while循环永远不会进入，故复杂度就是O(n)。
(6)考虑一个严格递减的序列，它永远满足12行的条件，因此每次的ans都被设置为i，但是每次while循环都会循环到序列结束，故这种情况下复杂度为O(n2)。
2.分析程序过程，fa数组和getRoot函数构成了并查集的基本操作，cnt表示的应该是并查集集合内点的个数。但是需要注意的是，主函数内对两个集合的合并操作并没有特判两个点本来就属于同一集合的情况。
判断题：
(1)正确，并查集初始化的范围是[0,n-1]，所以点的范围也应该如此。
(2)错误，这一步对应的是并查集的初始化操作，必须将fa[i]初始化为i。
(3)正确，fa数组的意义是该集合的祖先对应的点，对应的正好是点的范围。
(4)错误，虽然cnt数组的意义是集合的大小，但合并时由于没有判定两个点本来就属于同一集合的情况，如果两个点来自相同的集合，也会执行一次合并操作，并导致cnt数组计算出现重复！
选择题：
(5)每次都是选择两个不同集合的根节点进行合并，我们对于每一个点进行计数，每个点都会产生n-1=49的贡献（因为25行的计数相当于一个集合的每个点都累计上另一个集合的点的个数的贡献），一共有n=50个点，而且每一对节点的贡献被重复计算了一次，所以答
案为50∗492=1225。
(6)这是一个没有路径压缩的并查集，所以整体复杂度可以达到O(n2)。
3.
判断题：
(1)正确，可知suf[i]的含义是求出s[i…slen-1]字符串最多能从右向左匹配到t字符串（子序列匹配）的长度。所以suf[i]从右向左一定是非严格递减的。此外，从代码中也可以看出，第17行suf[i]=j，j是没有增加操作的，也可以得出suf数组从右向左是递减的。
(2)错误，代入相等的两个串，如abc和abc，可以发现输出为0。
(3)错误，带入aaaa和bbbb，发现不满足条件。
(4)错误，在i=slen-1的时候不满足条件。
选择题：
(5)s串的长度此时至少为1，长度为0时会输入不进去。
(6)输出为2，证明最多可以删掉连续的两个字符还会使t是s的子序列。S如果长度小于等于11肯定不可以，因为删掉两个数字长度就小于10了，t的长度为10，不可能是s的子串，12是可以的，例如s=“aaaaaaaabbaa”,t=“aaaaaaaaaa”。
三、阅读程序写结果
一：本题的关键在于find函数，它的基本流程类似于拓扑排序：到一个入度为0并且能够选取的技术，然后从DAG上删除这个技术，unlock维护的就是每一个技术的度数。
1.此处说明当前技术可学，也就是没有未学完的前置技术，所以应该为unlock[i]==0。unlock[i]<=0不可以的原因是会把unlock[i]==-1的点再处理一次，是不对的，因为这份代码里unlock[i]==-1的含义是处理过了。
2.另一个当前技术可学的前提就是当前得分达到了相关技术的门槛。
3.如果能学这个技术了，肯定要学掉，获得对应的经验值。
4.该语句的意思是，当前技术如果被学掉了，相当于它作为先修技能的技术都少了一个先修技能，也就是把unlock值都减去1。
5.因为unlock[i]需要初始化为i技能所需的先修技能的个数，即这里输入的m。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。