该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

一、单项选择题(共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个二进制数，符号∧表示逻辑与运算，符号∨表示逻辑或运算。 若 A=1100 1101 0011，B=1100 0111 0110，C=0011 0110 1010，则表达式(A∨B)∧(A∨C)的值为（） {{ select(2) }}

• 1100 1110 0001
• 0011 0010 1111
• 1100 1111 0011
• 1100 0111 0001

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数"共有多少个？（注：回文数指从左到右读与从右到左读是相同的，如"121""1331"；两个条件都成立也是L数，如"131"）（）。 {{ select(7) }}

• 34
• 35
• 36
• 37

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

• 511
• 510
• 1023
• 1026

9. 共9个互不相同的数，它们的最大公约数是2021的一个大于1的因子(6有2、3、6这三个大于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之间(包括1和2015在内)不能被4、5、6三个数任意一个数整除的数有几个？（） {{ select(14) }}

• 1035
• 1105
• 1075
• 2000

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

• Cn表示有n+1个结点的不同形态的二叉树的个数
• Cn表示含n对括号的合法括号序列的个数
• Cn表示长度为n的入栈序列对应的合法出栈序列个数
• Cn表示通过连接顶点而将n+2边的凸多边形分成三角形的方法个数

二、阅读程序(程序输人不超过数组或字符串定义的范围; 除特殊说明外，判断题1.5分，选择题3分，共计40分)

阅读程序1：

#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. (1分)将第04行的&去除后，程序仍能通过编译。 {{ 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. 输入为33 7 2时，输出为（）。 {{ select(21) }}

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

阅读程序2：

#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. 若输入的X[1],X[2],…,X[N]中有相同的数，程序会陷入死循环。 {{ select(22) }}

• 正确
• 错误

23. 当且仅当输入的X[1],X[2],…,X[N]全部相同时输出的两行结果相同。 {{ select(23) }}

• 正确
• 错误

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

• 正确
• 错误

25. 若输入的X[1],X[2],…,X[N]互不相同，则下列说法正确的是（）。 {{ select(25) }}

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

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

• 输出的第一行即为将X[1],X[2],…,X[N]从小到大排序后得到的结果
• 输出的第二行即为将X[1],X[2],…,X[N]从大到小排序后得到的结果
• 若将a[i]>a[j]改为a[i]>=a[j]，则程序输出无变化
• 不存在时间复杂度更优的能与本程序达到相同目的的算法

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

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

阅读程序3：

#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<<"\n";
    return 0;
}

28. 代码中max_primedivisor=max(max_primedivisor,num);这句话去掉对答案没有影响。 {{ select(28) }}

• 正确
• 错误

29. 当读入的num=p*q，其中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*p*p*q*q*r*r*s*t时，其中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分)

完善程序1（电电鼠与方阵）： 有一个n*n(2<=n<=5000)的方阵，其中每个方格有一个电力值。小Y可以在这个方阵中得到电力，方法就是在一些方格放上电电鼠来吸收电力，这样就可以获得这些方格上的电力。不过放的电电鼠须要遵循两个规则：1.一个方格最多只能放一只电电鼠;2.所有2*2的子矩阵(共有(n-1)*(n-1)个)必须恰好包含两只电电鼠。小Y用了一个程序求出了能获得的最大总电力值。试补全程序。

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

完善程序2（排列）： 给定一个1~n的排列A，你需要给出一个1~n的排列B，使得排列B的字典序值最小。输出字典序最小的排列B。 输入两行，第一行一个正整数n，第二行n个整数表示排列A。 提示：将问题分为n是奇数和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=n/2;
        for(int i=1;i<=n;i++){
            if(A[i]> ③ ){
                B[i]=++p1;
            }else{
                B[i]=++p2;
            }
        }

        p1=0;p2=n/2+1;
        for(int i=1;i<=n;i++){
            if(A[i]>= ④ ){
                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