一、单项选择题（共计 $30$ 分）

共 $15$ 题，每题 $2$ 分。每题有且仅有一个正确选项。

1. 以下哪个序列对应数字 $0$ 至 $7$ 的 $4$ 位二进制格雷码（　）。

{{ select(1) }}

• 0000, 0001, 0011, 0010, 0110, 0111, 0101, 1000
• 0000, 0001, 0011, 0010, 0110, 0111, 0101, 0100
• 0000, 0001, 0011, 0010, 0100, 0101, 0111, 0110
• 0000, 0001, 0011, 0010, 0110, 0111, 0100, 0101

2. 以下判断一个正整数 n 是否是偶数的代码中，错误的是（　）。

{{ select(2) }}

• if (n % 2 == 0)
• if (!(n % 2))
• if (n & 1)
• if (n % 2 != 1)

3. 在 C++ 中，5 ^ -5 和 5 & -5 的值分别为（　）。

{{ select(3) }}

• -10, 5
• -2, -5
• -2, 1
• -10, 1

4. 一棵哈夫曼树，拥有 $13$ 个叶结点。则该哈夫曼树的结点总数为（　）。

{{ select(4) }}

• $25$
• $26$
• $27$
• 无法确定

5. 下列关于树的描述中正确的是（　）。

{{ select(5) }}

• 有 $n$ 个结点的树，边数只能是 $n-1$ 条。
• 在哈夫曼树中，叶子结点比非叶子结点多 $1$ 或 $2$ 个。
• 完全二叉树是二叉排序树。
• 在二叉树的后序遍历序列中，若结点 u 在结点 v 之前，则 u 一定是 v 的祖先。

6. 下面代码构成的是（　）类型的数据结构。

struct Node
{
    int value;
    Node* link;
};

Node* add(Node* node, int value)
{
    Node* new_node = new Node;
    new_node->link = node;
    new_node->value = value;
    return new_node;
}

Node* del(Node* node)
{
    Node* new_node = node->link;
    delete node;
    return new_node;
}

int main()
{
    Node* head = add(nullptr, 1);
    head = add(head, 2);
    head = del(head);
}

{{ select(6) }}

• 双向链表
• 栈
• 循环链表
• 队列

7. 以下代码调用 $F(n)$ 的时间复杂度为（　）。

int F(int n)
{
    if (n <= 2)
        return 1;
    else
        return F(n - 1) + F(n - 2);
}

{{ select(7) }}

• $O(1)$
• $O(n)$
• $O(n^2)$
• $O(2^n)$

8. 在简单图中，有 $n$ 个顶点的强连通图最少有（　）条边，最多有（　）条边。

{{ select(8) }}

• $n-1$，$n$
• $n-1$，$n(n-1)$
• $n$，$n(n-1)$
• $n$，$\dfrac{n(n-1)}{2}$

9. 以下关于强连通图的说法中，正确的是（　）。

{{ select(9) }}

• 图中一定有环
• 每个顶点的度数都大于 $0$
• 对于大于 $1$ 个点的强连通图，任意两个顶点之间都有路径相连
• 每个顶点至少都连有一条边

10. 用线性探测法把 $k$ 个关键字相同但内容不同的数据存入哈希表中，至少要进行（　）次探测。

{{ select(10) }}

• $k+1$
• $k-1$
• $\dfrac{(k+1)k}{2}$
• $\dfrac{(k-1)k}{2}$

11. 求 $a,b,c,d,e,f$ 六个字母的全排列中不允许出现 ace 和 df 子串的排列数（　）。

{{ select(11) }}

• $177$
• $377$
• $477$
• $582$

12. 一堆卡片共 $2025$ 张，设定一个数量，不断从牌堆中取该数量的牌，记 $A$ 表示该数量为素数的方案数，记 $B$ 为该数量为奇数的方案数。则 $A+B=$（　）。

{{ select(12) }}

• $16$
• $17$
• $18$
• $19$

13. 正整数 $n>3$ 称为理想数，若存在正整数 $k$（$1<k<n-1$）使得 $C(n,k-1)$、$C(n,k)$、$C(n,k+1)$ 构成等差数列（其中 $C(n,k)$ 为组合数，且 $C(n,k)=\dfrac{n!}{k!(n-k)!}$），则不超过 $2026$ 的理想数的个数为（　）。

{{ select(13) }}

• $43$
• $44$
• $45$
• $46$

14. 已知一棵二叉树有 $2026$ 个结点，则其中至多有（　）个结点有 $2$ 个子结点。

{{ select(14) }}

• $1010$
• $1011$
• $1012$
• $1013$

15. 从乘法算式 $1\times 2\times 3\times 4\times\cdots\times 24\times 25$ 中，最少要删掉（　）个数才能使剩下的数的乘积是完全平方数。

{{ select(15) }}

• $3$
• $4$
• $5$
• $6$

二、阅读程序（共计 40 分）

判断题 $1$ 分，选择题 $3$ 分，共计 $40$ 分。

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

第1题

bool check(int n, int a[])
{
    bool found = false;
    for (int i = 0; i + 1 < n; ++i) {
        if (a[i] > a[i+1]) {
            found = true;
            auto temp = a[i];
            a[i] = a[i+1];
            a[i+1] = temp;
        }
    }
    return found;
}
void solve(int n, int a[])
{
    while (check(n, a))
        ;
}

判断题

16. solve 函数的 while 语句只写一份分号会产生语法错误。

{{ select(16) }}

• 正确
• 错误

17. 当输入参数 $n \in [0, 1024]$ 时，solve 可能会进入死循环。

{{ select(17) }}

• 正确
• 错误

18. 当 $n=5$，$a=[1, 2, 3, 4, 5]$ 时，while 循环只运行一次。

{{ select(18) }}

• 正确
• 错误

19. 当 $n=5$，$a=[5, 4, 3, 2, 1]$ 时，while 循环运行两次。

{{ select(19) }}

• 正确
• 错误

20. solve 结束后，a 数组以降序排列。

{{ select(20) }}

• 正确
• 错误

选择题

21. 当输入为 $n=5$，$a=[3, 1, 4, 1, 5]$ 时，程序结束时，$a=$（ ）。

{{ select(21) }}

• $[1, 3, 1, 4, 5]$
• $[5, 4, 3, 1, 1]$
• $[1, 1, 3, 4, 5]$
• $[3, 1, 4, 1, 5]$

22. 程序交换 a[i] 与 a[i+1] 的次数（ ）。

{{ select(22) }}

• 小于数组 a 的逆序对数量
• 等于数组 a 的逆序对数量
• 大于数组 a 的逆序对数量
• 与数组 a 的逆序对数量无关

23. 程序的最坏时间复杂度是（ ）。

{{ select(23) }}

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

第2题

bool move(int b[], int n)
{
    for (int i = 0; i < n; ++i) {
        if (b[i] == 1) {
            b[i] = 0;
        }
        else {
            b[i] = 1;
            return true;
        }
    }
    return false;
}
void print(int n)
{
    int b[n];
    for (int i = 0; i < n; ++i) b[i] = 0;
    do {
        for (int i = 0; i < n; ++i) std::cout << b[i];
        std::cout << "\n";
    }
    while (move(b, n));
}
int count(int n)
{
    int b[100];
    for (int i = 0; i < n; ++i) b[i] = 0;
    int c = 0;
    do {
        c++;
    }
    while (move(b, n));
    return c;
}

判断题

24. 当输入参数 $n \in (0, 20)$ 时，count 可能会陷入无尽的循环。

{{ select(24) }}

• 正确
• 错误

25. print 输出的 0 与 1 必然一样多。

{{ select(25) }}

• 正确
• 错误

26. print(6) 输出的第 $5$ 行第 $4$ 列的字符为 0。

{{ select(26) }}

• 正确
• 错误

27. print(16) 输出的第 $523$ 行第 $14$ 列的字符为 1。

{{ select(27) }}

• 正确
• 错误

第2题（续）

选择题

28. count(2) 的返回值为（　）。

{{ select(28) }}

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

29. print(n) 与 count(n) 的时间复杂度为（　）。

{{ select(29) }}

• $\Theta(2^n)$，$\Theta(2^n)$
• $\Theta(n\cdot 2^n)$，$\Theta(2^n)$
• $\Theta(n\cdot 2^n)$，$\Theta(n\cdot 2^n)$
• $\Theta(4^n)$，$\Theta(2^n)$

30. 以下说法错误的是（　）。

{{ select(30) }}

• print(n) 前一半输出全是偶数，后一半输出全是奇数
• 若将 print(n) 输出的每行内容看成一个数字，则它们依次递增
• print(n) 输出的每一行内容都是不同的
• print(n) 输出的每一列内容都是不同的

第3题

const int mod = 1'000'000'007;
bool filled[maxn][maxn];
int mem[maxn][maxn];

int solve(int i, int j, int a[], int b[])
{
    if (i == 0 || j == 0) {
        return 1;
    }
    if (filled[i][j]) {
        return mem[i][j];
    }
    filled[i][j] = true;
    int sum = (solve(i - 1, j, a, b) + solve(i, j - 1, a, b)) % mod;
    if (a[i] == b[j]) {
        return mem[i][j] = sum;
    }
    else {
        return mem[i][j] = (sum - solve(i - 1, j - 1, a, b)) % mod;
    }
}

判断题

31. 若 $a[1]=1$，$a[2]=3$，$b[1]=3$，$b[2]=1$，solve(2, 2, a, b) 返回 $3$（　）。

{{ select(31) }}

• 正确
• 错误

32. solve(0, 0, a, b) 返回 $1$（　）。

{{ select(32) }}

• 正确
• 错误

33. solve(n, n, a, a) 返回 $2^n$（　）。

{{ select(33) }}

• 正确
• 错误

34. 函数 solve 的返回值可能小于 $0$（　）。

{{ select(34) }}

• 正确
• 错误

选择题

35. 该程序的主要功能是（　）。

{{ select(35) }}

• 计算两个序列的最长公共子序列的长度
• 计算两个序列的公共子序列的数量
• 计算两个序列的公共子串的数量
• 计算两个序列的相同元素个数

36. solve(n, m, a, b) 的最坏时间复杂度为（　）。

{{ select(36) }}

• $O(n+m)$
• $O(n\cdot m)$
• $O(2^{m+n})$
• $O(n\log m)$

37. 当 a[i] != b[j] 时，返回值需要减去 solve(i - 1, j - 1, ...) 的原因是（　）。

{{ select(37) }}

• 排除重复情况
• 排除错误情况
• 优化程序的空间效率
• 优化程序的时间效率

三、完善程序（共计 $30$ 分）

单项选择题，每小题 $3$ 分。

第1题 套餐限价

有一家快餐店，出售 $N$ 种主食，其价格以数组 A[0..N) 表示，出售 $M$ 种饮料，其价格以数组 B[0..M) 表示。

现推出一种促销活动：顾客可以任选主食及饮料各一份形成套餐，若套餐价格超过一个给定的最高价格 $L$，则这份套餐只收取 $L$ 元。

请计算，若顾客购买所有食物与饮料的搭配（共有 $N\times M$ 种），需要花多少钱。

long long S[MAXN];
long long solve(int N, int M, int L, int A[], int B[])
{
    std::sort(A, A + ____(1)____);
    std::sort(B, B + M);
    S[0] = 0;
    for (int i = 0; i < M; ++i) {
        S[i + 1] = S[i] + B[i];
    }
    long long j = ____(2)____;
    long long sum = 0;
    for (int i = 0; i < N; ++i)
    {
        while (____(3)____ && A[i] + B[j - 1] > L)
        {
            j--;
        }
        sum += (A[i] * ____(4)____);
        sum += S[____(5)____];
        sum += (M - j) * L;
    }
    return sum;
}

38. （$1$）处应填（　）。

{{ select(38) }}

• N - 1
• N
• N + 1
• M

39. （$2$）处应填（　）。

{{ select(39) }}

• M - 1
• M
• M + 1
• N

40. （$3$）处应填（　）。

{{ select(40) }}

• j > 0
• j >= 0
• j > 1
• j < M

41. （$4$）处应填（　）。

{{ select(41) }}

• j - 1
• j
• j + 1
• i

42. （$5$）处应填（　）。

{{ select(42) }}

• i - 1
• i
• j - 1
• j

第2题

给定 $N$ 个点、$M$ 条边，构成一个图。请统计从 $1$ 号出发，有多少条简单路径。所谓简单路径，就是路径上的所有点及所有边不会重复出现两次。如果路径超过 $1024$ 条，则输出 $-1$。

#include <iostream>
#include <vector>

int N, M;
std::vector<int> adj[200001]; // 邻接表
bool visited[200001];
const int limit = 1024;
int cnt = 0;

void dfs(int node)
{
    ____(1)____;
    if (cnt > limit) return;
    visited[node] = ____(2)____;
    for (auto v : ____(3)____)
    {
        if (not visited[v])
        {
            dfs(____(4)____);
        }
    }
    visited[node] = ____(5)____;
}

int main()
{
    std::cin >> N >> M;
    for (int i = 0; i < M; ++i) {
        int A, B;
        std::cin >> A >> B;
        adj[A].push_back(B);
        adj[B].push_back(A);
    }
    dfs(____(6)____);
    if (cnt > limit) {
        std::cout << -1 << "\n";
    }
    else {
        std::cout << cnt << "\n";
    }
}

43. （$1$）处应填（　）。

{{ select(43) }}

• cnt += 1
• cnt -= 1
• cnt *= 2
• cnt += 2

44. （$2$）（$5$）处应填（　）。

{{ select(44) }}

• true 与 true
• true 与 false
• false 与 true
• false 与 false

45. （$3$）处应填（　）。

{{ select(45) }}

• visited[v]
• adj[v]
• visited[node]
• adj[node]

46. （$4$）处应填（　）。

{{ select(46) }}

• node
• cnt
• v
• limit

47. （$6$）处应填（　）。

{{ select(47) }}

• 0
• 1
• N
• cnt