题目为截取历年真题，不涉及过难超纲的题目

一

01 #include <iostream>
02
03 using namespace std;
04
05 int main()
06 {
07     unsigned short x, y;
08     cin >> x >> y;
09     x = (x | x << 2) & 0x33;
10     x = (x | x << 1) & 0x55;
11     y = (y | y << 2) & 0x33;
12     y = (y | y << 1) & 0x55;
13     unsigned short z = x | y << 1;
14     cout << z << endl;
15     return 0;
16 }

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

1. 删去第 7 行与第 13 行的 unsigned ，程序行为不变。（ ） {{ select(1) }}

• 正确
• 错误

2. 将第 7 行与第 13 行的 short 均改为 char ，程序行为不变。（） {{ select(2) }}

• 正确
• 错误

3. 程序总是输出一个整数“ 0 ”。（ ） {{ select(3) }}

• 正确
• 错误

4. 当输入为“ 2 2 ”时，输出为“ 10 ”。（ ） {{ select(4) }}

• 正确
• 错误

5. 当输入为“ 2 2 ”时，输出为“ 59 ”。（ ） {{ select(5) }}

• 正确
• 错误

6. 当输入为“ 13 8 ”时，输出为。 {{ select(6) }}

• “ 0 ”
• “ 209 ”
• “ 197 ”
• “ 226 ”

二

01 #include <iostream>
02
03 using namespace std;
04
05 int n, k;
06
07 int solve1()
08 {
09     int l = 0, r = n;
10     while (l <= r) {
11         int mid = (l + r) / 2;
12         if (mid * mid <= n) l = mid + 1;
13         else r = mid - 1;
14     }
15     return l - 1;
16 }
17
18 double solve2(double x)
19 {
20     if (x == 0) return x;
21     for (int i = 0; i < k; i++)
22         x = (x + n / x) / 2;
23     return x;
24 }
25
26 int main()
27 {
28     cin >> n >> k;
29     double ans = solve2(solve1());
30     cout << ans << ' ' << (ans * ans == n) << endl;
31     return 0;
32 }

假设 int 为 32 位有符号整数类型，输入的 n 是不超过 47000 的自然数、 k 是不超过 int 表示范围的自然数，完成下面的判断题和单选题：

7. 该算法最准确的时间复杂度分析结果为 𝑂(log 𝑛 + 𝑘) 。（ ） {{ select(7) }}

• 正确
• 错误

8. 当输入为“ 9801 1 ”时，输出的第一个数为“ 99 ”。 （ ） {{ select(8) }}

• 正确
• 错误

9. 对于任意输入的 n ，随着所输入 k 的增大，输出的第二个数会变成“ 1 ”。 （ ） {{ select(9) }}

• 正确
• 错误

10. 该程序有存在缺陷。当输入的 n 过大时，第 12 行的乘法有可能溢出，因此应当将mid 强制转换为 64 位整数再计算。（ ）。 {{ select(10) }}

• 正确
• 错误

11. 当输入为“ 2 1 ”时，输出的第一个数最接近（）。

{{ select(11) }}

• 1
• 1.414
• 1.5
• 2

12. 当输入为“ 3 10 ”时，输出的第一个数最接近（）。

{{ select(12) }}

• 1.7
• 1.732
• 1.75
• 2

13. 当输入为“ 256 11 ”时，输出的第一个数（ ）。

{{ select(13) }}

• 等于16
• 接近但小于16
• 接近但大于16
• 前三种情况都有可能

三

14.输入的 n 等于 1001 时，程序 不会 发生下标越界。（ ） {{ select(14) }}

• 正确
• 错误

15.输入的 a[i] 必须全为正整数，否则程序将陷入死循环。（） {{ select(15) }}

• 正确
• 错误

16.当输入为“5 2 11 9 16 10”时，输出为“3 4 3 17 5”。（ ） {{ select(16) }}

• 正确
• 错误

17.当输入为“1 511998”时，输出为“18”。（ ） {{ select(17) }}

• 正确
• 错误

18.将源代码中 g 函数的定义（14-17 行）移到 main 函数的后面，程序可以正常编译运 行。（ ） {{ select(18) }}

• 正确
• 错误

19.当输入为“2 -65536 2147483647”时，输出为（ ）。 {{ select(19) }}

• “65532 33”
• “65552 32”
• “65535 34”
• “65554 33”

四

1 #include <cstdlib>
2 #include <iostream>
3 using namespace std;
4
5 char encoder[26] = {'C', 'S', 'P', 0};
6 char decoder[26];
7
8 string st;
9 int main()
10 {
11	int k = 0;
12	for (int i = 0; i < 26; ++i)
13		if (encoder[i] != 0)
14			++k;
15	for (char x = 'A'; x <= 'Z'; ++x)
16	{
17		bool flag = true;
18		for (int i = 0; i < 26; ++i)
19			if (encoder[i] == x)
20			{
21				flag = false;
22				break;
23			}
24		if (flag)
25		{
26			encoder[k] = x;
27			++k;
28		}
29	}
30	for (int i = 0; i < 26; ++i)
31		decoder[encoder[i] - 'A'] = i + 'A';
32	cin >> st;
33	for (int i = 0; i < st.length(); ++i)
34		st[i] = decoder[st[i] - 'A'];
35	cout << st;
36	return 0;
37 }

20.输入的字符串应当只由大写字母组成，否则在访问数组时可能越界。（ ）

{{ select(20) }}

• 正确
• 错误

21.若输入的字符串不是空串，则输入的字符串与输出的字符串一定不一样。（）

{{ select(21) }}

• 正确
• 错误

22.将第 12 行的“i < 26”改为“i < 16”，程序运行结果不会改变。（ ）

{{ select(22) }}

• 正确
• 错误

23.将第 30 行的"i < 26”改为“i < 16”，程序运行结果不会改变。（ ）

{{ select(23) }}

• 正确
• 错误

24.若输出的字符串为“ABCABCABCA”，则下列说法正确的是（ ）。

{{ select(24) }}

• 输入的字符串中既有S又有P
• 输入的字符串中既有S又有B
• 输入的字符串中既有A又有P
• 输入的字符串中既有A又有B

25.若输出的字符串为“CSPCSPCSPCSP”，则下列说法正确的是（ ）。

{{ select(25) }}

• 输入的字符串中既有P又有K
• 输入的字符串中既有J又有R
• 输入的字符串中既有J又有K
• 输入的字符串中既有P又有R

五

#include <iostream>
using namespace std;

long long n, ans;
int k, len;
long long d[1000000];

int main()
{
	cin >> n >> k;
	d[0] = 0;
	len = 1;
	ans = 0;
	for (long long i = 0; i < n; ++i)
	{
		++d[0];
		for (int j = 0; j + 1 < len; ++j)
		{
			if (d[j] == k)
			{
				d[j] = 0;
				d[j + 1] += 1;
				++ans;
			}
		}
		if (d[len - 1] == k)
		{
			d[len - 1] = 0;
			d[len] = 1;
			++len;
			++ans;
		}
	}
	cout << ans << endl;
	return 0;
}

假设输入的 n 是不超过 $2^{62}$的正整数，k都是不超过 10000 的正整数，完成下面的题目：

26.若 k=1，则输出 ans 时，len=n。（ ）

{{ select(26) }}

• 正确
• 错误

27.若 k>1，则输出 ans 时，len —定小于 n。（ ）

{{ select(27) }}

• 正确
• 错误

28.若 k>1，则输出 ans 时，$k^{len}$—定大于n。（ ）

{{ select(28) }}

• 正确
• 错误

29.若输入的n等于：$10^{15}$，输入的 k 为 1，则输出等于（ ）。 {{ select(29) }}

• 1
• ($10^{30}$-$10^{15}$)/2
• ($10^{30}$+$10^{15}$)/2
• $10^{15}$

30.若输入的 n 等于205,891,132,094,649（即 $3^{30}$），输入的 k 为 3，则输出等于（ ）。 {{ select(30) }}

• $3^{30}$
• ($3^{30}$-1)/2
• $3^{30}$-1
• ($3^{30}$+1)/2

31.若输入的 n 等于 100,010,002,000,090，输入的 k 为 10，则输出等于（ ）。

{{ select(31) }}

• 11,112,222,444,543
• 11,122,222,444,453
• 11,122,222,444,543
• 11,112,222,444,453

六

#include <cstdio>
#include <cstring>
using namespace std;
char st[100];
int main()
{
	scanf("%s", st);
	int n = strlen(st);
	for (int i = 1; i <= n; ++i)
	{
		if (n % i == 0)
		{
			char c = st[i - 1];
			if (c >= 'a')
				st[i - 1] = c - 'a' + 'A';
		}
	}
	printf("%s", st);
	return 0;
}

32.输入的字符串只能由小写字母或大写字母组成。（） {{ select(32) }}

• 正确
• 错误

33.若将第8行的“i = 1”改为“i = 0”，程序运行时会发生错误。（）

{{ select(33) }}

• 正确
• 错误

34.若将第8行的“i <= n”改为“i * i <= n”，程序运行结果不会改变。（）

{{ select(34) }}

• 正确
• 错误

35.若输入的字符串全部由大写字母组成，那么输出的字符串就跟输入的字符串一样。（）

{{ select(35) }}

• 正确
• 错误

36.若输入的字符串长度为18,那么输入的字符串跟输出的字符串相比，至多有（）个字符不同。 {{ select(36) }}

• 18
• 6
• 10
• 1

37.若输入的字符串长度为（），那么输入的字符串跟输出的字符串相比，至多有36个字符不同。 {{ select(37) }}

• 36
• 100000
• 1
• 128

七

#include <cstdio>
using namespace std;
int n, m;
int a[100], b[100];

int main(){
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; ++i) 
        a[i] = b[i] = 0;
	for (int i = 1; i <= m; ++i){
		int x, y;
		scanf("%d%d", &x, &y);
		if (a[x] < y && b[y] < x){
			if (a[x] > 0)
				b[a[x]] = 0;
			if (b[y] > 0)
				a[b[y]] = 0;
			a[x] = y;
			b[y] = x;
		}
	}
	int ans = 0;
	for (int i = 1; i <= n; ++i){
		if (a[i] == 0)
			++ans;
		if (b[i] == 0)
			++ans;
	}
	printf("%d", ans);
	return 0;
}

假设输入的n和m都是正整数，x和y都是在［1, n］的范围内的整数，完成下面的题目：

38.当m>0时，输出的值一定小于2n。（）

{{ select(38) }}

• 正确
• 错误

39.执行完第27行的"++ans"时，ans —定是偶数。（）

{{ select(39) }}

• 正确
• 错误

40.a［i］和b［i］不可能同时大于0。（）

{{ select(40) }}

• 正确
• 错误

41.右程序执行到第13行时，x总是小于y,那么第15行不会被执行。（）

{{ select(41) }}

• 正确
• 错误

42.若m个x两两不同，且m个y两两不同，则输出的值为（） {{ select(42) }}

• 2n-2m
• 2n+2
• 2n-2
• 2n

43.若m个x两两不同，且m个y都相等，则输出的值为（） {{ select(43) }}

• 2n-2
• 2n
• 2m
• 2n-2m

八

#include <iostream>
using namespace std;
const int maxn = 10000;
int n;
int a[maxn];
int b[maxn];
int f(int l, int r, int depth){
	if (l > r)
		return 0;
	int min = maxn, mink;
	for (int i = l; i <= r; ++i){
		if (min > a[i]){
			min = a[i];
			mink = i;
		}
	}
	int lres = f(l, mink - 1, depth + 1);
	int rres = f(mink + 1, r, depth + 1);
	return lres + rres + depth * b[mink];
}
int main(){
	cin >> n;
	for (int i = 0; i < n; ++i)
		cin >> a[i];
	for (int i = 0; i < n; ++i)
		cin >> b[i];
	cout << f(0, n - 1, 1) << endl;
	return 0;
}

44.如果a数组有重复的数字，则程序运行时会发生错误。（）

{{ select(44) }}

• 正确
• 错误

45.如果b数组全为0,则输出为0。（）

{{ select(45) }}

• 正确
• 错误

46.当n=100时，最坏情况下，与第12行的比较运算执行的次数最接近的是：（）。 {{ select(46) }}

• 5000
• 600
• 6
• 100

47.当n=100时，最好情况下，与第12行的比较运算执行的次数最接近的是：（）。 {{ select(47) }}

• 100
• 6
• 5000
• 600

48.当n=10时，若b数组满足，对任意0<=i<n,都有b［i］ = i + 1,那么输出最大为（）。 {{ select(48) }}

• 386
• 383
• 384
• 385

49.当n=100时，若b数组满足，对任意0 S i < 71,都有b［i］=1,那么输出最小为（）。 {{ select(49) }}

• 582
• 580
• 579
• 581