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

1. 设 $A=C=\mathrm{False}$，$B=D=\mathrm{True}$，以下逻辑运算表达式值为假的有（ ）。

{{ select(1) }}

• $(A \land B) \lor (C \lor D)$
• $(A \lor \lnot B) \land (C \lor D)$
• $(\lnot A \lor C) \land (B \lor D)$
• $(A \land D) \lor (B \lor C)$

2. 一个 $8$ 位带符号整数的二进制补码为 10110101。其对应的十进制是（ ）。

{{ select(2) }}

• $53$
• $-53$
• $75$
• $-75$

3. 设 $X$、$Y$、$Z$ 分别表示三进制下的一位数码，若等式 $\overline{XY}+\overline{ZX}=\overline{XYX}$ 在三进制下成立，那么在三进制下，等式 $\overline{XY}\times\overline{ZX}=$（ ）也成立。

{{ select(3) }}

• $\overline{YXX}$
• $\overline{ZXY}$
• $\overline{XZY}$
• $\overline{YZX}$

4. 现有三根柱 $A$、$B$、$C$。$A$ 柱放有 $5$ 个圆盘。$A$ 柱从上到下的圆盘编号为 $1$ 到 $5$。将 $A$ 柱的盘子经 $B$ 柱移入 $C$ 柱，$B$ 柱操作记录为：进、出、进、进、出、进、出、出、进、出。$C$ 柱从下到上的圆盘编号为（ ）。

{{ select(4) }}

• 13425
• 13254
• 21435
• 31254

5. 完全二叉树有 $4n+1$ 个节点，则叶节点数是（ ）。

{{ select(5) }}

• $2n$
• $2n+1$
• $2n+2$
• $3n$

6. 某循环链表至少有三个节点，且它的尾指针为 tail，下面操作说明与代码对应正确的是（ ）。

{{ select(6) }}

• 在头部插入新节点 p：p->next = tail->next->next; tail->next = p;
• 在尾部插入新节点 p：p->next = tail->next; tail->next = p;
• 删除头部节点：p = tail->next; tail->next = p->next; delete p;
• 删除尾部节点：p = tail; tail = tail->next; delete p;

7. $3$ 个顶点的无权图邻接矩阵为 $[[0,1,0],[0,0,1],[1,0,0]]$，顶点编号依次记为 $v_1,v_2,v_3$。以下说法错误的是（ ）。

{{ select(7) }}

• 从 $v_1$ 开始的 DFS 及 BFS 序列相同
• 每个顶点的入度等于出度
• 该图是无向图
• 该图有且仅有一个环

8. 字符串 XYXY 的互不相等的非空子串数量为（ ）。

{{ select(8) }}

• $7$
• $8$
• $10$
• $15$

9. 给定一个序列 $2,5,8,12,16,20,23,38,56,72,91$，用二分法查找 $25$，比较次数是（ ）次。

{{ select(9) }}

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

10. 对一个序列 $a_i$ 来说，若有两个下标满足 $i<j$ 且 $a_i>a_j$，称 $(i,j)$ 构成逆序对。序列 $1,6,3,2,5,4$ 中逆序对数量为（ ）个。

{{ select(10) }}

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

11. 不合法的前缀码的组合为（ ）。

{{ select(11) }}

• (11, 01, 001, 0001)
• (0, 10, 110, 111)
• (1, 01, 001, 000)
• (0, 10, 110, 01)

12. 从 $0$ 到 $9$ 中挑选 $4$ 个不同的数字形成一个集合，且没有数字相差为 $1$ 的选法有（ ）种。

{{ select(12) }}

• $15$
• $18$
• $35$
• $70$

13. 以下方法不属于 std::vector 成员的是（ ）。

{{ select(13) }}

• push_back()
• at()
• pop()
• clear()

14. 能将变量 x 最低处的 1 改为 0 的代码是（ ）。

{{ select(14) }}

• x^=(x&-x);
• x=x^(x-1);
• x|=(x>>1);
• x=x|(x-1);

15. 关于内存下面的说法正确的是（ ）。

{{ select(15) }}

• RAM 是指每次具体分配给程序的内存位置是随机的。
• $1\mathrm{MB}$ 是指 $1024\times1024$ 个字节。
• 内存包括主存 memory、高速缓存 cache 与寄存器 register 三部分。
• 内存中的数据在断电的情况下也能保留 $24$ 小时以上。

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

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

第1题

void recursion(int n)
{
    if (n == 0) return;
    int lowbit = n % 3;
    recursion(n / 3);
    std::cout << lowbit;
}
void iteration(int n)
{
    int buffer[10];
    int size = 0;
    while (n > 0) {
        buffer[size++] = n % 3;
        n = n / 3;
    }
    while (size > 0) {
        std::cout << buffer[--size];
    }
}

16. recursion(0) 及 iteration(0) 都不输出任何内容。

{{ select(16) }}

• 正确
• 错误

17. 若整数 $n$ 满足 $0<n<2^{30}$，recursion(n) 与 iteration(n) 的输出是一致的。

{{ select(17) }}

• 正确
• 错误

18. recursion(n) 与 iteration(n) 具有相同的空间复杂度。

{{ select(18) }}

• 正确
• 错误

19. recursion(n) 的时间复杂度为（ ）。

{{ select(19) }}

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

20. iteration(n) 的时间复杂度为（ ）。

{{ select(20) }}

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

第2题

int solve1(int n)
{
    int s = 0;
    int f = 1;
    for (int i = 1; i <= n; ++i) {
        f = f * i;
        int m = f;
        while (m % 10 == 0) {
            s++;
            m = m / 10;
        }
    }
    return s;
}

int solve2(int n)
{
    int t = 0;
    while (n > 0) {
        t = t + n / 5;
        n = n / 5;
    }
    return t;
}

21. solve1(4) 的返回值为 $1$。

{{ select(21) }}

• 正确
• 错误

22. solve2(10) 的返回值为 $2$。

{{ select(22) }}

• 正确
• 错误

23. 当 $1\le n\le10$ 时，solve1(n) 的返回值等于 solve2(n) 的返回值。

{{ select(23) }}

• 正确
• 错误

24. 当 $n=100$ 时，（ ）。

{{ select(24) }}

• solve1(n) 与 solve2(n) 均会在运行时数值溢出。
• solve1(n) 与 solve2(n) 均不会在运行时数值溢出。
• solve1(n) 会数值溢出，而 solve2(n) 不会。
• solve2(n) 会数值溢出，而 solve1(n) 不会。

25. solve1(n) 的时间复杂度为（ ）。

{{ select(25) }}

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

26. solve2(n) 的时间复杂度为（ ）。

{{ select(26) }}

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

第三题

#include<iostream>
int play[3][3] = {0};
int score[3][3];

bool check_row(int i, int role) {
    if (play[i][0] != role) return false;
    if (play[i][1] != role) return false;
    if (play[i][2] != role) return false;
    return true;
}

bool check_col(int j, int role) {
    if (play[0][j] != role) return false;
    if (play[1][j] != role) return false;
    if (play[2][j] != role) return false;
    return true;
}

bool check_diag(int role) {
    if (play[1][1] != role) return false;
    if (play[0][0] == role && play[2][2] == role) return true;
    if (play[0][2] == role && play[2][0] == role) return true;
    return false;
}

bool check(int i, int j, int role) {
    return check_row(i, role) || check_col(j, role) || check_diag(role);
}

int adv(int step) {
    if (step == 9) return 0;
    int role = (step % 2) + 1;
    const int inf = 1000000000;
    int best = -inf;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            if (play[i][j] == 0) {
                play[i][j] = role;
                if (check(i, j, role)) {
                    best = inf;
                }
                else {
                    int test = score[i][j] - adv(step + 1);
                    if (best < test) {
                        best = test;
                    }
                }
                play[i][j] = 0;
            }
        }
    }
    return best;
}

int main() {
    for (int i = 0; i < 3; ++i)
        for (int j = 0; j < 3; ++j)
            std::cin >> score[i][j];
    int d = adv(0);
    if (d > 0)
        std::cout << "First Win\n";
    else
        std::cout << "Second Win\n";
}

27. 若在游戏过程中，被对手占据棋盘某一行、某一列或某对角线，将输掉比赛。

{{ select(27) }}

• 正确
• 错误

28. 在比赛结束后，累计从 score 获得分数累计为正数的玩家才能获胜。

{{ select(28) }}

• 正确
• 错误

29. 当输入为 0 0 0 0 -10 0 0 0 0 时，输出 First Win。

{{ select(29) }}

• 正确
• 错误

30. 当输入为 -5 0 -5 0 0 0 -5 0 -5 时，输出 First Win。

{{ select(30) }}

• 正确
• 错误

31. 关于程序的逻辑，下列说法错误的是（ ）。

{{ select(31) }}

• 程序解决了一个零和博弈游戏。
• 程序实现了极大极小博弈算法。
• 两个玩家都将以各自最优的策略来参与博弈。
• 第一个玩家追求从 score 里拿走更高的分数，第二个玩家追求从 score 里拿走更低的分数。

32. 设 score 每个元素的绝对值不超过 $100$，则调用 adv(0) 后得到的变量 d，下列说法错误的是（ ）。

{{ select(32) }}

• d 的绝对值不可能等于 inf。
• 当输入的每个数都是正数时，d 必然大于 $0$。
• 当输入的每个数都是奇数时，d 不可能是 $0$。
• 当输入的每个数都是负数时，d 必然小于 $0$。

33. 关于第一步的走法分析，下列说法正确的是（ ）。

{{ select(33) }}

• 第一步必须要放置在棋盘的中央位置才能赢下比赛。
• 第一步必须要放置在棋盘的四个角落位置才能赢下比赛。
• 第一步不能选择 score 值为负的格子。
• 第一步可以不选中央也可以不选四个角落。

34. 该程序主要使用了（ ）算法思想。

{{ select(34) }}

• 分治
• 贪心
• 动态规划
• 回溯

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

第1题

有 $n$ 名学生参加了一场考试，分数没有公开。现有 $m$ 条线索，其中第 $i$ 条线索确定第 $x_i$ 号学生的分数高于第 $y_i$ 号学生。又确定没有人分数是相同的。根据这些线索，将学生的分数排序后，多少人的名次是可以确定的呢？保证给定的线索没有矛盾。

#include<iostream>
int main()
{
    const int maxn = 100;
    bool f[maxn][maxn] = {false};
    int c[maxn] = {0};
    int n, m;
    std::cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int x, y;
        std::cin >> x >> y;
        ____(1)____;
    }

    for (int _(2)_ = 0; _(2)_ < n; ++ _(2)_)
        for (int _(3)_ = 0; _(3)_ < n; ++ _(3)_)
            for (int _(4)_ = 0; _(4)_ < n; ++ _(4)_)
                if (____(5)____)
                    f[i][j] = true;

    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            if (i != j)
                if (___(6)___)
                    c[i]++;

    int ans = 0;
    for (int i = 0; i < n; ++i)
        if (___(7)___) ans ++;
    std::cout << ans << '\n';
}

35. (1) 处应填（ ）。

{{ select(35) }}

• f[x][y] = true
• f[y][x] = true
• c[x] = 0
• c[y] = x

36. (2)、(3)、(4) 处应填（ ）。

{{ select(36) }}

• i、j、k
• i、k、j
• k、i、j
• j、k、i

37. (5) 处应填（ ）。

{{ select(37) }}

• f[i][k] && f[k][j]
• f[i][k] || f[k][j]
• f[i][k] == f[j][k]
• f[i][k] || f[j][k]

38. (6) 处应填（ ）。

{{ select(38) }}

• f[i][j] && f[j][i]
• f[i][j] || f[j][i]
• f[i][j] == f[j][i]
• !f[i][j]

39. (7) 处应填（ ）。

{{ select(39) }}

• c[i] == 0
• c[i] == 1
• c[i] == n - 1
• c[i] == n

第2题

给定 $n$ 个整数 $a_0,a_1,\ldots,a_{n-1}$，其中 $1\le n\le40$，请统计，这个序列有多少种子序列，其子序列的和大于 $0$？

#include<iostream>
#include<algorithm>
int a[40];
int x[1 << 20];
int y[1 << 20];

int generate(int begin, int end, int sum, int* out, int pos) {
    if (begin == end) {
        ____(1)____;
        return 1;
    }
    else {
        int f = generate(begin + 1, end, sum + a[begin], out, pos);
        int s = generate(begin + 1, end, ____(2)____);
        return f + s;
    }
}

int main() {
    int n;
    std::cin >> n;
    for (int i = 0; i < n; ++i) std::cin >> a[i];
    int x_size = ____(3)____;
    int y_size = ____(4)____;
    std::sort(x, x + x_size);
    std::sort(y, y + y_size);
    int j = y_size;
    long long pair = 0;
    for (int i = 0; i < x_size; ++i) {
        while (j > 0 && ____(5)____) {
            j--;
        }
        pair += ____(6)____;
    }
    std::cout << pair << "\n";
}

40. (1) 处应填（ ）。

{{ select(40) }}

• out = sum
• out[0] = sum
• out[pos] = sum
• out[pos+1] = sum

41. (2) 处应填（ ）。

{{ select(41) }}

• sum + a[end], out, pos + 1
• sum + a[end], out, pos + f
• sum, out, pos + 1
• sum, out, pos + f

42. (3) 处应填（ ）。

{{ select(42) }}

• generate(0, n/2, 0, x, 0)
• generate(0, n/2, 0, x, 1)
• generate(0, n/2, 1, x, 0)
• generate(0, n/2, 1, x, 1)

43. (4) 处应填（ ）。

{{ select(43) }}

• generate(n/2, n, 0, y, 0)
• generate(n/2 + 1, n, 0, y, 0)
• generate(n/2, n, 0, y, 1)
• generate(n/2 + 1, n, 0, y, 1)

44. (5) 处应填（ ）。

{{ select(44) }}

• x[i] + y[j-1] > 0
• x[i] + y[j-1] >= 0
• x[i] + y[j-1] <= 0
• x[i] + y[j-1] < 0

45. (6) 处应填（ ）。

{{ select(45) }}

• y_size - j - 1
• y_size - j
• j - 1
• j