一、单项选择题（共15题，每题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, / 表示整数除法)

{{ 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 语句
• 循环体至少会执行一次
• 它属于选择结构而不是循环结构

二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填 √，错误填 ×；除特殊说明外，判断题每题 1.5 分，选择题每题 3 分，共计 40 分）

阅读程序（一）

#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;
}

假设输入的 $n$ 是不超过 1000000 的非负整数。

判断题

---

16. 当输入为 5 时，程序输出为 101 110。

{{ select(16) }}

• 正确
• 错误

---

17. 当输入为 0 时，程序输出为 0 1。

{{ select(17) }}

• 正确
• 错误

---

18. 该程序中的函数 f 用于将十进制整数转换为八进制表示。

{{ select(18) }}

• 正确
• 错误

单项选择题

---

19. 当输入为 7 时，程序输出为？

{{ select(19) }}

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

---

20. 设输入的 $n > 0$，该程序的时间复杂度最准确地表示为？

{{ select(20) }}

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

阅读程序（二）

#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;
}

假设 $1 \le n \le 100$，输入的所有整数均在 int 范围内。

判断题

---

21. 当输入数组为 1 1 2 2 3 3 时，程序输出的第二行是 1 2 3。

{{ select(21) }}

• 正确
• 错误

---

22. 对任意输入数组，该程序都会删除所有重复出现的数，只保留每个数第一次出现的位置。

{{ select(22) }}

• 正确
• 错误

---

23. 程序中变量 $m$ 的值一定不会超过 $n$。

{{ select(23) }}

• 正确
• 错误

单项选择题

---

24. 若输入为：

6
1 1 2 2 3 3

• 2
  1 3
  

{{ select(24) }}

• 3
  1 2 3
  

• 4
  1 1 2 3
  

• 6
  1 1 1 2 3 3
  

---

25. 若输入为：

5
1 2 1 1 2

{{ select(25) }}

• 1
• 2
• 3
• 4

---

26. 该程序的时间复杂度为？

{{ select(26) }}

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

阅读程序（三）

#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;
}

假设 $1 \le n \le 100$，$0 \le m \le 100$，每组 $x, y$ 均满足 $1 \le x, y \le n$。

判断题

---

27. 若输入为：

4 2
1 2
3 4

---

28. 若 $m = 0$，程序输出一定为 $n$。

{{ select(27) }}

• 正确
• 错误

{{ select(28) }}

• 正确
• 错误

---

29. fd 函数在执行过程中可能会改变数组 fa 的值。

{{ select(29) }}

• 正确
• 错误

单项选择题

---

30. 若输入为：

5 3
1 2
2 3
4 5

{{ select(30) }}

• 1
• 2
• 3
• 5

---

31. 若输入为：

6 4
1 2
2 3
3 4
4 5

{{ select(31) }}

• 1
• 2
• 3
• 4

---

32. 若输入为：

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;
}

---

33. ① 处应填？

{{ select(33) }}

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

---

34. ② 处应填？

{{ select(34) }}

• i
• j
• n
• 2

---

35. ③ 处应填？

{{ select(35) }}

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

---

36. ④ 处应填？

{{ select(36) }}

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

---

37. ⑤ 处应填？

{{ select(37) }}

• n
• i
• isp[n]
• c

完善程序（二）

下面程序输出一棵二叉树的层序遍历结果。结点编号为 1 到 $n$，根结点为 1。若某个孩子不存在，则用 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;
}

---

38. ① 处应填？

{{ select(38) }}

• 0
• 1
• n
• l[1]

---

39. ② 处应填？

{{ select(39) }}

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

---

40. ③ 处应填？

{{ select(40) }}

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

---

41. ④ 处应填？

{{ select(41) }}

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

---

42. ⑤ 处应填？

{{ select(42) }}

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