CSP-S 卷

以比较为基本运算，在 $n$ 个数的数组中找最大的数，在最坏情况下至少要做（ ）次运算。

现在用如下代码来计算 $x^n$，其时间复杂度为（ ）。

01double quick_power(double x, unsigned n) {
02    if (n == 0) return 1;
03    if (n == 1) return x;
04    return quick_power(x, n / 2)
05        * quick_power(x, n / 2)
06        * ((n & 1) ? x : 1);
07}

将 $(2,7,10,18)$ 分别存储到某个地址区间为 $0\sim10$ 的哈希表中，如果哈希函数 $h(x)=$（ ），将不会产生冲突，其中 $a\bmod b$ 表示 $a$ 除以 $b$ 的余数。

下列哪些问题不能用贪心法精确求解？（ ）

对一个 $n$ 个顶点、$m$ 条边的带权有向简单图用 Dijkstra 算法计算单源最短路时，如果不使用堆或其它优先队列进行优化，则其时间复杂度为（ ）。

现有一个地址区间为 $0\sim10$ 的哈希表，对于出现冲突的情况，会往后找第一个空的地址存储（到 $10$ 冲突了就从 $0$ 开始往后）。现在要依次存储 $(0,1,2,3,4,5,6,7)$，哈希函数为 $h(x)=x^2\bmod 11$。请问 $7$ 存储在哈希表哪个地址中（ ）。

ack 函数在输入参数 (2,2) 时的返回值为（ ）。

01unsigned ack(unsigned m, unsigned n) {
02    if (m == 0) return n + 1;
03    if (n == 0) return ack(m - 1, 1);
04    return ack(m - 1, ack(m, n - 1));
05}

已知 $f(1) = 1$，且对于 $n \ge 2$ 有 $f(n) = f(n - 1) + f(\lfloor n/2 \rfloor)$，则 $f(4)$ 的值为（ ）。

考虑一个自然数 $n$ 以及一个模数 $m$，你需要计算 $n$ 的逆元（即 $n$ 在模 $m$ 意义下的乘法逆元）。下列哪种算法最为适合？

在设计一个哈希表时，为了减少冲突，需要使用适当的哈希函数和冲突解决策略。已知某哈希表中有 $n$ 个键值对，表的装载因子为 $a$（$0 < a \le 1$）。在使用开放地址法解决冲突的过程中，最坏情况下查找一个元素的时间复杂度为？

假设有一棵 $h$ 层的完全二叉树，该树最多包含多少个结点？

对于一个整数 $n$，定义 $f(n)$ 为 $n$ 的各位数字之和。问使 $f(f(x)) = 10$ 的最小自然数 $x$ 是多少？

设有一个长度为 $n$ 的 $01$ 字符串，其中有 $k$ 个 $1$。每次操作可以交换相邻两个字符。在最坏情况下将这 $k$ 个 $1$ 移到字符串最右边所需要的交换次数是多少？

有 $5$ 个红色球和 $5$ 个蓝色球，它们除了颜色之外完全相同。将这 $10$ 个球排成一排，要求任意两个蓝色球都不能相邻，有多少种不同的排列方法？

在 KMP 算法中，对于模式串 P="abacaba"，其 next 数组（next[i] 定义为模式串 P[0...i] 最长公共前后缀的长度，且数组下标从 $0$ 开始）的值是什么？

对一个大小为 $16$（下标 $0$-$15$）的数组上构建满线段树。查询区间 [3, 11] 时，最少需要访问多少个树结点（包括路径上的父结点和完全包含在查询区间内的结点）？

将字符串 "cat"、"car"、"cart"、"case"、"dog"、"do" 插入一个空的 Trie 树（前缀树）中。构建完成 Trie 树（包括根节点）共有多少个结点？

在一个大小为 $13$ 的哈希表中，使用闭散列法的线性探查来解决冲突。哈希函数为 $H(\text{key}) = \text{key} \bmod 13$。依次插入关键字 $18$、$26$、$35$、$9$、$68$、$74$。插入 $74$ 后，它最终被放置在哪个索引位置？

一个包含 $8$ 个顶点的完全图（顶点的编号为 $1$ 到 $8$），任意两点之间的边权重等于两顶点编号的差的绝对值。例如，顶点 $3$ 和 $7$ 之间的边权重为 $|7-3| = 4$。该图的最小生成树总权重是多少？

如果一棵二叉搜索树的后序遍历序列是 $2, 5, 4, 8, 12, 10, 6$，那么该树的前序遍历是什么？

一个 $0$-$1$ 背包问题，背包容量为 $20$。现有 $5$ 个物品，其重量和价值分别为 $7, 5, 4, 3, 6$ 和 $15, 12, 9, 7, 13$。装入背包的物品能获得的最大总价值是多少？

在一个初始为空的最小堆（min-heap）中，依次插入元素 $20, 12, 15, 8, 10, 5$。然后连续执行两次"删除最小值"（delete-min）操作。请问此时堆顶元素是什么？

$1$ 到 $1000$ 之间，不能被 $2$、$3$、$5$ 中任意一个数整除的整数有多少个？

斐波那契数列的定义为 $F(0)=0$，$F(1)=1$，$F(n) = F(n-1) + F(n-2)$。使用朴素递归方法计算 $F(n)$ 的时间复杂度是指数级的。而使用动态规划（或迭代）方法的时间复杂度是线性的。造成这种巨大差异的根本原因是？

有 $5$ 个独立的、不可抢占的任务 $A_1, A_2, A_3, A_4, A_5$ 需要在一台机器上执行（从时间 $0$ 开始执行），每个任务都有对应的处理时长和截止时刻，按顺序分别为 $3, 4, 2, 5, 1$ 和 $5, 10, 3, 15, 11$。如果某一个任务超时，相应的惩罚等于其处理时长。为了最小化总惩罚，应该优先执行哪个任务？

若一项任务可从两种互斥的方案中选择一种完成，其中，方案A有 $m$ 种做法，方案B有 $n$ 种做法，则总做法数为 $m + n$。

在图论中，树的重心是树上的一个结点，以该结点为根时，使得其所有子树中结点数最多的子树的结点数最少。一棵树可能有多个重心。下面哪种树一定只有一个重心？（ ）

⼀个袋⼦中有 $3$ 个完全相同的红⾊⼩球、$2$ 个完全相同的蓝⾊⼩球。每次从中取出 $1$ 个，再放回袋⼦，这样进⾏ $3$ 次后，可能的颜⾊顺序有 $8$ 种。

冒泡排序⼀般是不稳定的。

插入排序一般是稳定的。

在杨辉三角中，从第 $0$ 行开始计数，第 $10$ 行的所有数之和为（ ）。

对有 $n$ 个元素的⼆叉排序树进⾏中序遍历，其时间复杂度是（ ）

假设输⼊参数 $m$ 和 $n$ 满⾜ $m≤n$，则下⾯程序的最差情况的时间复杂度为（ ）

01int gcd(int m, int n){
02    while (m > 0){
03        int t = m;
04        m = n % m;
05        n = t;
06    }
07    return n;
08}

下⾯程序的时间复杂度为（ ）。

01long long power_mod(long long a, long long n, long long mod){
02    if (n == 0)
03        return 1;
04    a = a % mod;
05    if (n == 1)
06        return a;
07    long long pw = power_mod(a, n / 2, mod);
08    long long pw2 = pw * pw % mod;
09    if (n % 2 == 0)
10        return pw2;
11    return pw2 * a % mod;
12}

下⾯程序的输出为（ ）

01#include <iostream>
02using namespace std;
03
04int main(){
05    int cnt = 0;
06    for (int a = 1; a <= 10; a++)
07        for (int b = 1; b <= 10; b++)
08            for (int h = 1; h <= 10; h++)
09                if ((a + b) * h == 20)
10                    cnt++;
11    cout << cnt << endl;
12    return 0;
13}