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

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

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

{{ select(1) }}

• $\tt b$
• $\tt c$
• $98$
• $99$

2. 已知 $a$ 为 $\tt int$ 类型变量，下列表达式不符合语法的是（ ）科学家图灵。

{{ select(2) }}

• &a + 3
• +a & 3
• a - - 4
• a++3

3. 下列关于 $\tt C$++ 语言中指针的叙述，不正确的是（ ）。

{{ select(3) }}

• 指针变量中存储的是内存地址
• 指针变量指向的内存地址不一定能够合法访问
• 结构类型中的指针成员不能指向该结构类型
• 定义指针变量时必须指定其指向的类型

4. 下列关于 $\tt C$++ 类的说法，错误的是（ ）。

{{ select(4) }}

• 将 $\tt C$++ 类对象通过值传递给函数参数时，会自动调用复制构造函数
• 将一个类的对象赋值给该类的另一个对象时，不会自动调用构造函数
• 定义 $\tt C$++ 类对象时，一定会调用默认构造函数
• 构造派生类的对象时，一定会调用基类的构造函数

5. 某二叉树 $\tt T$ 的先序遍历序列为：$\{A\ B\ D\ C\ E\ G\ H\ F\}$，中序遍历序列为：$\{D\ B\ A\ H\ G\ E\ C\ F\}$，则下列说法中正确的是（ ）。

{{ select(5) }}

• $\tt T$ 的高为 $5$
• $\tt T$ 有 $4$ 个叶节点
• $\tt T$ 是平衡树
• 以上说法都不对

6. 一棵完全二叉树有 $431$ 个结点，则叶结点有多少个？（ ）

{{ select(6) }}

• $176$
• $215$
• $216$
• $255$

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

{{ select(7) }}

• 二叉树的中序遍历与其深度优先遍历总是相同的
• 所有树都可以构造一颗二叉树与之一一对应
• 如果树的一个叶结点有两个不同的祖先结点，那么其中一个一定是另一个的祖先结点
• 树的结点不能有两个父结点

8. 一个简单无向图有 $10$ 个结点、$30$ 条边。再增加多少条边可以成为完全图（ ）。

{{ select(8) }}

• $10$
• $15$
• $51$
• $60$

9. 以下哪个方案可以合理解决或缓解哈希表冲突（ ）。

{{ select(9) }}

• 丢弃发生冲突的新元素
• 用新元素覆盖发生冲突的元素
• 用新元素覆盖在冲突位置的下一个位置
• 将新元素放置在冲突位置之后的第一个空位

10. 一个迷宫，已知从起点不经过重复结点到达终点的路径有且仅有一条，则下面说法错误的是（ ）。

{{ select(10) }}

• 可以使用深度优先搜索找到这条路径
• 可以使用广度优先搜索找到这条路径
• 该迷宫内与起点连通的结点，一定也与终点连通
• 该迷宫内与起点连通的结点及它们之间的路径可以抽象为无向无环图

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

    #include <iostream>
    #include <cmath>
    using namespace std;
    int main() {
        cout << (int)log(8) << endl;
    return 0;
    }
    

{{ select(11) }}

• $2$
• $3$
• $8$
• 无法通过编译

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

    #include <iostream>
    #define N 10
    using namespace std;
    int path[N][N];
    int main() {
        for (int i = 1; i < N; i++)
            path[i][0] = i;
        for (int j = 1; j < N; j++)
            path[0][j] = j;
        for (int i = 1; i < N; i++)
            for (int j = 1; j < N; j++)
                path[i][j] = path[i - 1][j] + path[i][j - 1];
        cout << path[8][4] << endl;
        return 0;
    }
    

{{ select(12) }}

• $84$
• $495$
• $1012$
• 结果是随机的

13. 上题中程序的时间复杂度为（ ）。

{{ select(13) }}

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

14. 下面 $\tt fib$ 函数的时间复杂度为（ ）。

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

{{ select(14) }}

• $O(n)$
• $O(\phi^n)$，$\phi = \frac{\sqrt 5 - 1}{2}$
• $O(2^n)$
• 无法正常结束

15. 下列选项中，哪个可能是下图的广度优先遍历序列（ ）。

    

{{ select(15) }}

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

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

1. 表达式 'a' << 1 的结果为 'a '。（ ）

{{ select(16) }}

• 正确
• 错误

2. 在 $\tt C$++ 语言中，函数可以定义在另一个函数定义之内。（ ）

{{ select(17) }}

• 正确
• 错误

3. 选择排序一般是不稳定的。（ ）

{{ select(18) }}

• 正确
• 错误

4. 埃氏筛法和欧拉筛法都是使用筛法思想生成素数表的算法，欧拉筛法的时间复杂度更低。（ ）

{{ select(19) }}

• 正确
• 错误

5. 使用 $\tt math.h$ 或 $\tt cmath$ 头文件中的正弦函数，表达式 sin(30) 的结果类型为 $\tt double$、值约为 $0.5$。（ ）

{{ select(20) }}

• 正确
• 错误

6. 一棵 $N$ 层的完全二叉树，一定有 $2^N - 1$ 个结点。（ ）

{{ select(21) }}

• 正确
• 错误

7. 一个图，不管是否连通，都可以使用深度优先搜索算法进行遍历。（ ）

{{ select(22) }}

• 正确
• 错误

8. 某个哈希表键值 $x$ 为整数，$H(x) = x \% p$ 是常用的哈希函数之一，要求 $p$ 选择素数是因为这样不会产生冲突。（ ）

{{ select(23) }}

• 正确
• 错误

9. 使用单链表实现队列时，链表头结点作为队首比链表头结点作为队尾更便于操作。（ ）

{{ select(24) }}

• 正确
• 错误

10. 一个图中，每个结点表达一个人，连接两个结点的边表达两个结点对应的人相互认识，则这个图可以用来表达社交网络。（ ）

{{ select(25) }}

• 正确
• 错误