以下不属于面向对象程序设计语言的是（D）。

A. C++

B. Python

C. Java

D. C

c语言是一种面向过程的计算机语言。

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

A. 16

B. 15

C. 17

D. 32

完全二叉树的形态等于完全二叉树的叶子节点。

在数据压缩编码中的哈夫曼编码方法，在本质上是一种（B）的策略。

A. 枚举

B. 贪心

C. 递归

D. 动态规划

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

A. 14

B. 15

C. 16

D. 17

ret表示转换成二进制数的x有多少个1，return x&-x表示二进制数的x最后一个一在几位。

判断题

输入的n等于 1001时，程序不会发生下标越界。(错误)

因为数组a只有1000，1001会导致越界。

输入的a[i]必须全为正整数，否则程序将陷入死循环。(错误)

a[i]是整型数组，当输入小数时，会自动变成整型数组。

当输入为 5 2 11 9 16 10 时，输出为 3 4 3 17 5。(错误)

当输入为 1 511998 时，输出为 18。(正确)

将源代码中 g 函数的定义（14∼17行）移到main 函数的后面，程序可以正常编译运行。(错误)

单选题

21. 当输入为 2 -65536 2147483647 时，输出为(B)。

A. 65532 33

B. 65552 32

C. 65535 34

D. 65554 33

判断题

输出的第二行一定是由小写字母、大写字母、数字和+、 /、=构成的字符串。(错误)

如果它的输出不在table和base里面，就会输出乱码。

可能存在输入不同，但输出的第二行相同的情形。(正确)

输出的第一行为 -1。(正确)

单选题

设输入字符串长度为n，decode函数的时间复杂度为(B)

A. O(sqrt(n))

B. O(n)

C. O(n log n)

D. $O(n^2)$

当输入为Y3Nx时，输出的第二行为(B)。

A. csp

B. csq

C. CSP

D. Csp

当输入为 Y2NmIDIwMjE=时，输出的第二行为(C)。

A. ccf2021

B. ccf2022

C. ccf 2021

D. ccf 2022

主要考察了线性筛的用法f求约数个数，g求约数之和。

假设输入的x是不超过1000的自然数，完成下面的判断题和单选题：

判断题

若输入不为1，把第13行删去不会影响输出的结果。(正确)

第25行的f[i] / c[i * k]可能存在无法整除而向下取整的情况。(错误)

在执行完 init() 后，f 数组不是单调递增的，但 g 数组是单调递增的。 (错误)

单选题

init 函数的时间复杂度为(A)。

A. O(n)

B. O(n log n)

C. O(sprt(n))

D. O($n^2$)

在执行完 init() 后，f[1],f[2],f[3]…f[100]中有(C)个等于2。

A. 23

B. 24

C. 25

D. 26

当输入为1000时，输出为(C)。

A. 15 1340

B. 15 2340

C. 16 2340

D. 16 1340

有n个人围成一个圈，依次标号0至n−1。从0号开始，依次0,1,0,1,…0,1,0,1,…交替报数，报到1的人会离开，直至圈中只剩下一个人。求最后剩下人的编号。

i是每一个人的编号，c是剩余的人数，p是判断它是0还是1。

①处应填(D)

A.i < n

B.c < n

C.i < n- 1

D.c < n-1

②处应填(C)

A.i % 2 == 0

B.i % 2 == 1

C.p

D.!p

③处应填(C)

A.i++

B.i = (i + 1) % n

C.c++

D.p ^= 1

④处应填(D)

A.i++

B.i = (i + 1) % n

C.c++

D.p ^= 1

⑤处应填(B)

A.i++

B.i = (i + 1) % n

C.c++

D.p ^= 1

平面上有n个关键点，求有多少个四条边都和x轴或者y轴平行的矩形，满足四个顶点都是关键点。给出的关键点可能有重复，但完全重合的矩形只计一 次。

①处应填(B)

A. a.x != b.x ? a.x < b.x : a.id < b.id

B. a.x != b.x ? a.x < b.x : a.y < b.y

C. equals(a, b) ? a.id < b.id : a.x < b.x

D. equals(a, b) ? a.id < b.id : (a.x != b.x ? a.x < b.x : a.y < b.y)

②处应填(D)

A. i == 0 || cmp(A[i], A[i - 1])

B. t == 0 || equals(A[i], A[t - 1])

C. i == 0 || !cmp(A[i], A[i - 1])

D. t == 0 || !equals(A[i], A[t - 1])

③处应填(C)

A. b - (b - a) / 2 + 1

B. a + b + 1) >> 1

C. (a + b) >> 1

D. a + (b - a + 1) / 2

④处应填(B)

A. !cmp(A[mid], p)

B. cmp(A[mid], p)

C. cmp(p, A[mid])

D. !cmp(p, A[mid])

⑤处应填(D)

A. A[i].x == A[j].x

B. A[i].id < A[j].id

C. A[i].x == A[j].x && A[i].id < A[j].id

D. A[i].x < A[j].x && A[i].y < A[j].y

知识点：

求约数个数

公式：

数字378000可以被分解成$2^4*3^3*5^3*7^1$。

378000的约数个数是(4+1)$*$(3+1)$*$(3+1)$*$(1+1)=160。

求约数之和

数字8分解成质因数后，是$2^3$

数字72的约数之和是

$2^0*2^1*2^2*2^3*2^0*3^1*2^1*3^1*2^2*3^1*2^3*3^1*2^0*3^2*2^1*3^2*2^2*3^2*2^3*3^2$

埃氏筛法

const int N = 1e6+5;
int primes[N], cnt;  // primes用来存储质数，cnt是对应数组的下标
bool st[N];  // st[i]标记数字是否被筛掉

void get_primes(int n) {
	// 筛选 2~n中的所有质数
	for (int i=2; i<=n; i++) {
		if (!st[i]) {
			primes[++cnt] = i;  // 质数存到数组中
			for (int j=i+i; j<=n; j+=i) st[j] = 1;  // 筛掉质数的倍数
		}
	}
	// 这样过完之后，所有的质数就存到了primes数组中
	// 同时 st 中标记了每个数字是否是质数。
}

欧拉筛法

void get_primes(int n) {
	// 筛选 2~n中的所有质数
	for (int i=2; i<=n; i++) {
		if (!st[i]) primes[++cnt] = i;  // 质数存到数组中
			// primes[j] <= n/i 理解为 primes[j]*i <= n，即只筛n范围内的数字
			for (int j=1; primes[j]<=n/i; j++) {
				st[primes[j]*i] = 1;  // 筛掉i的素数倍数
				if (i%primes[j] == 0) break;  // 线性复杂度的关键
			}
	}
}