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

1. 以下哪一位是图灵奖得主？ {{ select(1) }}

• 特朗普
• 拜登
• 图灵
• 姚期智

2. 下列属于图像文件格式的有 {{ select(2) }}

• WMV
• MPEG
• JPEG
• AVI

3. 欧拉图C是指可以构成一个闭回路的图，且图C的每一条边恰好在这个闭回路上出现一次（即一笔画成）。在以下各个描述中，不一定是欧拉图的是 {{ select(3) }}

• 图C中没有度为奇数的顶点
• 包含欧拉环游的图（欧拉环游是指通过图中每边恰好一次的闭路径）
• 包含欧拉闭迹的图（欧拉闭迹是指通过图中每边恰好一次的路径）
• 存在一条回路，通过每个顶点恰好一次

4. 设 $A=B= \text{true}$，$C=D= \text{false}$，以下逻辑运算表达式值为false的是 {{ select(4) }}

• $(A \land B)\lor(C \land D \lor A)$
• $\neg(((A \land B) \lor C) \land D)$
• $A \land (B \lor C \lor D) \lor D$
• $(A \land (D \lor C)) \land B$

5. 以下图中一定可以进行黑白染色（相邻结点颜色不同） {{ select(5) }}

• 基环树
• 完全图
• 树
• 弦图

6. 与二进制小数0.1相等的十六进制数是 {{ select(6) }}

• 0.8
• 0.4
• 0.2
• 0.1

7. TCP协议属于哪一层协议 {{ select(7) }}

• 应用层
• 传输层
• 网络层
• 数据链路层

8. 汇编语言 {{ select(8) }}

• 是一种与具体硬件无关的程序设计语言
• 和汉语、英语并称为世界三大语言
• 可以直接访问寄存器、内存单元、I/O端口
• 随着高级语言的诞生，如今已被完全淘汰，不再使用

9. 某程序有一个大小为N的int数组a[N]，程序对这个数组做 $M(M<N)$ 次赋值操作，每次操作将均匀随机一个[1,N]的正整数X，以及一个int范围内整数Y，将所有X的倍数下标赋值为Y，求程序期望时间复杂度 {{ select(9) }}

• $O(M \log N)$
• $O(M \log_2 M)$
• $O(N \ln N)$
• $O(MN)$

10. 下列二进制数中，与1101001异或后数值最大的是 {{ select(10) }}

• 0011010
• 0010111
• 1011001
• 1000111

11. 下列问题目前不属于P问题的是 {{ select(11) }}

• 最长公共子串问题
• 旅行商问题
• 二维凸包问题
• 最长上升子序列问题

12. 填6位彩票，前导0允许，一等奖全同、二等奖恰1位不同、三等奖恰2位不同，得奖概率 {{ select(12) }}

• $\frac{13}{40000}$
• $\frac{111}{1000000}$
• $\frac{127}{100000}$
• $\frac{17}{40000}$

13. 表达式 $75 \% 4 + 1$ 的值是 {{ select(13) }}

• 2
• 3
• 5
• 7

14. 下列不属于面向对象语言 {{ select(14) }}

• C++
• Visual Basic
• Java
• C

15. 某进制下 $7*7=41$，该进制 $12*12=$ {{ select(15) }}

• 100
• 144
• 164
• 196

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

阅读程序1

#include<bits/stdc++.h>
using namespace std;
int n,ans=0;
int a[21],sum[21];
void print(){
    ans++;
    for(int i=0;i<n;i++) cout<<a[i];
    puts("");
}
void check(){
    memset(sum,0,sizeof(sum));
    for(int i=0;i<n;i++) sum[a[i]]++;
    for(int i=0;i<n;i++) if(a[i]!=sum[i]) return;
    print();
}
void dfs(int x){
    for(int i=0;i<=n;i++){
        a[x]=i;
        if(x==n-1) check();
        else dfs(x+1);
    }
}
int main(){
    cin>>n;
    dfs(0);
    cout<<ans;
    return 0;
}

16. 将print内a[i]替换为sum[i]，输出改变 {{ select(16) }}

• √
• ×

17. 执行print时a[0]一定是正整数 {{ select(17) }}

• √
• ×

18. print执行时a[0]~a[n-1]总和等于n {{ select(18) }}

• √
• ×

19. 仅当$n \le 3$时ans=0 {{ select(19) }}

• √
• ×

20. 程序时间复杂度最接近 {{ select(20) }}

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

21. ans最大取值 {{ select(21) }}

• 1
• 2
• 4
• 5

阅读程序2

#include<iostream>
using namespace std;
int n,a[1000];
int main()
{
    cin>>n;
    for (int i=0;i<n;i++)cin>>a[i];
    int sum=0;
    for(int i=0;i<n;i++)
        for(int j=i+1;j<n;j++)
            if (a[i]<a[j]) sum++;
    cout<<sum<<endl;
    return 0;
}

22. n>1000数组越界报错 {{ select(22) }}

• √
• ×

23. 程序求逆序对数量 {{ select(23) }}

• √
• ×

24. 合法输入sum不可能为0 {{ select(24) }}

• √
• ×

25. 算法时间复杂度 {{ select(25) }}

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

26. j=i+1改为哪一行输出不变 {{ select(26) }}

• j=0
• j=i
• j=i-1
• j=n

27. 输入5换行4 2 3 5 1，输出 {{ select(27) }}

• 3
• 4
• 5
• 6

阅读程序3

#include<bits/stdc++.h>
using namespace std;
const int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
bitset<1602>a[1602];
bitset<1602>b[1602];
int n,m,len;
inline void qz(int x,int y)
{
    for(int k=0;k<4;k++){
        int tx=x+dir[k][0];
        int ty=y+dir[k][1];
        if(tx<1||ty<1||tx>n||ty>m)continue;
        b[(x-1)*m+y][(tx-1)*m+ty]=0;
        b[(tx-1)*m+y][(x-1)*m+y]=0;
    }
    b[(x-1)*m+y][len+1]=1;
}
inline bool chk()
{
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            int cnt=b[(i-1)*m+j][len+1];
            for(int k=0;k<4;k++){
                int tx=i+dir[k][0];
                int ty=j+dir[k][1];
                if(tx<1||ty<1||tx>n||ty>m) continue;
                cnt+=b[(tx-1)*m+ty][len+1];
            }
            if (cnt&1) return false;
        }
    }
    return true;
}
int main(){
    srand(time(NULL));
    scanf("%d%d", &n, &m);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            a[(i-1)*m+j][(i-1)*m+j]=1;
            for(int k=0;k<4;k++){
                int tx=i+dir[k][0];
                int ty=j+dir[k][1];
                if(tx<1||ty<1||tx>n||ty>m) continue;
                a[(i-1)*m+j][(tx-1)*m+ty]=1;
            }
        }
    }
    len=n*m;
    bool flag=false;
    while(flag==false)
    {
        int x=rand()%n+1;
        int y=rand()%m+1;
        for(int i=1;i<=len;i++)
            for(int j=1;j<=len+1;j++)b[i][j]=a[i][j];
        q(x,y);
        flag=true;
        for(int i=1;i<=len;i++){
            int mx_pos=0;
            for(int j=i;j<=len;j++){
                if(b[j][i]>b[mx_pos][i])mx_pos=j;
            }
            swap(b[i],b[mx_pos]);
            for(int j=1;j<=len;j++){
                if(i==j) continue;
                b[j]^=b[i];
            }
        }
        if(!chk())flag=false;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            printf("%d", (int)b[(i-1)*m+j][len+1]);
            putchar((j==m)?'\n':' ');
        }
    }
    return 0;
}

28. 程序可能死循环 {{ select(28) }}

• √
• ×

29. 程序可能输出全1矩阵 {{ select(29) }}

• √
• ×

30. printf去掉(int)强制转换仍可编译 {{ select(30) }}

• √
• ×

31. n=5,m=5输出矩阵第3行第4列一定为0 {{ select(31) }}

• √
• ×

32. n=2,m=39，合法且1的数量为40的本质不同矩阵数量 {{ select(32) }}

• 0
• 1
• 2
• 3

33. n=3,m=5，qz(3,2)固定后可能输出矩阵 {{ select(33) }}

• 10001 11011 10001
• 01010 11111 01010
• 00111 01010 11100
• 无输出，死循环

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

完善程序1 放鞭炮贪心二分

#include<bits/stdc++.h>
#define LL long long
#define pb push_back
#define Sz(x)((int)x.size()-1)
#define ms(a,b) memset(a,b,sizeof a)
#define F(i,a,b)for(inti=(a);i<=(b);++i)
#define DF(i,a,b)for(inti=(a);i>=(b);--i)
inline int read(){
    char ch=getchar();int w=1,c=0;
    for(;!isdigit(ch);ch=getchar())if (ch=='-') w=-1;
    for(;isdigit(ch);ch=getchar())c=(c<<1)+(c<<3)+(ch^48);
    return w*c;
}
const int M=2e5+10;
int n,m,a,b,s[M];
void work(){
    n=read();m=read();a=read();b=read();
    if(a>b){
        a= ①;
        b=n-b+1;
    }
    F(i,1,m){ s[i]=read(); }
    int tim=2,num=min (b-a-1,m);
    sort(s+1,s+m+1);
    int l=0,r=num,ans=0;
    while (l<=r){
        int mid=(l+r)>>1;
        bool fl= ②;
        F(i,1,mid){
            int st= ③;
            if(st+s[i]>tim)fl=1;
        }
        if(fl)r=mid-1;
        else l=mid+1,ans= ④;
    }
    cout<<ans<<"\n";
}
int main(){
    int T=read();
    while (T--) work();
    return 0;
}

34. ① {{ select(34) }}

• n-a
• n-a+1
• a-n
• a+1

35. ② {{ select(35) }}

• 2
• 1
• 0
• 3

36. ③ {{ select(36) }}

• mid-i+1
• 1
• i+1
• mid-i

37. ④ {{ select(37) }}

• mid
• 1
• r
• mid+1

完善程序2 树链剖分维护路径边权

#include<bits/stdc++.h>
using namespace std;
struct edge{int nxt,to;}e[100001<<1];
int ans,l,r,tag,len;
struct tree{
    tree()(ans=l=r=tag=len=0;)
}t[100001<<2];
int son[100001],id[100001],cnt,top[100001];
int n,m,tot, h[100001],dep[100001], fa[100001],s[100001];
void add(int x,int y){
    nxt[++tot]=h[x];
    e[tot].to=y;
    h[x]=tot;
}
int ls(int k){return k<<1;}
int rs(int k){return k<<1|1;}
tree mer(tree x,tree y){
    tree res;
    res.ans=x.ans+y.ans;
    if( ⑤ )++res.ans;
    res.len=x.len+y.len;
    res.l=x.l;res.r=y.r;
    return res;
}
void pp(int k){t[k]=mer(t[ls(k)],t[rs(k)]);}
void pd(int k) {
    if(t[k].tag){
        t[ls(k)].ans=t[ls(k)].len-1;
        t[rs(k)].ans=t[rs(k)].len-1;
        t[ls(k)].l=t[ls(k)].r=t[ls(k)].tag=t[k].tag;
        t[rs(k)].l=t[rs(k)].r=t[rs(k)].tag=t[k].tag;
        t[k].tag=0;
    }
}
void bld(int k,int l,int r){
    t[k].len=2;t[k].tag=t[k].ans=0;
    if(l==r){t[k].l=t[k].r=1;return;}
    int mid=(l+r)>>1;
    bld(ls(k),l,mid) ;bld(rs(k),mid+1,r);
    pp(k);
}
void upd(int nl,int nr,int l,int r,int k,int p)
{
    if(l>=nl&&r<=nr){
        t[k].ans= ⑥;
        t[k].l=t[k].r=t[k].tag=p;
        return;
    }
    pd(k);
    int mid=(l+r)>>1;
    if (nl<=mid) upd(nl,nr,l,mid,ls(k),p);
    if (nr>mid) upd(nl,nr,mid+1,r,rs(k),p);
    pp(k);
}
tree qry(int nl,int r,int l,int r,int k){
    if(l>=nl&&r<=nr)return t[k];
    pd(k);
    int mid=(l+r)>>1;
    if (nr<=mid) return qry(nl,nr,l,mid, ls(k));
    if (nl>mid) return qry(nl,nr,mid+1,r,rs(k));
    return ⑦;
}
void dfs1(int k,int f,int deep){
    dep[k]=deep;fa[k]=f;s[k]=1;son[k]=0;int maxson =-1;
    for(int i=h[k];i;i=e[i].nxt){
        if(e[i].to==f)continue;
        dfs1(e[i].to, k,deep+1);
        s[k]+=s[e[i].to];
        if (s[e[i].to]>maxson){
            maxson =s[e[i]]; son[k]=e[i];
        }
    }
}
void dfs2(int k,int t){
    id[k]=++cnt;top[k]=t;
    if(!son[k])return;
    dfs2 (son[k],t);
    for(int i=h[k];i;i=e[i].nxt){
        if(e[i].to!=fa[k]&&e[i].to!=son[k])
            dfs2 (e[i],e[i]);
    }
}
void up(int x,int y,int p){
    while (top[x]!=top[y]){
        if (dep[top[x]]<dep[top[y]]) swap(x,y);
        upd(id[top[x]],id[x],1,n,1,p);
        x=fa[top[x]];
    }
    if (dep[x]>dep)swap(x,y);
    upd(id[x],id[y],1,n,1,p);
}
int LCA(int x,int y){
    while (top[x]!=top[y]){
        if (dep[top[x]]<dep[top[y]])swap(x,y);
        x=fa[top[x]];
    }
    if (dep[x]>dep)swap(x,y);
    return x;
}
int get(int x,int lca){
    tree res;
    while (top[x]^top[lca]){
        res= ⑧;
        x=fa[top[x]];
    }
    res =mer (qry(id[lca],id[x],1,n,1),res);
    return res.ans;
}
int q(int x,int y){
    int lca=LCA(x,y);
    return get(x, lca)+get(y,lca);
}
int main(){
    scanf("%d%d", &n, &m);
    for(int i=1;i<n;++i){
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y);add(y,x);
    }
    dfs1 (1,0,1);dfs2 (1,1);bld(1,1,n);
    for(int i=1;i<=m;++i){
        int opt,x,y;
        scanf("%d%d%d",&opt,&x,&y);
        if(opt==1)up(x,y,i+n);
        if(opt==2)printf("%d\n",q(x,y));
    }
    return 0;
}

38. ⑤ {{ select(38) }}

• x.l==y.l
• x.l==y.r
• x.r==y.l
• x.r==y.r

39. ⑥ {{ select(39) }}

• r-1
• r-l+1
• r-l+2
• 1-r

40. ⑦ {{ select(40) }}

• qry(nl,nr,l,mid, ls(k)).ans+qry(nl,nr,mid+1,r,rs(k)).ans
• mer(qry(nl,nr,l,mid,ls(k)),qry(nl,nr,mid+1,r,rs(k)))
• qry(nl,nr,l,mid ,ls(k)).ans
• qry(nl,nr,mid+1,r,rs(k)).ans

41. ⑧ {{ select(41) }}

• mer(qry(id[x],id[top[x]],1,n),res)
• mer(qry(id[x],id[lca],1,n),res)
• mer(qry(id[lca],id[x],1,n),res)
• mer(qry(id[top[x]],id[x],1,n)