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

1. 选出数值最大的数 {{ select(1) }}

• $(2333)_{10}$
• $(999)_{16}$
• $(100011111111)_2$
• $2^{11}$

2. 微型计算机存取速度最快的存储部件 {{ select(2) }}

• 高速缓存
• 寄存器
• 外存储器
• 内存储器

3. 128KB等于多少二进制位 {{ select(3) }}

• $128\times1000$
• $128\times1000\times8$
• $128\times1024$
• $128\times1024\times8$

4. 空队列依次执行：入队、入队、入队、出队、入队、出队、出队、入队，最终队首 {{ select(4) }}

• a
• c
• d
• e

5. int x，清零二进制第0~k-1位，其余不变的运算 {{ select(5) }}

• $x \&= (1<<k)-1$
• $x |= (1<<k)-1$
• $x \&= \sim((1<<k)-1)$
• $x |= \sim((1<<k)-1)$

6. 19条边的二分图，最少顶点数 {{ select(6) }}

• 8
• 9
• 10
• 11

7. 字符串abede不同非空子串数量 {{ select(7) }}

• 15
• 14
• 17
• 16

8. 不稳定排序算法 {{ select(8) }}

• 桶排序
• 归并排序
• 冒泡排序
• 选择排序

9. 数字1~7可重复组成三位数，是3的倍数的个数 {{ select(9) }}

• 43
• 72
• 78
• 115

10. 快速排序最坏时间复杂度 {{ select(10) }}

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

11. 图灵国籍 {{ select(11) }}

• 中国
• 日本
• 英国
• 美国

12. n顶点m边邻接矩阵存储，DFS时间复杂度 {{ select(12) }}

• $O(n^2)$
• $O(m^2)$
• $O(nm)$
• $O(n+m)$

13. 1414最多拆成多少个不同正整数之和 {{ select(13) }}

• 50
• 51
• 52
• 53

14. 属于解释型编程语言 {{ select(14) }}

• C++
• Pascal
• C
• Python

15. NOI考场禁止自带物品 {{ select(15) }}

• 笔
• 纸
• 准考证
• 身份证

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

阅读程序1 异或计数

#include<bits/stdc++.h>
using namespace std;
int n,a[5000],c[65536];
int main(){
    cin>>n;
    for(int i=0;i<n;i++) cin>>a[i];
    for(int i=0;i<n;i++)
        for (int j=0;j<n;j++){
            if(i!=j) c[a[i]^a[j]]++;
        }
    int t=0;
    for(int i=0;i<=65535;i++){
        if(c[i]>c[t]) t=i;
    }
    cout<<t<<endl;
    return 0;
}

16. n必须小于5000否则运行错误 {{ select(16) }}

• √
• ×

17. 合法输入下输出一定是正整数 {{ select(17) }}

• √
• ×

18. a[i]超出0~65535一定越界报错 {{ select(18) }}

• √
• ×

19. i循环从1开始输出不变 {{ select(19) }}

• √
• ×

20. n=1000，a[i]=i输出 {{ select(20) }}

• 0
• 1
• 2
• 1000

21. 所有a[i]≤15，输出有几种可能 {{ select(21) }}

• 8
• 15
• 16
• 32

阅读程序2 组合数统计

#include<bits/stdc++.h>
#define N 100000
using namespace std;
int n,Fac[N+5],FacInv[N+5],MOD=1e9+7;
char s1[N+5],s2[N+5];
int C(int x,int y){
    return 1LL*Fac[x]*FacInv[y]%MOD*FacInv[x-y]%MOD;
}
int quick_pow(int x,int y){
    int t=1;
    while (y){
        if(y&1) t=1LL*t*x%MOD;
        x=1LL*x*x%MOD;
        y>>=1;
    }
    return t;
}
int main(){
    int T,Mx=0;
    scanf("%d",&T);
    while (T--){
        scanf("%d",&n);
        int t1=0,t2=0,ans=0;
        scanf("%s",s1);
        while (Mx<n){
            Mx++;
            Fac[Mx]=1LL*Fac[Mx-1]*Mx%MOD;
            FacInv[Mx]=quick_pow(Fac[Mx], MOD-2);
        }
        for (int i=0;i<n;i++) if(s1[i]=='1') t1++;
        scanf("%s",s2);
        for (int i=0;i<n;i++) if(s2[i]=='1') t2++;
        int i=0;
        while (t1+t2-i>n) i++;
        for(;i<=min(t1,t2);i++){
            ans+=C(n,t1+t2-2*i),ans%=MOD;
        }
        printf("%d\n");
    }
    return 0;
}

22. C函数调用一定x≥y≥0 {{ select(22) }}

• √
• ×

23. while结束后i=t1+t2-n {{ select(23) }}

• √
• ×

24. 交换两个统计循环答案不变 {{ select(24) }}

• √
• ×

25. s1、s2可用同一个数组存储 {{ select(25) }}

• √
• ×

26. T=1,n=7,s1=0101010,s2=110110输出 {{ select(26) }}

• 49
• 56
• 63
• 81

27. 整体时间复杂度 {{ select(27) }}

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

阅读程序3 记忆化组合模运算

#include<bits/stdc++.h>
#define mod 1926
using namespace std;
int a[2001][2001],pw[1005];
int DP(int n,int m){
    if (a[n][m]!=0) return a[n][m];
    if(n<m) return 0;
    if(n==m||m==0) return a[n][m]=1;
    if(m==1){
        a[n][m]=n%mod;
        return n%mod;
    }else {
        a[n][m]=(DP(n-1,m-1)+DP(n-1,m))%mod;
        return a[n][m];
    }
}
int main(){
    int q,n,m,ans;
    pw[0]=1;
    for(int i=1;i<=1005;i++) pw[i]=2LL*pw[i-1]%mod;
    while (q--){
        cin>>n>>m;
        ans = (pw[m+1]-2-m+mod) % mod;
        for(int j=n+1;j<=m;j++){
            ans--;
            for(int i=j+1;i<=m;i++)
                ans= (ans-DP(i,j)+mod) mod;
        }
        cout<<ans<<'\n';
    }
    return 0;
}

28. 去掉记忆化数组复杂度不变 {{ select(28) }}

• √
• ×

29. n,m≤2000程序必运行报错 {{ select(29) }}

• √
• ×

30. j=n+1改为j=n输出不变 {{ select(30) }}

• √
• ×

31. i=j+1改为i=j输出不变 {{ select(31) }}

• √
• ×

32. q=1,n=3,m=5输出 {{ select(32) }}

• 30
• 39
• 50
• 59

33. q=1,n=15,m=20输出 {{ select(33) }}

• 1799
• 604
• 710
• 1794

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

完善程序1 迷宫染色计数

#include<bits/stdc++.h>
const int mod=1000000007;
int n,m,k,cnt[50],a[1005][1005],f[1005][1005];
int dfs (int x,int y){
    if(y==m+1) return dfs (x+1,1);
    if(x==n+1) return 1;
    f[x][y]= ①;
    int S=n+m,num=0,mar=0,res=0,las=0;
    for (int i=1;i<=k;i++){
        if(!(f[x][y]&(1<<i-1))) ++num;
    }
    if(num< ②) return 0;
    if (a[x][y]==0){
        for (int i=1;i<=k;i++){
            if(③){
                if(mar){
                    res+=④,res%=mod;
                else {
                    mar=1; cnt[i]++;
                    f[x][y]|=1<<i-1;
                    las=dfs(x,y+1);
                    f[x]^=1<<i-1;
                    cnt[i]--;
                    res+=las; res%=mod;
                }
                continue;
            }
            cnt[i]++;
            f[x][y]|=1<<i-1;
            res+=dfs(x,y+1); res%=mod;
            f[x]^=1<<i-1;
            cnt[i]--;
        }
    } else {
        if (!(f[x][y] &(1<<a[x][y]-1))){
            f[x][y]|=1<<a[x][y];
            res+=dfs(x,y+1); res%=mod;
            f[x]^=1<<a[x][y];
        }
    }
    return res;
}
int main(){
    cin>>n>>m>>k;
    int vv=⑤;
    if(k<vv){puts("0");return0;}
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>a[i][j],cnt[a[i][j]]++;
    int ans=dfs(1,1);
    cout<<ans<<endl;
    return0;
}

34. ① {{ select(34) }}

• f[x+1][y]|f[x][y+1]
• f[x+1][y]&f[x][y+1]
• f[x-1][y]|f[x][y-1]
• f[x-1][y]&f[x][y-1]

35. ② {{ select(35) }}

• x+y
• x+y+1
• n+m-x-y
• n+m-x-y+1

36. ③ {{ select(36) }}

• !(f[x][y]&(1<<i))
• !(f[x][y]&(1<<i-1))
• f[x][y]&(1<<i)
• f[x][y]&(1<<i-1)

37. ④ {{ select(37) }}

• res
• num
• las
• S

38. ⑤ {{ select(38) }}

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

完善程序2 树轻重链剖+子树路径加，求加权重心

#include<bits/stdc++.h>
#define LL long long
const int N=1e5+10;
int dep[N],sz[N],mx[N],dfn[N],bk[N],top[N],f[N][21];
int fir[N],nxt[N<<1],son[N<<1],tot;
LL T[N<<2],tg[N<<1];
inline void Add(int x,int y){
    nxt[++tot]=fir[x]; son[tot]=y; fir[x]=tot;
    nxt[++tot]=fir[y]; son[tot]=x; fir[y]=tot;
}
void Dfs1(int x,int fa){
    f[x][0]=fa; sz[x]=1; dep[x]=dep[fa]+1;
    for(int i=fir[x];i;i=nxt[i]){
        if(son[i]==fa) continue;
        Dfs1(son[i],x); sz[x]+=sz[son[i]];
        if(sz[son[i]]>sz[mx[x]]) mx[x]=son[i];
    }
}
void Dfs2(int x,int Top){
    top[x]=Top; dfn[x]=++cnt; bk[cnt]=x;
    if(mx[x]) Dfs2(mx[x],Top);
    for(int i=fir[x];i;i=nxt[i])
        if(son[i]!=f[x][0] && son[i]!=mx[x]) Dfs2(son[i],son[i]);
}
void pushup(int x){ T[x]=T[x<<1]+T[x<<1|1]; }
void pushdown(int x,int l,int r){
    if(tg[x]){
        int mid=l+r>>1;
        T[x<<1]+=tg[x]*(mid-l+1);
        T[x<<1|1]+=tg[x]*(r-mid);
        tg[x<<1]+=tg[x]; tg[x<<1|1]+=tg[x];
        tg[x]=0;
    }
}
void Modify(int L,int R,int v,int x=1,int l=1,int r=n){
    if(L<=l && r<=R){ T[x]+=v; tg[x]+=v; return; }
    pushdown(x,l,r); int mid=l+r>>1;
    if(L<=mid) Modify(L,R,v,x<<1,l,mid);
    if(R>mid) Modify(L,R,v,x<<1|1,mid+1,r);
    pushup(x);
}
LL QuerySum(int L,int R,int x=1,int l=1,int r=n){
    if(L<=l && r<=R) return T[x];
    pushdown(x,l,r); int mid=l+r>>1;
    LL s=0;
    if(L<=mid) s+=QuerySum(L,R,x<<1,l,mid);
    if(R>mid) s+=QuerySum(x<<1|1,mid+1,r);
    return s;
}
int QueryG(LL k,int x=1,int l=1,int r=n){
    if(l==r) return ①;
    pushdown(x,l,r); int mid=l+r>>1;
    if(T[x<<1]>=k) return QueryG(k,x<<1,l,mid);
    else return QueryG(k-T[x<<1],x<<1|1,mid+1,r);
}
void Update(int x,int y){
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]]) swap(x,y);
        Modify(dfn[top[x]],dfn[x],1);
        x=f[top[x]][0];
    }
    if(dfn[x]>dfn[y]) swap(x,y);
    Modify(dfn[x],dfn[y],1);
}
int Query(){
    LL k=T[1]/2+1;
    int i=bk[QueryG(k)];
    while(true){
        bool flag=false;
        for(int j=20;~j;j--){
            if(f[i][j] && ②){
                i=f[i][j]; flag=true;
            }
        }
        if(!flag) break;
    }
    return i;
}
int main(){
    int n,m; cin>>n;
    for(int i=1;i<n;i++){ int x,y; cin>>x>>y; Add(x,y); }
    Dfs1(1,0); Dfs2(1,1);
    for(int j=1;j<=20;j++)
        for(int i=1;i<=n;i++) f[i][j]=f[f[i][j-1]][j-1];
    cin>>m;
    while(m--){
        int op,x; cin>>op>>x;
        if(op==1) Modify(dfn[x],dfn[x]+sz[x]-1,1);
        else { int y; cin>>y; Update(x,y); }
        cout<<Query()<<endl;
    }
    return 0;
}

39. ① {{ select(39) }}

• bk[1]
• 1
• bk[k]
• k

40. ② {{ select(40) }}

• QuerySum(dfn[f[i][j]],dfn[f[i]]+sz[f[i]]-1)>=k
• QuerySum(dfn[f[i][j]],dfn[f[i]]+sz[f[i]]>k
• i>=k
• f[i][0]>k