一、单项选择题（共15题，每题2分，共计30分；每题仅有一个正确选项）

1. 下列选项中数值最大的是 {{ select(1) }}

• $(504)_{10}$
• $(111111000)_2$
• $(770)_8$
• $(1FA)_{16}$

2. 主机IP 194.32.6.22，掩码255.255.255.192，子网地址为 {{ select(2) }}

• 194.32.6.22
• 194.32.0.0
• 0.0.0.22
• 194.32.6.0

3. 普通计算机网关不能设置为 {{ select(3) }}

• 10.16.13.100
• 127.0.0.1
• 234.123.6.5
• 168.10.7.100

4. 共2021个节点的二叉树，叶子节点最大数量 {{ select(4) }}

• 1010
• 1
• 2020
• 1011

5. 深度优先搜索一定需要的数据结构 {{ select(5) }}

• 栈
• 二叉树
• 链式前向星
• 队列

6. $2023^{2023} \bmod 5$ 的结果 {{ select(6) }}

• 1
• 2
• 3
• 4

7. 以下希尔增量序列，最坏时间复杂度最优的是 {{ select(7) }}

• $1,2,4,8,\dots$
• $5,19,41,109\dots$
• $1,3,7,\dots,2^k-1$
• $1,2,3,4,5,\dots$

8. 下面问题存在多项式确定算法的是 {{ select(8) }}

• 01背包（n物品）
• 大数质因数分解（n位）
• TSP旅行商（n点）
• 求n阶矩阵行列式

9. 表达式 $3*(1-2)+4$ 后缀表达式 {{ select(9) }}

• $3\ 1\ 2\ -\ *\ 4\ +$
• $3\ 1\ -\ 2\ *\ 4\ +$
• $+\ *\ 3\ -\ 1\ 2\ 4$
• $3\ 1\ *\ 2\ -\ 4\ +$

10. 仅路径压缩的并查集最坏均摊复杂度 {{ select(10) }}

• $O(n)$
• $O(n\alpha(n))$
• $O(n\log n)$
• $O(n^2)$

11. 代码静态内存占用大小估算

const int N=1000,M=10000;
struct edge{double e;int nxt,v;}e[M<<1];
int h[N],tot,n,m;double d[N];

{{ select(11) }}

• 30000Bytes
• 324KB
• 3200KB
• 3MB

12 下列逻辑表达式恒为真的是 {{ select(12) }}

• (3)(4)
• (1)(3)
• (2)(4)
• (3)

13. 六位数（含前导0），包含数字9的“好数”个数 {{ select(13) }}

• 1000000
• 531441
• 468559
• 999999

14. 20人每人50%到场，趣味度为到场人数平方，数学期望 {{ select(14) }}

• 425/4
• 105
• 110
• 100

15. C++之父是 {{ select(15) }}

• 本贾尼·斯特劳斯特卢普(Bjarne Stroustrup)
• 图灵(Alan Turing)
• 吉多·范罗苏姆(Guido van Rossum)
• 姚期智

二、阅读程序（判断1.5分，选择3/3.5分，总分40）

阅读程序1 最大子段和+位运算

#include<algorithm>
#include<iostream>
using namespace std;
const int MAXN=1000;
int a[MAXN],c[MAXN];
int main(){
    int n,x,y;
    cin>>n>>x>>y;
    int sum=(x^y)+((x&y)<<1);
    n=n<<3^5&312;
    for(int i=1;i<=n;++i) cin>>a[i];
    int answer; c[1]=max(a[1],0);
    for(int i=2;i<=n;++i){
        c[i]=max(c[i-1]+a[i],a[i]);
        if(c[i]<=0) c[i]=0;
        answer =max (answer,c[i]);
    }
    if (answer<=sum) puts ("Good.");
    else puts("It's too sad.");
    return 0;
}

16. sum=x+y {{ select(16) }}

• √
• ×

17. 删除18、19行输出不变 {{ select(17) }}

• √
• ×

18. answer未初始化会出错 {{ select(18) }}

• √
• ×

19. n≤125否则数组越界 {{ select(19) }}

• √
• ×

20. 输入原始n=15，执行n=n<<3^5&312后n为 {{ select(20) }}

• 60
• 123
• 30
• 30

21. n=11，数组5,12,-7,-11,-9,4,9,5,-6,11，answer值 {{ select(21) }}

• 23
• 18
• 17
• 46

阅读程序2 积性函数卷积

#include<cmath>
#include<cstring>
#include<iostream>
using namespace std;
const int MAXN=1000000;
int n;
int f1[MAXN], f2[MAXN], f3[MAXN];
int calc_f1(int x) {
    int ans=1;
    int maxNum=sqrt(x);
    for(int i=2;i<=maxNum;++i)
        if(x%i==0){
            ans=-ans;
            x/=i;
            if(x%i==0) return 0;
        }
    if(x!=1) ans=-ans;
    return ans;
}
int calc_f2(int x){return x;}
void convolute(){
    memset (f3,0,sizeof(f3));
    for(int i=1;i<=n;++i)
        for (int j=1;j<=n/i;++j)
            if(i*j<=n) f3[i*j]=f3[i*j]+f1[i]*f2[j];
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i) f1[i]=calc_f1(i);
    for(int i=1;i<=n;++i) f2[i]=calc_f2(i);
    convolute();
    printf("%d\n",f3[n]);
    return 0;
}

22. n/i改为n程序仍正确 {{ select(22) }}

• √
• ×

23. 删除#include<iostream>可正常编译 {{ select(23) }}

• √
• ×

24. convolute时间复杂度 {{ select(24) }}

• $O(n^2)$
• $O(n)$
• $O(n\log n)$
• $O(n\sqrt{n})$

25. 输入n=3输出 {{ select(25) }}

• 2
• 1
• -1
• 数组越界

26. 输入n=1003输出 {{ select(26) }}

• 1002
• 928
• 1
• 数组越界

27. 输入n=1000000输出 {{ select(27) }}

• 999999
• 400000
• 0
• 数组越界

阅读程序3 埃氏筛求质数和

#include<iostream>
using namespace std;
const int maxn=10000000;
int n,size;
int prime[maxn+5];
bool vis[maxn+5];
int main(){
    cin>>n;
    size=0;
    for (int i=2;i<=n;++i) {
        if(!vis[i]){
            size=size+1;
            prime[size]=i;
        }
        for (int j=1;i*prime[j]<=n;++j){
            vis[i*prime[j]]=1;
            if (i%prime[j]==0) break;
        }
    }
    int sum=0;
    for(int i=1;i<=size;++i) sum= sum+prime[i];
    cout<<sum<<endl;
    return 0;
}

28. n>10000004会数组越界 {{ select(28) }}

• √
• ×

29. 输出结果可能等于1 {{ select(29) }}

• √
• ×

30. n=10000000输出≤1e7所有质数和 {{ select(30) }}

• √
• ×

31. 输出是≤n所有质数之和 {{ select(31) }}

• √
• ×

32. n=40输出质数和 {{ select(32) }}

• 820
• 197
• 196
• 217

33. 输出和在5e5~5e8之间，n量级 {{ select(33) }}

• 100~1000
• 1000~10000
• 10000~100000
• 100000~1000000

34. 筛法时间复杂度 {{ select(34) }}

• $O(n)$
• $O(n^2)$
• $O(n\log n)$
• $O(n\log\log n)$

三、完善程序（每题3分，共30分）

完善程序1 混合背包（多重/01/完全）

#include<iostream>
using namespace std;
int n,m,ans;
int f[1001],a[101],w[101],c[101];
int main(){
    cin>>m>>n;
    f[0]=0;
    for(int i=1;i<=m;①)
        f[i]=②;
    for (int i=1;i<=n;++i){
        cin>>tp[i]>>w[i]>>c[i];
        if(tp[i]==1) cin>>a[i];
        if(tp[i]==1){
            for (int j=1;j<=a[i];++j)
                for (int v=m;v>=w[i];--v)
                    f[v]=max(f[v],⑤);
        }
        else if (tp[i]==2){
            for (int v=m;v>=③;--v)
                f[v]=max(f[v],⑤);
        }
        else {
            for(④)
                f[v]=max(f[v],⑤);
        }
    }
    printf("%d",f[m]);
    return 0;
}

35. ① {{ select(35) }}

• i++
• i<=m
• i--
• i+=2

36. ② {{ select(36) }}

• 0
• 1
• -1
• 2147483647

37. ③ {{ select(37) }}

• m
• 0
• w[i]
• 1

38. ④ {{ select(38) }}

• int v=0;v<=m;++v
• int v=w[i];v<=m;++v
• int v=m;v>=w[i];--v
• int v=m;v>=0;--v

39. ⑤ {{ select(39) }}

• w[i]
• f[v-w[i]]+c[i]
• f[v-w[i]]
• f[v-c[i]]+w[i]

完善程序2 双向折半枚举背包

#include<iostream>
using namespace std;
const long long inf=①;
long long v[41];
long long w[41];
struct Item{
    long long value,weight,choose;
}itm[2][1<<20];
bool cmp1(Item a,Item b){
    return a.value <b.valuell(a.value==b.choose);
}
bool cmp2(Item a, Item b){
    return a.value<b.value ||(a.value ==b.choose);
}
int get_id(int n) {
    for(int i=0;;++i) if((n>>i))returni-1;
}
void sort (Item item[],int L,int R){
    if(L>=R)return;
    int x=rand()%(R-L+1)+L;
    swap (item[L],item[x]);
    int a=L+1,b=R;
    while (a<b){
        while (a<b && cmp1 (item[a],item[L])) ++a;
        while (a<b && ②) --b;
        swap (item[a],item[b]);
    }
    while (b<=R && item[b].value==item[L]) ++b;
    if (item[a].value<item[L].value) swap (item[a],item[L]);
    sort(item, L,a-1);
    sort(item, b,R);
}
int solve (int L,int R, Item item[]){
    item[0].value=0;
    item[0].choose=0;
    int len=③;
    for (int i=1;i<=len;++i){
        int tmp=④;
        item[i].value=item[i-tmp].value+v[L+get_id(tmp)];
        item[i].weight=item[i-tmp].weight+w[L+get_id(tmp)];
        if (item[i].value>inf) item[i].value=inf;
        item[i].choose=i;
    }
    sort (item, 0,len);
    return len;
}
int main(){
    int N;
    long long V,ans=0;
    cin>>N>>V;
    for(int i=1;i<=N;++i) cin>>v[i]>>w[i];
    int len1=solve (1,N/2,itm[0]);
    int len2=solve (N/2+1, N, itm[1]);
    for(int i=1;i<=len2;++i)
        itm[1][i].value=max(itm[1][i].value,itm[1][i-1].value);
    long long choose=0;
    for(int i=0;i<=len1;++i){
        while (len2>=0 && itm[0][i].weight+itm[1][len2].weight>V)
            --len2;
        if (len2>=0){
            long long new_val =itm[0][i].value+itm[1][len2].value;
            long long new_choose=⑤;
            if (ans==new_val) choose =max (choose, new_choose);
            if (ans<new_val){
                ans=new_val;
                choose =new_choose;
            }
        }
    }
    cout<<ans<<endl;
    for(int i=0;i<N;i++)
        if (choose &(1LL<<i)) cout<<i+1<<" ";
    cout<<endl;
    return 0;
}

40. ① {{ select(40) }}

• 1000000000000000LL
• 1LL
• 7LL
• 0xffLL

41. ② {{ select(41) }}

• cmp1(item[b],item[L])
• cmp1(item[L],item[b])
• cmp2(item[L],item[b])
• cmp2(item[b],item[L])

42. ③ {{ select(42) }}

• $(1<<R-L+1)-1$
• $1<<R-L+1$
• $(1<<R)-1$
• $1<<R$

43. ④ {{ select(43) }}

• i
• i&-i
• i+(i&-i)
• i-(i&-i)

44. ⑤ {{ select(44) }}

• itm[0][i].choose | itm[1][len2].choose
• itm[0][i].choose | (itm[1][len2].choose << N/2LL)
• itm[0][i].choose | (itm[1][len2].choose << N/2)
• itm[0][i].choose | (itm[1][len2].choose << N)