单选题（每题2分，共30分）

1. 已知小写字母 b 的ASCII码为98，下列C++代码的输出结果是（ ）。 {{ select(1) }}

• b
• c
• 98
• 99

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

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

3. 已知数组 a 的定义 int a[10] = {0}; ，下列说法不正确的是（ ）。 {{ select(3) }}

• 语句 a[-1] = 0; 会产生编译错误。
• 数组 a 的所有元素均被初始化为 0 。
• 数组 a 至少占用 10 个 int 大小的内存，一般为 40 个字节。
• 语句 a[13] = 0; 不会产生编译错误，但会导致难以预测的运行结果。

4. 下列关于C++类的说法，错误的是( )。

{{ select(4) }}

• 构造函数不能声明为虚函数，但析构函数可以。
• 函数参数如声明为类的引用类型，调用时不会调用该类的复制构造函数。
• 静态方法属于类、不属于对象，因此不能使用 对象.方法(...) 的形式调用静态方法。
• 析构派生类的对象时，一定会调用基类的析构函数。

5. 下列关于有向图的说法，错误的是( )。 {{ select(5) }}

• n个顶点的弱连通有向图，最少有n-1 条边
• n个顶点的强连通有向图，最少有n条边。
• n个顶点的有向图，最多有n*(n-1) 条边
• n个顶点的有向完全图，有n*(n-1) 条边。

6. 一棵二叉树的每个结点均满足：结点的左子树和右子树，要么同时存在，要么同时不存在。该树有197个结点，则其叶结点有多少个？( )。

{{ select(6) }}

• 98
• 99
• 不存在这样的树。
• 无法确定叶结点数量。

7. 下列关于二叉树的说法，错误的是（ ）。

{{ select(7) }}

• 二叉排序树的中序遍历顺序与元素排序的顺序是相同的。
• n个元素的二叉排序树，其高一定为$[log_2n]$
• 自平衡二叉查找树（AVL树）是一种二叉排序树。
• 任意的森林，都可以映射为一颗二叉树进行表达和存储。

8. 一个简单无向图有10个结点、6条边。在最差情况，至少增加多少条边可以使其连通？（ ）

{{ select(8) }}

• 3
• 4
• 6
• 9

9. 一个哈希表，包括n个位置（分别编号0~(n-1)），每个位置最多仅能存储一个元素。该哈希表只有插入元素和查询两种操作，没有删除或修改元素的操作。以下说法错误的是（ ）。 {{ select(9) }}

• 如果哈希函数取值范围为$0 ~ (n-1)$，且当发生哈希函数碰撞时循环向后寻找空位，则查询操作的最差时间复杂度为 $O(n)$。（“循环向后”指：$0$向后一位为$1$，$1$向后一位为$2，……，(n-2)$向后一位为$(n-1)，(n-1)$向后一位为$0$）
• 如果哈希函数取值范围为$0 ~ (n-1)$，且当发生哈希函数碰撞时仅循环向后一个位置寻找空位，则查询操作的最差时间复杂度为$O(1)$ 。
• 如果哈希函数取值范围为$0 ~ (m-1)（m < n）$，且当发生哈希函数碰撞时仅在m ~ (n-1)的范围内寻找空位，则查询操作的最差时间复杂度为 $O(n-m)$。
• 查询操作时，如果发现查询元素经哈希函数对应的位置为空位，该查询元素仍可能出现在哈希表内。

10. 以下关于动态规划的说法中，错误的是（ ）。

    {{ select(10) }}

• 动态规划方法将原问题分解为一个或多个相似的子问题。
• 动态规划方法通常能够列出递推公式。
• 动态规划方法有递推和递归两种实现形式。
• 递推实现动态规划方法的时间复杂度总是不低于递归实现。

11.下面程序的输出为（ ）。

{{ select(11) }}

• 4
• 7
• 100
• 无法通过编译。

12. 下面程序的输出为（ ）。 {{ select(12) }}

• 132
• 1430
• 16796
• 结果是随机的。

13. 上题中程序的时间复杂度为（ ）。 {{ select(13) }}

• $O$($N$ )
• $O$($N$ $log$ $N$)
• $O$($N^{3/2}$)
• $O$($N^2$)

14. 下面 init_sieve 函数的时间复杂度为( )。 {{ select(14) }}

• $O$($n$ )
• $O$($n$ $log$ $n$)
• $O$($n^2$)
• 无法正常结束。

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

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