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

1. 选出能够被3整除的数。 {{ select(1) }}

• $(14)_6$
• $(29)_{12}$
• $(4)_8$
• $(7^4)_9$

2. 运行计算机程序，必须将程序装入。 {{ select(2) }}

• CPU
• 硬盘
• 内存
• U盘

3. 入栈序列1,9,4,3,6，不可能的出栈序列。 {{ select(3) }}

• 6,3,4,9,1
• 1,4,9,3,6
• 9,4,6,3,1
• 3,4,1,6,9

4. 以下IP地址一定指向本机。 {{ select(4) }}

• 172.0.0.1
• 192.168.1.1
• 127.0.0.1
• 0.0.0.0

5. 递推式 $T(N)=4 T(N / 2)+N^{2} log ^{2} N,\ T(1)=1$，时间复杂度。 {{ select(5) }}

• $O\left(N^{3}\right)$
• $O\left(N^{2} log N\right)$
• $O\left(N^{2} log ^{2} N\right)$
• $O\left(N^{2} log ^{3} N\right)$

6. 不属于基于比较的排序算法。 {{ select(6) }}

• 堆排序
• 基数排序
• 希尔排序
• 插入排序

7. 女主人+5男4女圆桌男女交替就坐方案数。 {{ select(7) }}

• 2880
• 3600
• 2160
• 3000

8. 集合$N^*$与哪种运算无法构成群。 {{ select(8) }}

• 加法
• 减法
• 乘法
• 幂

9. 根高度为1，高4的线段树最少节点数。 {{ select(9) }}

• 16
• 15
• 9
• 8

10. C++98标准下行为不是未定义行为。 {{ select(10) }}

• 未初始化int变量
• i=i++
• 函数多参数求值顺序不确定
• 变量作为数组长度

11. 二叉树先序遍历ABDEFC。 {{ select(11) }}

• ABDEFC
• DBEFAC
• DFEBCA
• ABCDEF

12. $O(N)$、$\Omega(N)$分别代表。 {{ select(12) }}

• 上界、既是上界也是下界
• 上界、下界
• 下界、既是上界也是下界
• 下界、下界

13. 四个不同点简单无连通图总个数。 {{ select(13) }}

• 32
• 35
• 38
• 41

14. $4^{116} \bmod 113$余数。 {{ select(14) }}

• 30
• 16
• 60
• 120

15. 关于树描述正确。 {{ select(15) }}

• 所有节点入度均为1
• 重链剖分每条重链长度不超过$\log_2 n$
• 出度大于$\sqrt{n}$的节点不超过$\sqrt{n}$个
• 两点LCA的dfs序一定大于两点dfs序

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

阅读程序1 快速幂取模

#include<iostream>
using namespace std;
int fastpow(int a,int b,int p){
    int ans=1;a=a%p;
    for(int i=0;i<=31;i++){
        if(b &(1<<i)) ans=ans*a%p;
        a=a*a%p;
    }
    return ans;
}
int main(){
    int a,b,p;
    cin>>a>>b>>p;
    cout<<fastpow (a,b,p);
    return 0;
}

16. 第7、8行a*a两侧加括号无必要。 {{ select(16) }}

• √
• ×

17. 交换7、8行代码输出不变。 {{ select(17) }}

• √
• ×

18. 将循环上限缩小至10，任意a,p输入结果仍正确。 {{ select(18) }}

• √
• ×

19. 缩小p范围不影响答案正确性。 {{ select(19) }}

• √
• ×

20. a=2,b=15，输出不可能为。 {{ select(20) }}

• 16068
• 16086
• 16049
• 16091

21. 说法正确的是。 {{ select(21) }}

• 答案与a奇偶性一定相同
• a变小输出一定变小
• a=2且b≤30结果一定正确
• 算法复杂度$O(log^2 n)$

阅读程序2 可一段乘x的最大连续子段和

#include<iostream>
using namespace std;
int main(){
    int n,x;
    cin>>n>>x;
    int a=0,b=0,c=0,na,nb,nc,ans=0;
    for(int i=1;i<=n;i++){
        int now;
        cin>>now;
        na =max (a+now,0);
        nb =max(max (a+now*x,b+now*x),0);
        nc =max (c+now,b+now,0);
        a=na,b=nb,c=nc;
        ans =max (max (ans,a),max (b,c));
    }
    cout<<ans;
    return 0;
}

22. 程序共输入n+3个数字。 {{ select(22) }}

• √
• ×

23. 朴素无优化DP。 {{ select(23) }}

• √
• ×

24. 变量a代表前i个最大连续子序列和。 {{ select(24) }}

• √
• ×

25. 给定范围int可能溢出出错。 {{ select(25) }}

• √
• ×

26. 程序对应题意。 {{ select(26) }}

• 序列可将一段全部乘x，求最大连续子段和
• 最多x个元素加x求最大子段
• 任意元素加x求最大子段
• 长度不超过x的最长子段和

27. 输出结果最大输入组。 {{ select(27) }}

• 5 3 1 2 0 -2 5
• 3 10 1 -2 1
• 7 1 1 2 -1 1 2 -1 5
• 6 -1 1 2 3 4 5 6

阅读程序3 状压DP最长哈密顿路

#include<bits/stdc++.h>
using namespace std;
typedef long long int_t;
int_t dis[1<<18][18];
struct E{
    int_t to,w;
    E(int_t to, int_t w):to(to),w(w){}
};
vector<E>G[20];
int_t dfs (int_t rt,int_t vised, int_t n){
    if(rt==n-1) return 0;
    if(dis[vised][rt]) return dis[vised][rt];
    dis[vised][rt]=-998244353;
    for (Ee: G[rt]){
        int_t to=e.to,w=e.w;
        if((1<<to) &vised) continue;
        dis[vised][rt]=max(dis[vised][rt],dfs (to,vised|(1<<to),n) +w);
    }
    return dis[vised][rt];
}
int main(){
    int_t n,m;cin>>n>>m;
    while (m--){
        int_t u,v,w;
        cin>>u>>v;
        G[u].push_back (E(v,w));
    }
    cout<<dfs (0,1,n);
    return 0;
}

28. NOIP标准可编译。 {{ select(28) }}

• √
• ×

29. 可处理重边自环。 {{ select(29) }}

• √
• ×

30. 可使用Dijkstra替代该算法。 {{ select(30) }}

• √
• ×

31. 错误说法。 {{ select(31) }}

• 31行为u添加边(v,w)
• 删除17行复杂度不变
• 删除21行会死循环
• 19遍历rt所有出边

32. 输入：3条边 0 2 5 / 0 1 4 / 1 2 3，输出。 {{ select(32) }}

• 3
• 5
• 7
• 8

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

• $O\left(n^{2}+m\right)$
• $O(2^n+m)$
• $O(2^n(n+m))$
• $O\left(n^{2} log n+m\right)$

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

完善程序1 QQ禁言贪心

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5;
int big[MAXN],small[MAXN], sum[MAXN];
int p1=1,p2=1;
int n,m,k,x;
int main(){
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++){
        cin>>x;
        if(x<=k){
            ①
        } else {
            big[p2++]=x;
        }
    }
    sort (small+1, small+1+p1,greater<int>());
    sort (big+1,big+1+p2,greater<int>());
    for(int i=1;i<=p1;i++){
        ②
    }
    int ans =sum[p1],cur=0;
    for(int i=1;i<=p2;i++){
        cur+=big[i];
        int days= ③;
        if (days>n){
            break;
        }
        int left=min (n-days,p1);
        ans =max (ans,④);
    }
    cout<<ans<<endl;
    return 0;
}

34. ①处 {{ select(34) }}

• big[++p1]=x;
• big[p1++]=x;
• small[++p1]=x;
• small[p1++]=x;

35. ②处 {{ select(35) }}

• sum[i]=sum[i-1]+small[i];
• sum[i+1]=sum[i]+small[i+1];
• sum[i]=sum[i-1]+big[i];
• sum[i+1]=sum[i]+big[i];

36. ③处 {{ select(36) }}

• (i-1)*m
• i*(m+1)
• i*m
• (i-1)*(m+1)

37. ④处 {{ select(37) }}

• sum[left+1]+cur
• sum[left]+cur
• sum[left-1]+cur
• sum[left]+cur-1

完善程序2 树形DP时态同步

#include<bits/stdc++.h>
using namespace std;
typedef long long int_t;
int_t read(){
    int_t x=0,w=1;char ch=0;
    while(!isdigit (ch)){ch=getchar();if(ch=='-') w=-1;}
    while (isdigit(ch))
        ①;
    return x*w;
}
struct E{
    int_t to,w;
    E(int_t to0,int_t w0){to=to0;w=w0;}
};
vector<E>G[501000];
int_t ans;
int_t dfs(int_t rt,int_t fa){
    int_t ret=0,cnt=0;
    for(Ee: G[rt]) if(e.to!=fa){
        int_t res=dfs (e.to,rt)+e.w;
        if(②)ans+=cnt*(res-ret),③,cnt++;
        else ④,cnt++;
    }
    return ret;
}
int main(){
    int_t n=read(),s=read();
    for(int i=1;i<n;i++){
        int_t u=read(),v=read(),w=read();
        G[u].emplace_back (v, w);
        G[v].emplace_back (u, w);
    }
    ⑤
    cout<<ans;
    return 0;
}

38. ①处 {{ select(38) }}

• x*10+ch-60
• x*10+ch-48
• x*10+(int) ch
• x*10+ch-65

39. ②处 {{ select(39) }}

• res>ret
• res>=ret
• res<ret
• res<=ret

40. ③处 {{ select(40) }}

• ret=res
• ++res
• ret+=res
• ++ret

41. ④处 {{ select(41) }}

• ans+=(ret-res)
• ans+=(res-ret)
• ans-=(ret-res)
• ans-=(res-ret)

42. ⑤处 {{ select(42) }}

• dfs(1,0);
• dfs(s,1);
• dfs(0,-1);
• dfs(s,0);