一、单项选择题（共15题，每题2分，共计30分）

1. 在二进制下，1011001 + ( ) = 1100110。

{{ select(1) }}

• 1011
• 1101
• 1010
• 1111

2. 在布尔逻辑中，以下逻辑或性质说法错误的是（ ）。

{{ select(2) }}

• 交换律：$P\lor Q=Q\lor P$
• 结合律：$P\lor(Q\lor R)=(P\lor Q)\lor R$
• 幂等律：$P\lor0=0$
• 有界律：$P\lor1=1$

3. 一个正整数在二进制下有 $100$ 位，则它在十六进制下有（ ）位。

{{ select(3) }}

• $7$
• $13$
• $25$
• 不能确定

4. 如果一个栈初始时为空，且当前栈中的元素从栈底到栈顶依次为 $a,b,c$，另有元素 $d$ 已经出栈，则可能的入栈顺序是（ ）。

{{ select(4) }}

• $a,d,c,b$
• $b,a,c,d$
• $a,c,b,d$
• $d,a,b,c$

5. 如果一棵二叉树的中序遍历是 BAC，那么它的先序遍历不可能是（ ）。

{{ select(5) }}

• ABC
• CBA
• ACB
• BAC

6. 在含有 $n$ 个元素的双向链表中查询是否存在关键字为 $k$ 的元素，平均时间复杂度是（ ）。

{{ select(6) }}

• $\Theta(1)$
• $\Theta(\log n)$
• $\Theta(n)$
• $\Theta(n\log n)$

7. 如果根结点的深度记为 $1$，则一棵恰有 $2025$ 个叶子结点的二叉树的深度可能是（ ）。

{{ select(7) }}

• $9$
• $10$
• $11$
• $12$

8. （ ）是一种先进先出的线性表。

{{ select(8) }}

• 栈
• 队列
• 哈希表（散列表）
• 二叉树

9. 定义一种字符串操作，一次可以将其中一个元素移到任意位置。举例说明，对于字符串 BCA 可以将 A 移到 B 之前，变字符串 ABC。如果要将字符串 DACHEBGIF 变成 ABCDEFGHI，最少需要（ ）次操作。

{{ select(9) }}

• $2$
• $3$
• $4$
• $5$

10. 体育课的铃声响了，同学们都陆续地奔向操场，按老师的要求从高到矮站成一排。每个同学按顺序来到操场时，都从排尾走到排头，找到第一个比自己高的同学，并站在他的后面。这种站队的方法类似于（ ）算法。

{{ select(10) }}

• 快速排序
• 插入排序
• 冒泡排序
• 归并排序

11. 现有一篇文章，要通过二进制哈夫曼编码进行压缩。简单起见，假设这篇文章只由 $4$ 个字母 $A,B,C,D$ 组成，它们出现的次数分别为 $700,600,300,200$。那么，$C$ 的编码长度是（ ）。

{{ select(11) }}

• $1$
• $2$
• $3$
• $4$

12. 每份考卷都有一个 $8$ 位二进制序列号。当且仅当一个序列号含有偶数个 1 时，它才是有效的。例如，00000000、01010011 都是有效的序列号，而 11111110 不是。那么，有效的序列号共有（ ）个。

{{ select(12) }}

• $32$
• $64$
• $128$
• $256$

13. 如果平面上任取 $n$ 个整点（横纵坐标都是整数），其中一定存在两个点，它们连线的中点也是整点，那么 $n$ 至少是（ ）。

{{ select(13) }}

• $2$
• $3$
• $5$
• $7$

14. 从顶点 $A_0$ 出发，对有向图（ ）进行广度优先搜索 BFS 时，一种可能的遍历顺序是 $A_0,A_4,A_3,A_2,A_1$。

A.

B.

C.

D.

{{ select(14) }}

• A
• B
• C
• D

15. 计算机中的数值信息分为整数和实数（浮点数）。实数之所以能够表示很大或者很小的数，是由于使用了（ ）。

{{ select(15) }}

• 阶码
• 补码
• 反码
• 较长的尾数

二、阅读程序（判断题1分，选择题3分，共计40分）

判断题正确填 T，错误填 F。

第1题

#include<iostream>
int main()
{
    const int maxn = 100000;
    int n;
    std::cin >> n;
    int a[maxn];
    int b[maxn];
    for (int i = 0; i < n; ++i)
    {
        std::cin >> a[i];
        b[a[i]] = i;
    }
    for (int i = 0; i < n; ++i)
    {
        std::cout << b[i] << "\n";
    }
}

16. 当输入数据使得 a 数组的某个元素 a[i] 的值等于 n 时，程序可能出现数组越界的情况。

{{ select(16) }}

• 正确
• 错误

17. 存储输入数据的 a 与存储输出数据的 b 数组，不可能完全相等。

{{ select(17) }}

• 正确
• 错误

18. 当输入数据使得数组 a 构成一个 $0$ 到 $n-1$ 的排列时，数组 b 也构成一个 $0$ 到 $n-1$ 的排列。

{{ select(18) }}

• 正确
• 错误

19. 程序的时间复杂度为（ ）。

{{ select(19) }}

• $\Theta(1)$
• $\Theta(n)$
• $\Theta(\log n)$
• $\Theta(n^2)$

20. 当 i 与 j 是属于 $0$ 到 $n-1$ 的整数，且输入数组 a 是构成一个 $0$ 到 $n-1$ 的排列，当程序结束时，以下三个判定有多少个是恒成立的（ ）。

甲：b[a[i]] == i

乙：a[b[i]] == i

丙：a[a[i]] == b[b[i]]

{{ select(20) }}

• $0$ 个
• $1$ 个
• $2$ 个
• $3$ 个

第2题

#include<iostream>
#include<algorithm>
int main()
{
    int n, d;
    std::cin >> n >> d;
    int x[n];
    for (int i = 0; i < n; ++i) {
        std::cin >> x[i];
    }
    std::sort(x, x + n);
    long long pair = 0;
    int j = 1;
    for (int i = 0; i < n; ++i) {
        while (j < n and x[j] - x[i] <= d) {
            j++;
        }
        pair += j - i - 1;
    }
    std::cout << pair << "\n";
}

21. 如果输入数据中所有点的坐标互不相同且 $d=0$，则程序输出 $0$。

{{ select(21) }}

• 正确
• 错误

22. 若输入数据已按升序排列，删除 std::sort(x, x + n); 后程序仍能正确输出结果。

{{ select(22) }}

• 正确
• 错误

23. 双指针循环中，内层 while 循环的迭代次数总和为 $\Theta(n)$。

{{ select(23) }}

• 正确
• 错误

24. 该程序的时间复杂度为（ ）。

{{ select(24) }}

• $\Theta(n)$
• $\Theta(n\log n)$
• $\Theta(n^2)$
• $\Theta(n\log d)$

25. 关于变量 pair 的类型，以下说法最准确的是（ ）。

{{ select(25) }}

• 使用 int 足够，因为 $n\le100000$，点对数不超过 $50000000$。
• 使用 long long 是必要的，因为 $n=100000$ 时，点对数最大可能达到约 $50$ 亿，超过 int 的表示范围。
• 使用 long long 是必要的，因为坐标值可能很大。
• 使用 long long 是必要的，因为 d 可能很大。

26. 对于输入 $n=5,d=2,x=[3,1,4,1,5]$，程序输出为（ ）。

{{ select(26) }}

• $6$
• $7$
• $8$
• $9$

27. 若将 pair += j - i - 1 改为 pair += j - i，输入 $n=3,d=1,x=[1,2,3]$ 时输出变为（ ）。

{{ select(27) }}

• $2$
• $3$
• $4$
• $5$

第三题

#include<iostream>
int mem[2000000] = {0};
int q[2000000] = {0};
int main()
{
    int r, b;
    std::cin >> r >> b;
    int step = 0;
    while (r != 0) {
        step++;
        if (mem[r] > 0) {
            break;
        }
        else {
            mem[r] = step;
        }
        q[step] = r * 2 / b;
        r = r * 2 % b;
    }
    std::cout << "0.";
    if (r == 0) {
        for (int i = 1; i <= step; ++i) std::cout << q[i];
    }
    else {
        int begin = mem[r];
        for (int i = 1; i < begin; ++i)
            std::cout << q[i];
        std::cout << "(";
        for (int i = begin; i < step; ++i)
            std::cout << q[i];
        std::cout << ")";
    }
}

28. 当余数 r 重复出现时，程序会立即终止循环并标记循环节起始位置。

{{ select(28) }}

• 正确
• 错误

29. 对于任意输入 r 和 b（$r<b$），程序输出结果中，小数点后的位数不超过 $b$。

{{ select(29) }}

• 正确
• 错误

30. 若 $r=0$，程序会输出 0 后直接结束。

{{ select(30) }}

• 正确
• 错误

31. 当 $b=2000000$ 且循环节长度为 $b-1$ 时，程序会运行时错误。

{{ select(31) }}

• 正确
• 错误

32. 当输入 $r=1,b=2$ 时，程序输出为（ ）。

{{ select(32) }}

• 0.0
• 0.1
• 0.(0)
• 0.(1)

33. 若 $r=1,b=5$，程序输出为（ ）。

{{ select(33) }}

• 0.0011
• 0.0101
• 0.(0011)
• 0.(0101)

34. 数组 mem 的作用是（ ）。

{{ select(34) }}

• 存储每一步的商
• 记录余数首次出现的位置
• 标记循环节的结束位置
• 缓存输入数据

35. 该程序的时间复杂度为（ ）。

{{ select(35) }}

• $\Theta(b)$
• $\Theta(r)$
• $\Theta(\log b)$
• $\Theta(b\log b)$

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

第1题

给定一个长度为 $n$、由正整数组成的序列 $a_1,a_2,\ldots,a_n$，请你求出所有子段中第 $k$ 小的子段和。

#include<iostream>
int n,k,a[100005];
bool check(long long mid) {
    long long s = 0;
    for(int l = 1,r = 1;r <= n; r++) {
        while(l <= r && ____(1)____) l++;
        s+=____(2)____;
    }
    return ____(3)____;
}
int main(){
    std::cin>>n>>k;
    for(int i=1;i<=n;i++) {
        std::cin >>a[i];
        a[i]+=a[i-1];
    }
    long long lbound = 0,rbound = 5000000000,mid;
    while(lbound <= rbound) {
        mid = (lbound + rbound) >> 1;
        if(check(mid)) ____(4)____rbound = mid - 1;
        else ____(5)____lbound = mid + 1;
    }
    std::cout << lbound;
    return 0;
}

36. (1) 处应填（ ）。

{{ select(36) }}

• a[l] > mid
• a[r] > mid
• a[r] - a[l-1] > mid
• a[r] - a[l] > mid

37. (2) 处应填（ ）。

{{ select(37) }}

• l
• r
• r-l
• r-l+1

38. (3) 处应填（ ）。

{{ select(38) }}

• s<k
• s<=k
• s>k
• s>=k

39. (4)(5) 处应填（ ）。

{{ select(39) }}

• lbound = mid + 1、rbound = mid
• rbound = mid - 1、lbound = mid
• lbound = mid + 1、rbound = mid - 1
• rbound = mid - 1、lbound = mid + 1

第2题

给定 $n\times m$ 个方格构成的图，每个格子都有一种地形：有一些格子是墙，以符号 # 表示，墙不可通行；有一些格子是空地，以符号 . 表示，空地可以通行。请统计从左上角的方格出发，有多少种不同的路线可以以最短距离走到右下角。在行走过程中，不能进入地形为墙的方格，保证起点与终点方格地形不是墙。且行走时，只能移动到水平或垂直方向相邻的方格。由于方案数可能很大，输出模 $1000000007$ 的余数。

#include<iostream>
char a[1000][1000];
int d[1000][1000];
int w[1000][1000];
int n, m;
int qx[1000*1000];
int qy[1000*1000];
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};

void bfs(int x, int y) {
    qx[0] = x;
    qy[0] = y;
    d[x][y] = 1;
    w[x][y] = 1;
    int head = 0;
    int tail = 1;
    while (head < tail) {
        int x = qx[head];
        int y = qy[head];
        head++;
        for (int k = 0; k < 4; ++k) {
            int nx = x + dx[k];
            int ny = y + dy[k];
            if (0 <= nx and nx < n and 0 <= ny and ny < m and a[nx][ny] == '.') {
                if ( ____(1)____ ) {
                    d[nx][ny] = ____(2)____;
                    w[nx][ny] = ____(3)____;
                    qx[tail] = nx;
                    qy[tail] = ny;
                    tail++;
                }
                else if (____(4)____) {
                    w[nx][ny] = ____(5)____;
                    w[nx][ny] %= 1000000007;
                }
            }
        }
    }
}

int main()
{
    std::cin >> n >> m;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j) {
            std::cin >> a[i][j];
        }
    bfs(0, 0);
    std::cout << ____(6)____ << "\n";
}

40. (1) 处应填（ ）。

{{ select(40) }}

• d[nx][ny] == 0
• d[nx][ny] != 0
• w[nx][ny] == 0
• w[nx][ny] != 0

41. (2) 处应填（ ）。

{{ select(41) }}

• d[x][y]
• d[x][y] + 1
• d[nx][ny] + d[x][y]
• d[nx][ny] + 1

42. (3) 处应填（ ）。

{{ select(42) }}

• w[x][y]
• w[x][y] + 1
• w[nx][ny] + d[x][y]
• w[nx][ny] + 1

43. (4) 处应填（ ）。

{{ select(43) }}

• d[nx][ny] == 1
• d[nx][ny] == d[x][y] + 1
• w[nx][ny] == 1
• w[nx][ny] == w[x][y] + 1

44. (5) 处应填（ ）。

{{ select(44) }}

• d[x][y]
• d[nx][ny] + d[x][y]
• w[x][y]
• w[nx][ny] + w[x][y]

45. (6) 处应填（ ）。

{{ select(45) }}

• d[n-1][m-1]
• d[n][m]
• w[n-1][m-1]
• w[n][m]