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

1. 假设一个算法时间复杂度的递推式是$T(n)=2T(n-1)+1$（$n$为正整数），且$T(0)=1$，那么这个算法的时间复杂度是（）。 {{ select(1) }}

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

2. 下面关于“唯一分解定理”和“素数筛法”的说法中，错误的是（）。 {{ select(2) }}

• 如果预处理出$n$以内每个数的最小质因子，那么可以在$O(\log n)$时间内完成任意一个不超过$n$的整数的质因数分解。
• 线性筛（欧拉筛）能够保证每个合数只被其最小质因子筛掉一次，这一性质依赖于唯一分解定理。
• 唯一分解定理保证：若一个数未被任何不超过其平方根的质数筛去，则它一定是质数。
• 唯一分解定理是埃氏筛时间复杂度为$O(n\log\log n)$的根本原因。

3. 若字符串A与字符串B的最长公共子序列（LCS）长度为5，则（）。 {{ select(3) }}

• 它们的编辑距离为5
• 它们至少有5个公共字符
• 它们最长公共子串长度为5
• 它们一定长度相等

4. 对于一棵包含$n$个顶点（$n≥2$）的树，其所有顶点的度数之和必定等于（）。 {{ select(4) }}

• $n-1$
• $2(n-1)$
• $n$
• $2n$

5. 关于哈希表（Hash Table）在不考虑扩容且采用简单均匀哈希函数的前提下，下列说法中错误的是（）。 {{ select(5) }}

• 装载因子越大，发生冲突的概率通常越高
• 开放定址法在删除元素时实现相对复杂
• 链地址法在最坏情况下查找时间复杂度为$O(n)$
• 查找哈希表的时间复杂度总是$O(1)$

6. 深度优先搜索（DFS）在遍历图时，每当访问到某个顶点后，选择一个相邻的未访问顶点继续搜索，直到某个顶点的所有相邻顶点均已被访问，则退回到前一顶点继续搜索。该算法主要运用了（）。 {{ select(6) }}

• 分治
• 贪心
• 动态规划
• 回溯

7. 下面程序的运行结果为（）。

#include<iostream>
#include <algorithm>
using namespace std;

bool check(int n,int a[], int k,int dist) {
    int cnt=1;
    int last =a[0];
    for (int i=1;i<n;i++) {
        if (a[i]-last>= dist) {
            cnt++;
            last = a[i];
        }
    }
    return cnt>=k;
}

int solve(int n,int a[],int k) {
    sort(a,a + n);
    int l=0;
    int r= a[n -1]-a[0];
    while (l <r){
        int mid = (l+r+1)/ 2;
        if (check(n, a, k, mid))
            l =mid;
        else
            r=mid-1;
    }
    return l;
}

int main(){
    int a[]= {1, 2, 8, 4, 9};
    int n=5;
    int k=3;
    std::cout << solve(n, a, k) << std::endl;
    return 0;
}

{{ select(7) }}

• 2
• 3
• 4
• 5

8. 下面程序的时间复杂度是（），假设数组$a$的值域范围是$D$。

#include <iostream>
#include <algorithm>
using namespace std;

bool check(int n,int a[],int k,int dist) {
    int cnt=1;
    int last=a[0];
    for(int i=1;i<n;i++) {
        if (a[i] -last>= dist) {
            cnt++;
            last = a[i];
        }
    }
    return cnt>=k;
}

int solve(int n,int a[],int k) {
    sort(a,a+n);
    int l=0;
    int r= a[n -1] -a[0];
    while (l <r) {
        int mid =(l+ r+1)/2;
        if (check(n, a, k, mid))
            l=mid;
        else
            r=mid-1;
    }
    return l;
}

int main(){
    int a[]= {1, 2, 8, 4, 9};
    int n=5;
    int k=3;
    std::cout << solve(n, a, k) << std::endl;
    return 0;
}

{{ select(8) }}

• $O(n\log n +n\log D)$
• $O(n\log n\log D)$
• $O(n\log n)$
• $O(n\log D)$

9. 某二叉树共有10个结点，记为A~J，已知它的先序遍历序列为：ABDHIECFJG，中序遍历序列为：HDIBEAFJCG，则该二叉树的后序遍历序列是（）。 {{ select(9) }}

• HIDEBJFGCA
• HIDBEJFGCA
• IHDEBJFGCA
• HIDEBFJ GCA

10. 下面哪一个可能是下图的深度优先遍历序列（）。 {{ select(10) }}

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

11. 下面这个有向图的强连通分量的个数是（）。 {{ select(11) }}

• 3
• 4
• 5
• 6

12. 关于泛洪算法（Flood Fill）的说法，正确的是（）。 {{ select(12) }}

• 泛洪算法只适用于二维网格中的四连通或八连通问题。
• 泛洪算法必须使用递归方式实现。
• 泛洪算法本质上是对图进行一次从起点出发的搜索。
• 泛洪算法只能用于统计连通块个数，不能用于计算面积或周长。

13. 有6个字符，它们出现的次数分别为：{2, 3, 3, 4, 6, 8}，现在用哈夫曼编码为这些字符编码，最小加权路径长度WPL（每个字符的出现次数乘它的编码长度，再把每个字符结果加起来）的值为（）。 {{ select(13) }}

• 58
• 60
• 62
• 64

14. 关于单链表、双链表和循环链表，下列说法正确的是（）。 {{ select(14) }}

• 在单链表中，若已知某结点的指针，则可以在$O(1)$时间内删除该结点。
• 循环链表中一定不存在空指针。
• 在循环双链表中，尾结点的next指针一定为NULL。
• 在带头结点的循环单链表中，判定链表是否为空只需判断头结点的next是否指向自身。

15. 下列关于树的遍历的说法中，正确的一项是（）。 {{ select(15) }}

• 对任意一棵树进行深度优先遍历，所得序列一定唯一。
• 已知一棵二叉树的先序遍历和后序遍历序列，可以唯一确定这棵二叉树。
• 已知一棵二叉树的先序遍历和中序遍历序列，可以唯一确定这棵二叉树。
• 一棵二叉树的中序遍历序列是单调递增的，则该二叉树一定是二叉平衡树。

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

16. C++语言中，表达式4 ^ 2的结果类型为int，值为6。 {{ select(16) }}

• 正确
• 错误

17. C++中引用可以重新绑定。 {{ select(17) }}

• 正确
• 错误

18. 在C++中，若函数形参为引用类型，则在函数内部对该形参的修改会影响对应的实参。 {{ select(18) }}

• 正确
• 错误

19. 如果一个最值问题可以用动态规划在多项式时间内求解，那么也一定存在一种贪心策略，可以在多项式时间内求得最优解。 {{ select(19) }}

• 正确
• 错误

20. 使用归并排序对$n$个元素进行排序时，无论最好、最坏还是平均情况，时间复杂度均为$O(n\log n)$。 {{ select(20) }}

• 正确
• 错误

21. 在无向连通图中删除一条边，该图就一定变成非连通图。 {{ select(21) }}

• 正确
• 错误

22. 在一个无向图中，每个顶点有不同的编号，在执行深度优先遍历过程中选择下一个顶点时总是优先选择编号更小的相邻顶点，则从指定顶点开始的遍历序列是唯一的。 {{ select(22) }}

• 正确
• 错误

23. 若所有字符出现频率相同，则哈夫曼编码一定会得到完全二叉树。 {{ select(23) }}

• 正确
• 错误

24. 使用math.h或cmath头文件中的函数，表达式sin(90)的结果为1。 {{ select(24) }}

• 正确
• 错误

25. 在一个无向连通图中，从任意顶点开始进行深度优先遍历，最终得到的DFS生成树一定包含图中的所有顶点。 {{ select(25) }}

• 正确
• 错误