一、单项选择（共15题，每题2分，共计30分；每题有且仅有一个正确选项）

1. 一个32位无符号整数可以表示的最大值，最接近下列哪个选项?() {{ select(1) }}

• $4\times 10^9$
• $3\times 10^{10}$
• $2\times 10^9$
• $2\times 10^{10}$

2. 在C++中,执行 int x=255; cout<<(x&(x-1));后,输出的结果是?() {{ select(2) }}

• 255
• 254
• 128
• 0

3. 函数calc(n)的定义如下，则calc(5)的返回值是多少?()

int calc(int n){
    if(n<=1) return 1;
    if(n%2==0) return calc(n/2)+1;
    else return calc(n-1)+calc(n-2);
}

{{ select(3) }}

• 5
• 6
• 7
• 8

4. 用5个权值10、12、15、20、25构造哈夫曼树，该树的带权路径长度是多少?() {{ select(4) }}

• 176
• 186
• 196
• 206

5. 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和，这个总和等于?() {{ select(5) }}

• 顶点数
• 边数
• 顶点数+边数
• 顶点数2

6. 从5位男生和4位女生中选出4人组成一个学习小组,要求学习小组中男生和女生都有。有多少种不同的选举方法?() {{ select(6) }}

• 126
• 121
• 120
• 100

7. 假设a、b、c都是布尔变量,逻辑表达式(a&&b)||(!c&&a)的值与下列哪个表达式不始终相等?() {{ select(7) }}

• a&&(b||!c)
• (a||!c)&&(b||!c)&&(a||a)
• a&&(!b||c)
• !(a||!b)||(a&&!c)

8. 已知 $f[0]=1$ ,并且对于所有 $n\geq 2$ 有 $f[n]=(f[n-1]+f[n-2])\% 7$ ,那么 $f[2025]$ 的值是多少?() {{ select(8) }}

• 2
• 4
• 5
• 6

9. 下列关于C++ string类的说法,正确的是?() {{ select(9) }}

• string对象的长度在创建后不能改变
• 可以使用+运算符直接连接一个string对象和一个char类型的字符
• string的 length()和 size()方法返回的值可能不同
• string对象必须以\0结尾,且这个结尾符计入 length()

10. 考虑以下C++函数,在 main函数调用solve后, x和y的值分别是?()

void solve(int&a, int b){
    a=a+b;
    b=a-b;
    a=a-b;
}
int main(){
    int x=5, y=10;
    solve(x, y);
}

{{ select(10) }}

• 5, 10
• 10, 5
• 10, 10
• 5, 5

11. 一个 $8\times 8$ 的棋盘，左上角坐标为(1,1),右下角为(8,8)。一个机器人从(1,1)出发,每次只能向右或向下走一格。要到达(4,5)，有多少种不同的路径?() {{ select(11) }}

• 20
• 35
• 56
• 70

12. 某同学用冒泡排序对数组 $[6,1,5,2,4]$ 进行升序排序,请问需要进行多少次元素交换?() {{ select(12) }}

• 5
• 6
• 7
• 8

13. 十进制数720 ${}_{10}$ 和八进制数(原题此处缺失八进制数)的和用十六进制表示是多少?() {{ select(13) }}

• $388_{16}$
• $3DE_{16}$
• $288_{16}$
• $990_{16}$

14. 一棵包含1000个结点的完全二叉树，其叶子结点的数量是多少?() {{ select(14) }}

• 499
• 512
• 500
• 501

15. 给定一个初始为空的整数栈S和一个空的队列P。按顺序处理输入的整数队列A:7、5、8、3、1、4、2。处理规则:①若该数是奇数,压入栈S;②若该数是偶数且栈S非空,弹出栈顶元素加入队列P;③若该数是偶数且栈S为空,不操作。当队列A处理完毕后,队列P的内容是什么?() {{ select(15) }}

• 5, 1, 3
• 7, 5, 3
• 3, 1, 5
• 5, 1, 3, 7

二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题选正误；除特殊说明外，判断题每题1.5分，选择题每题3分，共40分）

(1)

01 #include <algorithm>
02 #include <cstdio>
03 #include <cstring>
04 inline int gcd(int a, int b) {
05   if (b == 0)
06     return a;
07   return gcd(b, a % b);
08 }
09 int main() {
10   int n;
11   scanf("%d", &n);
12   int ans = 0;
13   for (int i = 1; i <= n; ++i) {
14     for (int j = i + 1; j <= n; ++j) {
15       for (int k = j + 1; k <= n; ++k) {
16         if (gcd(i, j) == 1 && gcd(j, k) == 1
17             && gcd(i, k) == 1) {
18           ++ans;
19         }
20       }
21     }
22   }
23   printf("%d\n", ans);
24   return 0;
25 }

16. 当输入为2时，程序并不会执行第16行的判断语句。() {{ select(16) }}

• 正确
• 错误

17. 将第16行中的&& gcd(i，k)==1删去不会影响程序运行结果。() {{ select(17) }}

• 正确
• 错误

18. 当输入的 $n\geq 3$ 的时候,程序总是输出一个正整数。() {{ select(18) }}

• 正确
• 错误

19. 将第7行的 gcd(b,a%b)改为 gcd(a,a%b)后，程序可能出现的问题是() {{ select(19) }}

• 输出的答案大于原答案
• 输出的答案小于原答案
• 程序有可能陷入死循环
• 可能发生整型溢出问题

20. 当输入为8的时候,输出为() {{ select(20) }}

• 37
• 42
• 35
• 25

21. 调用gcd(36,42)会返回() {{ select(21) }}

• 6
• 252
• 3
• 2

(2)

01 #include <algorithm>
02 #include <cstdio>
03 #include <cstring>
04 #define ll long long
05 int n, k;
06 int a[200007];
07 int ans[200007];
08 int main() {
09   scanf("%d%d", &n, &k);
10   for (int i = 1; i <= n; ++i) {
11     scanf("%d", &a[i]);
12   }
13   std::sort(a + 1, a + n + 1);
14   n = std::unique(a + 1, a + n + 1) - a - 1;
15   for (int i = 1, j = 0; i <= n; ++i) {
16     for (; j < i && a[i] - a[j + 1] > k; ++j)
17       ;
18     ans[i] = ans[j] + 1;
19   }
20   printf("%d\n", ans[n]);
}

22. 当输入为"3 1 3 2 1"时，输出结果为2。() {{ select(22) }}

• 正确
• 错误

23. 假设输入的n为正整数，输出的答案一定小于等于n，大于等于1。() {{ select(23) }}

• 正确
• 错误

24. 将第14行的 n=std::unique(a+1,a+n+1)-a-1;删去后，有可能出现与原本代码不同的输出结果。() {{ select(24) }}

• 正确
• 错误

25. 假设输入的a数组和k均为正整数，执行第18行代码时，一定满足的条件不包括() {{ select(25) }}

• $j\leq i$
• $a[i]-a[j]>k$
• $j\leq n$
• $a[j]<a[i]$

26. 当输入的 $n=100$、$k=2$、$a=\{1,2,\dots,100\}$ 时，输出为() {{ select(26) }}

• 34
• 100
• 50
• 33

27. 假设输入的a数组和k均为正整数，但a数组不一定有序，若误删去第13行的std::sort(a+1,a+n+1);,程序有可能出现的问题有() {{ select(27) }}

• 输出的答案比原本答案更大
• 输出的答案比原本答案更小
• 出现死循环行为
• 以上均可能发生

（3）

01 #include <algorithm>
02 #include <cstdio>
03 #include <cstring>
04 #define ll long long
05 int f[5007][5007];
06 int a[5007], b[5007];
07 int n;
08 int main() {
09   scanf("%d", &n);
10   for (int i = 1; i <= n; ++i) {
11     scanf("%d", &a[i]);
12   }
13   for (int i = 1; i <= n; ++i) {
14     scanf("%d", &b[i]);
15   }
16   for (int i = 1; i <= n; ++i) {
17     for (int j = 1; j <= n; ++j) {
18       if (a[i] == b[j]) {
19         f[i][j] = f[i-1][j-1] + 1;
20       } else {
21         f[i][j] = std::max(f[i-1][j], f[i][j-1]);
22       }
23     }
24   }
25   printf("%d\n", f[n][n]);
26   return 0;
}

28. 当输入"412341322"时，输出为2。() {{ select(28) }}

• 正确
• 错误

29. 当程序运行完毕后，对于所有的 $1\leq i,j\leq n$，都一定有 $f[i][j]\leq f[n][n]$。() {{ select(29) }}

• 正确
• 错误

30. 将第18行的f[i][j]=std::max(f[i][j],std::max(f[i-1][j],f[i][j-1]));删去后，并不影响程序运行结果。() {{ select(30) }}

• 正确
• 错误

31. 输出的答案满足的性质有() {{ select(31) }}

• 小于等于n
• 大于等于0
• 不一定大于等于1
• 以上均是

32. 如果在16行的循环前加上以下两行: std::sort(a+1,a+n+1); std::sort(b+1,b+n+1),则答案会() {{ select(32) }}

• 变大或不变
• 变小或不变
• 一定变大
• 不变

33. 如果输入的a数组是1,2,...,n，而且b数组中数字均为1~n中的正整数，则上述代码等价于下面哪个问题:() {{ select(33) }}

• 求b数组去重后的长度
• 求b数组的最长上升子序列
• 求b数组的长度
• 求b数组的最大值

三、完善程序题（单选题，每小题3分，共计30分）

（一）字符串解码

（字符串解码） “行程长度编码”（Run-Length Encoding）是一种无损压缩算法，常用于压缩重复字符较多的数据，以减少存储空间。假设原始字符串不包含数字字符。压缩规则如下：

1. 如果原始字符串中一个字符连续出现N次（N≥2），在压缩字符串中它被表示为“字符*N”。例如，编码“A12”代表12个连续的字符A。
2. 如果原始字符串中一个字符只出现1次，在压缩字符串中它就表示为该字符本身。例如，编码“B”代表1个字符B。

以下程序实现读取压缩字符串并输出其原始的、解压后的形式。试补全程序。

#include<cctype>
#include<iostream>
#include<string>
using namespace std;

int main(){
    string z;
    cin>> z;
    string s="";
    for(int i=0;;){
        char ch= z[i];
        if( ①  &&isdigit(z[i+1])){
            int count=0;
            i++;
            while(i<z.length()&& isdigit(z[i])){
                count= ②;
                i++;
            }
            for(int j=0; j< ③ ;++j){
                s+= ch;
            }
        }else{
              s+=④;
            ⑤;
        }
    }
    cout<< s<< endl;
    return 0;
}

34. ①处应填() {{ select(34) }}

• $i<z$.length()
• $i-1\geq 0$
• $i+1<z$.length()
• isdigit(z[i])

35. ②处应填() {{ select(35) }}

• count+(z[i]-'0')
• count*10+(z[i]-'0')
• z[i]-'0'
• count+1

36. ③处应填() {{ select(36) }}

• count-1
• count
• 10
• z[i]-'8'

37. ④处应填() {{ select(37) }}

• $z[i+1]$
• ch
• z.back()
• (char)z[i]+1

38. ⑤处应填() {{ select(38) }}

• i--
• $i=i+2$
• i++
• 不执行任何操作

（二）精明与糊涂

（精明与糊涂）有N个人，分为两类： i）精明人：永远能正确判断其他人是精明还是糊涂； ii）糊涂人：判断不可靠，会给出随机的判断。 已知精明人严格占据多数，即如果精明人有k个，则满足k＞N/2。

你只能通过函数 query(i, j) 让第i个人判断第j个人：返回true表示判断结果为“精明人”；返回false表示判断结果为“糊涂人”。你的目标是，通过这些互相判断，找出至少一个百分之百能确定的精明人。同时，你无需关心query(i, j)的内部实现。

以下程序利用“精明人占多数”的优势。设想一个“消除”的过程，让人们互相判断并进行抵消。经过若干轮抵消后，最终留下的候选者必然属于多数派，即精明人。

例如，假设有三个人0、1、2。如果0说1是糊涂人，而1也说0是糊涂人，则0和1至少有一个是糊涂人。程序将同时淘汰0和1。由于三人里至少有两个精明人，我们确定2是精明人。

试补全程序。

#include <iostream>
#include <vector>
using namespace std;

int N;
bool query(int i, int j);

int main() {
    cin >> N;
    int candidate = 0;
    int count = ①;
    
    for (int i = 1; i < N; ++i) {
        if (②) {
            candidate = i;
            count = 1;
        } else {
            if (③) {
                ④;
            } else {
                count++;
            }
        }
    }
    
    cout << ⑤ << endl;
    return 0;
}

39. ①处应填() {{ select(39) }}

• 0
• 1
• N
• -1

40. ②处应填() {{ select(40) }}

• count<0
• count==1
• count==0
• query(candidate,i)==false

41. ③处应填() {{ select(41) }}

• query(candidate,i)==false
• query(i,candidate)==true
• query(candidate,i)==false&&query(i,candidate)==false
• query(candidate,i)==false||query(i,candidate)==false

42. ④处应填() {{ select(42) }}

• count--
• break
• count++
• candidate = i

43. ⑤处应填() {{ select(43) }}

• N-1
• count
• candidate
• 0