一、单选题
1、以下选项中，没有利用“比较”操作的算法是（ ）。
A 选择排序
B 冒泡排序
C 插入排序
D 桶排序
解析：【喵呜刷题小喵解析】
选择排序、冒泡排序和插入排序都是基于比较操作的排序算法。它们通过比较相邻或任意两个元素的大小，来确定元素的顺序。
桶排序则不同，它利用的是分治的思想。将待排序的元素分配到有限数量的桶子里，每个桶子再个别排序（有可能再使用别的排序算法或是递归地采用桶排序进行排序）。因此，桶排序并没有利用比较操作。
所以，没有利用“比较”操作的算法是桶排序，因此正确答案是D。
2、假设入栈顺序为a、b、c、d、e，则出栈序列不可能是（ ）。
A a、b、d、c、e
B b、a、d、c、e
C d、c、a、b、e
D c、b、a、d、e
解析：【喵呜刷题小喵解析】栈是一种遵循后进先出（LIFO）原则的数据结构。给定入栈顺序为a、b、c、d、e，我们可以通过模拟入栈和出栈过程来验证每个出栈序列是否可能。
* 选项A：a、b、d、c、e
+ 入栈顺序为a、b、c、d、e
+ 出栈a，栈中剩余b、c、d、e
+ 出栈b，栈中剩余c、d、e
+ 出栈d，栈中剩余c、e
+ 出栈c，栈中剩余e
+ 出栈e
+ 此序列是可能的。
* 选项B：b、a、d、c、e
+ 入栈顺序为a、b、c、d、e
+ 出栈b，栈中剩余a、c、d、e
+ 出栈a，栈中剩余c、d、e
+ 出栈d，栈中剩余c、e
+ 出栈c，栈中剩余e
+ 出栈e
+ 此序列是可能的。
* 选项C：d、c、a、b、e
+ 入栈顺序为a、b、c、d、e
+ 出栈d，栈中剩余a、b、c、e
+ 出栈c，栈中剩余a、b、e
+ 出栈a，栈中剩余b、e
+ 出栈b，栈中剩余e
+ 出栈e
+ 此序列是可能的。
* 选项D：c、b、a、d、e
+ 由于栈是后进先出（LIFO）的数据结构，栈顶元素最后出栈，因此，在a、b、c、d、e的入栈顺序下，不可能先出栈c。
+ 所以，此序列是不可能的。
因此，答案是选项D：c、b、a、d、e。
3、执行以下代码，输出的结果是（ ）。
#include <iostream>
using namespace std;
int f(int k)
{
if(k<= 2) return 1;
return 2 * f(k - 2) + f(k - 1);
}
int main()
{
int n = 7;
cout << f(n);
return 0;
}
A 21
B 41
C 43
D 45
解析：【喵呜刷题小喵解析】
首先，我们分析给定的递归函数 `f(k)`：
```cpp
int f(int k)
{
if(k <= 2) return 1;
return 2 * f(k - 2) + f(k - 1);
}
```
这个函数的定义表明：
* 当 `k` 小于或等于2时，函数返回1。
* 当 `k` 大于2时，函数返回 `2 * f(k - 2) + f(k - 1)`。
现在，我们按照 `n = 7` 来计算 `f(7)`：
1. `f(7) = 2 * f(5) + f(6)`
2. `f(6) = 2 * f(4) + f(5)`
3. `f(5) = 2 * f(3) + f(4)`
4. `f(4) = 2 * f(2) + f(3)`
5. `f(3) = 2 * f(1) + f(2)`
6. `f(2) = 1` 和 `f(1) = 1`
继续上面的计算，我们得到：
* `f(4) = 2 * 1 + 1 = 3`
* `f(5) = 2 * 3 + 1 = 7`
* `f(6) = 2 * 7 + 3 = 17`
* `f(7) = 2 * 17 + 7 = 41`
所以，`f(7)` 的值是41，因此输出的结果是41，对应选项B。
4、已定义字符串 string s ="Let lt Be" ，下列哪个选项可以获得字符串 的长度（ ）。
A s.size()
B len(s)
C sizeof(s)
D strlen(s)
解析：【喵呜刷题小喵解析】：在C++中，字符串长度可以通过调用其成员函数`size()`或`length()`来获取。所以，选项A中的`s.size()`是正确的。选项B中的`len(s)`在C++中并不是获取字符串长度的标准方法，应该是`s.length()`。选项C中的`sizeof(s)`会返回变量s在内存中的大小，而不是其包含的字符数。选项D中的`strlen(s)`是C语言中的函数，用于获取C风格字符串（以'\0'结尾的字符数组）的长度，但在C++中并不直接适用，需要包含头文件`#include
5、以下关于C++类的说法，正确的是（ ）。
A 析构函数和构造函数一样可以进行重载
B 析构函数里不能使用return语句
C 构造函数不需要返回值时，需要定义为返回void类型
D 如果自定义构造函数的参数都是默认参数，则不能再定义一个无参数的构造函数
解析：【喵呜刷题小喵解析】：
A选项：析构函数和构造函数一样可以进行重载。这是错误的。析构函数不能重载，每个类只能有一个析构函数。
B选项：析构函数里不能使用return语句。这是错误的。析构函数可以包含return语句，但通常析构函数没有返回值，所以return语句通常出现在void类型的析构函数中。
C选项：构造函数不需要返回值时，需要定义为返回void类型。这是错误的。构造函数没有返回值，它们不需要定义为返回void类型。
D选项：如果自定义构造函数的参数都是默认参数，则不能再定义一个无参数的构造函数。这是正确的。如果类有一个或多个带有默认参数的构造函数，那么编译器将不会生成默认的无参数构造函数。因此，如果希望有一个无参数的构造函数，需要明确地定义它。
因此，正确答案是D。
二、实操题
6、八进制回文平方数
时间限制： 1000MS
内存限制： 65536KB
提示：
八进制数：指逢8进位的一种进位计数制，以0、1、2、3、4、5、6、7共八个数码表示。例如：十进制数8等于八进制数10，十进制数64等于八进制数100，以此类推。
回文数：反向排列与原来一样的数。例如，12321是回文数，1231不是回文数。
平方数：可以写成某个整数的平方的数。例如，9 = 3^2，9 是一个平方数。
题目描述：
给定一个十进制正整数N（1≤N≤109），请从小到大输出1~N之间（含1和N）所有满足以下要求的数：
1. 这个数转换为八进制后是一个回文数；
2. 这个数是一个平方数。
例如：N=20，在1~20之间满足要求的数有1、4、9，因为有，
1转换为八进制为1，是一个回文数；且1 = 1^2，是一个平方数；
4转换为八进制为4，是一个回文数；且4 = 2^2，是一个平方数；
9转换为八进制为11，是一个回文数；且9 = 3^2，是一个平方数。
故输出1 4 9
输入描述
输入一个十进制正整数N（1≤N≤109）
输出描述
输出一行，包含若干个十进制正整数，表示满足题目要求的数。结果从小到大输出，两个正整数之间用一个空格隔开
样例输入
20
样例输出
1 4 9
参考答案：1 4 9
解析：【喵呜刷题小喵解析】：题目要求找出1到N之间（含1和N）所有满足两个条件的数：1）这个数转换为八进制后是一个回文数；2）这个数是一个平方数。
首先，我们需要将每个数转换为八进制，并检查它是否是回文数。然后，我们需要检查这个数是否是平方数。
对于输入N=20，我们需要检查1到20之间的每个数。
1. 1转换为八进制为1，是一个回文数；且1 = 1^2，是一个平方数。
2. 4转换为八进制为4，是一个回文数；且4 = 2^2，是一个平方数。
3. 9转换为八进制为11，是一个回文数；且9 = 3^2，是一个平方数。
因此，输出结果为1 4 9。
7、主要成分
时间限制： 1000MS
内存限制： 65536KB
背景信息：
金星是离地球最近的行星，人类发射的“金星快车”探测器的主要任务是对金星大气层进行精确的探测，分析其化学成分。
题目描述：
从金星探测器传回来一组测量数据，这是一个长度为N（1≤N≤1000000）的整数数列，数列中的每个整数代表某一种化学成分（相同的整数代表相同的化学成分）。
主要成分：指在包含的所有化学成分中比例超过一半（N÷2的结果向下取整）的成分。
现在要判断其是否有主要成分；如果有，其主要成分是哪一种？
例如：
当N=7，整数数列为1 2 3 2 2 1 2，其中成分2有4个，超过了7的一半（7的一半向下取整为3），所以主要成分是2。
当N=6，整数数列为1 102 31 31 1 102，其中的每一种成分都只有2个，未超过6的一半（6的一半为3），所以没有主要成分。
输入描述
第一行输入一个正整数N（1≤N≤1000000），表示数列长度
第二行输入N个整数（1≤整数≤2×109），每个整数表示一种化学成分，两个整数之间用一个空格隔开
输出描述
输出一行，如果存在主要成分，则输出代表主要成分的整数，否则，输出No
样例输入
7
1 2 3 2 2 1 2
样例输出
2
参考答案：2
解析：【喵呜刷题小喵解析】：
根据题目描述，我们需要判断数列中是否存在主要成分，即比例超过一半的成分。如果存在，我们需要找出这种成分。
首先，我们需要统计每个成分的数量。可以使用一个哈希表来记录每个成分出现的次数。遍历输入的数列，每次遇到一个成分，就在哈希表中对应的计数器上加1。
然后，我们计算数列长度的一半（N÷2的结果向下取整）。遍历哈希表中的每个计数器，如果某个计数器的值大于数列长度的一半，那么我们就找到了主要成分，输出对应的成分即可。
如果不存在任何一个计数器的值大于数列长度的一半，那么就没有主要成分，输出"No"。
在本题中，输入的数列长度为7，数列中的成分有1、2、3，其中成分2出现了4次，超过了7的一半（7的一半向下取整为3），所以主要成分是2，输出2即可。
8、简单算术题
时间限制： 1000MS
内存限制： 65536KB
题目描述：
给定一道没有括号的四则混合运算算术题（可能包含多余的空格），请编程计算出结果。
运算规则如下：
1. 既有乘、除法又有加、减法的，要先算乘除法，再算加减法
2. 同级运算时，要从左往右按顺序计算
3. 所有除法运算的结果都只保留整数部分（直接舍弃小数部分）
例如：当算术题为 2 + 3 * 4 - 1 0 / 6 + 1 / 2 * 4时，优先计算乘除法，有3*4=12，10/6=1，1/2*4=0；然后再计算加减法，2+3*4-10/6+1/2*4=2+12-1+0=13，故输出13。
输入描述
输入一个字符串，表示算术题，5≤字符串长度≤100000，字符串中只包含数字字符以及“+”、“-”、“*”、“/”运算符，不含括号，可能包含空格；
算式中的运算数范围：1≤运算数≤200。
输出描述
输出一个整数，表示算术题的计算结果。
题目数据保证算式的每一步运算的结果都在-2×109~2×109之间。
样例输入
2+3*4-10/6+1/2*4
样例输出
13
参考答案：13
解析：【喵呜刷题小喵解析】：根据题目描述，给定的算术题需要按照运算规则进行计算。首先，我们需要处理输入字符串，将字符串中的多余空格去掉，并保留运算数和运算符。然后，按照运算规则进行计算。
首先，根据运算规则，既有乘、除法又有加、减法的，要先算乘除法，再算加减法。因此，我们需要找到字符串中的乘法和除法运算，并按照从左到右的顺序进行计算。
对于除法运算，题目要求只保留整数部分，直接舍弃小数部分。因此，在进行除法运算时，我们需要将结果向下取整。
然后，对于乘法和除法运算的结果，我们需要按照从左到右的顺序进行加法和减法运算。同样，我们需要按照从左到右的顺序进行计算。
最后，我们将所有的运算结果累加起来，得到最终的算术题的计算结果。
根据题目给定的样例输入和样例输出，我们可以验证我们的解析和计算过程是正确的。对于样例输入“2+3*4-10/6+1/2*4”，我们按照运算规则进行计算，得到的结果为13，与样例输出一致。
9、数独填数
时间限制： 1000MS
内存限制： 65536KB
数独是源自18世纪瑞士的一种数学游戏。玩家需要根据9×9网格上的已知数字，将剩余的所有空格填上数字，使得9×9网格上每一行、每一列及每一个3×3方块（粗线）内的数字均包含1~9，并且数字不重复。
例1：下图（左）是未完成的数独，下图（右）是完成后的结果。
这个数独可以使用如下9×9的字符方阵表示（空格用“.”表示）：
未完成
17.5..8..
.52.1....
.....759.
.8...94.3
.197.4..8
7......15
4.1...6..
3...2..59
...96..3.
已完成
174593826
952816347
638247591
286159473
519734268
743682915
491375682
367428159
825961734
例2：
未完成
68.9.5...
..3...5.8
4.21.87.3
39.72.8..
.......1.
.45..69..
.6.8.4..2
..1..2.75
7...13...
已完成
687935241
913247568
452168793
396721854
278459316
145386927
569874132
831692475
724513689
例3：
未完成
835.2..41
.2.....39
.4.81....
.869.....
2.1..47..
9.....286
...356..7
.9..4.3..
5....7.1.
已完成
835729641
127465839
649813572
386972154
251684793
974531286
418356927
792148365
563297418
现在给定一道数独题，请编程完成填数，并输出最后的结果。
输入描述
共有9行，表示未完成的数独
每一行包含9个字符（字符只能为1~9的数字和“.”），字符之间没有空格及其他字符
其中“.”表示数独上的空格
题目数据保证数独有效且答案唯一
输出描述
输出9行，表示已完成的数独
每行9个数字，数字之间没有空格及其他字符
样例输入
17.5..8..
.52.1....
.....759.
.8...94.3
.197.4..8
7......15
4.1...6..
3...2..59
...96..3.
样例输出
174593826
952816347
638247591
286159473
519734268
743682915
491375682
367428159
825961734
参考答案：```174593826952816347638247591286159473519734268743682915491375682367428159825961734```
解析：【喵呜刷题小喵解析】：
题目要求根据给定的数独填数，并输出最后的结果。数独是一种数学游戏，玩家需要根据9×9网格上的已知数字，将剩余的所有空格填上数字，使得9×9网格上每一行、每一列及每一个3×3方块内的数字均包含1~9，并且数字不重复。
根据题目描述，输入是一个9×9的字符方阵，其中空格用“.”表示。题目数据保证数独有效且答案唯一。
解析过程如下：
1. 遍历数独方阵，找到第一个空格。
2. 对于找到的空格，判断其所在行、列及3×3方块中哪些数字已经出现过，哪些数字还未出现过。
3. 从1~9的数字中，选择未出现过的数字填入空格。
4. 重复步骤1~3，直到所有空格都被填满。
由于题目保证数独有效且答案唯一，因此上述过程一定能够成功填满所有空格，得到完整的数独。
最后，按照题目要求输出完整的数独，每行9个数字，数字之间没有空格及其他字符。
10、数学实验
时间限制： 1000MS
内存限制： 262144KB
题目描述：
老师在黑板上写出了一个正整数数列，让所有同学都来做一个数学实验，要求如下：
1. 这组数总共不超过500000个，每个数的大小范围在1~80之间；
2. 要从这组数中找出两个相邻且相同的数，删掉其中一个数，剩下的一个数加1（例如：两个相邻的6，变成一个7）；
3. 重复执行第2步；
4. 当操作无法继续进行时，实验结束，此时，实验结果就是这组数里面最大的数。
注意：不同的实验方案得到的最大数不同。
现在给定了一个正整数数列，请你编写程序计算出能够得到的实验结果最大是多少。
例如：
当N=6，这个正整数数列是 1、2、2、2、3、4时，得到最大数的方法如下：
先将后面两个2变成一个3，然后3和3变成4，最后4和4变成5。可以证明，没有其它更好的方案，故输出5。
输入描述
第一行输入一个正整数N（1≤N≤500000）
第二行输入N个正整数（1≤正整数≤80），相邻两个数之间用一个空格隔开
输出描述
输出一个正整数，表示实验结束后能够得到的最大的实验结果
样例输入
6
1 2 2 2 3 4
样例输出
5
参考答案：```#include
解析：【喵呜刷题小喵解析】：
该题目要求的是对给定的正整数数列进行操作，找到两个相邻且相同的数，然后删掉其中一个数，剩下的一个数加1，重复执行此操作，直到无法继续为止，最后输出得到的最大数。
我们可以使用C++编写程序来解决这个问题。首先，我们需要读取输入的正整数数列，然后遍历数列，找到两个相邻且相同的数，然后执行操作，将其中一个数加1，并更新最大数。最后，输出最大数即可。
在程序中，我们使用vector来存储输入的数列，使用max函数来更新最大数。在遍历数列时，我们只需要遍历到倒数第二个数，因为最后一个数无法与前面的数形成相邻且相同的数对。
注意，我们需要使用if语句来判断当前数是否与前一个数相同，如果相同，则执行操作，否则更新最大数。最后，输出最大数即可。
11、月球疏散行动
时间限制： 1000MS
内存限制： 65536KB
题目描述：
为了避免太阳爆发引起的灾难，人类决定给地球装上发动机，最终逃离太阳系。原计划要带着月球一起走，结果月球行星发动机发生灾难性故障，必须炸毁月球。为此，在月球上的工作人员都要疏散回地球。
月球基地有一艘太空穿梭机可以用来疏散工作人员。但是人们分散在各处，必须前往基地集合，他们到达基地的时间不等。穿梭机可以将抵达基地等待登机的工作人员先送回地球，然后再返回基地疏散下一批工作人员。
总共有N名工作人员需要疏散，太空穿梭机从月球到地球往返一次花时间M小时，第i个人抵达基地等待登机的时刻为Ti。
指挥官希望所有工作人员在基地等待的时间总和最小，而且他可以任意安排穿梭机的起飞时间，假定穿梭机足够大，可以装下所有工作人员，在不计登机和下机时间等因素的情况下，最小的等候时间总和是多少？
例如：N=5，M=4，1号~5号工作人员到达基地的时刻依次为11、3、3、5、10，
穿梭机可以在3时出发，先送2号、3号工作人员去地球，然后于7时返回月球基地；
此时，4号工作人员已于5时到达基地，等候了2小时。这时让穿梭机马上送走他，然后于11时从地球返回基地；
此时，5号工作人员已于10时到达基地，等候了1小时；
而1号工作人员刚好于11时到达基地，等候0小时；
穿梭机于11时将两人送走，即完成全部疏散任务。总的等候时间=4号工作人员等候时间+5号工作人员等候时间=2+1=3小时。
无法再找到有更小等候时间总和的方案。
输入描述
第一行输入两个正整数N（1≤N≤500），M（1≤M≤100），以一个空格隔开，分别表示工作人员人数和穿梭机的往返时间
第二行输入N个正整数，依次表示某个工作人员到达基地等候登机的时刻Ti（1≤Ti≤4000000），相邻两数之间用一个空格隔开
输出描述
输出一个整数，表示所有工作人员等候时间之和的最小值（单位：小时）
样例输入
5 4 11 3 3 5 10
样例输出
3
参考答案：3
解析：【喵呜刷题小喵解析】：对于这个问题，我们需要找到一个最优的穿梭机起飞时间，使得所有工作人员在基地等待的时间总和最小。为了解决这个问题，我们可以使用贪心算法。
首先，将工作人员的到达时间按照升序进行排序。然后，我们可以遍历这个排序后的列表，并使用一个变量来跟踪当前的等待时间。开始时，等待时间为0。
接下来，对于列表中的每个工作人员，我们可以选择立即让穿梭机送他们回地球，或者让他们在基地等待下一趟穿梭机。为了让等待时间最小，我们应该让穿梭机立即送他们回地球，然后计算新的等待时间。新的等待时间应该是当前的等待时间加上工作人员等待穿梭机的时间（从他们到达基地到穿梭机再次到达基地的时间）。
然后，我们可以更新等待时间为新的等待时间和当前工作人员的等待时间中的较大值。这是因为，如果当前工作人员的等待时间已经超过了当前的等待时间，那么让穿梭机立即送他们回地球并不能减少总的等待时间。
最后，我们返回等待时间作为结果。这就是所有工作人员在基地等待的时间总和的最小值。
在这个例子中，工作人员按照到达时间排序后是3，3，5，10，11。我们可以让穿梭机在3时出发，先送2号、3号工作人员去地球，然后于7时返回月球基地。此时，4号工作人员已于5时到达基地，等候了2小时。这时让穿梭机马上送走他，然后于11时从地球返回基地。此时，5号工作人员已于10时到达基地，等候了1小时；而1号工作人员刚好于11时到达基地，等候0小时。穿梭机于11时将两人送走，即完成全部疏散任务。总的等候时间=4号工作人员等候时间+5号工作人员等候时间=2+1=3小时。无法再找到有更小等候时间总和的方案。
喵呜刷题：让学习像火箭一样快速，快来微信扫码，体验免费刷题服务，开启你的学习加速器！
