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

1. 阅读下面代码,输出结果是?

char c = '9';
cout << c - '0' + 1;

{{ select(1) }}

• $9$
• '9'
• $1$
• $10$

2. 四进制数 $123_4$ 与八进制数 $45_8$ 的和对应的十进制值是?

{{ select(2) }}

• $60$
• $62$
• $64$
• $66$

3. 阅读下面代码,输出结果是?

int s = 0;
for (int i = 1; i <= 5; i++) {
    if (i % 2 == 0)
        s += i;
    else
        s -= i;
}
cout << s;

{{ select(3) }}

• $-3$
• $-1$
• $3$
• $15$

4. 阅读下面代码,输出结果是?

void f(int a, int b) {
    int t = a;
    a = b;
    b = t;
}
int main() {
    int x = 1, y = 2;
    f(x, y);
    cout << x << " " << y;
    return 0;
}

{{ select(4) }}

• $1$ $2$
• $2$ $1$
• $1$ $1$
• $2$ $2$

5. 阅读下面代码,输出结果是?

struct Node {
    int v;
    Node* nxt;
};
Node a, b, c;
int main() {
    a.v = 1; b.v = 2; c.v = 3;
    a.nxt = &b; b.nxt = &c; c.nxt = 0;
    a.nxt = a.nxt->nxt;
    cout << a.v << " " << a.nxt->v;
    return 0;
}

{{ select(5) }}

• $1$ $2$
• $1$ $3$
• $2$ $3$
• 程序无法通过编译

6. 一棵有 $100$ 个结点的完全二叉树用数组存储,根结点下标为 $1$。下标为 $50$ 的结点有几个孩子?

{{ select(6) }}

• $0$
• $1$
• $2$
• 无法判断

7. 一棵有 $12$ 个结点的树有多少条边?

{{ select(7) }}

• $10$
• $11$
• $12$
• $13$

8. 后缀表达式 $5\ 1\ 2\ +\ 4\ *\ +\ 3\ -$ 的值是?

{{ select(8) }}

• $12$
• $14$
• $16$
• $20$

9. 用 $1,2,3,4$ 组成没有重复数字的四位数,个位是偶数的有多少个?

{{ select(9) }}

• $6$
• $12$
• $18$
• $24$

10. 递归函数定义如下:

f(0)=0
f(n)=n%2+f(n/2)  (n>0, / 表示整除)

则 f(2026) 的值为?

{{ select(10) }}

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

11. 递归的非递归实现通常使用哪种数据结构?

{{ select(11) }}

• 队列
• 栈
• 哈希表
• 堆

12. 下面代码片段的时间复杂度是?

for (int i = 1; i <= n; i *= 2)
    for (int j = 1; j <= n; j *= 2)
        cout << i + j << endl;

{{ select(12) }}

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

13. 一棵有 $2026$ 个结点的树有多少条边?

{{ select(13) }}

• $2024$
• $2025$
• $2026$
• $4050$

14. 阅读下面代码,输出结果是?

priority_queue<int, vector<int>, greater<int> > q;
q.push(5); q.push(1); q.push(3);
cout << q.top();

{{ select(14) }}

• $1$
• $3$
• $5$
• 程序无法通过编译

15. 下列关于 do-while 循环的说法,正确的是?

{{ select(15) }}

• 循环体一次也不执行
• 循环体中不能使用 break
• 循环体至少会执行一次
• do-while 是选择结构而不是循环结构

二、阅读程序

程序输入不超过数组或字符串定义的范围。判断题正确填“$\surd$”,错误填“$\times$”。

除特殊说明外,判断题每题 $1.5$ 分,选择题每题 $3$ 分,共 $40$ 分。其中第 $16\sim 18$ 题每题 $2$ 分,第 $32$ 题 $4$ 分。

阅读程序(一)

下面程序把非负整数转成二进制表示(不含前导零,数字 $0$ 输出 0)。假设输入是不超过 $1000000$ 的非负整数。

#include <iostream>
#include <string>
using namespace std;

string f(int n) {
    if (n == 0)
        return "0";
    string s;
    while (n > 0) {
        s = char('0' + n % 2) + s;
        n /= 2;
    }
    return s;
}

int main() {
    int n;
    cin >> n;
    cout << f(n) << " " << f(n + 1) << endl;
    return 0;
}

(程序 1,每题 2 分)

(1) 当输入为 $5$ 时,程序输出为 101 110。

{{ select(16) }}

• 正确
• 错误

(2) 当输入为 $0$ 时,程序输出为 0 1。

{{ select(17) }}

• 正确
• 错误

(3) 函数 f 把十进制数转换成二进制表示。

{{ select(18) }}

• 正确
• 错误

(4) 当输入为 $7$ 时,程序输出为?

{{ select(19) }}

• 111 111
• 1000 111
• 111 1000
• 7 8

(5) 当 $n>0$ 时,该程序的时间复杂度最准确地表示为?

{{ select(20) }}

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

阅读程序(二)

下面程序删除数组中的相邻重复段,只保留每一段的一个值。假设 $1 \leq n \leq 100$。

#include <iostream>
using namespace std;

int a[105], b[105];

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    int m = 0;
    for (int i = 1; i <= n; i++) {
        if (i == 1 || a[i] != a[i - 1])
            b[++m] = a[i];
    }
    cout << m << endl;
    for (int i = 1; i <= m; i++)
        cout << b[i] << " ";
    return 0;
}

(程序 2,每题 1.5 分)

(1) 当输入为 $5$ 以及 $1$ $1$ $2$ $2$ $3$ 时,第二行输出为 $1$ $2$ $3$。

{{ select(21) }}

• 正确
• 错误

(2) 对任意数组,程序都会把每种值只保留第一次出现的位置。

{{ select(22) }}

• 正确
• 错误

(3) $m$ 一定不会超过 $n$。

{{ select(23) }}

• 正确
• 错误

(4) 若输入为:

6
1 1 1 2 3 3

程序第一行输出为?

{{ select(24) }}

• $2$
• $3$
• $4$
• $6$

(5) 若输入为:

5
1 2 1 1 2

程序第一行输出为?

{{ select(25) }}

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

(6) 该程序的时间复杂度为?

{{ select(26) }}

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

阅读程序(三)

下面程序用并查集统计无向图的连通块个数。假设 $1 \leq n \leq 100$, $0 \leq m \leq 100$。

#include <iostream>
using namespace std;

int fa[105];

int fd(int x) {
    if (fa[x] == x)
        return x;
    return fa[x] = fd(fa[x]);
}

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        fa[i] = i;
    for (int i = 1; i <= m; i++) {
        int x, y;
        cin >> x >> y;
        int fx = fd(x);
        int fy = fd(y);
        if (fx != fy)
            fa[fx] = fy;
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        if (fd(i) == i)
            ans++;
    }
    cout << ans << endl;
    return 0;
}

(程序 3,每题 1.5 分)

(1) 当输入为 $4$ $2$ 以及边 $1$ $2$、$3$ $4$ 时,程序输出为 $2$。

{{ select(27) }}

• 正确
• 错误

(2) 当 $m=0$ 时,程序一定输出 $n$。

{{ select(28) }}

• 正确
• 错误

(3) fd 执行过程中可能会修改 fa 的值。

{{ select(29) }}

• 正确
• 错误

(4) 若输入为:

5 3
1 2
2 3
4 5

程序输出为?

{{ select(30) }}

• $1$
• $2$
• $3$
• $5$

(5) 若输入为:

6 4
1 2
2 3
3 4
4 5

程序输出为?

{{ select(31) }}

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

(6) 若输入为:

7 3
1 2
2 3
4 5

程序输出为?

{{ select(32) }}

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

三、完善程序

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

完善程序(一)

下面程序用埃氏筛统计 $1$ 到 $n$ 中质数的个数。请补全程序。

#include <iostream>
using namespace std;

bool isp[1005];

int main() {
    int n;
    cin >> n;
    for (int i = 2; i <= n; i++)
        isp[i] = true;
    for (int i = 2; i * i <= n; i++) {
        if (isp[i]) {
            for (int j = ①; j <= n; j += ②) {
                ③;
            }
        }
    }
    int c = 0;
    for (int i = 2; i <= n; i++) {
        if (④)
            c++;
    }
    cout << ⑤ << endl;
    return 0;
}

(1) ① 处应填( )

{{ select(33) }}

• i
• 2 * i
• i * i
• n

(2) ② 处应填( )

{{ select(34) }}

• i
• j
• n
• 2

(3) ③ 处应填( )

{{ select(35) }}

• isp[i] = false
• isp[j] = false
• isp[j] = true
• j = false

(4) ④ 处应填( )

{{ select(36) }}

• i
• j
• isp[i]
• isp[j]

(5) ⑤ 处应填( )

{{ select(37) }}

• n
• i
• isp[n]
• c

完善程序(二)

下面程序按层序遍历一棵二叉树。结点 $1$ 到 $n$ 的左右孩子存在 l[i]、r[i] 中,$0$ 表示空。请补全程序。

#include <iostream>
using namespace std;

int l[105], r[105], q[105];

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> l[i] >> r[i];
    int hd = 0, tl = 0;
    q[tl++] = ①;
    while (②) {
        int u = ③;
        cout << u << " ";
        if (④)
            q[tl++] = l[u];
        if (r[u])
            ⑤;
    }
    return 0;
}

(1) ① 处应填( )

{{ select(38) }}

• 0
• 1
• n
• l[1]

(2) ② 处应填( )

{{ select(39) }}

• hd < tl
• hd > tl
• hd == tl
• tl == 0

(3) ③ 处应填( )

{{ select(40) }}

• q[tl++]
• q[hd++]
• q[hd]
• q[--tl]

(4) ④ 处应填( )

{{ select(41) }}

• l[u]
• r[u]
• u
• n

(5) ⑤ 处应填( )

{{ select(42) }}

• q[tl++] = r[u]
• q[hd++] = r[u]
• r[u] = q[tl++]
• q[tl++] = u