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

• A. (4 x 10^9 )
• B. (3 x 10^10 )
• C. (2 x 10^9 )
• D. (2 x 10^10 )

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

• A. 255
• B. 254
• C. 128
• D. 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) }}

• A. 5
• B. 6
• C. 7
• D. 8

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

• A. 176
• B. 186
• C. 196
• D. 206

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

• A. 顶点数
• B. 边数
• C. 顶点数+边数
• D. 顶点数×2

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

• A. 126
• B. 121
• C. 120
• D. 100

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

• A. a && (b || !c)
• B. (a || !c) && (b || !c) && ( a|| a)
• C. a && (!b || c)
• D. !(!a || !b) || (a && !c)

8. 已知f[1]=1，f[1]=1并且对于所有n ≥ 2有f[n]=(f[n-1]+f[n-2])%7，那么f[2025]的值是多少？（ ）{{ select(8) }}

• A. 2
• B. 4
• C. 5
• D. 6

9. 下列关于C++ string类的说法，正确的是？（ ）{{ select(9) }}

• A. string对象的长度在创建后不能改变。
• B. 可以使用+运算符直接连接一个string对象和一个char类型的字符。
• C. string的length()和size()方法返回的值可能不同。
• D. 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) }}

• A. 5, 10
• B. 10, 5
• C. 10, 10
• D. 5, 5

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

• A. 20
• B. 35
• C. 56
• D. 70

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

• A. 5
• B. 6
• C. 7
• D. 8

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

• A. 388
• B. 3DE
• C. 288
• D. 990

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

• A. 499
• B. 512
• C. 500
• D. 501

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

• A. 5, 1, 3
• B. 7, 5, 3
• C. 3, 1, 5
• D. 5, 1, 3, 7

二、阅读程序

(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. （1分）当输入为2时，程序并不会执行第16行的判断语句。（ ）{{ select(16) }}

• A. 正确
• B. 错误

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

• A. 正确
• B. 错误

18. 当输入的n ≥ 3的时候，程序总是输出一个正整数。（ ）{{ select(18) }}

• A. 正确
• B. 错误

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

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

20. 当输入为8的时候，输出为（ ）。{{ select(20) }}

• A. 37
• B. 42
• C. 35
• D. 25

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

• A. 6
• B. 252
• C. 3
• D. 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) }}

• A. 正确
• B. 错误

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

• A. 正确
• B. 错误

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

• A. 正确
• B. 错误

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

• A. j≤i
• B. a[i]−a[j]>k
• C. j≤n
• D. a[j]<a[i]

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

• A. 34
• B. 100
• C. 50
• D. 33

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

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

(3)

#include <algorithm>
#include <cstdio>
#include <cstring>
#define ll long long
int f[5007][5007];
int a[5007], b[5007];
int n;
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] = std::max(f[i-1][j], std::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) }}

• A. 正确
• B. 错误

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

• A. 正确
• B. 错误

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

• A. 正确
• B. 错误

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

• A. 小于等于n
• B. 大于等于0
• C. 不一定大于等于1
• D. 以上均是

32. 如果在16行的循环前加上以下两行：

std::sort(a+1,a+n+1);
std::sort(b+1,b+n+1);

则答案会（ ）。{{ select(32) }}

• A. 变大或不变
• B. 变小或不变
• C. 一定变大
• D. 不变

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

• A. 求b数组去重后的长度
• B. 求b数组的最长上升子序列
• C. 求b数组的长度
• D. 求b数组的最大值

三、完善程序

（1）字符串解码 “行程长度编码”（Run-Length Encoding）是一种无损压缩算法，常用于压缩重复字符较多的数据，以减少存储空间。假设原始字符串不包含数字字符，压缩规则如下： ①如果原始字符串中一个字符连续出现N次（N≥2），在压缩字符串中表示为“字符+数字N”。例如，编码“A12”代表12个连续的字符A。 ②如果原始字符串中一个字符只出现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; 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 += ④ ;
            }
        }else{
            s += ch;
            ⑤;
        }
    }
    cout << s << endl;
    return 0;
}

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

• A. i < z.length()
• B. i - 1 ≥ 0
• C. i + 1 < z.length()
• D. isdigit(z[i])

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

• A. count + (z[i]-'0')
• B. count * 10 + (z[i]-'0')
• C. z[i]-'0'
• D. z[i]-'0'

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

• A. count-1
• B. count
• C. 10
• D. count+1

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

• A. z[i+1]
• B. ch
• C. z.back()
• D. (char)z[i]+1

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

• A. i--
• B. i = i+2
• C. i++
• D. //不执行任何操作

（2）精明与糊涂 有N个人，分为两类： ①精明人：永远能正确判断其他人是精明还是糊涂； ②糊涂人：判断不可靠，会给出随机的判断。 已知精明人严格占据多数，即如果精明人有k个，则满足k > N/2。你只能通过函数query(i,j)让第i个人判断第j个人；返回true表示判断结果为“精明人”；返回false表示判断结果为“糊涂人”。目标是通过互相判断，找出至少一个百分之百确定的精明人（无需关心query(i,j)的内部实现）。 以下程序利用“精明人占多数”的优势，通过“消除”过程让人们互相判断并抵消，经过若干轮抵消后，最终留下的候选者必然属于多数派（精明人），试补全程序。

#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) }}

• A. 0
• B. 1
• C. N
• D. -1

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

• A. count < 0
• B. count == 1
• C. count == 0
• D. query(candidate, i) == false

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

• A. query(candidate,i)==false
• B. query(i,candidate)==true
• C. query(candidate,i)==false && query(i,candidate)==false
• D. query(candidate,i)==false || query(i,candidate)==false

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

• A. count--
• B. break
• C. count++
• D. 0

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

• A. N-1
• B. count
• C. candidate
• D. 0