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

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

• $O(n)$
• $O(n log n)$
• $O\left(n^{2}\right)$
• $O\left(2^{n}\right)$

第 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$
• $2n-2$
• $2n$
• $n^2$

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

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

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

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

第 7 题 下面程序的运行结果为()。

#include <iostream>
#include <algorithm>
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)
{
    std::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>
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)
{
    std::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(nlogn +nlog D)$
• $O(n log nlog D)$
• $O(nlogn)$
• $O(nlog D)$

第 9 题 某二叉树共有10个结点,记为A~J,已知它的先序遍历序列为: A B D H I E C F J G,中序遍历序列为: H D I B E A F J C G,则该二叉树的后序遍历序列是()。 {{ select(9) }}

• H I D E B J F G C A
• H I D B E J F G C A
• I H D E B J F G C A
• H I D E B F J G C A

第 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) }}

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