一、单选题（每题 2 分，共 30 分）

1. 国家 “以旧换新” 政策仍在继续，小杨家决定在家里旧的冰箱、电视、洗衣机、微波炉中选两种换新。其中，冰箱有 $4$ 种型号可选，电视有 $6$ 种型号可选，洗衣机有 $3$ 种型号可选，微波炉有 $5$ 种型号可选。请问小杨家共有多少种换新的方案？（ ）

{{ select(1) }}

• $18$
• $119$
• $238$
• $360$

2. 小杨和 $3$ 位朋友约好一起去看电影 “哪吒 2”。打开购票软件，他们发现，已经没有同一排连续的四个座位了（图中每个方框代表一个座位，红色方框代表已经售出）。朋友们商量了一下，决定分为两组，每组两人在同一排的相邻两个座位，且两组之间至少有一对座位是前后相邻的。请问共有多少种购票方案？（ ）。

   

{{ select(2) }}

• $495$
• $96$
• $7$
• $4$

3. 下面关于 C++ 类构造和析构函数的说法，错误的是（ ）。

{{ select(3) }}

• 构造函数不能声明为虚函数。
• 析构函数必须声明为虚函数。
• 类的默认构造函数可以被声明为 private。
• 类的析构函数可以被声明为 private。

4. 下列关于树和图的说法，错误的是（ ）。

{{ select(4) }}

• 树是一种有向无环图，有向无环图都是一棵树。
• 如果把树看做有向图，每个节点指向其子节点，则该图是弱连通图。
• $N$ 个顶点且连通的无向图，其最小生成树一定包含 $N-1$ 个条边。
• $N+1$ 个顶点、$N$ 条边的有向图，一定不是强连通的。

5. 从 $1$ 到 $2025$ 这 $2025$ 个数中，包含数字 $5$ 的个数（ ）。

{{ select(5) }}

• $600$
• $601$
• $602$
• $603$

6. 已定义 double 类型的变量 $r$ 和 $theta$，分别表示图中圆半径和圆心角。下列表达式中可以求出弦长 $s$ 的是（ ）。

   

{{ select(6) }}

• r * cos(theta)
• r * cos(theta / 2) * 2
• r * sin(theta)
• r * sin(theta / 2) * 2

7. $N$ 个节点的平衡二叉树的高为（ ）。

{{ select(7) }}

• $\lfloor \log_2 N\rfloor$
• $\lceil \log_2 N\rceil$
• $\lfloor \log_2 N\rfloor + 1$
• 无法确定

8. 下列关于算法的说法，错误的是（ ）。

{{ select(8) }}

• 如果有足够的时间和空间，枚举法能解决一切有限的问题。
• 分治算法将原问题分为多个子问题进行求解，且分解出的子问题必须相互独立。
• 如果能找到合理的贪心原则，贪心算法往往能够比其他方法更快求解。
• 倍增法在搜索未知长度的有序数组时，通过动态倍增或减半步长，快速定位目标范围。

9. $2025$ 是个神奇的数字，因为它是由两个数 $20$ 和 $25$ 拼接而成，而且 $2025=(20+25)^2$。小杨决定写个程序找找小于 $N$ 的正整数中共有多少这样神奇的数字。下面程序横线处应填入的是（ ）。

    #include <string>
    int count_miracle(int N) {
        int cnt = 0;
        for (int n = 1; n * n < N; n++) {
            int n2 = n * n;
            std::string s = std::to_string(n2);
   
            for (int i = 1; i < s.length(); i++)
                if (s[i] != '0') {
                    std::string sl = s.substr(0, i);
                    std::string sr = s.substr(i);
                    int nl = std::stoi(sl);
                    int nr = std::stoi(sr);
                    if (_________) // 在此处填入选项
                        cnt++;
                }
        }
        return cnt;
    }
   

{{ select(9) }}

• nl + nr == n
• nl + nr == n2
• (nl + nr) * (nl + nr) == n
• (nl + nr) ^ 2 == n2

10. 上一题中程序的时间复杂度为（ ）。

{{ select(10) }}

• $O(N\log N)$
• $O(N^{1/2})$
• $O(N^{1/2}\log N)$
• $O(N^{1/2}(\log N)^2)$

11. 下面的欧氏筛法程序中，两个横线处应填入的分别是（ ）。

    int primes[MAXP], num = 0;
    bool isPrime[MAXN + 1] = {false};
    void sieve() {
        for (int n = 2; n <= MAXN; n++) {
            if (!isPrime[n])
                primes[num++] = n;
            for (int i = 0; i < num && ________; i++) { // 在此处填入选项
                isPrime[n * primes[i]] = true;
                if (________) // 在此处填入选项
                    break;
            }
        }
    }
    

{{ select(11) }}

• n * primes[i] < MAXN
  n % primes[i] == 0
  

• n * primes[i] < MAXN
  primes[i] > n
  

• n * primes[i] <= MAXN
  n % primes[i] == 0
  

• n * primes[i] <= MAXN
  primes[i] > n
  

12. 下面 Floyd 算法中，横线处应该填入的是（ ）。

    #include <iostream>
    using namespace std;
    
    #define N 21
    #define INF 99999999
    int map[N][N];
    int main() {
        int n, m, t1, t2, t3;
        cin >> n >> m;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (i == j)
                    map[i][j] = 0;
                else
                    map[i][j] = INF;
            }
        }
        for (int i = 1; i <= m; i++) {
            cin >> t1 >> t2 >> t3;
            map[t1][t2] = t3;
        }
        for (int k = 1; k <= n; k++)
            for (int i = 1; i <= n; i++)
                for (int j = 1; j <= n; j++)
                    if (map[i][j] > map[i][k] + map[k][j])
                        ________; // 在此处填入选项
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                cout.width(4);
                cout << map[i][j];
            }
            cout << endl;
        }
    }
    

{{ select(12) }}

• map[i][j] = map[i][k] + map[k][j]
• map[i][k] = map[i][j] - map[k][j]
• map[i][j] = map[i][k] - map[k][j]
• map[k][j] = map[i][j] - map[i][k]

13. 上一题中程序的时间复杂度为（ ）。

{{ select(13) }}

• $O(N)$
• $O(N^2)$
• $O(N^3)$
• $O(N^2\log N)$

14. 下列程序实现了输出杨辉三角形，代码中横线部分应该填入的是（ ）。

    #include <iostream>
    using namespace std;
    #define N 35
    int a[N];
    int main() {
        int n;
        cin >> n;
        for (int i = 0; i < n; i++) {
            a[i] = 1;
            for (int j = i - 1; j > 0; j--)
                ________; // 在此处填入选项
            for (int j = 0; j <= i; j++)
                cout << a[j] << " ";
            cout << endl;
        }
        return 0;
    }
    

{{ select(14) }}

• a[j] += a[j + 1]
• a[j] += a[j - 1]
• a[j - 1] += a[j]
• a[j + 1] += a[j]

15. 上一题中程序的时间复杂度为（ ）。

{{ select(15) }}

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

二、判断题（每题 2 分，共 20 分）

1. 表达式 '5' - 3.0 的结果为 $2.0$，类型为 double。（ ）

{{ select(16) }}

• 正确
• 错误

2. 在 C++ 语言中，如果想要在一个函数内调用一个类的私有方法，可以在该类中将该函数声明为友元函数。（ ）

{{ select(17) }}

• 正确
• 错误

3. 插入排序一般是稳定的。（ ）

{{ select(18) }}

• 正确
• 错误

4. $5$ 个相同的红球和 $4$ 个相同的蓝球排成一排，要求蓝球不能相邻，则一共有 $15$ 种排列方案。（ ）

{{ select(19) }}

• 正确
• 错误

5. 使用 math.h 或 cmath 头文件中的函数，表达式 pow(2, 5) 的结果类型为 int、值为 $32$。（ ）

{{ select(20) }}

• 正确
• 错误

6. C++ 是一种面向对象编程语言，C 则不是。多态是面向对象三大特性之一，虚函数是动态多态的代表特性。因此，使用 C 语言无法实现虚函数。（ ）

{{ select(21) }}

• 正确
• 错误

7. 在 $N$ 个节点的平衡二叉树中查找指定元素的最差时间复杂度为 $O(N)$。（ ）

{{ select(22) }}

• 正确
• 错误

8. 定义 int 类型的变量 $a$ 和 $b$，求二次函数 $y=x^2+ax+b$ 取最小值时 $x$ 的值，可以通过表达式 -a / 2.0 求得。（ ）

{{ select(23) }}

• 正确
• 错误

9. 判断无向图中是否有环，可以通过广度优先搜索实现。（ ）

{{ select(24) }}

• 正确
• 错误

10. 从 $32$ 名学生中选出 $4$ 人分别担任班长、副班长、学习委员和组织委员，共有 $C_{32}^4$ 种不同的选法。（ ）

{{ select(25) }}

• 正确
• 错误