一、单项选择题（共 15 题，每题 2 分，共计 30 分）

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

• 4×10⁹
• 3×10¹⁰
• 2×10⁹
• 2×10¹⁰

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

• 255
• 254
• 28
• 8

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
• 180

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，f[1]=1，并且对于所有 n>=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++ 函数：

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);
    return 0;
}

在 main 函数调用 solve 后，x 和 y 的值分别是（） {{ select(10) }}

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

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

• 20
• 35
• 56
• 78

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

• 5
• 6
• 7
• 8

13. 十进制数 720 和八进制数 270 的和用十六进制表示是多少？（） {{ select(13) }}

• 388
• 3DE
• 288
• 990

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

• 499
• 512
• 500
• 501

15. 给定一个初始为空的整数栈 S 和一个空的队列 P。我们按顺序处理输入的整数队列 A：7,5，8，3，1，4，2。 规则：奇数压入栈 S；偶数且栈非空则弹出栈顶加入队列 P；偶数且栈空则不操作。 处理完毕后，队列 P 的内容是什么？（） {{ select(15) }}

• 5，1，3
• 7，5，3
• 3，1，5
• 5，1，3，7

二、阅读程序（判断题 1.5 分，选择题 3 分，共计 40 分）

（1）最大公约数三元组统计

#include <algorithm>
#include <cstdio>
#include <cstring>
inline int gcd(int a, int b){
    if(b==0) 
    return a;
    return gcd(b, a%b);
}
int main(){
    int n;
    scanf("%d", &n);
    int ans=0;
    for(int i=1;i<=n;++i){
        for(int j=i+1; j<=n;++j){
            for(int k =j+1;k<=n;++k){
                if(gcd(i, j)==1 &&gcd(j, k)==1 &&gcd(i, k)==1){
                    ++ans;
                }
            }
        }
    }
    printf("%d\n", ans);
    return 0;
}

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

• 对
• 错

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

• 对
• 错

18. 当输入的 n>=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）去重+双指针分组

#include <algorithm>
#include <cstdio>
#include <cstring>
#define ll long long
int n,k;
int a[200007];
int ans [200007];
int main(){
    scanf("%d%d", &n, &k);
    for(int i=1;i<=n;++i){
        scanf("%d" , &a[i]);
    }
    std::sort (a+1, a+n+1);
    n=std::unique(a+1, a+n+1)-a-1;
    for(int i=1, j=0;i<=n;++i){
        for(;j<i&&a[i]-a[j+1]>k; ++j);
        ans[i]=ans[j] +1;
    }
    printf("%d\n", ans [n]);
    return 0;
}

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

• 对
• 错

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

• 对
• 错

24. 将第 14 行的去重语句删去后，有可能出现与原本代码不同的输出结果。（） {{ select(24) }}

• 对
• 错

25. 执行第 18 行代码时，一定满足的条件不包括（） {{ select(25) }}

• j<=i
• a[i]-a[j]>k
• j<=n
• a[j]<a[i]

26. 当输入 n=100、k=2、a={1,2,...,100} 时，输出为（） {{ select(26) }}

• 34
• 100
• 50
• 33

27. 若删去第 13 行排序语句，程序有可能出现的问题是（） {{ select(27) }}

• 答案更大
• 答案更小
• 死循环
• 以上均可能

（3）最长公共子序列

#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
int f[5007][5007];
int n;
int a[5007], b[5087];
int main(){
    scanf("%d", &n);
    for(int i=1;i<=n;++i){
        scanf("%d" , &a[i]);
    }
    for(int i=1;i<=n;++i){
        scanf("%d", &b[i]);
    }
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j){
            f[i][j]=max(f[i][j], max(f[i-1][j], f[i][j-1]));
            if(a[i]==b[j]){
                f[i][j]=std::max(f[i][j], f[i-1][j-1]+1);
            }
        }
    }
    printf("%d\n", f[n][n]);
    return 0;
}

28. 当输入 4 1 2 3 4 1 3 2 2 时，输出为 2。（） {{ select(28) }}

• 对
• 错

29. 程序运行完毕后，对于所有 1<=i,j<=n，都一定有 f[i][j]<=f[n][n]。（） {{ select(29) }}

• 对
• 错

30. 将第 18 行的 max 语句删去后，并不影响程序运行结果。（） {{ select(30) }}

• 对
• 错

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

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

32. 如果在循环前对 a、b 排序，则答案会（） {{ select(32) }}

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

33. 如果输入 a={1,2,...,n}，代码等价于（） {{ select(33) }}

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

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

（1）行程长度编码（字符串解码）

#include <cctype>
#include <iostream>
#include <string>
using namespace std;
int main(){
    string z;
    cin >> z;
    string s="";
    for(int i=0; i<z.length();){
        char ch =z[i];
        if(① &&isdigit(z[i+1])){
            i++;
            int count =0;
            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 >= 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]-'0'

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

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

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

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

（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