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

1. 假设有定义：int a[5]={1,2,3,4,5},i=3,*p=a,*q=a;，不能正确执行的语句是()。 {{ select(1) }}

• i=*p+*q;
• a=i;
• *p=*(a+i);
• i=*p * *(q+2);

2. 下列不属于CPU的有()。 {{ select(2) }}

• 海思麒麟990
• Intel酷睿i7
• 影驰RTX2070
• AMD Ryzen 7

3. $(2019)_{10}+(2020)_{10}$ 的结果是()。 {{ select(3) }}

• $(3049)_{10}$
• $(BF3)_{16}$
• $(101111110001)_2$
• $(5765)_8$

4. 某二叉树先序遍历和后序遍历序列正好相反，则该二叉树特征是()。 {{ select(4) }}

• 高度等于结点数
• 任一结点无左孩子
• 任一结点无右孩子
• 空或只有一个结点

5. 定义char x[]="12345"; char y[]={'1','2','3','4','5'};，则()。 {{ select(5) }}

• x、y占用内存相同
• x比y占用内存更大
• x比y占用内存更小
• x等价于y数组

6. 公交每小时10、30、55分发车，乘客随机到站，到站等于发车时间无法乘车，候车时间数学期望（精确到秒）()。 {{ select(6) }}

• 8分40秒
• 15分20秒
• 22分30秒
• 10分25秒

7. 序列<Q,H,C,Y,P,A,M,S,R,D,F,X>以首元素分界，快速排序一趟扫描结果()。 {{ select(7) }}

• F,H,C,D,P,A,M,Q,R,S,Y,X
• P,A,C,S,Q,D,F,X,R,H,M,Y
• A,D,C,R,F,Q,M,S,Y,P,H,X
• H,C,Q,P,A,M,S,R,D,F,X,Y

8. n点m边连通图，删除几条边能变成一棵树()。 {{ select(8) }}

• $m-n+1$
• $m-n$
• $m+n+1$
• $n-m+1$

9. 2红1蓝1白放入10个不同编号盒子，每盒最多一球，放法总数()。 {{ select(9) }}

• 5040
• 2520
• 1260
• 420

10. 木材113单位，桌子20单位/张售价30；椅子16单位/张售价20，最大收益()。 {{ select(10) }}

• 140
• 150
• 160
• 170

11. 插入、冒泡、选择、快速排序平均时间复杂度依次为()。 {{ select(11) }}

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

12. 以下不是线性结构的是()。 {{ select(12) }}

• 广义表
• 二叉树
• 队列
• 栈

13. 不能处理负权的最短路算法()。 {{ select(13) }}

• Dijkstra
• Floyd
• Bellman-Ford
• SPFA

14. 栈最多存4个元素，入栈序列1,2,3,4,5,6，哪个出栈序列合法()。 {{ select(14) }}

• 5,4,3,2,1,6
• 3,2,5,4,1,6
• 2,3,5,6,1,4
• 1,4,6,5,2,3

15. 三条平行线分别7、5、6个点，无三点共线，可组成四边形数量()。 {{ select(15) }}

• 18
• 210
• 2250
• 4500

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

阅读程序1 递归函数

#include<cstdio>
using namespace std;
int findvall(int n)
{
    int f;
    if(n==0)return1;
    else
    {
        f=findvall(n/2);
        return(n*f);
    }
}
int main()
{
    int n;
    printf("%d\n",findvall(n));
    scanf("%d",&n);
    return 0;
}

16. 将if(n==0)改为if(n==1)，输入正整数输出不变。 {{ select(16) }}

• √
• ×

17. 输入正整数，输出值≤n。 {{ select(17) }}

• √
• ×

18. 输入负数会无限递归死循环。 {{ select(18) }}

• √
• ×

19. n单调递增正整数，输出严格单调递增。 {{ select(19) }}

• √
• ×

20. 两次输入相差1，输出一正一负，可能的一组是()。 {{ select(20) }}

• 不可能
• -6,-7
• -15,-16
• -23,-24

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

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

阅读程序2 下一个排列

#include<cstdio>
#include<cstring>
using namespace std;
int main(){
    char str[60];
    int len,i,j,chr[26];
    char mmin='z';
    scanf("%s",str);
    len=strlen(str);
    for(i=len-1;i>=1;i--)
        if (str[i-1]<str[i])break;
    if(i==0){
        printf ("No result!\n");
        return 0;
    }
    for (j=0;j<i-1;j++) putchar(str[j]);
    memset (chr,0, sizeof (chr));
    for(j=i;j<len;j++){
        if (str[j]>str[i-1] && str[j]<mmin)
            mmin=str[j];
        chr[str[j]-'a']++;
    }
    chr[mmin-'a']--;
    chr[str[i-1]-'a']++;
    putchar (mmin);
    for(i=0;i<26;i++)
        for(j=0;j<chr[i];j++)
            putchar(i+'a');
    putchar('\n');
    return0;
}

22. 输入字符串长度范围[1,59]。 {{ select(22) }}

• √
• ×

23. 输入字符串完全降序，输出No result!。 {{ select(23) }}

• √
• ×

24. 第25行输出全局最小字符。 {{ select(24) }}

• √
• ×

25. 26~28行将剩余字符升序输出。 {{ select(25) }}

• √
• ×

26. 输入abcdzdcba，第16行输出()。 {{ select(26) }}

• abc
• abcd
• abcdz
• abcdzd

27. 输出ffghhggh，输入可能是()。 {{ select(27) }}

• ffghhghg
• ffghhhgg
• ffghghhg
• ffghghgh

阅读程序3 贪吃蛇模拟

#include<bits/stdc++.h>
#include<windows.h>
using namespace std;
int a,mp[101][101];
int t[100003];
int y[100003];
int cnt;
int len=2,dir=3,die=0;
const int dx[5]={0,0,-1,0,1};
const int dy[5]={0,-1,0,1,0};
int nx=0,ny=1;
int px=1,py=2;
int check(int x,int yy)
{
    if(x<1||x>a||yy<1||yy>a)
        return 1;
    if(cnt+1-mp[x][yy]<len)
        return 1;
    return 0;
}
void work()
{
    if(die) return;
    px+=nx;
    py+=ny;
    die=check (px,py);
    if(die) return;
    mp[px][py]=++cnt;
}
void show()
{
    for(int i=1;i<=a;++i)
    {
        for(int j=1;j<=a;++j)
            if(mp[i][j]!=0 && mp[i][j]>=cnt-len+1)
                putchar('o');
            else
                putchar('.');
        puts("");
    }
}
int main()
{
    mp[1][1]=++cnt;
    mp[1][2]=++cnt;
    int n,m,op,xx;
    char s[3];
    scanf("%d",&a);
    scanf("%d%d", &n,&m);
    while(n--)
    {
        scanf ("%d%d", &op,&xx);
        if(op==1)
        {
            t[xx]=1;
            scanf("%s",s);
            if(s[0]=='L')
                y[xx]=1;
            else if(s[0]=='U')
                y[xx]=2;
            else if(s[0]=='R')
                y[xx]=3;
            else
                y[xx]=4;
        }
        else
        {
            t[xx]=2;
        }
    }
    for(int tm=1;tm<=m;++tm)
    {
        if(t[tm]==1)
        {
            if(y[tm]!=dir)
            {
                dir=y[tm];
                nx=dx[y[tm]];
                ny=dy[y[tm]];
            }
        }
        else if(t[tm]==2)
        {
            ++len;
        }
        work();
        if(die)
            break;
    }
    show();
    return0;
}

28. 蛇初始长度2，头(1,2)尾(1,1)。 {{ select(28) }}

• √
• ×

29. check函数检测是否吃到食物。 {{ select(29) }}

• √
• ×

30. op=1 xx s代表第xx秒按下L/U/R/D控制方向。 {{ select(30) }}

• √
• ×

31. 样例输入运行后蛇第9秒死亡，输出死亡前第7秒地图。 {{ select(31) }}

• √
• ×

32. 地图边长x，n次操作，程序时间复杂度()。 {{ select(32) }}

• $O(x^2)$
• $O(n^2)$
• $O(n^2*x)$
• $O(x^2*n)$

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

完善程序1 KFC取餐往返BFS

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int MAXN=1e3+10;
const int INF=0x3f3f3f3f;
typedef pair<int,int>P;
char s[MAXN][MAXN];
int n,m;
int dir[2][4]={{1,-1,0,0},{0,0,1,-1}};
int dis[2][MAXN][MAXN];

void bfs (int p,int a,int b){
    memset (dis[p], INF,sizeof (dis[p]));
    dis[p][a][b]=0;
    queue<pair<P, int>>q;
    q.push ({{a,b},0});
    while (!q.empty()){
        int x=q.front().fi.fi,
        y=q.front().fi.se,
        d=q.front().se;
        q.pop ();
        for(int i=0;i<4;i++){
            int dx=x+dir[0][i],
            dy=y+dir[1][i];
            if (dx<1 || dy<1 || dx>n || dy>m || s[dx][dy]=='#')
                continue;
            if( ① ){
                ②;
                ③;
            }
        }
    }
}

int main(void)
{
    while (scanf("%d%d",&n, &m)!=EOF){
        int ans= INF;
        for(int i=1;i<=n;i++)
            scanf("%s",s[i]+1);
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                if(s[i][j]=='S')
                    bfs(0,i,j);
                else if(s[i][j]=='E')
                    ④;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                if(s[i][j]=='K')
                    ans= ⑤;
        if(ans==INF)
            ans=-1;
        printf("%d\n",ans);
    }
    return 0;
}

33. ①处填() {{ select(33) }}

• dis[p][dx][dy]>d
• dis[p][dx][dy]>d+1
• dis[p][dx][dy]<d
• dis[p][dx][dy]<d+1

34. ②处填() {{ select(34) }}

• dis[p][dx][dy]=d
• dis[p][dx][dy]=d-1
• dis[p][dx][dy]=d+1
• dis[p][dx][dy]=1

35. ③处填() {{ select(35) }}

• q.push({{dx,dy},d+1})
• q.push({{dx,dy},d})
• q.push({{dx,dy},d-1})
• q.push({{dx,dy},1})

36. ④处填() {{ select(36) }}

• bfs(0,j,i)
• bfs(1,j,i)
• bfs(0,i,j)
• bfs(1,i,j)

37. ⑤处填() {{ select(37) }}

• min(ans, dis[0][i][j]+dis[1][i][j])
• min(ans,dis[0][j][i]+dis[1][j][i])
• min(ans,dis[0][i][j])
• min(ans,dis[1][i][j])

完善程序2 尺取法求区间和≤k区间数量

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int mx=1e6+10;
int n,a[mx];
ll k,sum,ans;
int main()
{
    scanf("%d%lld", &n, &k);
    for(int i=1;i<=n;++i)
    {
        scanf("%d",&a[i]);
    }
    int r=0;
    for(int i=1;i<=n;++i)
    {
        while (r<n) {
            if( ① )
                ②;
            else break;
        }
        ③;
        ④;
    }
    printf("%lld\n",ans);
    return 0;
}

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

• sum+a[r+1]<=k
• sum+a[r]<=k
• sum+a[r+1]<k
• sum+a[r]<k

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

• sum+=a[r]
• sum+=a[++r]
• sum+=a[r++]
• sum+=a[r+1]

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

• ans+=r-i+1
• ans+=r-i
• ans+=r-i-1
• ans+=n-i+1

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

• sum+=a[i]
• sum=a[r]
• sum=a[i]
• sum-=a[i]