单选题（每题只有一个正确选项，每题2分，共30分）

1. 以下哪一项不是组成冯诺依曼计算机的部件{{ select(1) }}

• 运算器
• 存储器
• 输入设备
• 网络设备

2. 两位老师带四个学生去坐有六个位置的圆形旋转木马，那么两位老师不相邻的概率是{{ select(2) }}

• 3/5
• 2/3
• 11/15
• 1/2

3. 已知一棵二叉树的先序遍历序列为 ABDGCEFH，中序遍历序列为 DGBAECHF，则后序遍历序列为{{ select(3) }}

• GDBAEHFC
• GDBEHFCA
• GDBEFHCA
• GDBECHFA

4. 关于以下代码片段，正确的是

int a[5], *pa;
pa = a;
pa = pa + 2;

{{ select(4) }}

• 指针 pa 指向 a[2]
• 指针 pa 指向的内容是 a[0]+2
• 指针 pa 指向 a[0]
• 代码语法有误，无法正常运行

5. 王老师去银行兑换面值5元，10元，20元的人民币，已知王老师总共花费500元，且兑换得人民币45张，则有多少种兑换方法。{{ select(5) }}

• 13
• 14
• 15
• 16

6. 八进制数字777和二进制数字111的和是 {{ select(6) }}

• $(1000000110)2$
• $(516){10}$
• $(1066)8$
• $(517){10}$

7. 班上的6位学生将要去3个不同的考点参加C++编程大赛，每个考点由一名老师带领两名同学参加，现有3位老师可带领学生们参赛，人员分配由班主任决定，请你帮班主任算算一共有几种不同的参赛方案{{ select(7) }}

• 360种
• 540种
• 720种
• 1080种

8. 小明买了一个存储空间为 256G 的手机，用于存放 256G 内容的硬件属于哪一种硬件？{{ select(8) }}

• 内存
• 外存
• 高速缓冲存储器(cache)
• 输入设备

9. 张老师最近在想要办理一个新的宽带网络，运营商给了张老师四种方案，张老师想要办理性价比最高的一条（即宽带速率/宽带价格最大），请你帮张老师算一算以下哪个方案性价比最高{{ select(9) }}

• 129元/月 300Mb/s
• 62元/月 20MB/s
• 500元/月 1000Mb/s
• 200元/月 100MB/s

10. 元素A，B，C，D，E依次进入初始为空的栈中，若元素进栈后可停留、可出栈，直到所有元素都出栈，则以下不可能的出栈序列是{{ select(10) }}

• EDCBA
• DCEAB
• DECBA
• ABCDE

11. 在一个包含n个顶点的有向图中，如果所有顶点的出度和为s，则所有顶点的入度和为{{ select(11) }}

• n
• s
• n-1
• s-(s/n)

12. 某二叉树共有12个结点，其中叶子结点只有1个。则该二叉树的深度（根结点在第1层）为{{ select(12) }}

• 3
• 6
• 8
• 12

13. 一棵二叉树不具有的性质是{{ select(13) }}

• 可能有结点没有孩子
• 一定没有环
• 每个结点最多两个孩子
• 每个节点都有父亲结点

14. 在一个单链表中，已知q节点是p节点的前驱节点，若在p和q之间插入节点s，则必须执行{{ select(14) }}

• s->next=p->next; p->next=s;
• s->next=p; q->next=s;
• p->next=s->next; s->next=p;
• p->next=s; s->next=q;

15. func(12) 的结果是

int func(int x) {
    return 2 == x ? 1 : x + func(x - 2);
}

{{ select(15) }}

• 29
• 33
• 37
• 41

程序阅读理解题（共3大题。程序输入不超过数组或字符串定义的范围，除特殊说明外，判断题1.5分，选择题3分，共计40分）

#include <bits/stdc++.h>
using namespace std;
void M(int &a, int &b){
    a ^= b;
    b ^= a;
    a ^= b;
}
int T(int x, int y){
    M(x, y);
    int res = 0, t = 1;
    int k = y << x + 1;
    while(t <= k){
        res += x & x - 1 | 1;
        t *= y;
    }
    return res;
}
int main() {
    int a, b;
    cin >> a >> b;
    cout << T(T(b, a), b) << endl;
    return 0;
}

判断题

16. 函数 M(int &a, int &b) 的时间复杂度是 O(3)。 {{ select(16) }}

• 对
• 错

17. 函数 T(2, 5) 返回值 res 是 25。（2分） {{ select(17) }}

• 对
• 错

18. 当程序输入 20 1时，程序无法正常运行。 {{ select(18) }}

• 对
• 错

单选题

19. （4分）当程序输入的 b > 1且 a < 30 的正整数时 T 函数的时间复杂度是 {{ select(19) }}

• $\log_y k$
• $O(\sqrt{k})$
• $\log_2 k$
• $O(k)$

20. （4分）当程序输入 1024 2024 时，程序的输出是 {{ select(20) }}

• 22185
• 22186
• 22187
• 22188

#include <bits/stdc++.h>
using namespace std;
bool check(int n){
    for(int i = 2; i < n; i++)
        if(n%i == 0) return 0;
    return 1;
}
int solve(int n){
    int res = 0;
    while(n > 0){
        res = res + (n&1);
        n >>= 1;
    }
    return res;
}
int main(){
    int n, tot = 0;
    cin >> n;
    for(int i = 2; i <= n; i++)
        if(check(i)) tot += solve(i);
    cout << tot;
    return 0;
}

判断题

21. 若程序输入 6，则最终输出 5。 {{ select(21) }}

• 对
• 错

22. 将程序的第4行修改成 for(int i = 2; i <= n/i; i++) 后，程序的结果一定不会发生变化。 （2分） {{ select(22) }}

• 对
• 错

23. 将程序的第 1 行修改成 #include <stdio.h> 程序的结果一定不会发生变化。 {{ select(23) }}

• 对
• 错

单选题

24. 输入 20，则输出是什么？ {{ select(24) }}

• 17
• 18
• 19
• 20

25. 若将第 11 行修改成 res = res ^ n，输入 15，输出的是什么 （4分） {{ select(25) }}

• 38
• 26
• 50
• 68

#include <bits/stdc++.h>
#define mod 1000000007
typedef long long ll;
using namespace std;

ll C(int n, int m) {
    ll ret = 1;
    for(int i=n-m+1;i<=n;++i) ret*=i;
    for(int i=2;i<=m;++i) ret/=i;
    return ret;
}

int main() {
    int n, m;
    cin >> n >> m;
    cout << C(n, m) << endl;
    int a, b;
    cin >> a >> b;
    int x, y;
    while(1) {
        x = a ^ b;
        y = a & b;
        if(y == 0) break;
        a = x;
        b = y << 1;
    }
    cout << x << endl;
}

判断题

26. 函数 C 的作用是求 $C_n^m$。 {{ select(26) }}

• 对
• 错

27. （2分）第 24 行计算得到的 x 每次比上一次计算得到的大。 {{ select(27) }}

• 对
• 错

28. 存在一组范围内的 a, b 使程序会陷入死循环。 {{ select(28) }}

• 对
• 错

29. （2分）若输入 n=3, m=2, a = 155, b = 229，程序各执行第 27,28 行八次。 {{ select(29) }}

• 对
• 错

单选题

假设不考虑上述代码中的 n、m 以及 C 函数，完成下列两题： 30. （4分）设 N 为 max(a, b)，最优情况下，此程序的时间复杂度是 {{ select(30) }}

• $O(1)$
• $O(\log N)$
• $O(N)$
• $O(N \log N)$

31. （4分）设 N 为 max(a, b)，最坏情况下，此程序的时间复杂度是 {{ select(31) }}

• $O(1)$
• $O(\log N)$
• $O(N)$
• $O(N \log N)$

程序完善题（共2大题，每个选择题3分，共计30分）

（选择数对）有 n 个小朋友分别拿着一个数字，现在要求你将小朋友两两配对，要求每对小朋友手上的数字之差大于给定值 k。问最多可以从数组中选出多少对符合条件小朋友。（每个小朋友最多只能和另外一个小朋友配对，不能脚踏两条船）

输入格式：第一行给出 n, k 分别表示小朋友的个数，以及参数 k。$(1 \leq n,k \leq 10^5)$，接下来给出 n 个数字，表示每个小朋友手上的数字。

提示：二分最终的结果，对于二分的结果 mid，在 check 函数中 O(n) 判断能否选出 mid 对小朋友符合要求，最终保留二分的结果。

#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 1e5 + 5;
int a[maxn], n, k;

bool check(int mid){
    bool flag = true;
    for(int i = 1, **1**; j <= n; j++, i++){
        if(**2**)
            flag = false;
    }
    return flag;
}

int main(){
    cin >> n >> k;
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    int l = **3**, r = n, ans;
    sort(a+1, a+1+n);
    while(l <= r){
        int mid = (l + r) / 2;
        if(check(mid)){
            **4**;
            ans = mid;
        }else{
            **5**;
        }
    }
    cout << ans << endl;
}

32. 1 处应该填的代码是: {{ select(32) }}

• j = 1
• j = n - mid
• j = n - mid + 1
• j = mid

33. 2 处应该填的代码是: {{ select(33) }}

• a[i] - a[j] > k
• a[i] - a[j] <= k
• a[j] - a[i] > k
• a[j] - a[i] <= k

34. 3 处应该填的代码是: {{ select(34) }}

• 1
• 0
• n/2
• a[1]

35. 4 处应该填的代码是: {{ select(35) }}

• l = mid
• r = mid
• l = mid + 1
• r = mid - 1

36. 5 处应该填的代码是: {{ select(36) }}

• l = mid
• r = mid
• l = mid + 1
• r = mid - 1

（逃离森林）你发现你身处一片森林，你需要找到出口逃离这里。但是在森林中还有其他人和很多树木。他们会给你造成阻碍。所有人都会沿向终点的最短路径行进。输出在你到达出口前，到达出口的人数（包括与你同时到达终点的人）。

#include<bits/stdc++.h>
using namespace std;
struct point{
    int x,y,s;
};
queue<point>q;
int maxn=1e9,n,m,sx,sy,ans,book[1001][1001];
char a[1001][1001];
int xx[4]={1,-1,0,0},yy[4]={0,0,1,-1};
void bfs(){
    point p1=①;
    q.push(p1);
    while(!q.empty()){
        ②
        if(book[p.x][p.y]||p.s>maxn)
            continue;
        book[p.x][p.y]=1;
        if(a[p.x][p.y]=='S'){
            maxn=p.s;
            continue;
        }
        if(a[p.x][p.y]>='0'&&a[p.x][p.y]<='9')
            ③
        for(④){
            int tx=p.x+xx[i],ty=p.y+yy[i];
            if(a[tx][ty]=='T'||tx<0||tx>=n||ty<0||ty>=m)
                continue;
            ⑤
        }
    }
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    cin>>n>>m;
    for(int i=0;i<n;i++){
        cin>>a[i];
        for(int j=0;j<m;j++)
            if(a[i][j]=='E')
                sx=i,sy=j;
    }	
    bfs();
    printf("%d",ans);
    return 0;
}

37. ①处应该填写 {{ select(37) }}

• {1,1,0}
• {sx,sy,0}
• make_pair{sx,sy}
• make_pair{1,1}

38. ②处应该填写 {{ select(38) }}

• point p=q.front();
• point p=q.front(); q.pop(); q.push({sx,sy,1});
• point p=q.front(); q.pop(); q.push({sx,sy});
• point p=q.front(); q.pop();

39. ③处应该填写 {{ select(39) }}

• ans+=a[p.x][p.y]-'0';
• ans=a[p.x][p.y]-'0';
• q.push({p.x,p.y,a[p.x][p.y]-'0'})
• q.push({p.x,p.y,a[p.x][p.y]})

40. ④处应该填写 {{ select(40) }}

• int i=1;i<=4;i++
• int i=1;i<=8;i++
• int i=0;i<4;i++
• int i=0;i<8;i++

41. ⑤处应该填写为 {{ select(41) }}

• q.pop()
• point p2={tx,ty,p.s+1}; q.push(p2);
• return;
• sx=tx,sy=ty; BFS();