CSP-J-2021真题
以下不属于面向对象程序设计语言的是（ ）。
C++
Python
Java
C
以下奖项与计算机领域最相关的是（ ）。
奥斯卡奖
图灵奖
诺贝尔奖
普利策奖
目前主流的计算机储存数据最终都是转换成（ ）数据进行储存。
二进制
十进制
八进制
十六进制
以比较作为基本运算，在 N 个数中找出最大数，最坏情况下所需要的最少的比较次数为 （ ）
N^2
N
N-1
N+1
对于入栈顺序为 a, b, c, d, e 的序列，下列（ ）不是合法的出栈序列。
a, b, c, d, e
e, d, c, b, a
b, a, c, d, e
c, d, a, e, b
对于有 n 个顶点、m 条边的无向连通图 (m>n)，需要删掉（ ）条边才能使其成为一棵 树。
n-1
m-n
m-n-1
m-n+1
二进制数 101.11 对应的十进制数是（ ）。
6.5
5.5
5.75
5.25
如果一棵二叉树只有根结点，那么这棵二叉树高度为 1。请问高度为 5 的完全二叉树有 （ ）种不同的形态？
16
15
17
32
表达式 a*(b+c)*d 的后缀表达式为( )，其中“*”和“+”是运算符。
**a+bcd
abc+*d*
abc+d**
*a*+bcd
6 个人，两个人组一队，总共组成三队，不区分队伍的编号。不同的组队情况有（ ） 种
10
15
30
20
在数据压缩编码中的哈夫曼编码方法，在本质上是一种（ ）的策略。
枚举
贪心
递归
动态规划
由 1，1，2，2，3 这五个数字组成不同的三位数有（ ）种。
18
15
12
24
考虑如下递归算法
solve(n) if n<=1 return 1 else if n>=5 return n*solve(n-2) else return n*solve(n-1)
则调用solve(7)得到的返回结果为（）。
105
840
210
420
以a为起点，对右边的无向图进行深度优先遍历，则b,c,d,e四个点中有可能作为最后一个遍历到的点的个数为（）。
1
2
3
4
有四个人要从A点坐一条船过河到B点，船一开始在A点。该船一次最多可坐两个人。已知这四个人中每个人独自坐船的过河时间分别为1，2，4，8，且两个人坐船的过河时间为两人独自过河时间的较大者。则最短（）时间可以让四个人过河到B点（包括从B点把船开回A点的时间）。
14
15
16
17
阅读程序 回答下列问题
第1题 判断
输入的n等于1001时，程序不会发生下标越界。这句话描述是否正确？
第2题 判断
输入的a[i]必须全为正整数，否则程序将陷入死循环。这句话的描述是否正确？
第3题 判断
当输入为“5 2 11 9 16 10”时，输出为“3 4 3 17 5”。这句话的描述是否正确？
第4题 判断
当输入为“1 511998”时，输出为“18”。这句话的描述是否正确？
第5题 判断
将源代码中g函数的定义（13-16行）移到main函数的后面，程序可以正常编译运行。这句话的描述是否正确？
第6题 单选
当输入为“2 -65536 2147483647”时，输出为（）
"65532 33"
"65552 32"
"65535 34"
"65554 33"
阅读程序完成以下问题
第1题 判断
输出的第二行一定是由小写字母、大写字母、数字和“+”、“/”、“=”构成的字符串。这句话的描述是否正确？
第2题 判断
可能存在输入不同，但输出的第二行相同的情形。这句话的描述是否正确？
第3题 判断
输出的第一行为“-1”。这句话的描述是否正确？
第4题 单选
设输入字符串长度为n，decode函数的时间复杂度为（）
第5题 单选
当输入为“Y3Nx”时，输出的第二行为（）
“csp”
“csq”
“CSP”
“Csp”
第6题 单选
当输入为“Y2NmIDIwMjE=”时，输出的第二行为（）
“ccf2021”
“ccf2022”
“ccf 2021”
“ccf 2022”
完善程序
第1题 单选
①处填（ ）
i<n
c<n
i<n-1
c<n-1
第2题 单选
②处填（ ）
i%2==0
i%2==1
p
!p
第3题 单选
③处填（ ）
i++
i=(i+1)%n
c++
p^=1
第4题 单选
④处填（）
i++
i=(i+1)%n
c++
p^=1
第5题 单选
⑤处填（ ）
i++
i=(i+1)%n
c++
p^=1
二）
（矩形计数）平面上有n个关键点，求有多少个四条边都和x轴或者y轴平行的矩形，满足四个顶点都是关键点。给出的关键点可能有重复，但完全重合的矩形只计一次。
试补全枚举算法。
第1题 单选
①处应填（）
a.x != b.x ? a.x < b.x : a.id < b.id
a.x != b.x ? a.x < b.x : a.y< b.y
equals(a,b) ? a.id<b.id:a.x<b.x
equals(a,b) ? a.id<b.id: (a.x != b.x ? a.x < b.x : a.y< b.y)
第2题 单选
②处应填（）
i == 0 || cmp(A[i], A[i - 1])
t == 0 || equals(A[i], A[t - 1])
i == 0 || !cmp(A[i], A[i - 1])
t == 0 || !equals(A[i], A[t -1])
第3题 单选
③处应填（）
b – (b – a) / 2 + 1
(a + b + 1) >> 1
(a + b) >> 1
a + (b – a + 1) / 2
第4题 单选
④处应填（）
!cmp(A[mid], p)
cmp(A[mid], p)
cmp(p, A[mid])
!cmp(p, A[mid])
第5题 单选
⑤处应填（）
A[i].x == A[j].x
A[i].id < A[j].id
A[i].x == A[j].x && A[i].id < A[j].id
A[i].x<A[j].x && A[i].y < A[j].y