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

1. 下列关于排序的说法，正确的是（ ）。

{{ select(1) }}

• 冒泡排序是最快的排序算法之一
• 快速排序通常是不稳定的
• 最差情况，$N$ 个元素做归并排序的时间复杂度为 $O(N)$
• 以上均不正确

2. 下面的程序属于哪种算法（ ）。

   int pos[8];
   void queen(int n) {
       for (int i = 0; i < 8; i++) {
           pos[n] = i;
           bool attacked = false;
           for (int j = 0; j < n; j++)
               if (pos[n] == pos[j] || pos[n] + n == pos[j] + j 
                   || pos[n] - n == pos[j] - j) {
                   attacked = true;
                   break;
               }
           if (attacked)
               continue;
           if (n == 7) {
               return;
           } else {
               queen(n + 1);
           }
       }
   }
   

{{ select(2) }}

• 贪心算法
• 动态规划
• 深度优先搜索
• 广度优先搜索

3. 下面有关 $\tt C$++ 类的说法，错误的是（ ）。

{{ select(3) }}

• $\tt C$++ 类对象销毁时，会执行析构函数
• $\tt C$++ 类可以通过定义构造函数实现自动类型转换
• $\tt C$++ 类可以通过重载 [] 运算符实现通过给定下标访问数组成员的元素
• $\tt C$++ 类可以包含任意类型的成员变量

4. 一个连通的简单无向图，共有 $28$ 条边，则该图至少有（ ）个顶点。

{{ select(4) }}

• $6$
• $7$
• $8$
• $9$

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

{{ select(5) }}

• 在每个哈希表项处，使用单链表管理该表项的冲突元素
• 建立额外的单链表，用来管理所有发生冲突的元素
• 使用不同的哈希函数再建立一个哈希表，用来管理所有发生冲突的元素
• 用新元素覆盖发生冲突的哈希表项

6. 已知一颗二叉树的中序遍历序列为：$\{C\ F\ B\ A\ E\ D\ G\}$，后序遍历序列为：$\{F\ C\ B\ E\ G\ D\ A\}$，则下列说法中正确的是（ ）。

{{ select(6) }}

• 该树是平衡二叉树
• 该树的高为 $4$
• 该树有 $4$ 个叶节点
• 以上说法都不对

7. 以下关于二叉排序树的说法，正确的是（ ）。

{{ select(7) }}

• 二叉排序树的中序遍历序列一定是有序的
• 在含 $n$ 个节点的二叉排序树中查找元素，最差情况的时间复杂度为 $O(\log n)$
• 二叉排序树一定是二叉平衡树
• 以上说法都不对

8. 已知 $x$ 为 $\tt double$ 类型的变量，且值大于 $0$，则下列表达式的值一定大于 $0$ 的是（ ）。

{{ select(8) }}

• sin(x) / x
• exp(x) - x
• log(x) - x
• x * x - x

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

{{ select(9) }}

• $60$
• $70$
• $15$
• $20$

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

    

{{ select(10) }}

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

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

    #include <algorithm>
    using namespace std;
    struct activity {
        int id, start, end;
    };
    bool compare(activity a, activity b) {
        return a.end < b.end;
    }
    int schedule(int n, activity * p) {
        sort(p, p + n, compare);
        int cnt = 0, end = 0;
        for (int i = 0; i < n; i++) {
            if (p[i].start >= end) {
                end = p[i].end;
                cnt++;
            }
        }
        return cnt;
    }
    

{{ select(11) }}

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

12. 下面 $\tt 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 - 1;
            }
        }
        return -1;
    }
    

{{ select(12) }}

• $O(n)$
• $O(\log n)$
• $O(1)$
• 可能无法返回

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

    int count_triple(int n) {
        int cnt = 0;
        for (int a = 1; a <= n; a++)
            for (int b = a; a + b <= n; b++)
                for (int c = b; a + b + c <= n; c++)
                    if (a * a + b * b == c * c)
                        cnt++;
        return cnt;
    }
    

{{ select(13) }}

• $O(n)$
• $O(n^2)$
• $O(n^3)$
• $O(n^4)$

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

    #include <iostream>
    using namespace std;
    int down(int n) {
        if (n <= 1)
            return n;
        return down(n - 1) + down(n - 2) + down(n - 3);
    }
    int main() {
        cout << down(6) << endl;
        return 0;
    }
    

{{ select(14) }}

• $6$
• $13$
• $20$
• 无法正常结束

15. 下面的程序使用邻接矩阵表达的带权无向图，则从顶点 $0$ 到顶点 $3$ 的最短距离为（ ）。

    int weight[4][4] = {
        {0, 2, 5, 8},
        {2, 0, 1, 7},
        {5, 1, 0, 4},
        {8, 7, 4, 0}};
    

{{ select(15) }}

• $6$
• $7$
• $8$
• $9$

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

1. 祖冲之是南北朝时期杰出的数学家、天文学家，其主要贡献在数学、天文历法和机械制造三方面。他首次将圆周率精算到小数第七位，即在 $3.1415926$ 和 $3.1415927$ 之间。（ ）

{{ select(16) }}

• 正确
• 错误

2. $\tt C$++ 语言中，表达式 2 ^ 3 的结果类型为 $\tt int$、值为 $8$。（ ）

{{ select(17) }}

• 正确
• 错误

3. 一棵有 $N$ 个节点的完全二叉树，则树的深度为 $\lfloor \log_2 N \rfloor + 1$。（ ）

{{ select(18) }}

• 正确
• 错误

4. 能用动态规划解决的问题，一般也可以用贪心法解决，但动态规划的效率更高。（ ）

{{ select(19) }}

• 正确
• 错误

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

{{ select(20) }}

• 正确
• 错误

6. 要求出简单有向图中从顶点 $A$ 到顶点 $B$ 的最短路径，在深度优先搜索和广度优先搜索中选择，广度优先更适合。（ ）

{{ select(21) }}

• 正确
• 错误

7. 某 $N$ 个表项的哈希表，在发生哈希函数冲突时采用向后寻找空位的方法解决冲突。其查找操作的平均时间复杂度为 $O(1)$，即使当该哈希表的每个表项都有元素时，查找操作的平均时间复杂度仍为 $O(1)$。（ ）

{{ select(22) }}

• 正确
• 错误

8. 动态规划有递推实现和递归实现，有时两种实现的时间复杂度不同。（ ）

{{ select(23) }}

• 正确
• 错误

9. 围棋游戏中，判断落下一枚棋子后是否会提掉对方的子，可以使用泛洪算法来实现。（ ）

{{ select(24) }}

• 正确
• 错误

10. 类 $\tt B$ 继承了抽象类 $\tt A$，但未实现类 $\tt A$ 中的纯虚函数 $\tt f$，则类 $\tt B$ 不能直接实例化。（ ）

{{ select(25) }}

• 正确
• 错误