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

1. 下列C++表达式，值最大的是。 {{ select(1) }}

• 'Z'-'A'
• 52 % 53>>1
• (rand()-rand()+1)%26
• 20+15 % 28 / 3

2. 下列属于解释执行的程序设计语言是。 {{ select(2) }}

• C
• C++
• Pascal
• Python

3. 对于64KB的存储器，其最大地址码用十六进制表示是。 {{ select(3) }}

• 10000
• FFFF
• 1FFFF
• EFFFF

4. 为解决Web应用中的不兼容问题，保障信息流通，制定HTML、XML、CSS标准的组织是。 {{ select(4) }}

• 微软
• 美国计算机协会(ACM)
• 联合国教科文组织
• 万维网联盟(W3C)

5. 下列表达式无法判断整数x是否为完全平方数的是。 {{ select(5) }}

• floor (sqrt(x)+0.5)==sqrt(x)
• int(sqrt(x))==sqrt(x)
• x / int(sqrt(x))==int(x / int(sqrt(x)))
• int(sqrt(x)) * int(sqrt(x))==x

6. 将8个名额分给5个不同班级，允许班级无名额，分配方案总数。 {{ select(6) }}

• 60
• 120
• 495
• 792

7. 同时查找2n个数最大值、最小值，最少比较次数。 {{ select(7) }}

• 3(n-2)/2
• 4n-2
• 3n-2
• 2n-2

8. n顶点e边邻接表存储图，DFS、BFS时间复杂度。 {{ select(8) }}

• $O(n^2)$
• $O(e^2)$
• $O(ne)$
• $O(n+e)$

9. 两根蜡烛粗细材质相同，初始长度21:16，燃烧18分钟后15:11，长蜡烛剩余燃烧时间。 {{ select(9) }}

• 150分钟
• 225分钟
• 128分钟
• 9分钟

10. 考试两部分，15人满分，第一部分对31人，第二部分错19人，两部分全错人数。 {{ select(10) }}

• 3
• 4
• 6
• 12

11. 序列(50,40,95,20,15,70,60,45)，希尔排序初始增量d=4，第二趟后前4个关键字。 {{ select(11) }}

• 15,20,50,40
• 15,40,60,20
• 15,20,40,45
• 15,20,40,50

12. 下列邻接矩阵对应有向无环图DAG的是。 {{ select(12) }}

• $\begin{pmatrix}0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0\end{pmatrix}$
• $\begin{pmatrix}0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0\end{pmatrix}$
• $\begin{pmatrix}1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0\end{pmatrix}$
• $\begin{pmatrix}0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0\end{pmatrix}$

13. 关于最短路算法说法正确的是。 {{ select(13) }}

• 无负权回路但存在负权边，Dijkstra可求单源最短路
• 无负权边时，多次Dijkstra可求每对点最短路
• 存在负权回路，单次Dijkstra一定求出源点所有最短路
• 存在负权边，堆优化Dijkstra可求出源点所有最短路

14. 等差数列$a_1>0$，$a_{2020}+a_{2021}>0$，$a_{2020} \cdot a_{2021}<0$，使$S_n>0$最大n。 {{ select(14) }}

• 2020
• 4040
• 4041
• 4042

15. 消回文最少次数DP，不考虑回文时转移方程包含。 {{ select(15) }}

• $\min_{i \leq k<j}\{f(i, k)+f(k+1, j)\}$
• $\min_{i \leq k<j}\{f(i, k)+f(k+1, j)\}+1$
• $\min_{i \leq k<j}\{f(i, k) * f(k+1, j)\}$
• $f(i, k)+f(k+1, j)$

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

阅读程序1 十字/竖轴最长回文长度

#include<iostream>
#include<cstdio>
using namespace std;
int L,ans;
char a[2002][2002];
int cross(int x,int y){
    int length=1;
    if (x<=1||x>=L) return 1;
    for(int i=1;;i++){
        if (x-i<=0||x+i>=L+1) return length;
        else if (a[x-i][y]!=a[x+i][y]) return length;
        else length+=2;
    }
}
int down (int x,int y) {
    int length=1;
    if (y<=1 || y>=L) return 1;
    for(int i=1;;i++){
        if (y-i<=0||y+i>=L+1) return length;
        else if (a[x][y-i]!=a[x][y+i]) return length;
        else length+=2;
    }
}
int MAXN(int a,int b){
    if(a>=b) return a;
    else return b;
}
int main(){
    cin>>L;
    for(int i=1;i<=L;i++)
        for(int j=1;j<=L;j++)
            cin>>a[i][j];
    int x,y;
    cin>>x>>y;
    ans =MAXN (cross (x, y), down (x,y));
    cout<<ans;
    return 0;
}

16. 35行交换两个函数参数，运行结果不变。 {{ select(16) }}

• √
• ×

17. x或y输入0，程序运行报错。 {{ select(17) }}

• √
• ×

18. ans输出值可能等于0。 {{ select(18) }}

• √
• ×

19. 输入x>y，cross返回一定大于down。 {{ select(19) }}

• √
• ×

20. L*L矩阵，ans理论最大值。 {{ select(20) }}

• L-1
• L
• 2L
• $L^2$

21. L=5，矩阵abcba/bedeb/ededc/bedeb/abeba，x=y=3输出。 {{ select(21) }}

• 2
• 3
• 5
• 10

阅读程序2 埃氏筛+欧拉函数

#include<cstdio>
#include<cmath>
const int N=1e9;
int isnp[50005],p[50005],pcnt;
inline void getPrime (const int n=sqrt(N)){
    isnp[0]=isnp[1]=1;
    for (register int i=2;i<=n;++i){
        if(!isnp[i]) p[pcnt++]=i;
        for (register int j=0;i*p[j]<=n &&j<pcnt;++j){
            isnp[i*p[j]]=1;
            if(!(i%p[j]))break;
        }
    }
}
int main(){
    getPrime();
    int n;
    while (scanf("%d",&n) && n){
        int _sqrt=sqrt(n),ans=n;
        for (register int j=0;p[j]<=_sqrt && j<pcnt;++j){
            if (n%p[j]==0){
                while (n%p[j]==0) n/=p[j];
                ans=1ll*ans*(p[j]-1)/p[j];
            }
        }
        if(n!=1) ans=1ll*ans*(n-1)/n;
        printf("%d\n",ans);
    }
    return 0;
}

22. 删除筛法break语句，结果正确。 {{ select(22) }}

• √
• ×

23. 删除while除循环，结果正确。 {{ select(23) }}

• √
• ×

24. n≤1e8，第10行j<pcnt可省略。 {{ select(24) }}

• √
• ×

25. n≤1e8，第21行j<pcnt可省略。 {{ select(25) }}

• √
• ×

26. n=504输出ans。 {{ select(26) }}

• 288
• 144
• 504
• 503

27. getPrime时间复杂度。 {{ select(27) }}

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

阅读程序3 树重心求解

#include<iostream>
using namespace std;
const int inf=0x3f3f3f3f,N=4e5+5;
struct edge{
    int to,nt;
}E[N<<1];
int cnt,n,m,rt,MX;
int H[N],sz[N],mxs[N];
void add_edge (int u,int v){
    E[++cnt]=(edge){v,H[u]};
    H[u]=cnt;
}
void dfs (int u,int fa) {
    sz[u]=1;
    for (int e=H[u];e;e=E[e].nt) {
        int v=E[e].to;
        if(v==fa) continue;
        dfs (v,u);
        sz[u]+=sz[v];
        mxs[u]=max(mxs[u],sz[v]);
    }
    mxs[u]=max(mxs[u],n-sz[u]);
    if(mxs[u]<mxs[rt])rt=u;
    if(mxs[u]==mxs[rt] && u<rt) rt=u;
}
int main(){
    cin>>n;
    rt=cnt=0;
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        add_edge (u,v);
        add_edge (v,u);
    }
    mxs[0]=inf;
    dfs (1,0);
    cout<<rt<<' '<<mxs[rt]<<'\n';
    return0;
}

28. 仅保留一条add_edge，程序正确。 {{ select(28) }}

• √
• ×

29. dfs第二个参数只要≤0即可。 {{ select(29) }}

• √
• ×

30. 输入重边不影响输出。 {{ select(30) }}

• √
• ×

31. 存在i满足sz[i]==mxs[i]。 {{ select(31) }}

• √
• ×

32. n=6，边(1,3)(6,3)(2,6)(5,6)(3,4)输出。 {{ select(32) }}

• 3 2
• 3 3
• 6 3
• 6 2

33. n=1000，mxs数组最大值。 {{ select(33) }}

• 499
• 500
• 999
• 1000

三、完善程序（每题2.5分，合计30分）

完善程序1 翻硬币

#include<iostream>
using namespace std;
int solve(int m);
int main(){
    int m;
    do{
        scanf("%d",&m);
        if(m>0 &&m<1000)
            printf("%d\n", ①);
    } while(m>0 &&m<1000);
    return0;
}
int solve(int m){
    int i,t,s=-1;
    int flag;
    if(m==1)
        s=2;
    else{
        int d=2*m+1;
        t=②;
        i=1;
        flag=0;
        do{
            if(t==1){
                s=③;
                flag=1;
            }else if(④){
                s=i*m-1;
                flag=1;
            }else{
                t=⑤;
                i=i+1;
            }
        } while(!flag);
    }
    return s;
}

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

• solve(m+1)
• solve(2*m)
• solve(m)
• solve(m)+1

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

• 0
• 1
• 2
• -1

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

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

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

• t==2*m-1
• t==2*m
• t==2*m+1
• t==2*(m+1)

38. ⑤处应填 {{ select(38) }}

• (t*2+1)%d
• (t*2)%d
• (t*2)%d+1
• t%d

完善程序2 FB串Z串递归分解

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int n=8;
char str1[2*n][n];
char str2[40]="";
int main(){
    int s1,s2,x,s,t;
    s1=s2=x=0;
    gets (str1[0]);
    while(①){
        s=t=0;
        for (int i=0;i<n;i++){
            if(str1[s2][i]=='1') s++;
            if (str1[s2][i]=='0') t++;
        }
        if(②)
            str2[x++]='B';
        else if(③)
            str2[x++]='Z';
        else {
            str2[x++]='F';
            int j=(s+t)>>1;
            for (int k=④;k>=0;k--){
                for (int i=0;i<n;i++)
                    str1[k+2][i]=str1[k][i];
            }
            for (int i=0;i<j;i++){
                str1[s2+1][i]=str1[s2][i];
                str1[s2+2][i]=⑤;
            }
            for(int i=⑥;i<n;i++)
                str1[s2+2][i]=' ';
        }
        s2++;
    }
    puts (str2);
    return 0;
}

39. ①处应填 {{ select(39) }}

• s1<=s2
• s2<=s1
• x<=n
• s<=t

40. ②处应填 {{ select(40) }}

• t==0
• s==0
• t>0
• s>0

41. ③处应填 {{ select(41) }}

• t==0
• s==0
• t>0
• s>0

42. ④处应填 {{ select(42) }}

• s2
• s2+1
• s1
• s1+1

43. ⑤处应填 {{ select(43) }}

• str1[s2][j]
• str1[s2+1][i]
• str1[s2][i+j]
• str1[s2+1][i+j]

44. ⑥处应填 {{ select(44) }}

• 1
• j
• s1
• s2