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

1. 下列关于NOIP的说法，错误的是 {{ select(1) }}

• NOIP中文名称为全国青少年信息学奥林匹克联赛，于2020年恢复举行
• 参加NOIP是参加NOI的必要条件，不参加NOIP将不具有参加NOI的资格
• NOIP竞赛全国前五十名将进入国家集训队
• 在NOIP复赛中，NOIP各省组织单位必须严格遵循CC《关于NOIP数据提交格式的说明》，赛后规定时间向CCF提交选手程序

2. 二进制001001与100101按位异或结果为 {{ select(2) }}

• 101000
• 100100
• 101101
• 101100

3. 8位二进制补码10101011表示的十进制数是 {{ select(3) }}

• 43
• -43
• -85
• -84

4. 下列不属于平衡树的数据结构是 {{ select(4) }}

• 线段树
• Splay树
• 替罪羊树
• 红黑树

5. 组合数与卡特兰相关说法错误的是 {{ select(5) }}

• $\binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1}$
• $0\le k\le2n$时$\binom{2n}{k}$在$k=n$取最大值
• 卡特兰数$C_n=\binom{2n}{n}/n$
• n个0、k个1无相邻1字符串方案数$\binom{n+1}{k}$

6. 有关CPU说法正确的是 {{ select(6) }}

• CPU负责转换驱动显示器画面
• CPU性能取决于主频与IPC，合并为IPS
• AMD是首家x86架构最大半导体厂商
• CPU自带3D图形加速，又称图形加速器

7. 未使用贪心思想的算法是 {{ select(7) }}

• Kruskal最小生成树
• Tarjan求点双连通分量
• Dijkstra单源最短路
• 以上均使用贪心

8. Bellman-Ford单源最短路最坏时间复杂度 {{ select(8) }}

• $O(|V||E|)$
• $O(V\log V)$
• $O(E\log E)$
• $O(E)$

9. g++开启-Ofast、C++11、保留调试，生成exec命令 {{ select(9) }}

• g++ prog.cpp -Ofast exec -std=c++11 -debug
• g++ prog.cpp -Ofast exec -std=c++11 -g
• g++ prog.cpp -o exec -Ofast -std=c++11 -debug
• g++ prog.cpp -o exec -Ofast -std=c++11 -g

10. α袋4张5元3张1元；β袋2张10元3张1元；γ袋3张20元3张50元；每袋随机丢弃2张，满足$v_\alpha<v_\beta<v_\gamma$概率 {{ select(10) }}

• $\frac{8}{35}$
• $\frac{9}{35}$
• $\frac{11}{35}$
• $\frac{12}{35}$

11. Hackenbush博弈说法正确的是 {{ select(11) }}

• 无绿色边一定无先手必胜局面
• 不存在后手必胜局面
• 无红绿边问题仍是NP-Hard
• 无绿色边为P类问题

12. 斯特林数$f_n$相关正确的是 {{ select(12) }}

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

13. 递归$T(n)=k\sqrt{n}T(\sqrt{n})+n$说法正确 {{ select(13) }}

• k=1时$T(n)=O(n\log n)$
• k=1时$T(n)=O(n\log^2 n)$
• k=4时$T(n)=O(n\log n)$
• k=4时$T(n)=O(n\log^2 n)$

14. 完全图$K_4$删一条边后Tutte多项式为 {{ select(14) }}

• $x^{3}+2 x^{2}+x+2 x y+y+y^{2}$
• $x^{3}+x^{2}+x+2 x y+y+y^{2}$
• $x^{3}+2 x^{2}+2 x+2 x y+y+y^{2}$
• $x^{3}+x^{2}+2 x+2 x y+y+y^{2}$

15. 满足$k!=\prod_{i=0}^{n-1}(2^n-2^i)$正整数对$(k,n)$个数 {{ select(15) }}

• 1
• 2
• 3
• 4

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

阅读程序1 奇偶下标求和取模

#include<cstdio>
#include<vector>
const int mod=1e9+7;
std::vector<int>vec;
inline int inc(int x,int y)
{x+=y-mod;return x+(x>>31 &mod);}
inline int mul(int x,int y){return 1ll*x*y%mod;}
int main()
{
    int n;
    scanf("%d",&n);
    vec.push_back(0);
    for(int i=1;i<=n;++i)
    {
        int x;
        scanf("%d",&x);
        vec.push_back(x);
    }
    int ans=0;
    for(int i=1;i<=n;++i)
        if(i&1)
            for(int j=i;j<=n;j+=i)
                ans =inc (ans, mul (vec[i],vec[j]));
    printf("%d\n",ans);
    return 0;
}

16. vec.push_back(x)向容器尾部插入元素 {{ select(16) }}

• √
• ×

17. $0\le i\le2^{31}-1$时i&1等价i%2 {{ select(17) }}

• √
• ×

18. 运算存在int溢出风险 {{ select(18) }}

• √
• ×

19. inc返回$(x+y)\bmod (10^9+7)$ {{ select(19) }}

• √
• ×

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

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

21. 说法错误的是 {{ select(21) }}

• 空间复杂度$O(n)$
• push_back(0)因为vector下标从0开始
• inc参数改为long long仍正确
• $(x-y)\bmod mod$可用inc(x, mod-y)

阅读程序2 最小生成树Prim类实现

#include<bits/stdc++.h>
const int N=1e6+50;
int n,m,min[N],out[N],f[N],siz[N],ans;
struct edge
{
    int u,v,w;
}e[N];
inline int find(int x)
{
    while(x!=f[x])
        x=f[x]=f[f[x]];
    return x;
}
inline void merge(int x,int y)
{
    if (siz[x]>siz[y]) std::swap (x,y);
    f[x]=y;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)
    {
        f[i]=i,siz[i]=1;
    }
    for(int i=1;i<=m;++i)
    {
        scanf("%d%d",&e[i].u,&e[i].v,&e[i].w);
    }
    int components=n;
    while (components>1)
    {
        memset (min, 0x3f,sizeof (min));
        for(int i=1;i<=m;++i)
        {
            int u=find(e[i]),v=find(e[i]),w=e[i].w;
            if(u!=v)
            {
                if (w<min[u]) min[u]=w,out[u]=v;
                if (w<min[v]) min[v]=w,out[v]=u;
            }
        }
        for(int i=1;i<=n;++i)
        {
            int x=find(i);
            if(out[x])
            {
                int y=find(out[x]);
                if(x!=y)
                {
                    merge (x,y);
                    ans+=min[x];
                    --components;
                }
            }
        }
    }
    printf("%d",ans);
    return 0;
}

22. 程序实现无向图最小生成树 {{ select(22) }}

• √
• ×

23. 使用邻接矩阵存图 {{ select(23) }}

• √
• ×

24. 输入所有边权互不相同才正确 {{ select(24) }}

• √
• ×

25. 任意合法输入有限步结束 {{ select(25) }}

• √
• ×

26. components运行最小值 {{ select(26) }}

• 1
• 0
• $\lfloor n/2\rfloor$
• $m-(n-1)$

27. 程序时间复杂度 {{ select(27) }}

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

阅读程序3 树双向链表哈密顿序列

#include<bits/stdc++.h>
const int N=2e6+50;
int n,head[N],nxt[N],ver[N],dep[N],prv[N],suc[N],cnt;
inline void add(int u,int v)
{
    nxt[++cnt] =head[u],ver[cnt]=v, head[u]=cnt;
}
void dfs (int u,int fa)
{
    dep[u]=dep[fa]+1;
    for (int i=head[u];i;i=nxt[i])
        if(ver[i]!=fa) dfs (ver[i],u);
}
void solve (int u,int fa,bool rv=false)
{
    int isLeaf=true,t=u;
    for (int i=head[u];i;i=nxt[i])
    {
        int y=ver[i];
        if(y!=fa)
        {
            isLeaf=false;
            solve (y,u,rv^1);
            if(rv)
            {
                int mp=prv[y];
                suc[t]=y,prv[y]=t,t=mp;
            }
            else
            {
                suc[t]=suc[y];
                prv[suc[y]]=t;
                suc[t]=0;
            }
        }
    }
    if (isLeaf) suc[u]=prv[u]=u;
    else suc[t]=u,prv[u]=t;
}
int main()
{
    scanf("%d",&n);
    for(int i=1,u,v;i<n;++i)
    {
        scanf("%d%d",&u,&v);
        add (u,v);add (v,u);
    }
    dfs(1,1);
    solve (1,-1);
    printf("1");
    int p=1,v=suc[p];
    while (v!=p)
    {
        printf("%d",v);
        v=suc[v];
    }
    return 0;
}

28. 输入为一棵树 {{ select(28) }}

• √
• ×

29. dfs计算节点深度存入dep {{ select(29) }}

• √
• ×

30. solve用BFS构造路径 {{ select(30) }}

• √
• ×

31. 输出长度为n的排列 {{ select(31) }}

• √
• ×

32. 输入8条边1-2/2-3/3-4/4-5/5-6/6-7/7-8输出 {{ select(32) }}

• 13875642
• 13786542
• 13875624
• 13786524

33. 图G'与路径描述正确 {{ select(33) }}

• $d_G(u,v)\le2$，哈密顿路径
• $d_G(u,v)\le2$，欧拉路径
• $d_G(u,v)\le3$，哈密顿路径
• $d_G(u,v)\le3$，欧拉路径

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

完善程序1 树k阶线图点数

#include<bits/stdc++.h>
const int N=5e3+7;
int n,k,d[N];
std::vector<int>p[N];
bool e[N][N];
int main(){
    scanf("%d",&n,&k);
    --n;
    for(int i=1,x,y;i<=n;i++)
    {
        scanf("%d",&x,&y);
        for (int j:p[x]) e[i][j]=e[j][i]=1;
        for (int j:p[y]) e[i][j]=e[j][i]=;
        ①;
    }
    int ans=0;
    if(k==2)
    {
        for (int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        ②;
    }
    else if(k==3)
    {
        for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++) d[i]+=e[i][j];
        for(int i=1;i<=n;i++) ③;
    }
    else if(k==4)
    {
        for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++) d[i]+=e[i][j];
        for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        if(e[i][j])
            ④;
        ans/=4;
    }
    else if(k==5)
    {
        for(int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)d[i]+=e[i][j];
        static int c[N][N];
        for(int i=1;i<=n;i++)
        {
            int x1=0,x2=0;
            for (int j=1;j<=n;j++) if(e[i][j])
                c[i][j]=d[i]+d[j]-3,
                x1+=c[i][j],x2+=c[i]*c[i];
            for (int j=1;j<=n;j++)
            if(e[i][j])
                ans+=⑤;
        }
        ans/=4;
    }
    printf("%d",ans);
    return 0;
}

34. ① {{ select(34) }}

• p[x].push_back(i), p[y].push_back(i)
• p[x].push_back(y), p[y].push_back(x)
• p[i].push_back(x), p[i].push_back(y)
• p[x].push_back(y), p[i].push_back(x)

35. ② {{ select(35) }}

• ans+=e[i][j]
• ans+=e[i][j]*2
• ans+=n-e[i][j]
• ans+=n-e[i]*2

36. ③ {{ select(36) }}

• $ans +=d[i]*(d[i]+1)/2$
• $ans +=d[i]*(d[i]-1)/2$
• $ans +=d[i]*(d[i]+1)$
• $ans +=d[i]*(d[i]-1)$

37. ④ {{ select(37) }}

• $ans +=(d[i]+d[j])*(d[i]+d[j]-1)$
• $ans +=(d[i]+d[j]-1)*(d[i]+d[j]-2)$
• $ans +=(d[i]+d[j]-2)*(d[i]+d[j]-3)$
• $ans +=(d[i]+d[j]-3)*(d[i]+d[j]-4)$

38. ⑤ {{ select(38) }}

• $ans +=(d[i]+d[j])*(d[i]+d[j]-1)$
• $ans +=(d[i]+d[j]-1)*(d[i]+d[j]-2)$
• $ans +=(d[i]+d[j]-2)*(d[i]+d[j]-3)$
• $ans +=(d[i]+d[j]-3)*(d[i]+d[j]-4)$

完善程序2 区间二分图染色计数

#include<bits/stdc++.h>
const int N=5e6+50;
const int mod=998244353;
int n,top,head[N],nxt[N],ver[N],col[N],cnt;
std::pair<int,int>stack[N];
struct seg
{
    int l,r;
}p[N];
inline void add(int u,int v)
{
    nxt[++cnt]=head[u], ver[cnt]=v,head[u]=cnt;
    nxt[ ++cnt]=head[v],ver[cnt]=u,head[v]=cnt;
}
bool dfs(int x,int c)
{
    if(①)return col[x]==c;
    col[x]=c;
    for (int i=head[x];i;i=nxt[i])
    if (dfs (ver[i],c^1)==false)
        return false;
    return true;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i) scanf("%d%d",p[i].l,p[i].r);
    std::sort(p+1,p+n+1,[](seg u,seg v)
    {
        return ②;
    });
    for(int i=1;i<=n;i++)
    {
        while (top>0 && ③)
            add (stack[top--].second, i);
        stack[ ++top]=std::make_pair (p[i].r,i);
    }
    memset (col, -1, sizeof col);
    int ans=1;
    for(int i=1;i<=n;++i)
    if(col[i]==-1)
    {
        if (dfs(i,0)==false) return printf("0"),0;
        ④;
    }
    int mx[2];mx[0]=mx[1]=0;
    for(int i=1;i<=n;i++)
    {
        if(⑤)return printf("0"),0;
        mx[col[i]]=p[i].r;
    }
    printf("%d",ans);
    return 0;
}

39. ① {{ select(39) }}

• col[x] & 1
• col[x] != -1
• !col[x]
• ~col[x]

40. ② {{ select(40) }}

• u.l<v.l
• u.l>v.l
• u.r<v.r
• u.r>v.r

41. ③ {{ select(41) }}

• stack[top].first < p[i].l
• stack[top].first > p[i].l
• stack[top].first < p[i].r
• stack[top].first > p[i].r

42. ④ {{ select(42) }}

• ans += 1
• ans *= ans
• ans /= 2
• ans *= 2

43. ⑤ {{ select(43) }}

• mx[col[i]] > p[i].l
• mx[col[i]] > p[i].r
• col[i] > p[i].l
• col[i] > p[i].r