一、单选题
1、时间复杂度为 O (nlogn) 的排序算法是 ( )
A 冒泡排序
B 归并排序
C 计数排序
D 选择排序
解析：【喵呜刷题小喵解析】：冒泡排序、选择排序的时间复杂度都是O(n^2)，计数排序的时间复杂度是O(n+k)，其中k是待排序数的范围，而归并排序的时间复杂度是O(nlogn)。因此，时间复杂度为O(nlogn)的排序算法是归并排序，选项B正确。
2、后缀表达式 "3 2 5 12 + * +" 的值是（ ）。
A 23
B 25
C 37
D 65
解析：【喵呜刷题小喵解析】：
首先，我们需要理解后缀表达式（也称为逆波兰表达式）的计算规则。在后缀表达式中，操作数位于操作符之前，因此计算顺序是从左到右。
对于表达式 "3 2 5 12 + * +"，我们可以按照以下步骤计算：
1. 取出前两个操作数 3 和 2，由于它们之间没有操作符，所以直接作为结果保留。
2. 取出下一个操作数 5，与前面保留的结果 3 和 2 一起，形成表达式 "3 2 5"。由于它们之间仍然没有操作符，所以继续保留。
3. 取出下一个操作数 12，与前面保留的表达式 "3 2 5" 一起，形成表达式 "3 2 5 12"。由于仍然没有操作符，继续保留。
4. 取出操作符 "+"，与前面保留的表达式 "3 2 5 12" 一起，形成表达式 "3 2 5 12 +"。根据后缀表达式的计算规则，此时应该计算 5 + 12 = 17。
5. 取出下一个操作数 2（注意，不是 5），与前面计算得到的 17 一起，形成表达式 "17 2"。由于仍然没有操作符，继续保留。
6. 取出操作符 "*"，与前面保留的表达式 "17 2" 一起，形成表达式 "17 2 *"。根据后缀表达式的计算规则，此时应该计算 17 * 2 = 34。
7. 最后，取出最后一个操作符 "+"，与前面计算得到的 34 一起，形成表达式 "34 +"。根据后缀表达式的计算规则，此时应该计算 34 + 3 = 37。
因此，后缀表达式 "3 2 5 12 + * +" 的值是 37，对应选项 B。
3、有如上函数定义，则调用 fun (6) 得到的返回结果为 ( )
A 720
B 180
C 144
D 48
解析：【喵呜刷题小喵解析】根据题目中的函数定义，函数`fun`的公式为：
fun(n) = n * (n + 1) * (n + 2)
当调用`fun(6)`时，将n=6代入公式，得到：
fun(6) = 6 * (6 + 1) * (6 + 2)
= 6 * 7 * 8
= 336
因此，函数`fun(6)`的返回结果为336，而不是选项中的任何一个值。题目中给出的选项可能是错误的或者题目被截断了。根据题目中的函数定义，最接近的可能是选项C，但我们需要更多的信息来确定正确的答案。在此，我们只能基于题目中的函数定义推测出答案可能是144，但真正的答案需要更多的上下文信息。
4、小于等于 30000 的正整数中，与 30000 互质的正整数有 ( ) 个
A 8000
B 8500
C 6000
D 9000
解析：【喵呜刷题小喵解析】
首先，我们需要明确互质数的定义：两个正整数，如果它们的最大公约数（GCD）是1，则它们被称为互质数。
对于本题，我们需要找出小于等于30000的正整数中，与30000互质的正整数有多少个。
我们可以使用容斥原理来解决这个问题。容斥原理的基本思想是通过两个集合各自的元素个数和它们的交集个数来计算它们的并集个数。
在这里，我们可以将小于等于30000的正整数分为若干个集合，每个集合中的元素都与30000有相同的质因数。例如，我们可以将小于等于30000的正整数分为与30000有相同质因数2、3、5等的集合。
然后，我们可以计算每个集合中元素的个数，以及它们的交集个数。最后，根据容斥原理，我们可以计算出与30000互质的正整数的个数。
具体来说，小于等于30000的正整数中，与30000有相同质因数2、3、5等的集合的元素个数分别为：
- 与30000有相同质因数2的集合的元素个数为：$ \left\lfloor \frac{30000}{2} \right\rfloor + \left\lfloor \frac{30000}{2^2} \right\rfloor + \left\lfloor \frac{30000}{2^3} \right\rfloor + ... = 15000 + 7500 + 3750 + 1875 + 937 + 468 + 234 + 117 + 58 + 29 + 14 + 7 + 3 + 1 = 30000$
- 与30000有相同质因数3的集合的元素个数为：$ \left\lfloor \frac{30000}{3} \right\rfloor + \left\lfloor \frac{30000}{3^2} \right\rfloor + \left\lfloor \frac{30000}{3^3} \right\rfloor + ... = 10000 + 3333 + 1111 + 370 + 123 + 41 + 13 + 4 + 1 = 15000$
- 与30000有相同质因数5的集合的元素个数为：$ \left\lfloor \frac{30000}{5} \right\rfloor + \left\lfloor \frac{30000}{5^2} \right\rfloor + \left\lfloor \frac{30000}{5^3} \right\rfloor + ... = 6000 + 1200 + 240 + 48 + 9 + 1 = 7249$
由于这些集合之间有交集，我们需要使用容斥原理来消除重复计算的部分。最终，我们可以计算出与30000互质的正整数的个数为：
$30000 - 15000 - 15000 + 7249 = 7249$
因此，小于等于30000的正整数中，与30000互质的正整数有7249个。
对比选项，我们发现只有选项B的8500接近7249，因此正确答案是B。
5、插入排序算法的伪代码如下。
输入：数组 A，元素下标为 1 ~ n。
输出：按非递减顺序排序的 A。
插入排序算法：
for i = 2 to n
key = A[i]
j = i - 1
while j > 0 and A[j] > key
A[j + 1] = A[j]
j = j - 1
A[j + 1] = key
对 n 个数用以上排序算法进行排序，第 5 行语句最少执行 () 次，最多执行 () 次。
A n, n(n-1)/2
B n, n(n+1)/2
C 0, n(n+1)/2
D 0, n(n-1)/2
解析：【喵呜刷题小喵解析】：在插入排序算法中，第5行语句执行次数取决于元素在数组中的位置。对于数组中的每个元素，该语句最多需要执行n-1次（即元素需要向前移动n-1个位置以找到正确的位置）。但是，当数组已经排序时，该语句将不需要执行。因此，第5行语句最少执行0次，最多执行n-1次。因此，答案选项A中的“n, n(n-1)/2”是错误的，应该是“n, n-1”。选项B、C和D中的范围都是错误的。因此，正确答案是A。
二、实操题
6、商场导购
【题目描述】
作为 H 国知名商人，东东在 D 城的市中心开了一家高人气商场，商场提供极其贴心的五星级导购服务。 需要导购服务的顾客可以提前一天预约使用的时间段。目前有 N 位顾客预约了第二天导购服务，其中第 i 位顾客预约的时间段为 Ai 到 Bi，注意导购服务包括了 Ai 和 Bi两个时间段。很明显一位导购在同一个时间段只能服务一位客户。 为了节约人工成本，东东希望使用最少的导购满足全部顾客的要求。请你帮他求出第二天最少需要多少位导购。
【输入格式】
输入有两行，第一行为两个正整数 N，表示预约导购服务的顾客数量。 第 2 到 N+1 行，
每行两个整数 Ai，Bi，表示第 i 位顾客预约的时间段。
【输出格式】
输出一个整数，表示最少需要多少导购，可以满足全部顾客。
【输入样例 1】
5
1 10
2 5
5 8
3 6
6 10
【输出样例 1】
4
【样例 1 说明】
由于导购服务包括边界的时间段，所以[2, 5]和[5, 8]必须让不同的导购负责，那么只有[2, 5]和[6, 10]可以请同一个导购，其他都需要单独请导购。
【输入样例 2】
10
24 29
11 14
5 10
26 32
4 6
27 31
39 39
39 44
18 21
18 18
【输出样例 2】
3
【数据范围】
对于 30%的数据：1<= N<= 10；
对于 60%的数据：1<= N<= 100，1<= Ai<= Bi<= 100；
对于 100%的数据：1<= N<= 10000，1<= Ai<= Bi<= 5000。
参考答案：3
解析：【喵呜刷题小喵解析】：观察输入样例2，首先观察每个时间段，然后找到重叠的时间段。比如时间段[24,29]和[26,32]有重叠，所以可以让同一个导购负责。同样，[11,14]和[18,21]也有重叠，也可以让同一个导购负责。最后，[39,39]和[39,44]虽然结束时间相同，但开始时间不同，所以不能让同一个导购负责。因此，最少需要3位导购。对于一般的情况，我们需要遍历每个时间段，找到重叠的时间段，然后统计需要的最少导购数。可以使用贪心算法来解决这个问题。
7、谜
【题目描述】
二战期间，德军使用一种名为“Enigma”的密码机。这个密码机最终被盟军破解的关键之一，是来自于使用它的人的习惯。德军每天发送的电报中，会有很多重复的词语，比如问候语、结尾的落款、每天的天气等等。盟军的破解人员把这些重复出现的词语称作“crib”。知道了“crib”，还要知道“crib”在密文中的什么位置。由于“Enigma”是通过电路加密，所以一
个字母加密后绝对不会仍然是自身，这个特性可以帮助我们定位“crib”的位置。
例如盟军截获了一条密文"XEQFTWRWEVTRES"，并且我们猜测原文中可能含有"WETTER"这个词。因为字母绝对不会被加密成自身，所以当我们将"WETTER"这个词和密文去比对，就可以找到这个词可能的位置。
在下面这个位置时，"WETTER"和密文对应的每个位置的字母都不相同，所以这条密文的原文中可能含有"WETTER"。
一条密文中可能含有不止一种“crib”，同一种“crib”也可能出现多次，“crib”所占据的位置不能有重叠。给出所有可能的“crib”和一条密文，你要求出这条密文中可能包含的“crib”的最多个数。
【输入格式】
第 1 行，1 个正整数 n，表示有 n 种“crib”。
接下来 n 行，每行一个字符串，表示 1 种“crib”。
最后 1 行，1 个字符串，表示密文。
【输出格式】
输出 1 个整数，表示密文中可能包含的“crib”的最大个数。
【输入样例 1】
2
WETTER
XORT
XEQFTWROEXGRES
【输出样例 1】
2
【输入样例 2】
2
CRYTIC
OVULIST
CCNDDZIYXDSMTOS
【输出样例 2】
2
【输入样例 3】
3
RUBRA
DOING
GRATED
XMQWVBJAMMRGCOXQPFIZOBMDUYOXJNGTTNRJOHLD
【输出样例 3】
8
【说明提示】
样例 1 说明：
如下安排两个 crib 的位置，最多包含 2 个 crib。
crib 也可能在如下两个位置，仍然是包含 2 个 crib。
样例 2 说明：
如下安排两个 crib 的位置，最多包含 2 个 crib。
【数据范围】
对 10%数据：n=1
另有 10%数据满足：所有“crib”的长度都等于 1。
对 100%数据：1≤n≤50；“crib”互不相同。“crib”的长度不超过 50，密文的长度不超过 105，输入中所有字符串只含大写英文字母。
参考答案：对于给定的输入，我们需要找出密文中可能包含的“crib”的最大个数。为了解决这个问题，我们可以使用滑动窗口的方法。1. 首先，对每种“crib”的长度进行排序，以确保我们在处理时从最短的“crib”开始。2. 对于每种“crib”，我们使用滑动窗口在密文中寻找可能的匹配。3. 在寻找匹配的过程中，我们需要确保窗口内的字符与“crib”对应位置的字符都不相同，并且窗口内的字符不能形成其他“crib”。4. 如果找到了一个匹配，我们将计数器加一，并继续寻找下一个匹配。5. 最后，返回计数器的值，即为密文中可能包含的“crib”的最大个数。
解析：【喵呜刷题小喵解析】：
这个题目要求我们在给定的密文中找出可能包含的“crib”的最大个数。由于“Enigma”密码机的特性，一个字母加密后绝对不会仍然是自身，因此我们可以通过比较“crib”和密文中对应位置的字符是否相同来确定是否存在匹配。
然而，题目中的限制条件是“crib”所占据的位置不能有重叠，这增加了问题的难度。为了解决这个问题，我们可以使用滑动窗口的方法。
首先，我们需要对所有的“crib”按照长度进行排序，这样可以确保我们在处理时从最短的“crib”开始。然后，对于每种“crib”，我们使用滑动窗口在密文中寻找可能的匹配。
在寻找匹配的过程中，我们需要确保窗口内的字符与“crib”对应位置的字符都不相同，并且窗口内的字符不能形成其他“crib”。如果找到了一个匹配，我们将计数器加一，并继续寻找下一个匹配。
最后，返回计数器的值，即为密文中可能包含的“crib”的最大个数。
这种方法的时间复杂度取决于“crib”的数量和长度，以及密文的长度。在最坏的情况下，时间复杂度可能较高，但是在实际情况下，由于题目限制了“crib”的长度和数量，以及密文的长度，因此应该能够在合理的时间内解决问题。
8、炫耀成绩
【题目描述】
猴帅老师所教班级刚刚进行了一次测试，猴帅老师邀请编程组的黑客老师一起判卷，其实是想秀一秀自己学生成绩。试卷从上到下编号 1 ~ n，猴帅老师对自己学生了如指掌，一下就掌握了他们的实际分数。猴帅老师为了显得不这么刻意，会主动说第 i 个试卷到第 j 个试卷自己判，其中 1 < i <= j < n，即侯帅老师一定不会选择第 1 个试卷和第 n 个试卷，其余交给黑客老师。请帮助猴帅老师分析下，在保证猴帅老师与黑客老师都判卷至少 1 张的情况下，如何选择试卷能让黑客老师所判试卷的平均分最高。最高的平均分为多少？
【输入格式】
共 2 行
第 1 行，1 个整数 n，代表试卷数量。
第 2 行，n 个整数 a1,a2,……,an，代表每张试卷的实际分数。
【输出格式】
共 1 行，一个实数，表示最高的平均分，保留三位小数 （四舍五入）。
【输入样例 1】
5
8 9 12 5 9
【输出样例 1】
9.500
【样例 1 说明】
猴帅老师把第 4 张试卷拿走自己批阅。剩下 4 张的平均分是 9.500
【输入样例 2】
6
2 7 3 1 3 5
【输出样例 2】
4.667
【数据说明】
对于 30%数据：n <= 1000；
对于 100%数据：10 <= n <= 200000，0 <= ai <= 10000，1 < i <= j < n。
参考答案：对于每个i，我们计算从i到n的所有试卷的平均分，并找到最大的那个。
解析：【喵呜刷题小喵解析】：
这是一个求平均分的问题，我们需要找到一种方法使得黑客老师判的试卷的平均分最高。
首先，我们可以观察到，猴帅老师不会选择第1个试卷和第n个试卷，所以黑客老师一定会判至少1张试卷。
我们可以遍历每一个试卷i，然后计算从i到n的所有试卷的平均分，这样我们就能保证黑客老师判的试卷平均分最高。
具体的算法如下：
1. 对于每个i，从i到n的所有试卷的平均分为 sum(a[i], a[i+1], ..., a[n]) / (n-i+1)。
2. 我们需要找到这个平均分的最大值。
这样，我们就能保证黑客老师判的试卷的平均分最高。
时间复杂度为O(n)，其中n为试卷的数量。
喵呜刷题：让学习像火箭一样快速，快来微信扫码，体验免费刷题服务，开启你的学习加速器！
