GESP 202506 C++ 七级

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

1. [2 分] 已知小写字母 b 的 ASCII 码为 98，下列 C++ 代码的输出结果是（ ）。

#include <iostream>
using namespace std;
int main() {
    char a = 'b' ^ 4;
    cout << a;
    return 0;
}

（ {{ select(1) }} ）

• b
• bbbb
• f
• 102

2. [2 分] 已知 a 为 int 类型变量，p 为 int * 类型变量，下列赋值语句不符合语法的是（ ）。 （ {{ select(2) }} ）

• *(p + a) = *p;
• *(p - a) = a;
• p + a = p;
• p = p + a;

3. [2 分] 下列关于 C++ 类的说法，错误的是（ ）。 （ {{ select(3) }} ）

• 如果要用基类的指针释放派生类对象，基类的析构函数应声明为虚析构函数。
• 构造派生类对象时，只调用派生类的构造函数，不会调用基类的构造函数。
• 基类和派生类分别实现了同一个虚函数，派生类对象仍能够调用基类的该方法。
• 如果函数形参为基类指针，调用时可以传入派生类指针作为实参。

4. [2 分] 下列 C++ 代码的输出是（ ）。

#include <iostream>
using namespace std;
int main() {
    int arr[5] = {2, 4, 6, 8, 10};
    int *p = arr + 2;
    cout << p[3] << endl;
    return 0;
}

（ {{ select(4) }} ）

• 6
• 8
• 编译出错，无法运行。
• 不确定，可能发生运行时异常。

5. [2 分] 假定只有一个根节点的树的深度为 1，则一棵有 $N$ 个节点的完全二叉树，则树的深度为（ ）。 （ {{ select(5) }} ）

• $\lfloor \log_2(N) \rfloor + 1$
• $\lceil \log_2(N) \rceil$
• $\lceil \log_2(N) \rceil$
• 不能确定。

6. [2 分] 对于如下图的二叉树，说法正确的是（ ）。

（ {{ select(6) }} ）

• 先序遍历是 ABDEC。
• 中序遍历是 BDACE。
• 后序遍历是 DBCEA。
• 广度优先遍历是 ABCDE。

7. [2 分] 图的存储和遍历算法，下面说法错误的是（ ）。 （ {{ select(7) }} ）

• 图的深度优先遍历必须要借助队列来完成。
• 图的深度优先遍历和广度优先遍历对有向图和无向图都适用。
• 使用邻接矩阵存储一个包含 $n$ 个顶点的有向图，统计其边数的时间复杂度为 $O(n^2)$。
• 同一个图分别使用出边邻接表和入边邻接表存储，其边结点个数相同。

8. [2 分] 一个连通的简单有向图，共有 28 条边，则该图至少有（ ）个顶点。 （ {{ select(8) }} ）

• 5
• 6
• 7
• 8

9. [2 分] 以下哪个方案不能合理解决或缓解哈希表冲突（ ）。 （ {{ select(9) }} ）

• 在每个哈希表项处，使用不同的哈希函数再建立一个哈希表，管理该表项的冲突元素。
• 在每个哈希表项处，建立二叉排序树，管理该表项的冲突元素。
• 使用不同的哈希函数建立额外的哈希表，用来管理所有发生冲突的元素。
• 覆盖发生冲突的旧元素。

10. [2 分] 以下关于动态规划的说法中，错误的是（ ）。 （ {{ select(10) }} ）

• 动态规划方法通常能够列出递推公式。
• 动态规划方法的时间复杂度通常为状态的个数。
• 动态规划方法有递推和递归两种实现形式。
• 对很多问题，递推实现和递归实现动态规划方法的时间复杂度相当。

11. [2 分] 下面程序的输出为（ ）。

#include <iostream>
using namespace std;
int rec_fib[100];
int fib(int n) {
    if (n <= 1)
        return n;
    if (rec_fib[n] == 0)
        rec_fib[n] = fib(n - 1) + fib(n - 2);
    return rec_fib[n];
}
int main() {
    cout << fib(6) << endl;
    return 0;
}

（ {{ select(11) }} ）

• 8
• 13
• 64
• 结果是随机的。

12. [2 分] 下面程序的时间复杂度为（ ）。

int rec_fib[MAX_N];
int fib(int n) {
    if (n <= 1)
        return n;
    if (rec_fib[n] == 0)
        rec_fib[n] = fib(n - 1) + fib(n - 2);
    return rec_fib[n];
}

（ {{ select(12) }} ）

• $O(2^n)$
• $O(\phi^n), \phi = \frac{\sqrt{5}+1}{2}$
• $O(n^2)$
• $O(n)$

13. [2 分] 下面 search 函数的平均时间复杂度为（ ）。

int search(int n, int *p, int target) {
    int low = 0, high = n;
    while (low < high) {
        int middle = (low + high) / 2;
        if (target == p[middle])
            return middle;
        else if (target > p[middle])
            low = middle + 1;
        else
            high = middle;
    }
    return -1;
}

（ {{ select(13) }} ）

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

14. [2 分] 下面程序的时间复杂度为（ ）。

int primes[MAXP], num = 0;
bool isPrime[MAXV] = {false};
void sieve() {
    for (int n = 2; n <= MAXV; n++) {
        if (!isPrime[n])
            primes[num++] = n;
        for (int i = 0; i < num && n * primes[i] <= MAXV; i++)
            isPrime[n * primes[i]] = true;
        if (n % primes[i] == 0)
            break;
    }
}

（ {{ select(14) }} ）

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

15. [2 分] 下列选项中，哪个不可能是下图的广度优先遍历序列（ ）。 （ {{ select(15) }} ）

• 1, 2, 4, 5, 3, 7, 6, 8, 9
• 1, 2, 5, 4, 3, 7, 8, 6, 9
• 1, 4, 5, 2, 7, 3, 8, 6, 9
• 1, 5, 4, 2, 7, 3, 8, 6, 9

---

二、 判断题（每题 2 分，共 20 分）

16. [2 分] C++ 语言中，表达式 9 & 12 的结果类型为 int，值为 8。 （ {{ select(16) }} ）

• 正确
• 错误

17. [2 分] C++ 语言中，指针变量指向的内存地址不一定都能够合法访问。 （ {{ select(17) }} ）

• 正确
• 错误

18. [2 分] 对 $n$ 个元素的数组进行快速排序，最差情况的时间复杂度为 $O(n \log n)$。 （ {{ select(18) }} ）

• 正确
• 错误

19. [2 分] 一般情况下，long long 类型占用的字节数比 float 类型多。 （ {{ select(19) }} ）

• 正确
• 错误

20. [2 分] 使用 math.h 或 cmath 头文件中的函数，表达式 pow(10, 3) 的结果值为 1000，类型为 int。 （ {{ select(20) }} ）

• 正确
• 错误

21. [2 分] 二叉排序树的中序遍历序列一定是有序的。 （ {{ select(21) }} ）

• 正确
• 错误

22. [2 分] 无论哈希表采用何种方式解决冲突，只要管理的元素足够多，都无法避免冲突。 （ {{ select(22) }} ）

• 正确
• 错误

23. [2 分] 在 C++ 语言中，类的构造函数和析构函数均可以声明为虚函数。 （ {{ select(23) }} ）

• 正确
• 错误

24. [2 分] 动态规划方法将原问题分解为一个或多个相似的子问题，因此必须使用递归实现。 （ {{ select(24) }} ）

• 正确
• 错误

25. [2 分] 如果将城市视作顶点，公路视作边，将城际公路网络抽象为简单图，可以满足城市间的车道路线导航需求。 （ {{ select(25) }} ）

• 正确
• 错误