一、单项选择题(每题 $2$ 分,共 $30$ 分)

1. 关于 C++ 虚函数,下列说法正确的是( )

{{ select(1) }}

• 虚函数可以是静态成员函数
• 虚函数的声明必须包含函数体
• 虚函数可用于实现动态绑定(多态)
• 构造函数和析构函数都可以声明为虚函数

2. 一棵完全二叉树有 $768$ 个结点,则叶子结点数为( )

{{ select(2) }}

• $384$
• $385$
• $383$
• 无法确定

3. 若一个有 $10$ 个顶点的图用邻接矩阵存储,且该矩阵对称,则该图一定是( )

{{ select(3) }}

• 有向图
• 无向图
• 完全图
• 连通图

4. 二维数组 $a[10][10]$ 按行优先存储,每个元素占 $4$ 字节。若 $a[0][0]$ 的地址为 $100$,则 $a[3][7]$ 的地址是( )

{{ select(4) }}

• $248$
• $252$
• $264$
• $268$

5. 下列哪组关键字用于 C++ 异常处理?( )

{{ select(5) }}

• try
• throw
• catch
• 以上都是

6. 执行以下代码后,输出是( )

int a[] = {1, 2, 3, 4};
int *p = a + 1;
cout << *(p + 2) - *p;

{{ select(6) }}

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

7. 在不带头结点的单链表中,在第一个元素结点之前插入新结点 $s$,正确操作是( )

{{ select(7) }}

• head = s; s->next = head;
• s->next = head->next; head = s;
• head->next = s; s->next = head;
• s->next = head; head = s;

8. 用权值为 $5,9,12,13,16,45$ 的叶子构造哈夫曼树,其带权路径长度 WPL 为( )

{{ select(8) }}

• $225$
• $219$
• $224$
• $208$

9. 一棵三叉树中有 $2$ 个度为 $3$ 的结点,$3$ 个度为 $2$ 的结点,$4$ 个度为 $1$ 的结点,则叶子结点数为( )

{{ select(9) }}

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

10. 八进制数 $75.4$ 转换成十进制是( )

{{ select(10) }}

• $61.5$
• $61.75$
• $63.5$
• $63.75$

11. 字符串 "ababa" 的所有不同非空子串个数为( )

{{ select(11) }}

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

12. 执行以下代码后,变量的值和指针指向关系为( )

int a = 50, b = 80;
int *p = &a;
*p = b;
p = &b;
*p = 100;

{{ select(12) }}

• $a=50$, $b=100$, $p$ 指向 $a$
• $a=80$, $b=100$, $p$ 指向 $b$
• $a=80$, $b=80$, $p$ 指向 $b$
• $a=50$, $b=80$, $p$ 指向 $a$

13. 栈 $S$ 和队列 $Q$ 初始为空,现有元素 $a,b,c,d,e$ 依次入栈,操作可交错(入栈、出栈、入队、出队)。已知队列出队序列为 $c,b,e,a,d$,则栈 $S$ 的最小容量为( )

{{ select(13) }}

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

14. 现有字符频率:$f:5\%$, $g:12\%$, $h:18\%$, $i:25\%$, $j:40\%$,构建哈夫曼树,字符 $h$ 的编码长度为( )

{{ select(14) }}

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

15. 关于 C++ 结构体和类的区别,说法错误的是( )

{{ select(15) }}

• struct 默认成员为公有权限,class 默认私有
• 二者均可以定义成员变量和成员函数
• 二者均支持面向对象封装特性
• struct 不可以继承,class 可以继承

程序输入不超过数组或字符串定义的范围。

除特殊说明外,判断题每题 $1.5$ 分,选择题每题 $3$ 分,共 $40$ 分。判断题正确填「正确」,错误填「错误」。

阅读程序(一)

#include <bits/stdc++.h>
using namespace std;
int n, b, d;
vector<int> ans;

int hammingDist(int x) {
    int cnt = 0;
    while (x) {
        cnt++;
        x &= (x - 1);
    }
    return cnt;
}

int main() {
    cin >> n >> b >> d;
    for (int i = 0; i < (1 << b); i++) {
        bool ok = true;
        for (int x : ans) {
            if (hammingDist(x ^ i) < d) {
                ok = false;
                break;
            }
        }
        if (ok) {
            ans.push_back(i);
            if ((int)ans.size() == n) break;
        }
    }
    for (int i = 0; i < n; i++) {
        cout << ans[i] << " ";
    }
    return 0;
}

(1) hammingDist 函数的时间复杂度是 $O(n)$。

{{ select(16) }}

• 正确
• 错误

(2) x &= (x - 1); 这行代码的作用是将 $x$ 的最低位的 $1$ 变为 $0$。

{{ select(17) }}

• 正确
• 错误

(3) 程序输出的最后一个数一定是 $2^b-1$。

{{ select(18) }}

• 正确
• 错误

(4) 当输入 $n=4$, $b=3$, $d=2$ 时,程序的输出是什么?

{{ select(19) }}

• 0 3 5
• 0 3 6
• 0 5 6
• 0 3 5 6

(5) hammingDist(9) 的返回值是多少?( $2$ 分)

{{ select(20) }}

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

(6) 当输入 $n=6$, $b=3$, $d=3$ 时,程序的行为如何?

{{ select(21) }}

• 输出 0 7 0 0 4 0
• 输出 0 7 0 0 4
• 输出 0 1 2 3 4 5 6 7,然后停止
• 程序会陷入死循环

阅读程序(二)

#include <bits/stdc++.h>
using namespace std;
int n, a[1000005], k;
int gcd(int x, int y) {
    while (y != 0) {
        int r = x % y;
        x = y;
        y = r;
    }
    return x;
}
int lcm(int x, int y) {
    int r = gcd(x, y);
    return x / r * y;
}
int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    k = lcm(a[0], a[1]);
    for (int i = 2; i < n; i++) {
        k = lcm(k, a[i]);
    }
    cout << k << "\n";
    return 0;
}

(1) lcm 函数中的 return x / r * y 可以安全地改为 return x * y / r。

{{ select(22) }}

• 正确
• 错误

(2) 如果输入的所有数互质,程序输出的结果等于所有数的乘积。

{{ select(23) }}

• 正确
• 错误

(3) gcd 函数中,如果 $x$ 和 $y$ 都是负数,算法仍然能够正确计算最大公约数的绝对值。

{{ select(24) }}

• 正确
• 错误

(4) 程序的时间复杂度为 $O(n\log M)$,其中 $M$ 是数组中的最大值。( $2$ 分)

{{ select(25) }}

• 正确
• 错误

(5) 如果输入 $n=2$, $a=[12,18]$,gcd(12,18) 执行过程中,$r$ 的值依次是什么?( $2$ 分)

{{ select(26) }}

• $6,0$
• $12,6,0$
• $6,12,0$
• $18,12,6$

(6) 程序在计算 lcm 时使用 return x / r * y 而不是 return x * y / r 的主要原因是?

{{ select(27) }}

• 提高计算精度
• 避免中间结果溢出
• 减少函数调用次数
• 加快计算速度

(7) 若输入 $n=4$, $a=[2,3,4,5]$,程序的输出是?

{{ select(28) }}

• $60$
• $120$
• $30$
• $240$

阅读程序(三)

#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 100010;
int n, p1[MAX_N], p2[MAX_N], pos[MAX_N], seq[MAX_N], lis[MAX_N];

int lower_bound(int arr[], int len, int target) {
    int left = 0, right = len;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return left;
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> p1[i];
        pos[p1[i]] = i;
    }
    for (int i = 1; i <= n; ++i) {
        cin >> p2[i];
        seq[i] = pos[p2[i]];
    }
    int len = 0;
    for (int i = 1; i <= n; ++i) {
        int idx = lower_bound(lis, len, seq[i]);
        if (idx == len) {
            lis[len++] = seq[i];
        } else {
            lis[idx] = seq[i];
        }
    }
    cout << len << endl;
    return 0;
}

(1) pos[p1[i]] = i 中,pos 数组的作用是记录每个数值在 p1 中的位置。

{{ select(29) }}

• 正确
• 错误

(2) 程序中的 lis 数组在算法执行过程中始终保持严格递增。

{{ select(30) }}

• 正确
• 错误

(3) 该算法的时间复杂度为 $O(n\log n)$。( $2$ 分)

{{ select(31) }}

• 正确
• 错误

(4) 当输入为 $n=5$, $p1=[3,2,4,1,5]$, $p2=[2,1,3,4,5]$ 时,程序的输出是?( $2$ 分)

{{ select(32) }}

• $1$
• $3$
• $5$
• $0$

(5) 当输入为 $n=5$, $p1=[10,8,12,19,6]$, $p2=[3,9,8,8,2]$ 时,程序的输出是?

{{ select(33) }}

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

(6) 如果输入 $n=4$, $p1=[2,4,1,3]$, $p2=[3,1,4,2]$,seq 数组的值是?( $2$ 分)

{{ select(34) }}

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

(7) lower_bound(lis, len, seq[i]) 调用中,如果 seq[i] 大于 lis 中所有元素,返回值 idx 等于什么?

{{ select(35) }}

• $0$
• $\mathrm{len}$
• $\mathrm{len}-1$
• 任意值

单项选择题,每题 $3$ 分,共 $30$ 分。

完善程序(一)

B3738 [信息与未来 2018] 素数方阵

把前 $n^2$ 个素数从左上角开始按右、下、左、上、右、下、左、上……的顺序填入 $n\times n$ 的方阵,就得到蛇形素数方阵。$n=4$ 和 $n=5$ 时如下:

$$\begin{array}{cccc} 2 & 3 & 5 & 7 \\ 37 & 41 & 43 & 11 \\ 31 & 53 & 47 & 13 \\ 29 & 23 & 19 & 17 \end{array} \qquad \begin{array}{ccccc} 2 & 3 & 5 & 7 & 11 \\ 53 & 59 & 61 & 67 & 13 \\ 47 & 89 & 97 & 71 & 17 \\ 43 & 83 & 79 & 73 & 19 \\ 41 & 37 & 31 & 29 & 23 \end{array}$$

给定 $n,x,y$,输出 $n\times n$ 蛇形素数方阵第 $x$ 行第 $y$ 列的值。

样例:

5 4 3

79

下面程序请补全。

#include <bits/stdc++.h>
using namespace std;

bool isPrime(int n) {
    if (n < 2) return false;
    if (n == 2) return true;
    if (n % 2 == 0) return false;
    for (int i = 3; i * i <= n; i += 2) {
        if (n % i == 0) return false;
    }
    return true;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, x, y, num = 2;
    cin >> n >> x >> y;
    vector<int> primes;
    while (primes.size() < n * n) {
        if (isPrime(num)) {
            primes.push_back(num);
        }
        num++;
    }
    vector<vector<int> > g(n, vector<int>(n, 0));
    ①;
    int dir = 0, row = 0, col = 0;
    for (int i = 0; i < n * n; i++) {
        ②;
        int nx = row + dx[dir], ny = col + dy[dir];
        if (③) {
            ④;
            nx = row + dx[dir], ny = col + dy[dir];
        }
        row = nx, col = ny;
    }
    cout << ⑤ << endl;
    return 0;
}

(1) ① 处应填( )

{{ select(36) }}

• int dx[] = {1, 0, 0, -1}, dy[] = {1, -1, 0, 0}
• int dx[] = {1, 0, -1, 0}, dy[] = {0, -1, 1, 0}
• int dx[] = {0, 1, -1, 0}, dy[] = {0, 0, -1, 1}
• int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}

(2) ② 处应填( )

{{ select(37) }}

• g[col][row] = i
• g[col][row] = primes[i]
• g[row][col] = i
• g[row][col] = primes[i]

(3) ③ 处应填( )

{{ select(38) }}

• nx < 0 || nx >= n || ny < 0 || ny >= n || g[nx][ny] == 0
• nx < 0 || nx >= n || ny < 0 || ny >= n || g[nx][ny] != 0
• nx >= 0 && nx < n && ny >= 0 && ny < n && g[nx][ny] == 0
• nx >= 0 && nx < n && ny >= 0 && ny < n && g[nx][ny] != 0

(4) ④ 处应填( )

{{ select(39) }}

• dir = (dir + 1) / 4
• dir = dir / 4
• dir = (dir + 1) % 4
• dir = dir % 4

(5) ⑤ 处应填( )

{{ select(40) }}

• g[x - 1][y - 1]
• g[row - 1][row - 1]
• g[row][row]
• g[x][y]

完善程序(二)

P11962 [GESP202503 六级] 树上漫步

小 A 有一棵 $n$ 个结点的树。从某个结点出发,每一步走到相邻结点,且只在偶数步(可为 $0$ 步)后结束。对于树上每个结点,求从它出发经过偶数步能到达的结点数(结点可重复经过,计不同结束结点)。

第一行正整数 $n$。接下来 $n-1$ 行每行两个整数 $u_i,v_i$ 表示边。输出一行 $n$ 个整数,第 $i$ 个表示从结点 $i$ 出发的答案。

样例:

4
1 3
3 2
4 3

3 3 1 3

下面程序请补全。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 5;
const int MAXM = MAXN << 1;
int n;
int to[MAXM], nextEdge[MAXM], head[MAXN], cnt;
int ans[MAXN], bel[MAXN];

void addEdge(int u, int v) {
    cnt++;
    to[cnt] = v;
    nextEdge[cnt] = head[u];
    head[u] = cnt;
}

void dfs(int u, int p, int d) {
    ①;
    ②;
    for (int e = head[u]; e; e = nextEdge[e]) {
        if (to[e] != p) {
            ③;
        }
    }
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i < n; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        addEdge(u, v);
        addEdge(v, u);
    }
    ④;
    for (int i = 1; i <= n; i++) {
        printf("%d ", ⑤);
    }
    return 0;
}

(1) ① 处应填( )

{{ select(41) }}

• bel[u] = d
• bel[d] = u
• bel[u] = p
• bel[p] = u

(2) ② 处应填( )

{{ select(42) }}

• ans[p] = u
• ans[u]++
• ans[p]++
• ans[d]++

(3) ③ 处应填( )

{{ select(43) }}

• dfs(to[e], p, d)
• dfs(to[e], u, d)
• dfs(to[e], p, d ^ 1)
• dfs(to[e], u, d ^ 1)

(4) ④ 处应填( )

{{ select(44) }}

• dfs(1, 0, 1)
• dfs(1, 0, 0)
• dfs(1, 1, 1)
• dfs(1, 1, 0)

(5) ⑤ 处应填( )

{{ select(45) }}

• ans[i]
• bel[i]
• bel[ans[i]]
• ans[bel[i]]