You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

一、单项选择题（共15题，每题2分，共计30分）

1. 将二进制数 101101 转换为八进制数，结果是（ ）。

{{ select(1) }}

• 45
• 55
• 53
• 57

2. 将十进制数 87 转换为二进制数，结果是（ ）。

{{ select(2) }}

• 1010111
• 1011011
• 1010101
• 1000111

3. 从 7 名同学中选出 2 名代表参加比赛，共有（ ）种不同的选法。

{{ select(3) }}

• 21
• 42
• 14
• 7

4. 已知字符 '3' 的 ASCII 码为 51，则字符 '0' 的 ASCII 码是（ ）。

{{ select(4) }}

• 45
• 48
• 51
• 54

5. 在 C++ 中，表达式 7 ^ 3（按位异或）的值是（ ）。

{{ select(5) }}

• 4
• 5
• 6
• 10

6. 栈的特点是（ ）。

{{ select(6) }}

• 先进先出
• 后进先出
• 随机存取
• 只能插入不能删除

7. 快速排序的平均时间复杂度为（ ）。

{{ select(7) }}

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

8. 一棵深度为 5 的满二叉树，其叶子结点的个数为（ ）。（根的深度为 1）

{{ select(8) }}

• 16
• 15
• 31
• 32

9. 一个具有 6 个顶点的有向完全图共有（ ）条边。

{{ select(9) }}

• 15
• 30
• 36
• 60

10. 在 64 位系统中，sizeof(long long) 的值通常为（ ）。

{{ select(10) }}

• 4
• 8
• 16
• 2

11. 设 x = true，y = false，z = false，则表达式 x && (y || z) 的值是（ ）。

{{ select(11) }}

• true
• false
• 不确定
• 编译错误

12. 已知一棵二叉树的前序遍历为 A B C，中序遍历为 B A C，则其后序遍历为（ ）。

{{ select(12) }}

• B C A
• C B A
• A B C
• B A C

13. 在有序数组 {1, 3, 5, 7, 9, 11, 13} 中使用二分查找法查找元素 11，需要比较（ ）次才能找到。

{{ select(13) }}

• 2
• 3
• 4
• 5

14. 6 名同学排成一排，要求甲、乙两人必须相邻，共有（ ）种不同的排列方式。

{{ select(14) }}

• 240
• 120
• 720
• 480

15. 在 C++ 中，表达式 10 / 4 的值是（ ）。

{{ select(15) }}

• 2
• 2.5
• 3
• 0

---

二、阅读程序

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

程序 1

#include <iostream>
using namespace std;

int main() {
    int n, cnt = 0;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        if (x % 2 == 0) cnt++;
    }
    cout << cnt << endl;
    return 0;
}

判断题

16. （1.5 分）该程序统计输入的 n 个数中偶数的个数。（ ）

{{ select(16) }}

• √
• ×

17. （1.5 分）当输入为 "4\n1 2 3 4" 时，程序的输出为 2。（ ）

{{ select(17) }}

• √
• ×

18. （1.5 分）当输入为 0 时，程序的输出为 0。（ ）

{{ select(18) }}

• √
• ×

19. （1.5 分）若将 x % 2 == 0 改为 x % 2 == 1，程序统计的仍然是能被 2 整除的数的个数。（ ）

{{ select(19) }}

• √
• ×

选择题

20. （3 分）当输入为 "5\n2 4 6 8 10" 时，程序的输出为（ ）。

{{ select(20) }}

• 4
• 5
• 6
• 0

21. （3 分）若输入的 n 个数全部为奇数，则程序的输出为（ ）。

{{ select(21) }}

• 0
• 1
• n
• n / 2

---

程序 2

#include <iostream>
using namespace std;

int main() {
    int n, x;
    cin >> n >> x;
    int a[100];
    for (int i = 0; i < n; i++) cin >> a[i];

    int pos = -1;
    for (int i = 0; i < n; i++) {
        if (a[i] == x) {
            pos = i;
            break;
        }
    }
    cout << pos << endl;
    return 0;
}

判断题

22. （1.5 分）程序在数组 a 中查找 x，若找到则输出其下标（从 0 开始），否则输出 -1。（ ）

{{ select(22) }}

• √
• ×

23. （1.5 分）当输入为 "5 3\n1 2 3 4 5" 时，程序的输出为 3。（ ）

{{ select(23) }}

• √
• ×

24. （1.5 分）若 x 在数组中出现多次，程序输出的是 x 第一次出现的位置。（ ）

{{ select(24) }}

• √
• ×

选择题

25. （3 分）当输入为 "5 6\n1 2 3 4 5" 时，程序的输出为（ ）。

{{ select(25) }}

• -1
• 0
• 5
• 6

26. （3 分）若删除程序中的 break，当 x 在数组中出现多次时，程序输出的是 x（ ）出现的位置。

{{ select(26) }}

• 第一次
• 最后一次
• 中间一次
• 无法确定

27. （3 分）该程序的时间复杂度为（ ）。

{{ select(27) }}

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

---

程序 3

#include <iostream>
using namespace std;

long long fact(int n) {
    if (n <= 1) return 1;
    return n * fact(n - 1);
}

int main() {
    int n;
    cin >> n;
    cout << fact(n) << endl;
    return 0;
}

判断题

28. （1.5 分）该程序计算的是 n 的阶乘（n!）。（ ）

{{ select(28) }}

• √
• ×

29. （1.5 分）当输入为 5 时，程序的输出为 120。（ ）

{{ select(29) }}

• √
• ×

30. （1.5 分）当输入为 0 时，程序的输出为 0。（ ）

{{ select(30) }}

• √
• ×

选择题

31. （3 分）当输入为 6 时，程序的输出为（ ）。

{{ select(31) }}

• 5040
• 720
• 120
• 360

32. （3 分）当输入为 10 时，程序的输出为（ ）。

{{ select(32) }}

• 362880
• 40320
• 3628800
• 39916800

33. （3 分）若将 return n * fact(n - 1) 改为 return n + fact(n - 1)，当输入为 5 时，程序的输出为（ ）。

{{ select(33) }}

• 10
• 15
• 25
• 120

---

三、完善程序（单选题，每小题 3 分，共计 30 分）

程序 1：冒泡排序

给定 n 个整数，使用冒泡排序将它们按从小到大排序后输出。试补全程序。

#include <iostream>
using namespace std;

const int MAXN = 1005;
int a[MAXN];

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];

    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - 1 - i; j++) {
            if (a[j] > a[j + 1]) {
                ①;
            }
        }
    }

    for (int i = 0; i < n; i++) cout << ② << " ";
    cout << endl;
    return 0;
}

34. （3 分）① 处应填（ ）。

{{ select(34) }}

• swap(a[j], a[j + 1])
• swap(a[i], a[j])
• a[j] = a[j + 1]
• swap(a[j], a[i])

35. （3 分）② 处应填（ ）。

{{ select(35) }}

• a[i]
• a[n - i]
• i
• a[j]

36. （3 分）当输入为 "5\n5 4 3 2 1" 时，程序的输出为（ ）。

{{ select(36) }}

• 1 2 3 4 5
• 5 4 3 2 1
• 4 5 3 2 1
• 2 3 4 5 1

37. （3 分）冒泡排序在最坏情况下的时间复杂度为（ ）。

{{ select(37) }}

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

38. （3 分）若将条件 a[j] > a[j + 1] 改为 a[j] < a[j + 1]，程序的输出变为（ ）。

{{ select(38) }}

• 从小到大排列
• 从大到小排列
• 输出不变
• 程序报错

---

程序 2：统计大写字母个数

给定一个字符串 s（只含字母和数字），统计其中大写字母的个数。试补全程序。

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

int main() {
    string s;
    cin >> s;
    int cnt = ①;
    for (int i = 0; i < ②; i++) {
        if (③) cnt++;
    }
    cout << ④ << endl;
    return 0;
}

39. （3 分）① 处应填（ ）。

{{ select(39) }}

• -1
• 0
• 1
• s.length()

40. （3 分）② 处应填（ ）。

{{ select(40) }}

• s.length()
• s.length() - 1
• s.size() - 1
• 100

41. （3 分）③ 处应填（ ）。

{{ select(41) }}

• s[i] >= 'a' && s[i] <= 'z'
• s[i] >= 'A' && s[i] <= 'Z'
• s[i] >= '0' && s[i] <= '9'
• s[i] == 'A'

42. （3 分）④ 处应填（ ）。

{{ select(42) }}

• s
• cnt
• s.length()
• s[0]

43. （3 分）当输入为 "AbC123" 时，程序的输出为（ ）。

{{ select(43) }}

• 3
• 2
• 1
• 0