一、单选题
1、以下选项中，没有利用“比较”操作的算法是（ ）。
A 选择排序
B 冒泡排序
C 插入排序
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
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
4、已定义字符串 string s ="Let lt Be" ，下列哪个选项可以获得字符串 的长度（ ）。
A s.size()
B len(s)
C sizeof(s)
D strlen(s)
5、以下关于C++类的说法，正确的是（ ）。
A 析构函数和构造函数一样可以进行重载
B 析构函数里不能使用return语句
C 构造函数不需要返回值时，需要定义为返回void类型
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
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
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
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```
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
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
喵呜刷题：让学习像火箭一样快速，快来微信扫码，体验免费刷题服务，开启你的学习加速器！
