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

第 2 题 在C++中，执行 int x = 255;cout << (x &(x - 1));后，输出的结果是?( )

第 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);
}

第 4 题 用5个权值10, 12,15,20,25构造哈夫曼树，该树的带权路径长度是多少?( )

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

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

第 7 题 假设a,b,c都是布尔变量，逻辑表达式(a && b) ll(!c && a)的值与下列哪个表达式不始终相等?( )

第 8 题 己知 f[0]= 1, f[1]=1，并且对于所有n ≥ 2有 f[n] =(f[n-1] + f[n-2])%7.那么F[2025]的值是多少?( )

第 9 题 下列关于 C++ string类的说法，正确的是? ( )

第 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);
}

在main 函数调用solve后，x和y的值分别是?( )

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

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

第 13 题 十进制数$720_{10}$和八进制数$270_{8}$的和用十六进制表示是多少?( )

第 14 题 一棵包含1008个结点的完全二叉树，其叶子结点的数量是多少?( )

第 15 题 给定一个初始为空的整数栈s和一个空的队列P。我们按顺序处理输入的整数队列A: 7, 5, 8, 3, 1, 4, 2。对于队列A中的每一个数，执行以下规则:如果该数是奇数，则将其压入栈S；如果该数是偶数，且栈S非空，则弹出一个栈顶元素，并加入到队列P的末尾；如果该数是偶数，且栈S为空，则不进行任何操作。当队列A中的所有数都处理完毕后，队列P的内容是什么? ( )

二、判断题（每题 2 分，共 20 分）

第 16 题

#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行的判断语句。( )

第 17 题 将第16行中的“&& gcd(1,k)==1”删去不会影响程序运行结果。( )

第 18 题 当输入的n≥3的时候，程序总是输出一个正整数。( )

第 19 题 将第7行的“gcd(b,a%b)”改为“gcd(a,a%b)”后，程序可能出现的问题是( )。

第 20 题 当输入为8的时候，输出为( )。

第 21 题 调用gcd(36,42)会返回( )。

第 23 题

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

第 23 题 当输入为“3132 1”时，输出结果为2。( )

第 24 题 假设输入的n为正整数，输出的答案一定小于等于n，大于等于1。( )

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

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

第 27 题 当输入的n=100、k=2、 a={1,2,...,100}时， 输出为( )。

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

第 30 题

#include <algorithm>
#include <cstdio>
#include <cstring>
#define ll 1ong 1ong
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][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;
}

第 30 题 当输入“412341322”时，输出为2。( )

第 31 题 当程序运行完毕后，对于所有的1≤i,j≤n,都一定有f[i][j]<=f[n][n]。( )

第 32 题 将第18行的“f[i][j]=std::max(f[i][j], std::max(f[i-1][j],f[i][j-1]));”删去后，并不影响程序运行结果。( )

第 33 题 输出的答案满足的性质有( ) 。

第 34 题 如果在16行的循环前加上以下两行:“std::sort(a+1,a+n+1); std::sort(b+1,b+n+1)”，则答案会( )。

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

三、编程题（每题 25 分，共 50 分）

第 37 题 (字符串解码) “行程长度编码”(Run-Length Encoding)是一种无损压缩算法，常用于压缩重复字符较多的数据，以减少存储空间。假设原始字符串不包含数字字符。压缩规则如下: i)如果原始字符串中一个字符连续出现N次(N≥2)，在压缩字符串中它被表示为“字符+数字N”。例如，编码“A12”代表12个连续的字符A。ii)如果原始字符串中一个字符只出现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( ____(1)____ && isdigit(z[i + 1])) {
            i++;
            int count = 0;
            while (i < z.length() && isdigit(z[i])) {
                count = ____(2)____ ;
                i++;
            }
            for (int j =0; j< ____(3)____ ; ++j) {
                s += ch;
            }
        }  else {
            s += ____(4)____ ;
            ____(5)____  ;
        }
    }
    
    cout << s << endl;
    return 0;
}

第 37 题 ⑴处应填( )。

第 38 题 ⑵处应填( )。

第 39 题 ⑶处应填( )。

第 40 题 ⑷处应填( )。

第 41 题 ⑸处应填( )。

第 43 题 (精明与糊涂)有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 = ___(1)___ ;

    for(int i=1; i<N; ++i) {
        if ( ___(2)___ ) {
            candidate = 1;
            count = 1;
        } else {
            if( ___(3)___ ) {
                ___(4)___ ;
            } else {
                count++;
            }
        }
    }

    cout << ___(5)___ << endl;
    return 0;
}

第 43 题 ⑴处应填( )。

第 44 题 ⑵处应填( )。

第 45 题 ⑶处应填( )。

第 46 题 ⑷处应填( )。

第 47 题 ⑸处应填( )。