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

1. IPv4中，以下IP地址不合法的是（）。 {{ select(1) }}

• 255.255.255.255
• 0.1.1.1
• 1.1.1.0
• 1.0.0.0

2. 已知A,B,C是3个二进制数，符号∧表示逻辑与运算，符号∨表示逻辑或运算。 C = 001101101010 则表达式(A∨B)∧(A∨C)的值为（）。 {{ select(2) }}

• 110011100001
• 001100101111
• 1100 1111 0011
• 110001110001

3. Linux下可执行文件的默认扩展名为（）。 {{ select(3) }}

• exe
• chm
• dll
• 都不是

4. 八进制数7042转化为十六进制数是（）。 {{ select(4) }}

• 3521
• F22
• E22
• 111000100010

5. 以下排序算法中，不需要进行关键字比较操作的算法是（）。 {{ select(5) }}

• 基数排序
• 冒泡排序
• 堆排序
• 直接插入排序

6. 一个袋子中有3个蓝球，2个红球，2个黄球，则从中抽出三个球颜色各不相同的概率是多少?（） {{ select(6) }}

• 10/21
• 13/33
• 12/35
• 3/7

7. 定义L数：素数或者是回文数满足两者中任意一个条件的数。大于等于10并且小于等于120的"L数"共有多少个？（注：回文数指从左到右读与从右到左读相同，两个条件都成立也算L数）（） {{ select(7) }}

• 34
• 35
• 36
• 37

8. 定义有根树的深度：根结点的深度为0，其余结点的深度等于其父结点深度加1。以下数字中可以作为深度为9的完全二叉树的总结点数的是（）。 {{ select(8) }}

• 511
• 510
• 1023
• 1026

9. 共9个互不相同的数，它们的最大公约数是2021的一个大于1的因子，且这9个数的和小于等于2021，则这9个数的和是多少？（） {{ select(9) }}

• 1849
• 1935
• 2021
• 1927

10. 以下哪位科学家被称为"博弈论之父"、"现代计算机之父"？（） {{ select(10) }}

• 图灵
• 冯诺依曼
• 塔扬
• 比尔盖茨

11. 设栈S和队列Q初始状态为空，元素a₁, a₂, …, a₆依次通过栈S，一个元素出栈后进入队列Q。若出队顺序为a₂, a₄, a₃, a₆, a₅, a₁，则栈S的容量至少是（）。 {{ select(11) }}

• 2
• 3
• 4
• 5

12. 对有序数组{5,13,19,21,37,56,64,75,88,92,100}进行二分查找，等概率下查找成功的平均查找长度（平均比较次数）是（）。 {{ select(12) }}

• 35/11
• 34/11
• 3
• 32/11

13. 一个n个顶点的强连通图最少有几条边？（） {{ select(13) }}

• n
• n+1
• n-1
• n*(n-1)

14. 在1到2015之间（包含两端）不能被4、5、6任意一个数整除的数有几个？（） {{ select(14) }}

• 1035
• 1105
• 1075
• 2000

15. 关于Catalan数Cₙ，下列说法中错误的是（）。 {{ select(15) }}

• Cₙ表示有n+1个结点的不同形态二叉树的个数
• Cₙ表示含n对括号的合法括号序列的个数
• Cₙ表示长度为n的入栈序列对应的合法出栈序列个数
• Cₙ表示将n+2边的凸多边形划分为三角形的方法数

二、阅读程序（共计40分；除特殊说明外，判断题每题1.5分，选择题每题3分）

（一）递归函数

#include<bits/stdc++.h>
using namespace std;
int p;
void fun(int &x, int &y);
void func(int &x, int &y){
    if(y > x) return;
    x--; y /= 2;
    fun(x, y);
}
void fun(int &x, int &y){
    if(x == 1) return;
    x /= 2; y += p;
    func(x, y);
}
int main(){
    int x, y;
    cin >> x >> y >> p;
    fun(x, y);
    cout << x << ' ' << y;
    return 0;
}

判断题 16. 将第4行的&去除后，程序仍能通过编译。（） {{ select(16) }}

• 正确
• 错误

17. 读入的x, y, p为int范围内任意值时程序均能正常结束运行。（） {{ select(17) }}

• 正确
• 错误

18. 若输入x=1，则输出的x, y与输入值一致。（） {{ select(18) }}

• 正确
• 错误

19. 输出的x必然小于等于输入的x。（） {{ select(19) }}

• 正确
• 错误

选择题 20. 输入为7 33 2时，输出为（）。 {{ select(20) }}

• 4 31
• 4 35
• 3 31
• 3 35

21. 输入为3 3 7 2时，输出为（）。 {{ select(21) }}

• 5 3
• 3 5
• 6 4
• 4 6

（二）双向冒泡排序

#include<iostream>
using namespace std;
const int maxn = 105;
int n, a[maxn], b[maxn];
int main()
{
    cin >> n;
    int x;
    for(int i = 1; i <= n; i++){
        cin >> x;
        a[i] = b[i] = x;
    }

    for(int i = 1; i <= n; i++)
        for(int j = i + 1; j <= n; j++){
            if(a[i] > a[j]) swap(a[i], a[j]);
            if(b[i] < b[j]) swap(b[i], b[j]);
        }

    for(int i = 1; i <= n; i++) cout << a[i] << " ";
    cout << "\n";
    for(int i = 1; i <= n; i++) cout << b[i] << " ";
    cout << "\n";
    return 0;
}

判断题 22. 若输入序列中有相同的数，程序会陷入死循环。（） {{ select(22) }}

• 正确
• 错误

23. 当且仅当输入序列全部相同时，输出的两行结果相同。（） {{ select(23) }}

• 正确
• 错误

24. 该算法的原理是基数排序。（） {{ select(24) }}

• 正确
• 错误

选择题 25. 若输入序列中元素互不相同，则下列说法正确的是（）。 {{ select(25) }}

• 输出的两行结果相同
• 将第一行结果整体翻转后与第二行相同
• 将第一行首尾元素交换后与第二行相同
• 以上说法都不正确

26. 下列说法不正确的是（）。 {{ select(26) }}

• 第一行是输入序列从小到大排序的结果
• 第二行是输入序列从大到小排序的结果
• 将a[i]>a[j]改为a[i]>=a[j]，程序输出无变化
• 不存在时间复杂度更优的算法实现相同功能

27. 该程序的时间复杂度为（）。 {{ select(27) }}

• O(n)
• O(n log n)
• O(n²)
• O(n√n)

（三）质因数分解与约数个数

#include<bits/stdc++.h>
using namespace std;
int main(){
    int num = 0;
    cin >> num;
    //保证num>=100，且在int范围内
    int max_primedivisor = 0;
    int cnt = 1;
    for(int i = 2; i * i <= num; i++){
        if(num % i == 0){
            int tmp = 1;
            while(num % i == 0) num /= i, tmp++;
            max_primedivisor = max(max_primedivisor, i);
            cnt *= tmp;
        }
    }
    max_primedivisor = max(max_primedivisor, num);
    if(num > 1) cnt *= 2;
    cout << max_primedivisor << " " << cnt << endl;
    return 0;
}

判断题 28. 去掉max_primedivisor = max(max_primedivisor, num);对答案没有影响。（） {{ select(28) }}

• 正确
• 错误

29. 若num = p * q，其中p<q且均为质数，则for循环中i遍历到q时才退出循环。（） {{ select(29) }}

• 正确
• 错误

选择题 30. 该算法的最坏时间复杂度为（）。 {{ select(30) }}

• O(log num)
• O(√num)
• O(num)
• O(num√num)

31. 读入2021时输出为（）。 {{ select(31) }}

• 43 2
• 43 4
• 47 2
• 47 4

32. 若num = p³ × q² × r² × s × t，其中p<q<r<s<t均为质数，则输出的第二个数为（）。 {{ select(32) }}

• 不确定
• 9
• 12
• 144

33. 在最好情况下，该算法的时间复杂度为（）。 {{ select(33) }}

• O(log num)
• O(√num)
• O(num)
• O(num√num)

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

（一）电电鼠与方阵

有一个n×n的方阵，每个方格有一个电力值。在方格中放置电电鼠可获得对应电力，需满足：

1. 每个方格最多放一只电电鼠；
2. 所有2×2子矩阵都恰好包含两只电电鼠。 求能获得的最大总电力值。

#include<bits/stdc++.h>
using namespace std;
const int N = 5100;
int a[①];
int main(){
    int n, ans1 = 0, ans2 = 0;
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            scanf("%d", &a[i][j]);
    for(int i = 1; i <= n; i++){
        int odd = 0, even = 0;
        for(int j = 1; j <= n; j++){
            int x = ②;
            if (j & 1) odd += x; else even += x;
        }
        ans1 += max(odd, even);
    }
    for(int i = 1; i <= n; i++){
        int odd = 0, even = 0;
        for(int j = 1; j <= n; j++){
            int x = ③;
            if(④) even += x; else odd += x;
        }
        ans2 += max(odd, even);
    }
    printf("%d\n", ⑤);
    return 0;
}

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

• [N][2]
• [2][N]
• [N][1100]
• [5100][5100]

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

• a[j][i]
• a[i][j]
• a[i+j][(i+j)&1]
• a[(i+j)&1][i+j]

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

• a[j][i]
• a[i][j]
• a[i+j][(i+j)&1]
• a[(i+j)&1][i+j]

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

• j&1
• j||1
• !(j&1)
• !(j||1)

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

• max(ans1, ans2)
• min(ans1, ans2)
• ans1+ans2
• max(ans1,ans2) - min(ans1,ans2)

（二）最小字典序排列

给定1~n的排列A，构造1~n的排列B，使B的字典序最小。 提示：分n为奇数和偶数两种情况贪心处理。

#include<bits/stdc++.h>
using namespace std;
int A[1000010]; int B[1000010]; int C[1000010];
int main(){
    int n; scanf("%d", &n);
    for(int i = 1; i <= n; i++) scanf("%d", &A[i]);

    if(①){
        int p1 = 0; int p2 = ②;
        for(int i = 1; i <= n; i++){
            if(A[i] > n/2){
                B[i] = ++p1;
            }else{
                B[i] = ++p2;
            }
        }
    }else{
        int p1 = 0; int p2 = ③;
        for(int i = 1; i <= n; i++){
            if(A[i] > n/2){
                B[i] = ++p1;
            }else{
                B[i] = ++p2;
            }
        }

        p1 = 0; p2 = ④;
        for(int i = 1; i <= n; i++){
            if(A[i] >= n/2 + 1){
                C[i] = ++p1;
            }else{
                C[i] = ++p2;
            }
        }

        int flag = 0;
        for(int i = 1; i <= n; i++){
            if(B[i] < C[i]){ flag = 1; break; }
            if(B[i] > C[i]){ flag = 2; break; }
        }
        if(flag != ⑤) swap(B, C);
    }
    for(int i = 1; i < n; i++) printf("%d ", B[i]);
    printf("%d\n", B[n]);
    return 0;
}

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

• n%2 == 0
• n%2 == 1
• n == 1
• n == 2

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

• p1
• n/2-1
• n/2
• n/2+1

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

• p1
• n/2-1
• n/2
• n/2+1

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

• p1
• n/2-1
• n/2
• n/2+1

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

• 0
• 1
• 2
• 3