一、单项选择题（共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