5317：[GESP202506七级] 客观题
文件提交：无需freopen
内存限制：128 MB
时间限制：1.000 S
评测方式：文本裁判
金币值：
命题人：
提交：0
解决：0
题目描述
## 一、单选题（每题 2 分，共 30 分）
**第 1 题** 已知小写字母 $b$ 的 `ASCII` 码为 $98$，下列 `C++` 代码的输出结果是()
```cpp
01 #include
02 using namespace std;
03 int main() {
04 char a = 'b' ^ 4;
05 cout << a;
06 return 0;
07 }
```
- $b$
- $bbbb$
- $f$
- $102$
**第 2 题** 已知 $a$ 为 `int` 类型变量， $p$ 为 `int *` 类型变量，下列赋值语句不符合语法的是()
- `*(p + a) = *p;`
- `*(p - a) = a;`
- `p + a = p;`
- `p = p + a;`
**第 3 题** 下列关于 `C++` 类的说法，错误的是()
- 如需要使用基类的指针释放派生类对象，基类的析构函数应声明为虚析构函数。
- 构造派生类对象时，只调用派生类的构造函数，不会调用基类的构造函数。
- 基类和派生类分别实现了同一个虚函数，派生类对象仍能够调用基类的该方法。
- 如果函数形参为基类指针，调用时可以传入派生类指针作为实参。
**第 4 题** 下列 `C++` 代码的输出是()
```cpp
01 #include
02 using namespace std;
03 int main() {
04 int arr[5] = {2, 4, 6, 8, 10};
05 int * p = arr + 2;
06 cout << p[3] << endl;
07 return 0;
08 }
```
- 6
- 8
- 编译出错，无法运行
- 不确定，可能发生运行时异常
**第 5 题** 假定只有一个根节点的树的深度为 $1$，则一棵有 $N$ 个节点的完全二叉树，则树的深度为()
- $\lfloor log_2(N) \rfloor + 1$
- $\lfloor log_2(N) \rfloor$
- $\lceil log_2(N) \rceil$
- 不能确定
**第 6 题** 对于如下图的二叉树，说法正确的是( )
- 先序遍历是 `ABDEC`。
- 中序遍历是 `BDACE`。
- 后序遍历是 `DBCEA`。
- 广度优先遍历是 `ABCDE`。
**第 7 题** 图的存储和遍历算法，下面说法错误的是()
- 图的深度优先遍历须要借助队列来完成。
- 图的深度优先遍历和广度优先遍历对有向图和无向图都适用。
- 使用邻接矩阵存储一个包含 个顶点的有向图，统计其边数的时间复杂度为 $O(v^2)$。
- 同一个图分别使用出边邻接表和入边邻接表存储，其边结点个数相同。
**第 8 题** 一个连通的简单有向图，共有 $28$ 条边，则该图至少有( )个顶点。
- $5$
- $6$
- $7$
- $8$
**第 9 题** 以下哪个方案不能合理解决或缓解哈希表冲突()
- 在每个哈希表项处，使用不同的哈希函数再建立一个哈希表，管理该表项的冲突元素。
- 在每个哈希表项处，建立二叉排序树，管理该表项的冲突元素。
- 使用不同的哈希函数建立额外的哈希表，用来管理所有发生冲突的元素。
- 覆盖发生冲突的旧元素。
**第 10 题** 以下关于动态规划的说法中，错误的是()
- 动态规划方法通常能够列出递推公式。
- 动态规划方法的时间复杂度通常为状态的个数。
- 动态规划方法有递推和递归两种实现形式。
- 对很多问题，递推实现和递归实现动态规划方法的时间复杂度相当。
**第 11 题** 下面程序的输出为()
```cpp
01 #include
02 using namespace std;
03 int rec_fib[100];
04 int fib(int n) {
05 if (n <= 1)
06 return n;
07 if (rec_fib[n] == 0)
08 rec_fib[n] = fib(n - 1) + fib(n - 2);
09 return rec_fib[n];
10 }
11 int main() {
12 cout << fib(6) << endl;
13 return 0;
14 }
```
- $8$
- $13$
- $64$
- 结果是随机的。
**第 12 题** 下面程序的时间复杂度为()
```cpp
01 int rec_fib[MAX_N];
02 int fib(int n) {
03 if (n <= 1)
04 return n;
05 if (rec_fib[n] == 0)
06 rec_fib[n] = fib(n - 1) + fib(n - 2);
07 return rec_fib[n];
08 }
```
- $O(2^n)$
- $O(\phi^2)，\phi = \frac{\sqrt 5-1}{2}$
- $O(n^2)$
- $O(n)$
**第 13 题** 下面 $search$ 函数的平均时间复杂度为()
```cpp
01 int search(int n, int * p, int target) {
02 int low = 0, high = n;
03 while (low < high) {
04 int middle = (low + high) / 2;
05 if (target == p[middle]) {
06 return middle;
07 } else if (target > p[middle]) {
08 low = middle + 1;
09 } else {
10 high = middle;
11 }
12 }
13 return -1;
14 }
```
- $O(nlog(n))$
- $O(n)$
- $O(log(n))$
- $O(1)$
**第 14 题** 下面程序的时间复杂度为()
```cpp
01 int primes[MAXP], num = 0;
02 bool isPrime[MAXN] = {false};
03 void sieve() {
04 for (int n = 2; n <= MAXN; n++) {
05 if (!isPrime[n])
06 primes[num++] = n;
07 for (int i = 0; i < num && n * primes[i] <= MAXN; i++) {
08 isPrime[n * primes[i]] = true;
09 if (n % primes[i] == 0)
10 break;
11 }
12 }
13 }
```
- $O(n)$
- $O(n \times log n)$
- $O(nloglogn)$
- $O(n^2)$
**第 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 分）
**第 1 题** `C++` 语言中，表达式 `9 & 12` 的结果类型为 `int`、值为 $8$。
- 正确
- 错误
**第 2 题** `C++` 语言中，指针变量指向的内存地址不一定都能够合法访问。
- 正确
- 错误
**第 3 题** 对 $n$ 个元素的数组进行快速排序，最差情况的时间复杂度为 $O(nlogn)$。
- 正确
- 错误
**第 4 题** 一般情况下， `long long` 类型占用的字节数比 `float` 类型多。
- 正确
- 错误
**第 5 题** 使用 `math.h` 或 `cmath` 头文件中的函数，表达式 `pow(10, 3)` 的结果的值为 `1000`、类型为 `int`。
- 正确
- 错误
**第 6 题** 二叉排序树的中序遍历序列一定是有序的。
- 正确
- 错误
**第 7 题** 无论哈希表采用何种方式解决冲突，只要管理的元素足够多，都无法避免冲突。
- 正确
- 错误
**第 8 题** 在 `C++` 语言中，类的构造函数和析构函数均可以声明为虚函数。
- 正确
- 错误
**第 9 题** 动态规划方法将原问题分解为一个或多个相似的子问题，因此必须使用递归实现。
- 正确
- 错误
**第 10 题** 如果将城市视作顶点，公路视作边，将城际公路网络抽象为简单图，可以满足城市间的车道级导航需求。
- 正确
- 错误