2021年 中小学信息学奥赛CSP-J真题解析

1、以下不属于面向对象程序设计语言的是

A、c++

B、python

C、java

D、c

答案：D

考点分析：主要考查编程语言，ABC都是面向对象语言，D选项c语言是面向过程语言，答案D

2、以下奖项与计算机领域最相关的是

A、奥斯卡讲

B、图灵奖

C、诺贝尔奖

D、普利策奖

答案：B

考点分析：主要考查名人名言，图灵奖是由ACM颁发的以纪念计算机科学奠基人之一艾伦·麦席森·图灵（Alan Mathison Turing）的奖项。这个奖项是计算机科学领域最高荣誉之一，旨在表彰对计算机科学做出杰出贡献的个人或团队；答案B

3、目前主流的计算机储存数据最终都是转换成()数据进行储存

A、二进制

B、十进制

C、八进制

D、十六进制

答案：A

考点分析：主要考查计算机相关知识，计算机存储的数据都是以二进制方式进行存储的，答案A

4、以比较作为基本运算，在 N 个数中找出最大数，最坏情况下所需要的最少的比较次数为

A、

B、N

C、N-1

D、N+1

答案：C

考点分析：主要考逻辑思维推理能力，题目告知最坏情况，以第一个数作为初始值，从第二个数开始比较，最坏情况下需要比较到序列末尾才能得到最大值，即比较N-1；答案C

5、对于入栈顺序为 a,b,c,d,e的序列，下列()不是合法的出栈序列

A、a, b, c, d,e

B、e, d, c, b,a

C、b, a, c, d,e

D、c, d, a, e, b

答案：D

考点分析：主要考查栈的相关知识，栈要遵循先进后出的原则，D选项中a先进入，b也进入了不可能a先出来，答案D

6、对于有 n 个顶点、m 条边的无向连通图(m>n)，需要删掉()条边才能使其成为一棵树。

A、n-1

B、m-n

C、m-n-1

D、m-n+1

答案：D

考点分析：主要考查树和图相关知识，n个节点的树有n-1条边，则需要留下n-1条边，即需要删除m-(n1)条边；答案D

7、二进制数 101.11 对应的十进制数是

A、6.5

B、5.5

C、5.75

D、5.25

答案：C

考点分析：主要考查进制转换，整数部分为：，小数部分为：；答案C

8、如果一棵二叉树只有根结点，那么这棵二叉树高度为 1。请问高度为 5 的完全二叉树有()种不同的形态?

A、15

B、16

C、17

D、32

答案：B

考点分析：主要考查二叉树相关知识，一课深度为5的完全二叉树第5层最多有=16个节点，那么从左到右依次可以有连续k(1≤k≤16)个节点，一共有16种情况，答案B

9、表达式 a*(b+c)*d 的后缀表达式为( )，其中“*”和“+”是运算符

A、**a+bcd

B、abc+*d

C、abc+d**

D、*a*+bcd

答案：B

考点分析：主要考查二叉树的遍历，分先序遍历，中序遍历和后续遍历；这里的后缀表达式根后续遍历差不多，先左子树然后右子树最后根，答案B

10、6个人，两个人组一队，总共组成三队，不区分队伍的编号。不同的组队情况有（）种

A、10

B、15

C、30

D、20

答案：B

考点分析：主要考查小朋友们的排列组合相关知识，第一组有C(6,2)=15种，第二组有C(4,2)=6种，第三组C(2,2)=1，共有15*6*1=90种；但这是有分队伍编号，题目要求不分队伍编号，所以还需要除以3的排列A(3,3)=6，也就是90/6=15，答案B

11、在数据压缩编码中的哈夫曼编码方法，在本质上是一种 ()的策略

A、枚举

B、贪心

C、递归

D、动态规划

答案：B

考点分析：主要考查编码和算法相关知识，哈夫曼编码的原理是根据数据的频率或概率分配不同长度的编码，使得出现频率较高的数据拥有较短的编码，从而达到压缩数据的目的；这比较符合贪心算法的策略，答案B

12、由 1，1，2，2，3这五个数字组成不同的三位数有()种

A、12

B、15

C、18

D、24

答案：C

考点分析：主要考查排列组合相关知识

第一种情况：3是开头，十位和百位各有2种（1和2）取法也就是2*2=4

第二种情况：不是3开头，百位就是2种（1和2）取法，这里如果十位是多出来的另外一个数，个位就是3种（1、2和3）取法，也就是2*3=6

第三种情况：不是3开头，百位就是2种（1和2）取法，且十位不是多出来的另外一个数，十位就有2种（3和百位的数字）取法，个位也有2种（剩下的未取到的和十位剩下的那个数），也就是2*2*2=8；总共就有4+6+8=18种，答案C

13、考虑如下递归算法

solve(n)
if n<=1 return 1
else if n>=5 return n*solve(n-2)
else return n*solve(n-1)

则调用 solve(7)得到的返回结果为

A、105

B、210

C、420

D、840

答案：B

考点分析：主要考查递归函数的使用运行结果为：

solve(7)=7*solve(7 -2)

solve(5)=5*solve(5 -2)

solve(3)= 3*solve(3 -1)

solve(2)= 2*solve(2-1)

solve(1)= 1那么solve(7)=7*5*3*2*1=210，答案B

14、以 a为起点，对右边的无向图进行深度优先遍历，则b、c、d、e四个点中有可能作为最后一个遍历到的点的个数为()。

A、1

B、2

C、3

D、4

答案：B

考点分析：主要考查图的遍历，题目要求的是深度优先，所以有3条路线分别是：从a向b的方向开始搜索的终点是e(a-b-d-c-e),从a向c的方向开始搜索的终点是b(a-c-e-d-b)或c(a-c-d-b-e)，而最后的终点分为b和c，答案B

15、有四个人要从 A 点坐一条船过河到 B 点，船一开始在 A 点。该船一次最多可坐两个人。已知这四个人中每个人独自坐船的过河时间分别为1,2,4,8,且两个人坐船的过河时间为两人独自过河时间的较大者。则最短()时间可以让四个人都过河到 B 点(包括从B 点把船开回 A 点的时间)

A、14

B、15

C、16

D、17

答案：B

考点分析：主要考查小朋友们的逻辑思维推理能力，

1、先让1，2过去，1在回来，用时为：2+1=3；

2、再让4，8过去，2在回来，用时为：8+2=10；

3、最后1，2过去，用时为2；总共用时为：3+10+2=15，答案B